Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
1 beğenilme 0 beğenilmeme
467 kez görüntülendi
$i \times j$  boyutlu tablonun her satırında $n$ adet birim kare seçiliyor. Döndürmelerin aynı kabul edildiği bu işlem kaç farklı şekilde yapılabilir? (Tablonun arka yüzü yoktur.)

Bu soruda tabloyu dikdörtgen gibi düşünüp, simetri eksenlerini sayarak simetrik durumları bölmeyi düşündüm ancak bir yere varamadım. İndirgemeli dizilerle çözmeyi denedim onunla da sonuca ulaşamadım. Tablonun köşelerindeki, merkezindeki, arada kalan kareleri boyamayı denedim ancak o da olmadı. Problem de döndürmelerin aynı sayılması da $i = j$ durumunda farklılık yaratıyor. Sanırım $i=j$ ve $i \neq j$ durumlarını ayrı ayrı değerlendirmek gerekiyor. Yardımcı olursanız sevinirim.
Lisans Matematik kategorisinde (24 puan) tarafından 
tarafından düzenlendi | 467 kez görüntülendi

2 Cevaplar

0 beğenilme 0 beğenilmeme
En İyi Cevap
$i \neq j$ durumunun çözümünü yapalım. Burada da $i$ nin çift sayı veya tek sayı olması durumuna göre iki alt durumda incelemekte fayda var. Çözümde, dikdörtgen tablonun merkezi $O$ noktası ile gösterilecektir.

 

$i=2a$ ($a \in \mathbb Z^+$) olsun. Her bir satırdan $n$ tanesi seçileceğinden tüm durumların sayısı $\dbinom{j}{n}^{2a}$ olur. Bu tüm durumlar içinde $O$ noktasına göre simetrik desenler birer kez görülürken, $O$ noktasına göre simetrik olmayan desenler ikişer kez sayılmıştır. Dolayısıyla $O$ noktasına göre simetrik desenlerin sayısı $\dbinom{j}{n}^{a}$ olup

$$ \text{istenen desenlerin sayısı} = \dfrac{\dbinom{j}{n}^{2a} - \dbinom{j}{n}^{a}}{2} + \dbinom{j}{n}^{a} = \dfrac{\dbinom{j}{n}^{2a} + \dbinom{j}{n}^{a}}{2} \tag{1}$$

elde edilir.

 

Şimdi de $i=2a-1$ ($a \in \mathbb Z^+$) durumuna bakalım. Tüm durumların sayısı $\dbinom{j}{n}^{2a-1}$ ve $O$ noktasına göre simetrik olan desenlerin sayısı $\dbinom{j}{n}^{a}$ olup

$$ \text{istenen desenlerin sayısı} = \dfrac{\dbinom{j}{n}^{2a-1} - \dbinom{j}{n}^{a}}{2} + \dbinom{j}{n}^{a} = \dfrac{\dbinom{j}{n}^{2a-1} + \dbinom{j}{n}^{a}}{2} \tag{2}$$

elde edilir. $(1)$ ve $(2)$ deki formülleri tek bir formül olarak ifade etmek istersek $ x \text{'in tam değeri} = \lfloor x \rfloor $ olmak üzere

$$ \text{istenen desenlerin sayısı} = \dfrac{\dbinom{j}{n}^{i} + \dbinom{j}{n}^{ \lfloor \dfrac{i+1}{2} \rfloor }}{2} \tag{3}$$

biçiminde yazılabilir.
(1.4k puan) tarafından 
tarafından seçilmiş
Çok teşekkürler hocam. $i=j$ durumunu da yapan olursa çok sevinirim :)

Formul $i=2a$ icin ise yariyor ama $i=2a-1$ icin ise yaramiyor.

 

$i=2a-1$ durumunda yazdığım formül işe yaramaz. Çünkü $a$-inci satır boyanırken bu satırın da $O$ merkezine göre simetri durumlarını incelemem gerekiyor. Bunun için $j$ değerlerinin de çift - tek durumlarına ayırmam gerekebilir.  Müsait vakitte ilgileneyim. (Uyarı için teşekkürler Ökkeş hocam.)
0 beğenilme 0 beğenilmeme

 

Duzeltme:

Eger sadece $i=j$  icin butun permutasyonlari ariyorsan su is gorur. 

ClearAll["Global`*"]

toplamPermPlot[n_, i_, j_, plot_ : 0] := Module[{}, SeedRandom@2;
  rotate90 = Reverse@Transpose@# &;
  rotate180 = Reverse@Map[Reverse]@# &;
  rotate270 = Transpose@# &;
  list0 = Flatten@{ConstantArray[0, j - n], ConstantArray[1, n]};
  list = DeleteDuplicates@
    RandomChoice[Permutations[list0, {j}], {1000000, i}];
  list2 = Subsets[list, {2}];
  s = {};
  istenmeyen = DeleteDuplicates@Last@Table[
      Which[
       i == j,
       If[
        SameQ @@ {list2[[k, 1]], rotate90@list2[[k, 2]]} || 
         SameQ @@ {list2[[k, 1]], rotate180@list2[[k, 2]]} || 
         SameQ @@ {list2[[k, 1]], rotate270@list2[[k, 2]]}, 
        AppendTo[s, list2[[k, 2]]], Nothing],
       i != j,
       If[SameQ @@ {list2[[k, 1]], rotate180@list2[[k, 2]]}, 
        AppendTo[s, list2[[k, 2]]], Nothing]], {k, Length@list2}];
  istenen = Complement[list, istenmeyen];
  Which[plot == 0, Length@istenen, plot == 1, 
   p1 = ArrayPlot[#, Mesh -> True, ImageSize -> 50, Frame -> True, 
       FrameStyle -> Green] & /@ istenen;
   p2 = ArrayPlot[#, Mesh -> True, ImageSize -> 50, Frame -> True, 
       FrameStyle -> Red] & /@ istenmeyen;
   Row[{Labeled[Framed@Multicolumn@p1, 
      Framed["Toplam Permustasyon=" <> ToString@Length@istenen], Top],
      Framed@Multicolumn@p2}, Spacer[1]]]]
 toplamPermPlot[1, 2, 3]

 6

