Problemino di combinatoria..

[hyoukarou]

Si ha un quadrato diviso in nove quadratini bianchi(griglia \(3 \times 3\)) e se ne anneriscono alcuni(o anche tutti o nessuno ). Quante possibili configurazioni ci sono a meno di rotazioni e riflessioni?

Una forse soluzione(fatemi sapere se vi torna):

La mia idea sarebbe che per ogni possibile colorazione ne esiste una "complementare", perciò il risultato dovrebbe essere \(\dfrac{2^9}{2 \cdot 8} = 2^5\) dove \(8\) è la cardinalità del gruppo delle simmetrie del quadrato.

Sapreste generalizzare il risultato nel caso in cui il quadrato viene diviso in \(n \times n\) quadratini e se ne anneriscono solo \(m\)?

[kobeilprofeta]

Se ne puoi annerire quanti ne vuoi e dibidi il quadrato in $n$ parti, allora hai $2^n$ possibilità, da dividere per le $4$ rotazioni e viene $2^{n-2}$. (senza considerare le simmetrie che non ho capito quante sono).

[hyoukarou]

In effetti quella cosa della colorazione complementare non aveva molto senso.. comunque rispetto le simmetrie e rotazioni del quadrato(per ogni \(n\)-agono regolare dovrebbero esserci \(n\) riflessioni e \(n\) rotazioni, picture). Rimane aperta la questione del caso generale

[kobeilprofeta]

Credo che sia $2^m/2^4*((n!)/(m!*(n-m)!))=(2^{m-4}*n!)/(m!*(n-m)!)$. Per il qudrato diviso in $n$ parti, cioè $sqrt(n) x sqrt(n)$.

[hyoukarou]

\(n = 9\), \(m = 1\), \(\dfrac{2^{m-4} \cdot n!}{m! \cdot (n-m)!} = \dfrac{2^{1-4} \cdot 9!}{1! \cdot8!} = \dfrac{9}{8}\)

Sbaglio o non torna? Che ragionamento hai seguito?

[kobeilprofeta]

scusa io ti ho scritto il caso in cui ne puoi annerire al massimo $m$. Il ragionamento era che ognuno degli $m$ quadrati puó essere o nero o bianco (da cui $2^m$) poi ho diviso per 4 e ancora per 4 (rotazioni e riflessioni) e visto in quanti modi posso scegliere gli $m$ quadrati tra gli $n$ disponibili.

Se ne annerisci $m$ dividi la formula di prima per $2^m$ perchè sugli $m$ quadrati non c'è più la scelta.

[hyoukarou]

"kobeilprofeta":scusa io ti ho scritto il caso in cui ne puoi annerire al massimo $m$. Il ragionamento era che ognuno degli $m$ quadrati puó essere o nero o bianco (da cui $2^m$) poi ho diviso per 4 e ancora per 4 (rotazioni e riflessioni) e visto in quanti modi posso scegliere gli $m$ quadrati tra gli $n$ disponibili.

Se ne annerisci $m$ dividi la formula di prima per $2^m$ perchè sugli $m$ quadrati non c'è più la scelta.

Beh, teoricamente \(m\) neri, \(n^2 - m\) bianchi(dove \(n\) è la lunghezza del bordo) e verrebbe \(\displaystyle \frac{2^m \cdot 2^{n^2 - m}}{8}\binom{n^2}{m} = \frac{2^{n^2}}{8}\binom{n^2}{m}\).

Il fatto è che mi sono appena accorto di un errore: alcune colorazioni, come le due a sinistra nell'immagine di sotto, rimangono invariate sotto ogni simmetria mentre altre, come quelle a destra, formano gruppi da \(4\) e altre ancora da \(8\)



Quindi in buona sostanza anche la risposta al primo quesito è sbagliata

[kobeilprofeta]

Hai ragione. Credo che dovrai affidarti ad un calcolatore probably...