Pokazać, że tożamość na podziałach liczby

[matinf]

Witam,

Mamy pokazać, że:
\(\displaystyle{ P_k(n) = P_k(n-k) + P_{k-1}(n-1)}\)

Jak to pokazać ?

[Qń]

Wskazówka - podziały liczby \(\displaystyle{ n}\) na \(\displaystyle{ k}\) części można podzielić na dwa rodzaje: takie, w których żaden składnik nie jest równy \(\displaystyle{ 1}\) oraz takie, w których istnieje składnik równy \(\displaystyle{ 1}\). Wystarczy zauważyć ile jest podziałów poszczególnych rodzajów.

Q.

[matinf]

No do tego między czasie doszedłem.
Faktycznie można takiego rozdziału dokonać.

Wszystkie podziały które mają w sobie jedynkę, to faktycznie podziały:
\(\displaystyle{ P_{k-1}(n-1)}\)
Tzn, po prostu chcą dostać dla liczby \(\displaystyle{ n}\) podziały które zawierają jedynkę, wystarcz powiedzieć sobie słownie, że "dodaję jedynkę" i mam ilość podziałów żądanej liczby \(\displaystyle{ n}\)


No ok, to jest pewna ilość podziałów - każdy z nich zawiera jedynkę. Problem polega na tym, że nie liczymy wszystkich, więc musimy jakieś dodać.

No i to co dostajemy od treści zadania wydaje mi się dziwne:
\(\displaystyle{ P_k(n-k)}\)
Bo ja o tym myślę tak:
Dziwne - przecież dodajemy jakby nie to co trzeba ? Ok, podział na k składników - wszystko fajnie, ale to nie jest podział liczby \(\displaystyle{ n}\)!. Jak to się ma do tego zadania ? Jak to rozumieć ?

[Qń]

\(\displaystyle{ P_{k-1}(n-1)}\)
Tzn, po prostu chcą dostać dla liczby \(\displaystyle{ n}\) podziały które zawierają jedynkę, wystarcz powiedzieć sobie słownie, że "dodaję jedynkę" i mam ilość podziałów żądanej liczby \(\displaystyle{ n}\).
(...)
\(\displaystyle{ P_k(n-k)}\)
Dziwne - przecież dodajemy jakby nie to co trzeba ? Ok, podział na k składników - wszystko fajnie, ale to nie jest podział liczby \(\displaystyle{ n}\)

Nie rozumiem co chcesz powiedzieć w żadnym z tych dwóch wypadków.

Więc może tak - po pierwsze: najwygodniej do opisu użyć diagramów Ferrersa. A po drugie: my nic nie "dodajemy", tylko przeciwnie - zabieramy coś (to co nam akurat wygodnie) i następnie zastanawiamy się na ile sposobów można ułożyć to co zostanie.

Q.

[matinf]

Ok, jak rozumiem to każdy podział to osobny diagram Ferrersa

tzn, weźmy \(\displaystyle{ n = 5}\) oraz\(\displaystyle{ k = 2}\)
Wówcza:
\(\displaystyle{ 5 = 3 + 2\\
5 = 4 + 1}\)
Innych podziałów "na dwa" nie ma.

Tak więc Diagramy Ferrersa to odpowiednio:

\(\displaystyle{ ...\\
..}\)
oraz
\(\displaystyle{ ....\\
.}\)

Intuicyjnie rozumiem o co chodzi :
Tzn, powiedzmy, że jest pytanie o liczbę podziałów liczby \(\displaystyle{ 10}\) na \(\displaystyle{ 3}\) liczby przy czym żądamy aby wystąpiła liczba \(\displaystyle{ 6}\) w tym podziale:
Wówczas ja twierdzę, że takich podziałów jest:
\(\displaystyle{ P_{3-1}(10-6) = P_2(4)}\)

Ale jak to się ma do naszego zadania ? Analogicznie wydzielamy część z podziałami, w których występuje jedynka. Ale to nie jedyne podziały - dlatego jeszcze dodajemy \(\displaystyle{ P_{k}(n-k)}\)
I teraz to należy rozważyć. Ale nie jest to takie łatwe....