toplamPermPlot[1, 2, 3, 1](*cizmek icin 4. arguman 1 olmali*)

Table[toplamPermPlot[1, k, k], {k, 2, 5}]

{2, 13, 129, 1543}

 

$
\begin{array}{c|cccc}n=1&1&2 & 3 & 4&5\\\hline1&1&1&2&2&3 \\
 2&1&2 & 6 & 10& 15 \\
3&1& 4& 14 &32  &65 \\
4&1 &10 &45  & 128 &325 \\5& 1&16& 126&  512&1553 \\
\end{array}
$

 

 

 

 

Soruyu cozdugumu dusunuyorum.  Bize gerek olan yesil sinirli matrislerin sayisi. Kirmizi olanlari 90, 180 veya 270 derece cevirerek yesilleri elde edebiliyoruz. Dikdorgen matrisler icin  90 veya 270 derece donduremezsin cok farkli bir sekil elde edersin.

 

 


 

 

 

Su linkte kod var, biraz oynayabilirsiniz.

 

https://www.open.wolframcloud.com/env/a14a66df-9dab-4a02-a721-9a42e498e49b

 

Ilk Cevap:

Yaptigim bazi deneyler sonucu su sonuclari elde ettim.

$i$ tablonun satir sayisini ve $j$  sutun sayisini gostersin. $n$  satirdaki siyah birim kare adedi olsun.

  • $n=1\equiv n=j-1$ durumunda , $p$ butun permutasyonlarin sayisi olmak uzere, $p=j^i$dir.

 

 

 

 

 

 

 

$n=1: 1\leq i\leq5,1\leq j\leq5j$ icin $p$'ler asagida gosterilmistir. $p=j^i$ oldugu aciktir. $n=j-1$ olmasi durumunda siyahlar beyaz ve beyazlar siyah olacagindan ayni permutasyonu verir.

Genel formul soyle olmali. $n=1$ iken $1.$ satirda siyah kareyi kac farkli sekilde seceriz? $\displaystyle\binom{j}{1}$ ve bunu her bir satir icin yapariz. Yani $p=\underbrace{\displaystyle\binom{j}{1}\cdot\displaystyle\binom{j}{1}\dots\displaystyle\binom{j}{1}}_{i \;\text{tane}}=\displaystyle\binom{j}{1}^i$

 

$n$ icin ise $p=\underbrace{\displaystyle\binom{j}{n}\cdot\displaystyle\binom{j}{n}\dots\displaystyle\binom{j}{n}}_{i \;\text{tane}}=\displaystyle\binom{j}{n}^i$ olur.

 

$\begin{array}{c|ccccc}
 n=1 & 1 & 2 & 3 & 4 & 5 \\\hline
 1 & 1 & 2 & 3 & 4 & 5 \\
 2 & 1 & 4 & 9 & 16 & 25 \\
 3 & 1 & 8 & 27 & 64 & 125 \\
 4 & 1 & 16& 81 & 256 & 625 \\
 5 &1& 32 & 243 &1024 & 3125 \\
\end{array}$

 

 

$\begin{array}{c|ccc}
  n=2&1& 2 & 3 & 4 \\\hline
 1 & 0&1 & 3 & 6 \\
 2 & 0 &1& 9 & 36 \\
 3 &0& 1&27 & 216 \\
 4 &0&1 & 81 & 1296 \\
\end{array}$

 

f[n_, i_, j_] := Module[{},
   SeedRandom@2;
   list = Flatten@{ConstantArray[0, j - n], ConstantArray[1, n]};
   list = 
    Length@DeleteDuplicates@
      RandomChoice[Permutations[list, {j}], {1000000, i}]];

f[2, 3, 4]
216

 

(2.7k puan) tarafından 
Hocam cevabınız için teşekkür ederim lakin perspektif durumlarını fazladan saymamak gerekiyor. Örneğin matris $2\times2$ olunca 4 değil 2 farklı şekilde yapabiliyoruz: Çünkü üst sol taraftaki tabloyu döndürerek alt sağ taraftaki tabloyu elde edebileceğimiz için fazladan saymamamız gerekiyor. Aynı şey üst sağ ile alt sol için de geçerli. Durum böyle olunca problem iyice zorlaşıyor. Problemi biraz fazla genellemiş olabilirim. Eğer $i \neq j$ için bulmak çok zor olacaksa sadece durumu $i = j$ için olsa da olur.
Haklisin galiba. Dikkat etmemisim, biraz dusuneyim bunu..
Yeni sonuclari ekledim. Biz goz atarmisin  bir problem var mi?
Uygar, $i=j$ durumu daha zordur. Çünkü dikdörtgende sadece $180^\circ$ döndürme özdeş desenler verirken karede $90^\circ$ ve $270^\circ$ durumları da vardır. $i \neq j$ için çözüm aramak daha kolaydır.
Hocam, bana $i=j$ durumu lazım zaten :)

Hocam bunlar özdeş değil mi?

Evet, kodda bug farkettim, duzelttim simdi..
19,468 soru
21,189 cevap
71,133 yorum
27,348 kullanıcı