Podziały liczby

[kpmkpm]

Dzień dobry. Takie zadanie jest do zrobienia:
Rozważamy wszystkie podziały liczby naturalnej \(\displaystyle{ n}\). Niech \(\displaystyle{ \pi}\) będzie wybranym podziałem. \(\displaystyle{ a(\pi)}\) definiujemy jako liczbę jedynek w podziale, a \(\displaystyle{ b(\pi)}\) jako liczbę różnych składników podziału (np. dla \(\displaystyle{ n = 12 ; \pi = 4+4+2+1+1}\) b wynosi 3).
Cel: pokazać, że \(\displaystyle{ \sum_{\pi \in Podzialy(n)}^{} a(\pi) = \sum_{\pi \in Podzialy(n)}^{} b(\pi)}\).
Wskazówka : wyrazić obie strony jako wyrażenia od \(\displaystyle{ P(1),...,P(n)}\), gdzie \(\displaystyle{ P(n)}\) to liczba podziałów liczby \(\displaystyle{ n}\).
Mój wkład:
Liczba podziałów liczby \(\displaystyle{ n}\) z co najmniej \(\displaystyle{ k}\) jedynkami wynosi \(\displaystyle{ P(n-k)}\); korzystamy z włączania-wyłączania (żeby znaleźć liczbę podziałów z dokładnie \(\displaystyle{ k}\) jedynkami) i mamy lewą stronę załatwioną.
Jak zrobić prawą?

[Premislav]

Wskazówka: diagramy Ferrersa.

[kpmkpm]

Rzuciłbyś trochę więcej mięsa?
Np. czy wyznaczenie prawej sumy jako wyrażenia od \(\displaystyle{ P( \cdot)}\) da się zrobić dla każdego zbioru \(\displaystyle{ A_k}\) osobno , gdzie \(\displaystyle{ A_k}\) to zbiór podziałów takich, że \(\displaystyle{ b(\pi) = k}\)?

[arek1357]

Fajne zadanie...

Najpierw znajdziemy ile mieści się jedynek we wszystkich rozkładach \(\displaystyle{ p(n)}\)

Oznaczmy:

R(n) - ilość podziałów bez jedynkowych w liczbie \(\displaystyle{ n}\)

np:

\(\displaystyle{ 4=2+2 , 4=4 , R(4)=2}\)

łatwo zaobserwować, że:

(*) \(\displaystyle{ p(n)-p(n-1)=R(n)}\)

a teraz liczmy ile jedynek wystąpi w każdym rozkładzie, łatwo zauważyć, że ta ilość to:

\(\displaystyle{ n+(n-2)R(2)+(n-3)R(3)+...+1 \cdot R(n-1)=}\)

biorą pod uwagę (*) otrzymamy:

\(\displaystyle{ n+(n-2)\left[ p(2)-p(1)\right]+(n-3)\left[ p(3)-p(2)\right] +(n-4)\left[ p(4)-p(2)\right]+...+1 \cdot \left[ p(n-1)-p(n-2)\right]=2+ \sum_{i=2}^{n-1}p(i)}\)

Dość ładny wzór.

Teraz trzeba się zająć różnymi składnikami , ile ich jest w danym rozkładzie.

Przyjmijmy:

\(\displaystyle{ W(n,k)}\) ile jest rozkładów liczby\(\displaystyle{ n}\) na \(\displaystyle{ k}\) różnych składników

\(\displaystyle{ W(n)}\) - ile jest możliwych rozkładów liczby n na różne składniki
np:

\(\displaystyle{ 6=6,6=5+1,6=4+2}\)

\(\displaystyle{ W(6)=W(6,1)+W(6,2)+W(6,3)+...=1+2+0=3}\)

Teraz pasuje znaleźć wzór na \(\displaystyle{ W(n,k)}\)

\(\displaystyle{ n=x_{1}+x_{2}+...+x_{k}}\)

Chcemy teraz aby składniki były różne , więc przyjmujemy:

\(\displaystyle{ x_{1}:=x_{1}}\)

\(\displaystyle{ x_{2}:=x_{2}+1}\)

\(\displaystyle{ x_{3}:=x_{3}+2}\)

.........................................

\(\displaystyle{ x_{k}:=x_{k}+(k-1)}\)

\(\displaystyle{ 1+2+3+...+(k-1)= \frac{k(k-1)}{2}}\)

