XXII OM - II - Zadanie 1

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

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)$ .