Partycja liczb

[mmss444]

Jesli moj temat jest nie tutaj, gdzie powinien, to prosze o jego przeniesienie.

Pytanie: Czy istnieje wzor na obliczanie partycji liczb??

Partycje malych liczb (np. do 10) jest latwo obliczyc, ale co z takimi liczbami jak 100, czy wieksze??

Prosze o pomoc.

[Mateusz Magier]

Przypominam sobie, że w czerwcowym numerze "Świata Nauki" zamieszczony został bardzo krótki artykuł, a właściwie informacja, która donosiła, że grupie matematyków udało się odkryć wzory, za pomocą których możliwe jest obliczanie partycji dla każdej liczby naturalnej, o czym teoretycy liczb marzyli od wielu lat. Wzory te są bardzo skomplikowane i opierają się na wzorach fraktalnych. Warto dodać również, że kilkadziesiąt lat temu matematyk Srinivasa Ramanujan poprawnie prognozował część zależności dotyczących partycji.

[Majeskas]

Oczywiście istnieje wzór rekurencyjny:

\(\displaystyle{ p_k(n)=p_{k-1}(n-1)+p_k(n-k)}\)

gdzie \(\displaystyle{ p_k(n)}\) oznacza ilość partycji liczby \(\displaystyle{ n}\) na \(\displaystyle{ k}\) części.

Chcąc mieć wszystkie partycję liczby \(\displaystyle{ n}\) mamy:

\(\displaystyle{ p(n)=\sum_{k=1}^np_k(n)}\)

Można też np. zauważyć, że \(\displaystyle{ p_2(n)=\left\lfloor\frac n2\right\rfloor}\).

[prudnicky]

Mógłbyś dokładnie wyjaśnić, jak obliczać takie wzory fraktalne? Załóżmy na przykładzie liczby 154

[Majeskas]

Nie bardzo rozumiem. Chodzi o wyznaczenie \(\displaystyle{ p(154)}\)? To zadanie raczej dla komputera.

[arek1357]

Służę wzorkiem, którego mnie nauczyła Pani w szkole:

\(\displaystyle{ P(n+k,k)= \sum_{i=1}^{k}P(n,i)}\)


No a jak chcesz wzór jawny kliknij tu:

https://www.matematyka.pl/400723.htm

[Majeskas]

Coś chyba nie tak z tym wzorkiem od pani…

[arek1357]

Co Ty mówisz a co jest nie tak??
Masz jakieś PRZESŁANKI ABY SĄDZIĆ INACZEJ???

[Majeskas]

Mam:

\(\displaystyle{ P(n,k)=P(n,1)+P(n,2)+\cdots+P(n,k)}\)

\(\displaystyle{ P(n,1)+P(n,2)+\cdots+P(n,k-1)=0}\)

[arek1357]

Przepraszam odszczekuję już poprawiłem brakło mi po prostu składnika \(\displaystyle{ k}\).

Moje Pani nie mogła się pomylić to ja po prostu się pomyliłem...

[Majeskas]

A ja właśnie nie pamiętałem jednego z tych wzorków na partycje, więc nie widziałem od razu, jak to poprawić.

Cóż za niezachwiana wiara w panią! Swoją drogą niezła ta pani. U mnie (był to co prawda pan, nie pani) podano tylko wzorki na wariacje, kombinacje i permutacje. O partycjach mowy nie było.

A z tym wzorem jawnym to ciekawe, nie wiedziałem o tym.

[arek1357]

No masz rację partycje są pomijane wstydliwie przez osoby , które tych wzorów nie znają i nawet nie chcą poznać, ogólnie stwierdzam, że wykłady z dyskretnej mają spore luki na studiach, raczej dyskretną traktuje się po macoszemu.
Mi samemu brakuje kilku rzeczy w dyskretnej których za Chiny nie mogę znaleźć.

[Majeskas]

Mówimy akurat o szkolnych wykładach z dyskretnej, gdzie na ogół jest mało, bo w przeciętnej szkole w ogóle wszystkiego jest mało. Na studiach miałem bardzo porządne wykłady z dyskretnej (jak zresztą wszystkie) i powyprowadzaliśmy różne wzorki rekurencyjne na partycje. O jawnych nie było mowy (może jeszcze nie było o nich wiadomo? to chyba świeży wynalazek). Swoją drogą, one rzeczywiście dają dokładnie to, co trzeba, bo na Wikipedii są w dziale o aproksymacji?

[arek1357]

A czy miałeś na studiach permutacje z ograniczeniami?

[Majeskas]

Miałem.