[Qń]

Podziały w których nie ma składnika równego jeden zliczamy w ten sposób, że usuwamy z diagramu Ferrersa pierwszą od lewej kolumnę i sprawdzamy na ile sposobów można dobrać resztę, a podziały w których jest składnik równy jeden zliczamy usuwając pierwszy wiersz od dołu (ten z jedynką) i sprawdzamy na ile sposobów można dobrać resztę.

Q.

[matinf]

Ok, może trochę to przeanalizuję:

Dzielimy na \(\displaystyle{ k}\) składników - \(\displaystyle{ k}\) wierszy.
Generalnie kropek (Ilość) ma być \(\displaystyle{ n}\).
Jeśli więc usuniemy 1wszą kolumnę faktycznie jeśli jakaś jedynka była w podziale to była w ostatnim wierszu (jedna kropka w 1szej kolumnie).

Tak więc faktycznie widać, że ta pojedyncza kropka znika (nie ma jedynki w podziale). A liczba kropek wszystkich to jest \(\displaystyle{ n-k}\)
Ale mimo wszystko mamy nadal \(\displaystyle{ k}\) wierszy (składników).

A więc te diagramy( może ich być kilka) reprezentowały \(\displaystyle{ P_k(n)}\).
Z kolei po usunięciu 1szej kolumny mamy: \(\displaystyle{ P_k(n-k)}\).

Więc podział bez jedynek mamy już!
Nastał czas, żeby usunąć ostatni wiersz - czyli kasujemy de'facto jedynkę - zakłądamy, że te podziały teraz "atakujemy". Więc dostajemy reprezentację \(\displaystyle{ P_{k-1}{n-1}}\)

Faktycznie, widać więc że to działa. Fajny dowód.
Mogę spróbować to dowieść jeszcze inną metodą ? tj indukcyjną ?

-- 7 kwi 2014, o 11:31 --

I dodam jeszcze jedną tożsamość:
\(\displaystyle{ P_k(n) = P_k(n-k) + P_{k-1}(n-k) + ... + P_{1}(n-k)}\)

Zanim ją zaatakuję indukcją, chciałbym ją zrozumieć diagramami Ferrersa.

Pierwszy składnik prawej sumy to oczywiście podziały, w których nie ma jedynek.
Wówczas intuicja jest taka, że każdy inny podział musi zawierać choćby jedną jedynkę ! (w przeciwnym razie policzymy jakiś podział 2 razy).

\(\displaystyle{ P_{k-1}(n-k)}\) - to rozważmy:
Żeby dostać to co w argumencie usuwamy pierwszą kolumnę. Wówczas, żeby zgadzał sie index dolny powinniśmy uważać, że w wyniku usunięcia 1szej kolumny jeden (dokładnie jeden wiersz znika). W takim razie musiała tam stać jedna jedynka - generalnie dany podział musiał mieć dokładnie jedną jedynkę.

Takie samo rozumowanie pojawia się dla następnych, tzn podział musiał mieć k jedynek skoro w wyniku usunięcia pierwszej kolumny znika nam k wierszy (składników w podziale).



Z drugiej strony jednak można o tym chyba pomyśleć inaczej. Usuńmy najpierw dowolny wiersz:
Zostało nam \(\displaystyle{ k-1}\) składników - tak jak chcieliśmy. Teraz musi zgadzać się to z argumentem, a więc usunęliśmy wiersz, w którym było \(\displaystyle{ k}\) składników - tzn zliczamy podziały, w których występuje składnik o wartości \(\displaystyle{ k}\).
Problem polega tylko na tym, że jak to się ma do coraz mniejszych indexów (w prawej sumie one sukcesywnie maleją o 1). Usuwamy wówczas dwa dowolne wiersze, ale uważając że sumowały się ich składniki do \(\displaystyle{ k}\)

Jak z tym co mówię? Właściwie to rozumie ? Bo są 2 drogi - pierwsza chyba lepsza.

Pozdrawiam!

-- 7 kwi 2014, o 18:12 --

Ok, problem rozwiązany. Temat do zamknięcia.