wystąpień liczby k jako części podziału λ∼ ◦ µ∼ jest sumą ilości wystąpień liczby k w podziale λ∼ i ilości wystąpień liczby k w podziale...

50. Równość F (t) = G(t)F (t2) otrzymujemy korzystając ze związku
1 − t2i = (1 − ti)(1 + ti) oraz ze wzorów F (t) = Q∞
1
i G(t) = Q∞ (1 + ti)
i=1 1−ti
i=1
udowodnionych na wykładzie. W tej sytuacji równość
P (n) = Q(n) + Q(n − 2)P (1) + Q(n − 4)P (2) + Q(n − 6)P (3) + · · · .
otrzymujemy porównując współczynniki przy tn w F (t) oraz w iloczynie
G(t)F (t2). Bezpośredni dowód powyższego wzoru otrzymujemy związując
z każdym podziałem λ = (λ1, λ2, . . .) = (1i1, 2i2, . . .) parę podziałów µ i ν
w następujący sposób. Podział µ składa się z tych części podziału λ, któ-
re występują w nim nieparzystą ilość razy, zaś podział µ dany jest wzorem
µ = (1b i1 c
c
2
, 2b i22 , . . .).
29
2.8
Liczby Stirlinga 51. n = n, gdyż wśród n−1 zbiorów jeden musi być 2-elementowy,
n−1
2
pozostałe zaś 1-elementowe. Zbiór 2-elementowy możemy wybrać na n spo-
2
sobów, pozostałe n − 2 elementy w jednoznaczny sposób tworzą zbiory 1-
elementowe. Podobnie n = n + 1 n n−2.
n−2
3
2
2
n−4
52. Zauważmy, że zbiór {1, . . . , n+1} możemy podzielić na k niepustych
podzbiorów w następujący sposób: wybieramy najpierw podzbiór A zawiera-
jący n + 1, a następnie dzielimy pozostałe elementy dzielimy na k − 1 niepu-
stych podzbiorów. Przy ustalonym zbiorze A możemy to zrobić na n+1−l
k−1
sposobów, gdzie l = l(A) jest ilością elementów zbioru A. Ponieważ przy
ustalonym l zbiór A możemy wybrać na
n sposobów oraz możliwe warto-
l−1
ści l to 1, . . . , n (gdy l > n − k − 2, to n+1−l = 0), więc wzór otrzymujemy
k−1
podstawiając j = n + 1 − l i korzystając z tożsamości
n = n.
n−j
j
53. Niech an,k będzie ilością rozstawień k wież na rozważanej szachowni-
cy. Oczywiście a

n,0 = 1 = n+1
oraz a
. Dla k = 1, . . . , n − 1
n+1
n,n = 1 = n+1
1
otrzymujemy, że an,k = an−1,k+(n+1−k)an−1,k−1. Istotnie, pierwszy składnik
wyrażenia po prawej stronie odpowiada tym rozstawieniom k wież, w których
żadna z wież nie stoi w pierwszej kolumnie, zaś drugi pozostałym. Korzysta-
jąc z założenia indukcyjnego oraz wzoru m = m−1 + lm−1 udowodnio-
l
l−1
l
nego na wykładzie, otrzymujemy, że a

n,k = n
+ (n + 1 − k)
n
=
n−k
n+1−k

n+1 .
n+1−k
54. Porównanie współczynników stojących przy tk w pierwszym wzorze
daje tożsamość n = kn−1 + n−1 udowodnioną na wykładzie. Podob-
k
k
k−1
nie druga równość sprowadza się do wzoru n = Pn−1 n−1 j poka-
k
j=0
j
k−1
zanego w zadaniu 52. Ostatni wzór jest konsekwencją dwóch poprzednich.
Istotnie, z pierwszego wzoru mamy tP 0 (t) = P
n
n+1(t) − tPn(t). Podstawiając
z drugiego wzoru P
n−1
n+1(t) = t Pn
P
j=0
j
j (t) i dzieląc otrzymaną równość
przez t, kończymy dowód. Zauważmy, że ostatni wzór daje nam tożsamość
(k + 1) n = Pn−1 nj , którą można też uzasadnić bezpośrednio.
k+1
j=0
j
k
2.9 Systemy reprezentantów
55. Niech Ai będzie zbiorem mężczyzn, których zna kobieta i. Warunki
zadania mówią, że ciąg (A1, . . . , An) spełnia warunek Halla, zatem istnieje dla
tego ciągu system reprezentantów, to znaczy każdą kobietę możemy połączyć
w parę ze znajomym mężczyzną tak, aby różne kobiety były połączone w
30
pary z różnymi mężczyznami. Jeśli wśród wybranych mężczyzn nie ma A,
to wprowadzamy go na miejsce mężczyzny, który został przyporządkowany
jednej z kobiet znanej przez A.
56. Możemy założyć, że ai,j ≥ 0 dla wszystkich i, j. Istotnie, macierz
J złożona z samych jedynek jest w trywialny sposób kombinacją liniową
macierzy permutacji oraz macierz A + µJ ma współczynniki nieujemne dla
dostatecznie dużego µ. Dowód będzie indukcyjny ze względu na ilość m par
(i, j) takich, że ai,j > 0. Gdy m = 0, to teza jest oczywista. Przypuśćmy
zatem, że m > 0. Dla każdego i = 1, . . . n niech Xi będzie zbiorem tych
indeksów j, dla których ai,j > 0. Pokażemy, że ciąg (X1, . . . , Xn) spełnia
warunek Halla. Ustalmy I ⊆ {1, . . . , n} i niech k = |X|, gdzie X = S
X
i∈I
i.
Wtedy |I|µ = P
Pn
a
P
a
P
a
i∈I
j=1
i,j = Pi∈I
j∈X
i,j = Pj∈X
i∈I
i,j ≤ kµ, skąd
|I| ≤ k. Niech (σ1, . . . , σn) będzie system reprezentantów ciągu (X1, . . . , Xn)
oraz P = (pi,j), gdzie pi,j = δσi,j. Wtedy P jest macierzą permutacji oraz
A − λP jest kombinacją liniową macierzy permutacji na mocy założenia in-
dukcyjnego, gdzie λ = min{ai,σ | i = 1, . . . , n}.
i
57. Z poprzedniego zadania wiemy, że rozważana podprzestrzeń liniowa
jest zbiorem rozwiązań układu równań Pn
a
a
i=1
i,j = Pn
i=1
i,1, j = 2, . . . , n,
Pn
a
a
i=1
j,i = Pn
i=1
i,1, j = 2, . . . , n, zatem jej wymiar jest równy n2 − 2(n −
1) = (n − 1)2 + 1.
58. Ustalmy macierz A = (ai,j) oraz oznaczmy przez N minimalną ilość


	wystąpień liczby k jako części podziału λ∼ ◦ µ∼ jest sumą ilości wystąpień liczby k w podziale λ∼ i ilości wystąpień liczby k w podziale...	Pomodliłem się do każdego boga jaki istniał bym był w wstanie wkurzyć tę kobietę do granic możliwości.