Tato úloha neprošla kontrolou správnosti.
Latinské obdélníky
Úloha číslo: 4588
Latinský obdélník je obdélníková tabulka \(k\times n\) vyplněná čísly z množiny \(\{1,\ldots,n\}\) tak, že v žádném řádku ani sloupci se čísla neopakují.
Spočítejte, kolik existuje latinských obdélníků tvaru \(2\times n\).
Řešení
Nejprve počítejme normalizované obdélníky, jejichž první řádek obsahuje čísla \(1, \ldots, n\) v rostoucím pořadí. Druhý řádek je nějaká permutace množiny \(\{1,\ldots,n\}\), která nemá pevný bod. Takové permutace počítá problém šatnářky, jejich počet označíme \(\check{s}(n)\).
Každý další latinský obdélník vznikne z nějakého normalizovaného obdélníku permutováním sloupců. To lze udělat \(n!\) způsoby.
Celkem tedy existuje \(n!\cdot\check{s}(n)\) latinských obdélníků \(2\times n\).
