szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 cze 2018, o 22:11 
Użytkownik

Posty: 4
Lokalizacja: Krakau
Dzień dobry. Takie zadanie jest do zrobienia:
Rozważamy wszystkie podziały liczby naturalnej n. Niech \pi będzie wybranym podziałem. a(\pi) definiujemy jako liczbę jedynek w podziale, a b(\pi) jako liczbę różnych składników podziału (np. dla n = 12 ; \pi = 4+4+2+1+1 b wynosi 3).
Cel: pokazać, że \sum_{\pi \in Podzialy(n)}^{} a(\pi) = \sum_{\pi \in Podzialy(n)}^{} b(\pi).
Wskazówka : wyrazić obie strony jako wyrażenia od P(1),...,P(n), gdzie P(n) to liczba podziałów liczby n.
Mój wkład:
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ą.
Jak zrobić prawą?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2018, o 12:52 
Użytkownik

Posty: 12322
Lokalizacja: Presslaw
Wskazówka: diagramy Ferrersa.
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2018, o 21:30 
Użytkownik

Posty: 4
Lokalizacja: Krakau
Rzuciłbyś trochę więcej mięsa?
Np. czy wyznaczenie prawej sumy jako wyrażenia od P( \cdot) da się zrobić dla każdego zbioru A_k osobno , gdzie A_k to zbiór podziałów takich, że b(\pi) = k?
Góra
Mężczyzna Offline
PostNapisane: 15 cze 2018, o 11:58 
Użytkownik
Avatar użytkownika

Posty: 3268
Lokalizacja: blisko
Fajne zadanie...

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

Oznaczmy:

R(n) - ilość podziałów bez jedynkowych w liczbie n

np:

4=2+2 , 4=4 , R(4)=2

łatwo zaobserwować, że:

(*) 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:

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

biorą pod uwagę (*) otrzymamy:

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:

W(n,k) ile jest rozkładów liczbyn na k różnych składników

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

6=6,6=5+1,6=4+2

W(6)=W(6,1)+W(6,2)+W(6,3)+...=1+2+0=3

Teraz pasuje znaleźć wzór na W(n,k)

n=x_{1}+x_{2}+...+x_{k}

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

x_{1}:=x_{1}

x_{2}:=x_{2}+1

x_{3}:=x_{3}+2

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

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

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

Czyli:

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

Gdzie:

P(n,k) - rozkład liczby n na 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:

4=4 - jeden

4=3+1 -dwa

4=2+2 -jeden

4=2+1+1 -dwa

4=1+1+1+1 -jeden

Razem:

1+2+1+2+1=7

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

\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:

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ć...
Góra
Mężczyzna Offline
PostNapisane: 16 cze 2018, o 12:44 
Użytkownik

Posty: 4
Lokalizacja: Krakau
Cytuj:
Czyli:

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

Mylisz się i to bardzo. Spójrz na przykład na W(10,2).
P(9,2) = 4
do W(10,2) na pewno należą
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ć?
Góra
Mężczyzna Offline
PostNapisane: 16 cze 2018, o 22:32 
Użytkownik
Avatar użytkownika

Posty: 3268
Lokalizacja: blisko
No co Ty W(n,k) to podział liczby na sumęk różnych
niezerowych składników.

W(10,2):

10=10

10=9+1

10=8+2

10=7+3

10=6+4

Jest ich pięć

ale:

W(10,2)=P(9,2)

P(9,2):

9=9

9=8+1

9=7+2

9=6+3

9=5+4

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

Cytuj:
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ł...

Cytuj:
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...


Cytuj:
do W(10,2) na pewno należą:
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...
Góra
Mężczyzna Offline
PostNapisane: 16 cze 2018, o 22:48 
Użytkownik

Posty: 4
Lokalizacja: Krakau
Cytuj:
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ć
Góra
Mężczyzna Offline
PostNapisane: 16 cze 2018, o 23:09 
Użytkownik
Avatar użytkownika

Posty: 3268
Lokalizacja: blisko
Wiem o tym ale wyprowadzenie tego wzoru na W(n,k) było mi potrzebne do dalszej części zadania...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podziały liczby - zadanie 2  sandra-91  2
 podziały liczby - zadanie 3  matinf  1
 Podziały liczby  ma9002  0
 Na ile sposobów można utworzyć liczby  tprzemo  1
 liczby naturalne 4-cyfrowe  BlueSky  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl