Kalkulator Funkcji Podziału

Witamy w Kalkulatorze Funkcji Podziału, wszechstronnym narzędziu do eksploracji jednego z najbardziej fascynujących obiektów kombinatoryki. Wprowadź dowolną nieujemną liczbę całkowitą \(n\), a narzędzie obliczy \(p(n)\) — liczbę sposobów zapisu \(n\) jako sumy dodatnich liczb całkowitych, gdzie kolejność nie ma znaczenia — wraz z liczbą podziałów na różne części \(q(n)\), liczbą podziałów na części nieparzyste \(o(n)\), przybliżeniem asymptotycznym Hardy'ego-Ramanujana, każdą dopasowaną kongruencją Ramanujana oraz (dla małych \(n\)) każdym pojedynczym podziałem wyrenderowanym jako animowany diagram Younga.

Co to jest funkcja podziału p(n)?

Funkcja podziału \(p(n)\) zlicza liczbę sposobów zapisu \(n\) jako sumy dodatnich liczb całkowitych, bez względu na kolejność. Dwie sumy, które różnią się tylko kolejnością składników, są uważane za ten sam podział. Na przykład podziały liczby 4 to:

• 4
• 3 + 1
• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

Co daje \(p(4) = 5\). Zgodnie z konwencją \(p(0) = 1\), co odpowiada „pustemu podziałowi”. Kilka innych wartości: \(p(1) = 1,\ p(5) = 7,\ p(10) = 42,\ p(50) = 204{,}226,\ p(100) = 190{,}569{,}292.\)

Funkcja tworząca

Leonhard Euler odkrył, że funkcja tworząca dla \(p(n)\) ma piękną, zwartą postać iloczynową:

Każdy czynnik \(1/(1 - x^k) = 1 + x^k + x^{2k} + \ldots\) wnosi wybór, ile razy część \(k\) pojawia się w podziale. Pomnożenie tych czynników generuje każdy podział dokładnie raz.

Diagramy Younga (Ferrersa)

Diagram Younga (zwany również diagramem Ferrersa) reprezentuje podział wizualnie jako wyrównaną do lewej tablicę pudełek. Każdy rząd odpowiada jednej części, a rzędy są wymienione od największego do najmniejszego. Na przykład podział \(4 + 2 + 1\) liczby 7 wygląda następująco:

Diagramy Younga pozwalają „zobaczyć” tożsamości podziałów. Odbicie diagramu względem głównej przekątnej zamienia rzędy na kolumny, co odpowiada podziałowi sprzężonemu. Ten kalkulator renderuje diagram Younga dla każdego podziału \(n\), gdy tylko \(n \le 15\).

Twierdzenie Eulera o podziałach

Jeden z najelegantszych wyników Eulera stwierdza:

Na przykład podziały liczby 7 na różne części to \(\{7\}, \{6+1\}, \{5+2\}, \{4+3\}, \{4+2+1\}\) — jest ich pięć. Podziały liczby 7 na części nieparzyste to \(\{7\}, \{5+1+1\}, \{3+3+1\}, \{3+1+1+1+1\}, \{1+1+1+1+1+1+1\}\) — również pięć. Panel podsumowania kalkulatora podaje zarówno \(q(n)\), jak i \(o(n)\), dzięki czemu możesz zweryfikować tę tożsamość dla wybranego \(n\).

Asymptotyka Hardy'ego-Ramanujana

W 1918 roku G.H. Hardy i Srinivasa Ramanujan udowodnili pierwszy wzór, który uchwycił prawdziwe tempo wzrostu \(p(n)\) dla dużych \(n\):

Wynik ten wyłonił się z metody kołowej Hardy'ego-Ramanujana, która integruje funkcję tworzącą wokół osobliwości na okręgu jednostkowym. Hans Rademacher udoskonalił go w 1937 roku do postaci dokładnego szeregu zbieżnego — jednego z najsłynniejszych wzorów w analitycznej teorii liczb.

Kongruencje podziałowe Ramanujana

Podczas studiowania tabeli wartości podziałów, Ramanujan zauważył trzy zadziwiające wzorce podzielności:

Na przykład \(p(4)=5,\ p(9)=30,\ p(14)=135,\ p(19)=490,\ p(24)=1575\) są wszystkie podzielne przez 5. Kalkulator automatycznie zaznacza, gdy wybrane przez Ciebie \(n\) należy do jednej z tych klas.

Jak korzystać z tego kalkulatora

1. Wprowadź nieujemną liczbę całkowitą do 500 w polu wejściowym lub kliknij jeden ze znanych szybkich przykładów (0, 4, 10, 42, 100, 200).
2. Kliknij "Oblicz podziały". Narzędzie obliczy \(p(n)\), \(q(n)\), \(o(n)\) oraz oszacowanie Hardy'ego-Ramanujana.
3. Przejrzyj panel główny pokazujący \(p(n)\) jako dużą liczbę w nagłówku, a następnie sprawdź siatkę podsumowania dla podziałów na różne części, części nieparzyste, oszacowanie asymptotyczne i błąd procentowy.
4. Zbadaj diagramy Younga — jeśli \(n \le 15\), każdy pojedynczy podział jest narysowany jako animowany diagram Younga w responsywnej siatce.
5. Eksploruj wykres wzrostu — przedstawia \(p(k)\), \(q(k)\) oraz krzywą Hardy'ego-Ramanujana dla \(k = 0, 1, \ldots, n\). Przełączaj między skalą liniową a logarytmiczną, aby zobaczyć kształt asymptotyczny.
6. Zapoznaj się z tabelą wzrostu — widok wiersz po wierszu \(p(k), q(k), o(k)\) dla małych \(k\). Użyj go, aby dostrzec pierwsze wystąpienia każdej kongruencji Ramanujana.

Przykład: Podziały liczby 5

Prześledźmy przypadek \(n = 5\). Wszystkie podziały to:

• \(5\)
• \(4 + 1\)
• \(3 + 2\)
• \(3 + 1 + 1\)
• \(2 + 2 + 1\)
• \(2 + 1 + 1 + 1\)
• \(1 + 1 + 1 + 1 + 1\)

Zatem \(p(5) = 7\). Podziały na różne części: \(\{5\}, \{4+1\}, \{3+2\}\) — są trzy, więc \(q(5) = 3\). Podziały na części nieparzyste: \(\{5\}, \{3+1+1\}, \{1+1+1+1+1\}\) — również trzy, więc \(o(5) = 3\). Twierdzenie Eulera zachodzi. Na koniec, \(n = 5 \equiv 0 \pmod 5\) nie jest postaci \(5k+4\), więc kongruencja dla 5 nie ma zastosowania; jednakże \(p(4) = 5\) spełnia \(p(5k+4) \equiv 0 \pmod 5\).

Klasyczne wartości p(n)

Historia

• Lata 1750.: Leonhard Euler bada podziały i odkrywa tożsamość funkcji tworzącej oraz twierdzenie „różne = nieparzyste”.
• 1915: Major Percy MacMahon publikuje tabelę \(p(n)\) dla \(n\) do 200 — obliczoną ręcznie.
• 1918: Hardy i Ramanujan udowadniają wzór asymptotyczny przy użyciu metody kołowej.
• 1919: Ramanujan publikuje słynne kongruencje \(p(5k+4),\ p(7k+5),\ p(11k+6)\).
• 1937: Hans Rademacher udoskonala wzór Hardy'ego-Ramanujana do postaci dokładnego szeregu zbieżnego.
• 2011: Ken Ono i Jan Bruinier udowadniają, że \(p(n)\) można wyrazić jako skończoną sumę algebraiczną dla każdej dodatniej liczby całkowitej.

Zastosowania

• Kombinatoryka i teoria reprezentacji — podziały indeksują nieredukowalne reprezentacje grupy symetrycznej \(S_n\).
• Mechanika statystyczna — liczby podziałów pojawiają się w entropii idealnych gazów kwantowych oraz w funkcjach podziału w teorii strun.
• Formy modularne — funkcja tworząca dla \(p(n)\) jest ściśle powiązana z funkcją eta Dedekinda.
• Informatyka — testy porównawcze wyliczania sumy podzbioru i programowania całkowitoliczbowego często wykorzystują liczby podziałów.

Często zadawane pytania

Co to jest funkcja podziału p(n)?

\(p(n)\) zlicza liczbę sposobów wyrażenia \(n\) jako sumy dodatnich liczb całkowitych, gdzie kolejność nie ma znaczenia. \(p(4) = 5\), ponieważ 4 można zapisać jako \(4\), \(3+1\), \(2+2\), \(2+1+1\) lub \(1+1+1+1\). Przyjmuje się, że \(p(0) = 1\).

Co to jest diagram Younga lub Ferrersa?

Diagram Younga to wizualna reprezentacja podziału: każda część staje się rzędem pudełek wyrównanych do lewej, przy czym części są wymienione od największej do najmniejszej od góry do dołu. Dla \(4+2+1\) rysuje się rząd 4, rząd 2 i rząd 1. Ten kalkulator renderuje diagram Younga dla każdego podziału, gdy \(n \le 15\).

Co mówi twierdzenie Eulera o podziałach?

Dla każdej dodatniej liczby całkowitej \(n\) liczba podziałów \(n\) na różne części jest równa liczbie podziałów \(n\) na części nieparzyste. Dla \(n = 5\): części różne dają \(\{5\}, \{4+1\}, \{3+2\}\); części nieparzyste dają \(\{5\}, \{3+1+1\}, \{1+1+1+1+1\}\). Obie liczby są równe 3.

Jaki jest wzór asymptotyczny Hardy'ego-Ramanujana?

Stwierdza on, że \(p(n) \sim \frac{1}{4n\sqrt{3}} \exp\!\left(\pi \sqrt{2n/3}\right)\), gdy \(n \to \infty\). Był to pierwszy wzór opisujący dokładne tempo wzrostu \(p(n)\), odkryty w 1918 roku przez G.H. Hardy'ego i Srinivasę Ramanujana.

Czym są kongruencje Ramanujana dla podziałów?

To trzy niezwykłe wzorce podzielności: \(p(5k+4) \equiv 0 \pmod 5\), \(p(7k+5) \equiv 0 \pmod 7\) oraz \(p(11k+6) \equiv 0 \pmod{11}\). Na przykład \(p(4)=5, p(9)=30, p(14)=135\) są wszystkie podzielne przez 5.

Jak szybko rośnie p(n)?

p(n) rośnie subwykładniczo, ale szybciej niż jakikolwiek wielomian, mniej więcej jak \(\exp(\pi \sqrt{2n/3})\). Dla porównania: \(p(10)=42\), \(p(50)=204{,}226\), \(p(100)=190{,}569{,}292\), a \(p(200) \approx 4 \times 10^{12}\). Użyj przełącznika skali logarytmicznej na wykresie, aby zwizualizować tę krzywą wzrostu.

Dodatkowe zasoby

• Funkcja podziału - Wikipedia
• Kongruencje Ramanujana - Wikipedia