365605315

I. K.ompozgej£ i Partycje

Rozważmy problem dotyczący liczby sposobów w jaki liczba może być zapisana jako suma. Jeśli kolejność warunków w sumie jest brana pod uwagę, suma jest nazywana kompozycją a liczba kompozycji n jest oznaczana jako c(n). jeśli kolejność warunków nie jest brana pod uwagę suma jest partycją a liczba partycji n jest oznaczana przez p(n). Zatem, kompozycja z 3 to

3 = 3; 3 = 1+2; 3 = 2+1; i 3 = 1 + 1 + 1;

tak więc c(3) = 4.

Partycja z 3 to

3 = 3; 3 = 2+1; i 3 = 1 + 1 + 1;

tak więc p(3) = 3

Istnieją trzy metody uzyskiwania wyników na kompozycje i partycje. Po pierwsze, przez czysto kombinatoryczne argumenty, po drugie przez argumenty algebraiczne z generowaniem serii i w końcu działania analityczne na wygenerowanej serii. Omówimy pierwsze z dwóch tych metod Najpierw rozważmy kompozycję, ponieważ są łatwiejsze w obsłudze niż partycje. Funkcję c(n) można łatwo określić w następujący sposób. Rozważmy n zapisane jako sumę jedynek. Mamy n-1 przestrzeni między nimi a w każdej przestrzeni możemy wstawić ukośnik,otzrymując 2"'¹ możliwości odpowiadające 2"'¹ kompozycji z n. Na przykład

3=1 1 1; 3 = 1=1 1; 3 = 1 1=1; 3 = 1=1=1

Zilustrujemy to metodą algebraiczną w tym raczej trywialnym przypadku jaki rozpatrujemy

Y1 ^c^^x"

Łatwo zweryfikować ,że

c(n)xⁿ

^ (x + x² + x³ H----)^m

m= 1

oo / \ m    oc

E(A)

Bardziej interesujące jest określenie liczby kompozycji c*(n) w części nieparzystej. Tu mamy podejście algebraiczne