Daire Diliminin Boyanması

Question

Problem: $k$ farklı renkte boyaya sahibiz. Bir daire $n$ dilime ayrılmış olsun. Ardışık dilimler farklı renkte olacak biçimde $n$ dilim kaç farklı yolla boyanır? (Burada, döndürmeler sonucu bir boyama diğerinden elde edilebilir, yani $abc$, $bca$, $cab$ gibi dairesel durumlar farklı olarak ele alınacaktır.)

Answer 1

Problem, indirgemeli diziler için iyi bir uygulamadır.

 

$n$ tane dilim $k$ tane renk ile istenen özellikte $a_n$ farklı yolla boyanabiliyor olsun. $n=1,2,3$ durumlarını incelemek kolaydır: $a_1=k$, $a_2=k(k-1)$, $a_3=k(k-1)(k-2)$ olur.

$n\geq 4$ durumunu inceleyelim. $i=1,2,\dots, n-1$ olmak üzere $i$-inci dilim ile $i+1$-inci dilim farklı renkte olacak şekilde tüm boyamaların sayısı $k\cdot (k-1)^{n-1}$ dir. Bu tüm durumların içinde $n$-inci dilim ile $1$-inci dilimin aynı renkte olduğu istenmeyen durumlar da vardır.

Bu istenmeyen durumları hesaplayalım: $n-1$-inci dilim ile $n$-inci dilim farklı renkte ve $n$-inci dilim ile $1$-inci aynı renkte olduğundan $n-1$-inci dilim ile $1$-inci dilim farklı renktedir. O halde bu ilk $n-1$ dilimde, ardışık dilimler farklı renkte olacak biçimde boyanma sayısı $a_{n-1}$ olur.

İstenen durumların sayısı ile istenmeyen durumların sayısı toplanıp tüm durumların sayısına eşitlenirse $n \geq 4$ için

$$ a_n + a_{n-1} = k\cdot (k-1)^{n-1} \tag{1}$$

indirgeme bağıntısı elde edilir. Homojen doğrusal indirgemeli dizinin karakteristik denklemi $r+1=0$ olup bir kök $r_1=-1$ dir. Ayrıca $(1)$ deki homojen olmayan bağıntı, homojen hale getirilmek istenirse karakteristik denklem için bir kök de $r_2=k-1$ olacaktır. İndirgemeli dizilerin çözüm teorisinden bunu biliyoruz. Fakat bilmesek bile $(1)$ de $n$ yerine $n+1$ yazıldıktan sonra ikinci mertebeden homojen denklem elde etmek zor değildir. Dolayısıyla $(1)$ bağıntısını $n\geq 4$ için

$$ a_n=C_1r_1^n + C_2r_2^n = C_1(-1)^n + C_2(k-1)^n \tag{2} $$

biçiminde açık halde ifade edebiliriz. $C_1$, $C_2$ sabitlerini belirlemek gerekiyor.

$n=4$ için $a_4 + a_3 = k\cdot (k-1)^3$ olup $a_4= k\cdot (k-1)^3 - k\cdot (k-1)\cdot (k-2)$

$n=5$ için $a_5 + a_4 = k\cdot (k-1)^4$ olup $a_5= k\cdot (k-1)^4 - k\cdot (k-1)^3 + k\cdot (k-1)\cdot (k-2)$

yazılır. $(2)$ de $n=4$ ve $n=5$ yazılarak $C_1$, $C_2$ değerleri çözülürse $C_1 = k-1$, $C_2=1$ elde edilir. Dolayısıyla $n\geq 4$ için

$$ a_n = (k-1)(-1)^n + (k-1)^n \tag{3}$$

formülü elde edilir.

Answer 2

 

Duzenleme: Sayilari biraz arastirinca suraya   cikti yol.

 

$a(n,k)=(k-1)^n + (-1)^n (k-1)$ dizisi cevap olmus oluyor.. Acikcasi binomlu formul bekliyordum, bu ne lan..

 

Ilk cevap:

Acik formul goremedim henuz ama deneysel olarak sunlari yapabiliriz. Satirlar boya sayisi $k$'yi ve sutunlar dilim sayisi $n$'yi gostersin.

Mathematica kodu.

s = 7;
sol[k_, n_] := 
 With[{list = Flatten@Take[Transpose@ConstantArray[Range@s, s], k]},
  perm = Permutations[list, {n}];
  Length@Complement[perm, 
    Flatten[{Table[
       Select[perm, #[[i]] == #[[i + 1]] &], {i, n - 1}], {Select[
        perm, #[[1]] == #[[-1]] &]}}, 2]]]

TableForm[Table[sol[k, n], {k, s}, {n, s}], 
 TableHeadings -> {Range@s, Range@s}]

 

$
\begin{array}{c|ccccccc} &1&2 & 3 & 4 & 5& 6& 7 &\\\hline
 1&0 & 0 & 0 & 0 & 0 & 0 & 0 \\
 2&0 & 2 & 0 & 2 & 0 & 2 & 0 \\
 3&0& 6 & 6 & 18 & 30 & 66 & 126 \\
4&0 & 12 & 24 & 84 & 240 & 732 & 2184 \\
5& 0& 20 & 60 & 260 & 1020 & 4100 & 16380 \\
6& 0 & 30 & 120 & 630 & 3120 & 15630 & 78120 \\
 7&0 & 42 & 210 & 1302 & 7770 & 46662 & 279930 \\
\end{array}
$

 

Bazi ornekleri cizelim.

 

plot[k_, n_] := 
 With[{list = Flatten@Take[Transpose@ConstantArray[Range@k, k], k]},
  perm = Permutations[list, {n}];
  r = Complement[perm, 
    Flatten[{Table[
       Select[perm, #[[i]] == #[[i + 1]] &], {i, n - 1}], {Select[
        perm, #[[1]] == #[[-1]] &]}}, 2]]; 
  data = Transpose /@ 
    Table[{ToString /@ r[[i]], ConstantArray[1, n]}, {i, Length@r}];
  colors = Thread[ToString /@ Range@k -> Take[Hue /@ (Range[5]/5), k]];
  fig = PieChart[#[[All, 2]], ChartStyle -> #[[All, 1]] /. colors, 
      ChartLabels -> #[[All, 1]], ImageSize -> 50] & /@ data;
  Labeled[
   Framed[Multicolumn[fig, {Automatic, 14}, 
     Appearance -> "Horizontal"]], 
   Row[{"k=" <> ToString@k, 
     "n=" <> ToString@n, 
     "Toplam Boyama Sayisi=" <> ToString@Length@fig}, Spacer[6]], 
   Top]]

 

 

 

 

 

Comments

Teşekkürler Ökkeş hocam, formülün matematiksel ispatı ile ilgili biraz süre tanıyalım. Sonra ben de probleme bir çözüm gönderebilirim.