Wariacje bez powtórzeń

Zbiór wszystkich funkcji różnowartościowych zbioru k-elementowego w zbiór n-elementowy. Funkcje różnowartościowe określone w zbiorze k-elementowym o wartościach w zbiorze n-elementowym nazywamy k-wyrazowymi wariacjami bez powtórzen n elementów. Dla pary liczb naturalnych n, k liczbę elementów zbioru k-wyrazowych wariacji bez powtórzeń n elementów oznaczamy V_n^k. Jeśli zbiorem k-elementowym jest zbiór {1, 2,..., k}, to wariacja bez powtórzeń f jest ciągiem k-wyrazowym (f (1), f (2),..., f (k)) elementów zbioru n-elementowego. Liczba V_n^k k-wyrazowych wariacji bez powtórzeń n elementów wyraża się wzorem

V_n^k = $$\binom{n}{k}$$k! = n(n - 1)...(n - k + 1).

W szczególności jeśli k > n, to V_n^k = 0. Rzeczywiście, jeśli k = 0 lub k = 1 to łatwo sprawdzić, że liczba $\binom{n}{0}$0! = 1 jest liczbą V_n⁰ pustych ciagów elementów zbioru n-elementowego, $\binom{n}{1}$1! = n jest liczbą V_n¹ jednowyrazowych ciagów elementów zbioru n-elementowego. Jeśli dla pewnej liczby k zachodzi równość $\binom{n}{k}$k! = n, to każdy ciąg k-wyrazowy można przedłużyć do ciągu (k + 1)-wyrazowego na tyle sposobów, ile elementów zbioru n-elementowego nie występuje w tym ciągu, czyli na n - k sposobów. Łącznie jest więc

V_n^k+1 = (n - k)V_n^k = (n - k)$$\binom{n}{k}$$k! = $${\frac{{n-k}}{{k+1}}}$$$$\binom{n}{k}$$(k + 1)! = $$\binom{n}{k+1}$$(k + 1)!

ciągów (k + 1)-wyrazowych i wzór na liczbę wariacji bez powtórzeń jest słuszny dla wszystkich liczb naturalnych k.