984501232

2. LICZBY NATURALNE. INDUKCJA MATEMATYCZNA

Przykład 2.6. Permutacje zbioru trójelementowego {1,2,3} wyszczególnione w przykładzie 2.4 mają następujące liczby inwersji:

I(Pi) = 0, /(p₂) = I(P3) = 1, J(P4) = I{Pb) = 2 oraz I{p₆) = 3.

Sprawdźmy ostatnią z tych równości, atwo zobaczyć, że w permutacji pe — (3,2,1) mamy trzy inwersje: (3,2), (3,1) oraz (2,1).

Z pojęciem permutacji związane są także tzw. współczynniki Newtona Dla dowolnych liczb całkowitych n oraz k większych lub równych 0, przy czym k ^ n, przyjmujemy

n\ _ n\ k) ~ k\(n — k)\'

Nietrudno sprawdzić, że zachodzą następujące równości:

Wzory (5), (6) i (7) wynikają wprost z definicji, a dla dowodu wzoru (8) wystarczy sprowadzić dwa ułamki do wspólnego mianownika:

(n\ i ( ⁿ i _ ⁿ- ,    ⁿ-

k) ⁺ U + lJ ⁼ k\ (n - k)\ ⁺ (k + 1)! [n - (k + 1)]! ⁼

_ n\ (k + 1) + n! (n — k) _ n! [(A: + 1) + (n — k)] _

(k + l)\(n — k)\    (k + 1)! (n — k)\

n!(n+l)    (n+1)!    /n + l\

⁼ (k + 1)! [(n + 1) — (A: + 1)]! ⁼ (k + 1)! [(n + 1) - (k + 1)]! ⁼ \k + lj’

Przy pomocy wzoru (8) można obliczać kolejne liczby ustawiając je w następującej tablicy zwanej trójkątem Pascala: