Matematyka dyskretna - zadania

Zadanie 1.
Pokazać, że ilość podziałów liczby n na r składników jest równa ilości podziałów
liczby n o największym składniku równym r.

Rozwiązanie:
Niech p = p

1

+ . . . + p

r

∈ P (n, r). Podziałowi p odpowiada diagram Ferrersa:

p

1

•

· · ·

•

· · · · · ·
p

r

•











r składników

Przyporządkujmy temu diagramowi jego diagram dualny

p

1

· · · p

r

•

· · ·

•

← największy składnik równy r

· · ·

•

Diagramowi dualnemu odpowiada podział liczby n na składniki nie przekraczające
r. Przyporządkowanie jest bijekcją co dowodzi równości.

Zadanie 2.
Zbadać, czy ilość podziałów liczby n na co najwyżej r składników jest równa ilości
podziałów tej liczby na sumę składników nie przekraczających r.

Rozwiązanie:
Podziałowi liczby n na co najwyżej r składników odpowiada diagram Ferrersa

p

1

•

· · ·

•

· · · · · ·
p

s

•











¬ r składników

Przyporządkujmy temu diagramowi diagram dualny

p

1

· · · p

s

•

· · ·

•

← największy składnik ¬ r

· · ·

•

Diagram dualny odpowiada podziałowi liczby n na składniki nie przekraczające r.
Przyporządkowanie jest bijekcją, a więc badana równość zachodzi.

Zadanie 3.
Pokazać, że ilość podziałów liczby n + k na k składników jest równa ilości podziałów
liczby n na co najwyżej k składników, tzn.: P (n + k, k) = p(n, k).

Rozwiązanie:
Niech (a

1

, . . . , a

k

) będzie podziałem liczby n + k na k składników. Przyporządkujmy

temu podziałowi podział (a

1

− 1, . . . , a

k

− 1). Jest to podział liczby n na co najwyżej

k składników.
A więc funkcja (a

1

, . . . , a

k

) → (a

1

− 1, . . . , a

k

− 1) wyznacza wzajemnie jednoznaczną

odpowiedniość między P (n + k, k) oraz p(n, k)

Zadanie 4.
Niech P (n, k) oznacza liczbę podziałów liczby n na dokładnie k składników. Pokazać,
że:

P (n, k) =

k

X

i=0

P (n − k, i) ,

dla n > k > 0

Rozwiązanie:
Niech p ∈ P (n, k). Największy składnik w podziale p może wynosić n − (k − 1).
Wtedy p = (n − (k − 1), 1, . . . , 1).
Podział p może nie zawierać liczby 1 lub może zawierać liczby 1 w ilości od 1 do
k − 1. Niech p = (p

1

, . . . , p

k

). Przyporządkujmy temu podziałowi podział q = (p

1

−

1, . . . , p

k

− 1).

Jeśli w podziale p nie ma liczby 1, to q ∈ P (n − k, k).
Jeśli w podziale p występuje jedna liczba 1, to q ∈ P (n − k, k − 1)
Jeśli w podziale p występuje k − 1 liczb 1, to q ∈ P (n − k, 1)
To postępowanie jest odwracalne. Jeśli q = (q

1

, . . . , q

s

) jest podziałem liczby n − k na

co najwyżej k składników, to podziałowi q przyporządkujemy podział p ∈ P (n, k),
taki że

p = (p

1

, . . . , p

k

) =

(

p

i

= q

i

+ 1 , gdy i ¬ s

p

i

= 1 , gdy i > s

A więc ostatecznie

P (n, k) =

k

X

i=0

P (n − k, i) ,

dla n > k > 0

Zadanie 5.
Pokazać, że ilość podziałów liczby 2n na dokładnie n składników jest równa ilości
wszystkich podziałów liczby n.

Rozwiązanie:
Zauważmy, że: P (2n, n) = P (n + n, n) = p(n, n). Jednak p(n, n) oznacza dokładnie
zbiór wszystkich podziałów liczby n. Stąd P (2n, n) = p(n).

Zadanie 6.
Pokazać następującą zależność dla podziałów liczby:

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

Rozwiązanie:
Niech π = (a

1

, . . . , a

k

) będzie podziałem liczby n na k składników. Jeśli a

k

= 1, to

przyporządkujmy podziałowi π podział (a

1

, . . . , a

k−1

). Jeśli a

k

> 1, to podziałowi π

przyporządkujemy podział (a

1

− 1, . . . , a

k

− 1). Funkcja

(a

1

, . . . , a

k

) →

(

(a

1

, . . . , a

k−1

),

gdy a

k

= 1

(a

1

− 1, . . . , a

k

− 1), gdy a

k

> 1

ustala wzajemnie jednoznaczną odpowiedniość między zbiorem P (n, k) i sumą zbio-
rów P (n − 1, k − 1) oraz P (n − k, k)

Zadanie 7.
Podziałem sprzężonym liczby n nazywamy podział określony przez transpozycję w
diagramie Ferrersa wierszy z kolumnami. Podział samosprzężony to podział liczby
n, w którym po zamianie wierszy z kolumnami w diagramie Ferrersa otrzymamy ten
sam podział.
Pokaż, że ilość podziałów samosprzężonych liczby n jest równa ilości podziałów licz-
by n na różne składniki nieparzyste.

Rozwiązanie:
Niech dany będzie podział samosprzężony π liczby n. Odpowiadający temu podziało-
wi diagram Ferrersa jest symetryczny. Zauważmy, że liczba punktów w pierwszej ko-
lumnie diagramu jest równa liczbie punktów w pierwszym wierszu. Ponadto pierwsza
kolumna i pierwszy wiersz mają jeden punkt wspólny. Oznacza to, że suma punktów
w pierwszej kolumnie i w pierwszym wierszu jest liczbą nieparzystą. Do analogicz-
nych wniosków dochodzimy dla kolumny drugiej, trzeciej itd.
Przyporządkujmy więc podziałowi π podział π

?

, którego składnikami będą sumy

odpowiednich wierszy i kolumn diagramu Ferrersa odpowiadającego podziałowi π.
Podział π

?

jest podziałem liczby n na różne składniki nieparzyste.

Proces ten jest odwracalny, stąd wnioskujemy, że ilość podziałów samosprzężonych
liczby n jest równa ilości podziałów liczby n na różne składniki nieparzyste.

Copyright

c

Grzegorz Gierlasiński