 Érdekes így egymás után feltéve a két kérdés. Miután az elsőt kiszámoltam (és ugyanazt az eredményt kaptam, mint Róbert Gida), a másodiknak is ugyanúgy álltam neki, mint az elsőnek. Ki is jött a helyes eredmény.
Utána viszont valaki elárulta, hogy van a második feladatra egy egyszerűbb megoldás is. Rá kellett volna jönnöm magamtól, csak az első elterelte a figyelmemet. Elmondom röviden.
Legyen egy &tex;\displaystyle n×n&xet;-es sakktáblánk, ahol &tex;\displaystyle n = 8 &xet;. Tekintsük azokat a színezéseit a sakktáblának, ahol minden mező fekete vagy fehér, és minden sorban van fekete és fehér mező is. Legyenek &tex;\displaystyle k, l &xet; nemnegatív egészek, és jelöljünk ki a sakktáblán &tex;\displaystyle k &xet; oszlopot csupa feketének, meg &tex;\displaystyle l &xet; ettől diszjunkt oszlopot csupa fehérnek, a többi oszlopban bármilyen színű mezők lehetnek. Jelölje &tex;\displaystyle a_{k,l} &xet; azt a számot, ahány színezés van az előbbiek közül, ha ezt a néhány rögzített oszlopot nem változtathatjuk. Ez nyilván független attól, hogy melyik oszlopokat jelöltük ki. Ha ismernénk az &tex;\displaystyle a_{k,l} &xet; számokat, akkor szitával megkaphatjuk azoknak a színezéseknek az &tex;\displaystyle r &xet; számát, amelyekben nincs sem csupa fekete, sem csupa fehér oszlop. Pontosan
&tex;\displaystyle
r = \sum_k\sum_l (-1)^{k+l}\binom{n}{k+l}\binom{k+l}{l}a_{k,l}
&xet;
Viszont &tex;\displaystyle a_{k,l} &xet; értékét azért könnyű kiszámolni, mert az ez által megszámolt színezésekben a sorok függetlenek. Azt kell tehát csak kiszámolni, hogy egy sort hányféleképpen színezhetünk ki megfelelően, és ezt &tex;\displaystyle n &xet;-edik hatványra emelni. Valóban,
&tex;\displaystyle
a_{k,l} = (2^{n-k-l} - [0 = l] - [0 = k])^n
&xet;
A két korrekciós tag azért kell, hogy kizárjuk a csupa fekete és a csupa fehér mezőből álló sort, de csupa fekete színezés csak akkor lehet, ha semelyik oszlopot nem rögzítettük fehérnek. Megoldásként tehát azt a dupla összeget kapjuk, hogy
&tex;\displaystyle
r = \sum_k\sum_l (-1)^{k+l}\binom{n}{k+l}\binom{k+l}{l}(2^{n-k-l} - [0 = l] - [0 = k])^n
&xet;
Ezt ki lehet számolni közvetlenül, de lehet egyszerűsíteni is. Ehhez szét kell választani négy részre az összeget a szerint, hogy &tex;\displaystyle k &xet; és &tex;\displaystyle l &xet; közül melyik nulla.
&tex;\displaystyle
r = r_0 + r_1 + r_2 + r_3
&xet;
&tex;\displaystyle
r_0 = (2^n - 2)^n
&xet;
&tex;\displaystyle
r_1 = \sum_{0 < l} (-1)^l\binom{n}{l}(2^{n-l} - 1)^n
&xet;
&tex;\displaystyle
r_2 = \sum_{0 < k} (-1)^k\binom{n}{k}(2^{n-k} - 1)^n
&xet;
&tex;\displaystyle
r_3 = \sum_{0 < k}\sum_{0 < l} (-1)^{k+l}\binom{n}{k+l}\binom{k+l}{l}(2^{n-k-l})^n
&xet;
Szimmetria miatt &tex;\displaystyle r_1 = r_2 &xet; (ez akkor is igaz lenne, ha nem négyzetes táblát használnánk). A negyedik részről észrevehetjük, hogy átlósan lehet összegezni, az &tex;\displaystyle m = k + l &xet; helyettesítéssel.
&tex;\displaystyle
r_3 = \sum_{2 \le m}\left((-1)^m 2^{n(n-m)}\binom{n}{m}\cdot\sum_{1 \le l < m} \binom{m}{l}\right) =
&xet;
&tex;\displaystyle
= \sum_{2 \le m}\left((-1)^m \binom{n}{m}(2^m - 2)2^{n(n-m)} \right)
&xet;
Így pedig már csak két szimpla összeget kell kiértékelni, és mindkettőben csak &tex;\displaystyle n-1 &xet; darab nemnulla tag van.
Itt vannak az egyes tagok.
&tex;\displaystyle r_0&xet; = 17324859965700833536;
&tex;\displaystyle r_1&xet; = -541401873928151048+6948361847490588-47761898096696 +179402343750-322828856+183708-8 = -534501094899058562;
&tex;\displaystyle r_3&xet; = 15762598695796736-369435906932736+4209067950080 -28185722880+113770496-258048+254 = 15397343784603902;
&tex;\displaystyle r = r_0 + 2r_1 + r_3&xet; = 16271255119687320314;
Az első feladatra nem ismerek ennyire gyors számítást, de persze nem tudom kizárni, hogy van.
|