Czyli:

\(\displaystyle{ W(n,k)=P(n-\frac{k(k-1)}{2},k)}\)

Gdzie:

\(\displaystyle{ P(n,k)}\) - rozkład liczby \(\displaystyle{ n}\) na \(\displaystyle{ k}\) niezerowych składników...

Teraz łatwo zauważyć, że ilość różnych składników na które rozłożona jest liczba to np:

\(\displaystyle{ 4=4}\) - jeden

\(\displaystyle{ 4=3+1}\) -dwa

\(\displaystyle{ 4=2+2}\) -jeden

\(\displaystyle{ 4=2+1+1}\) -dwa

\(\displaystyle{ 4=1+1+1+1}\) -jeden

Razem:

\(\displaystyle{ 1+2+1+2+1=7}\)

Łatwo zaobserwować, że ilość tych składników można wyliczyć ze wzoru:

\(\displaystyle{ \sum_{i=1}^{ \infty }iW(n,i) +\sum_{i=1}^{ \infty }iW(n-1,i)+...+\sum_{i=1}^{ \infty }iW(2,i)}\)

Teraz bierz pod uwagę,że:

\(\displaystyle{ W(s,i)=P(s- \frac{i(i-1)}{2},i)}\)

Podstaw , powinno nabrać wyglądu i upodobnić się do strony lewej tej z jedynkami.

Jeszcze tego sam nie zdążyłem uprościć...

[kpmkpm]

Czyli:

\(\displaystyle{ W(n,k)=P(n-\frac{k(k-1)}{2},k)}\)

Mylisz się i to bardzo. Spójrz na przykład na \(\displaystyle{ W(10,2)}\).
\(\displaystyle{ P(9,2) = 4}\)
do \(\displaystyle{ W(10,2)}\) na pewno należą
\(\displaystyle{ 1+9;1+1+8;1+1+1;7;1+1+1+1+6;1+1+1+1+1+5;1+1+1+1+1+1+4;1+1+!+1+!+1+1+3}\)

To żaden atak przysięgam, ale po co tracisz czas na rozpisywanie lewej strony, skoro napisałem jak ją zrobić?

[arek1357]

No co Ty \(\displaystyle{ W(n,k)}\) to podział liczby na sumę\(\displaystyle{ k}\) różnych
niezerowych składników.

\(\displaystyle{ W(10,2)}\):

\(\displaystyle{ 10=10}\)

\(\displaystyle{ 10=9+1}\)

\(\displaystyle{ 10=8+2}\)

\(\displaystyle{ 10=7+3}\)

\(\displaystyle{ 10=6+4}\)

Jest ich pięć

ale:

\(\displaystyle{ W(10,2)=P(9,2)}\)

\(\displaystyle{ P(9,2):}\)

\(\displaystyle{ 9=9}\)

\(\displaystyle{ 9=8+1}\)

\(\displaystyle{ 9=7+2}\)

\(\displaystyle{ 9=6+3}\)

\(\displaystyle{ 9=5+4}\)

Też pięć , aż tak bardzo się nie mylę, choć jam omylny jest...

po co tracisz czas na rozpisywanie lewej strony, skoro napisałem jak ją zrobić?

żadnego wzoru pasującej do strony lewej nie zauważyłem tu co byś podał...

Liczba podziałów liczby n z co najmniej k jedynkami wynosi P(n-k); korzystamy z włączania-wyłączania (żeby znaleźć liczbę podziałów z dokładnie k jedynkami) i mamy lewą stronę załatwioną.

Otóż załatwionej lewej strony nie mamy bo nie widać żadnego wzoru...

do \(\displaystyle{ W(10,2)}\) na pewno należą:
\(\displaystyle{ 1+9;1+1+8;1+1+1;7;1+1+1+1+6;1+1+1+1+1+5;1+1+1+1+1+1+4;1+1+!+1+!+1+1+3}\)

Niczego takiego nie pisałem i sobie nie przypominam...

[kpmkpm]

No co Ty W(n,k) to podział liczby na sumęk różnych

a w zadaniu chodzi o podział na k róznych składnikow, które mogą się powatarzać

[arek1357]

Wiem o tym ale wyprowadzenie tego wzoru na \(\displaystyle{ W(n,k)}\) było mi potrzebne do dalszej części zadania...