XXII OM - II - Zadanie 1

Na ile sposobów można tak wybrać $ k $ pól szachownicy $ n \times n $ ($ k \leq n $), aby żadne dwa z wybranych pól nie leżały ani w jednym wierszu, ani w jednej kolumnie?

Rozwiązanie

Można najpierw wybrać $ k $ wierszy, w których mają leżeć wybrane pola. Uczynić to można na $ \displaystyle \binom{n}{k} $ sposobów. Następnie w każdym z tych wierszy należy kolejno wybrać jedno z $ n $ pól, jedno z $ n - 1 $ pól leżących w pozostałych kolumnach, itd. - jedno z $ n - k + 1 $ pól. Zatem łączna liczba sposobów równa jest $ \displaystyle \binom{n}{k} n(n - 1) \ldots (n - k + 1) $.

Komentarze

Dodaj nową odpowiedź