Rozsazení u kulatého stolu

Uvedená metoda pochází ze statistické fyziky (tzv. metoda ,,transfer matice''). Používá se i ke studiu vícerozměrných ,,krystalických mříží'', kde je ovšem technicky značně komplikovanější. My se omezíme na jednorozměrný případ:

Okolo kulatého stolu majícího $ N$ židlí (očíslujeme je $ 0,1,\dots,\allowbreak
{N-1}$ a identifikujeme jako prvky cyklické grupy) chceme rozsadit $ N$ jedinců (atomů) příslušících některé z $ k$ různých tříd (muži, ženy, prázdno; atomy různych více či méně se snášejících prvků apod.)

Předpokládejme pro jednoduchost, že ,,interagují'' pouze nejbližší sousedé u stolu. Máme tedy zadánu jistou $ (k\times k)$ symetrickou matici ,,snášenlivosti'' $ A=(a_{ij})$, kde $ a_{ij}=a_{ji}=1$, resp. $ =0$ pokud se prvky tříd $ i$$ j$ snášejí vedle sebe či nikoliv.

Ptáme se nyní: kolik existuje přípustných rozsazení okolo stolu, tzn. zobrazení

$\displaystyle <tex2html_comment_mark>2574 F:\,\{0,1,\dots,N-1\}\ \rightarrow\ \{1,2,\dots,k\}$ (306)

takových, že $ a_{\{F(i),F(j)\}}=1$ pro každý pár nejbližších sousedů $ (i,j)$, kde $ j=(i+1)\,\mathrm{mod}\,N$? Stačí spočítat

$\displaystyle <tex2html_comment_mark>2576 Z~= \sum_{F}\prod_{i=1}^{N} a_{F(i),F(i+1)},$ (307)

kde sumace je přes všechna zobrazení $ F$. Stejný výsledek platí i v obecnějším případě $ a_{ij}=\exp\,[-E_{ij}]$, kde $ E=(E_{ij})$ je energetická matice jejíž prvky vyjádřují ,,energii'' -- stupeň (ne)libosti, kterou blízkost sousedů typu $ i$$ j$ produkuje. $ Z$ se pak nazývá partiční funkce.

Věta Platí rovnost

$\displaystyle <tex2html_comment_mark>2578 Z~= {\mathrm{Tr}}\,A^N.$ (308)

Dokažte!

Důsledek: Nechť $ \lambda_1,\dots,\lambda_k$ jsou (reálná!) vlastní čísla matice $ A$. Pak je

$\displaystyle <tex2html_comment_mark>2580 Z~= \sum_{i=1}^{k}\lambda_i^N = \lambda_1^N(1+\sum_{i=2}^{k} (\lambda_i/\lambda_1)^N).$ (309)

Poslední tvar je vhodný v případě, že $ \lambda_1$ je největší vlastní číslo. Pak platí přibližná formule

$\displaystyle <tex2html_comment_mark>2582 Z\ \doteq\ \lambda_1^N.\\ $ (310)

Příklad. Kolika způsoby lze rozsadit muže a ženy kolem kulatého stolu, aby

$ a)$
žádné dvě osoby neseděly těsně vedle sebe?
$ b)$
žádný muž a žena neseděli těsně vedle osoby druhého pohlaví?
$ c)$
žádná osoba nebyla obklopena jenom osobami stejného pohlaví, resp. prázdnem?

Řešení. $ a)$ situaci odpovídá matice $ A=
\left(\begin{array}{cc}
1&1\\
1&0
\end{array}\right),$

$\displaystyle <tex2html_comment_mark>2584 Z~= \tau^N + \frac{1}{\tau^N} = \frac...
...{2}\rfloor} {N \choose 2k} 5^{\frac{N}{2}-k},\quad \tau = \frac{\sqrt{5}+1}{2}.$ (311)

První řádek $ A$ odpovídá osobě a druhý prázdnu.

$ b)$ situaci odpovídá matice $ A=
\left(\begin{array}{ccc}
1&0&1\\
0&1&1\\
1&1&1
\end{array}\right)$.

$\displaystyle <tex2html_comment_mark>2586 Z~= (\sqrt{2}+1)^N + (-\sqrt{2}+1)^N ...
...rac{1}{2^{N-1}} \sum_{k=0}^{\lfloor \frac{N}{2}\rfloor} {N \choose 2k} 2^{k+1}.$ (312)

Řádky a sloupce matice $ A$ odpovídají mužům, ženám a prázdnu (v tomto pořadí).

$ c)$ To je početně trochu složitější problém.

Je třeba ho formulovat v řeči trojic sousedů (a jak se snášejí se sousedními, je protínajícími, trojicemi). Příslušná matice je rozměrů $ (27\times27)$ -- počet možných trojic je $ 3^3=27$, kde jednotlivá židle je obsazena buď ženou, mužem, nebo je prázdná. (Trojice typu (muž, muž, muž), či (muž, muž, prázdno), či (prázdno, muž, prázdno) jsou zakázány. Kompatibilita sousedících trojic je dána jejich společným průnikem).