Články

1.1: Skladby a oddiely


Zvažujeme problémy týkajúce sa počtu spôsobov, ako je možné číslo zapísať ako súčet. Ak sa objednávka nezohľadní, je to suma a prepážka a počet oddielov (n ) je označený ako (p (n) ). Teda zloženie 3 je

3 = 3, 3 = 1 + 2, 3 = 2 + 1 a 3 = 1 + 1 + 1,

takže (c (3) = 4 ). Priečky 3 sú

3 = 3, 3 = 2 + 1 a 3 = 1 + 1 + 1,

takže (p (3) = 3 ).

V zásade existujú tri spôsoby získavania výsledkov pre zloženie a priečky. Najprv čisto kombinatorickými argumentmi, potom algebraickými argumentmi s generujúcou sériou a nakoniec analytickými operáciami s generujúcou sériou. Budeme diskutovať iba o prvých dvoch z týchto metód.

Považujeme prvé kompozície, ktoré sa dajú zvládnuť ľahšie ako oddiely. Funkcia (c (n) ) sa dá ľahko určiť nasledovne. Zvážte (n ) napísané ako súčet 1. Medzi nimi máme (n - 1 ) medzery a do každej z nich môžeme vložiť lomku, čím vzniknú (2 ^ {n - 1} ) možnosti zodpovedajúce (2 ^ {n - 1} ) zloženie (n ). Napríklad

3 = 1 1 1, 3 = 1/1 1, 3 = 1 1/1, 3 = 1/1/1.

Len pre ilustráciu algebraickej metódy v tomto dosť triviálnom prípade uvažujeme

( sum _ { infty} ^ {n = 1} c (n) x ^ n ).

Je to ľahko overiteľné

( begin {array} {rcl} { sum_ {n = 1} ^ { infty} c (n) x ^ n} & = & { sum_ {m = 1} ^ { infty} (x + x ^ 2 + x ^ 3 + cdot cdot cdot) ^ m} {} & = & { sum_ {m = 1} ^ { infty} ( dfrac {x} {1 - x}) ^ m = dfrac {x} {1 - 2x} = sum_ {n = 1} ^ { infty} x ^ {n - 1} x ^ n.} end {pole} )

Príklad ( PageIndex {1} )

Ako cvičenie by som navrhol použiť kombinatorickú metódu aj algebraický prístup na preukázanie nasledujúcich výsledkov:

  1. Počet skladieb (n ) na presne (m ) časti je ({n - 1 vyberte m -1} ) (katalánčina);
  2. Počet skladieb (n ) do párnych častí je (2 ^ { dfrac {n} {2} - 1} ), ak (n ) je párne, a 0, ak (n ) je nepárny ;
  3. Počet skladieb (n ) na párny počet častí sa rovná počtu skladieb (n ) na nepárny počet častí.

Riešenie

Sem zadajte text.

O niečo zaujímavejšie je určenie počtu skladieb (c ^ {*} (n) ) (n ) do nepárnych častí. Tu sa získa algebraický prístup

( begin {array} {rcl} { sum_ {n = 1} c ^ {*} (n) x ^ n} & = & { sum_ {m = 1} ^ { infty} (x + x ^ 3 + x ^ 5 + cdot cdot cdot) ^ m} {} & = & { sum_ {m = 1} ^ { infty} ( dfrac {x} {1 - x ^ 2} ) ^ m = dfrac {x} {1 - x - x ^ 2} = suma F (n) x ^ n.} end {pole} )

Znásobením posledných dvoch výrazov to vidíme

(F_ {n + 2} = F_ {n} + F_ {n + 1} ), (F_0 = 0, F_1 ​​= 1 )

F sú teda takzvané Fibonacciho čísla

1, 1, 2, 3, 5, 8, 13, ....

Funkcia generovania poskytuje pre tieto čísla dva explicitné výrazy. Najskôr „čiastočným rozdelením“ ( dfrac {x} {1 - x - x ^ 2} ), rozšírením každého člena ako mocninovej rady a porovnaním koeficientov, získame

(F_n = dfrac {1} { sqrt {5}} {( dfrac {1 + sqrt {5}} {2}) ^ n - ( dfrac {1 - sqrt {5}} {2 }) ^ n}. )

Ďalší výraz pre (F_n ) sa získa pozorovaním tohto

( dfrac {x} {1 - x - x ^ 2} = x (1 + (x + x ^ 2) ^ 1 + (x + x ^ 2) ^ 2 + (x + x ^ 2) ^ 3 + cdot cdot cdot). )

Porovnaním tu získaných koeficientov (Lucas)

(F_n = {n - 1 zvoliť 0} + {n - 2 zvoliť 1} + {n - 3 zvoliť 2} + cdot cdot cdot). )

Mohli by ste zvážiť problém dedukovania tohto vzorca kombinatorickými argumentmi.

Predpokladajme, že označíme (a (n) ) počet skladieb n so všetkými sčítancami najviac 2 a b (n) počet skladieb (n ) so všetkými sčítancami najmenej 2. Zaujímavé výsledkom je (a (n) = b (n + 2) ). Tento výsledok dokážem a navrhnem problém nájsť primerané zovšeobecnenie.

Najprv si všimnite, že (a (n) = a (n - 1) + a (n - 2) ). To vyplýva zo skutočnosti, že každá prípustná skladba končí číslom 1 alebo 2. Vymazaním tohto posledného súčtu získame prípustnú skladbu (n - 1 ), respektíve (n - 2 ). Pretože (a (1) = 1 ) a (a (2) = 2 ), vyplýva z toho (a (n) = F_n ). Funkcia (b (n) ) spĺňa rovnaký vzorec rekurzie. V skutočnosti, ak je posledný súčet v prípustnom zložení (n ) 2, vymažte ho, aby ste získali prípustné zloženie (n - 2 ); ak je posledný súčet väčší ako 2, znížte ho o 1, aby ste dosiahli prípustné zloženie (n - 1 ). Pretože (b (2) = b (3) = 1 ), vyplýva z toho, že (b (n) = F_ {n − 2} ) takže (a (n) = F_n = b (n + 2) ).

Zaujímavým nápadom pre kompozície je predstava hmotnosti kompozície. Predpokladajme, že s každou kompozíciou spojíme číslo, ktoré sa nazýva váha a ktoré je produktom súčtov. Určíme súčet (w (n) ) váh zložení (n ). Generujúca funkcia (w (n) ) je

( sum_ {n = 1} ^ { infty} w (n) x ^ n = sum_ {m = 1} ^ { infty} (x + 2x ^ 2 + 3x ^ 3 + cdot cdot cdot) ^ m = dfrac {x} {1 - 3x + x ^ 2}. )

Z toho zistíme, že (w (n) = 3w (n - 1) - w (n - 2) ). Ponechávam to ako cvičenie, aby som z toho dokázal, že (w (n) = F_ {2n − 1} ).

Teraz sa obrátime na oddiely. Pre (p (n) ) neexistuje žiadny jednoduchý explicitný vzorec. Našim hlavným cieľom bude dokázať vzorec rekurzie

(p (n) = p (n - 1) + p (n - 2) - p (n - 5) - p (n - 7) + p (n - 12) + p (n - 15) + cdot cdot cdot )

objavil Euler. Algebraický prístup k teórii oddielov závisí od algebraických manipulácií s generujúcou funkciou

( sum_ {n = 0} ^ { infty} p (n) x ^ n = dfrac {1} {(1 - x) (1 - x ^ 2) (1 - x ^ 3) cdot cdot cdot} )

a súvisiace funkcie pre zakázané oddiely. Kombinatorický prístup závisí od použitia rozdelovacích (Ferrerových) diagramov. Napríklad Ferrerov diagram oddielu 7 = 4 + 2 + 1 je

Užitočná je tu predstava konjugovaného rozdelenia. To sa dosiahne zrkadlením diagramu v línii (45 ^ { circ} ), ktorá vedie nadol z ľavého horného rohu. Napríklad,

priečky

a

sú navzájom konjugované. Táto korešpondencia poskytuje takmer okamžite nasledujúce vety:

Počet oddielov (n ) na (m ) častí sa rovná počtu oddielov (n ) na časti, z ktorých najväčší je (m );
Počet oddielov (n ) na nie viac ako (m ) častí sa rovná počtu oddielov (n ) na časti nepresahujúcich (m ).

Trochu odlišná povaha je nasledovná: Počet oddielov (n ) na nepárne časti sa rovná počtu oddielov (n ) na odlišné časti. Za týmto účelom poskytujeme algebraický dôkaz. Výsledkom použitia pomerne zrejmých generujúcich funkcií pre požadované oddiely je výsledok

( dfrac {1} {(1 - x) (1 - x ^ 3) (1 - x ^ 5) (1 - x ^ 7) cdot cdot cdot} = (1 + x) (1 + x ^ 2) (1 + x ^ 3) (1 + x ^ 4) cdot cdot cdot. )

Krížové znásobenie robí výsledok intuitívnym.
Teraz pokračujeme k dôležitejšej vete vďaka Eulerovi:

((1 - x) (1 - x ^ 2) (1 - x ^ 3) cdot cdot cdot = 1 - x ^ 1 - x ^ 2 + x ^ 5 + x ^ 7 - x ^ {12 } - x ^ {15} + cdot cdot cdot, )

kde exponentmi sú čísla v tvare ( dfrac {1} {2} k (3k pm 1) ). Najprv si to všimneme

((1 - x) (1 - x ^ 2) (1 - x ^ 3) cdot cdot cdot = sum ((E (n) - O (n)) x ^ n, )

kde (E (n) ) je počet oddielov (n ) na párny počet samostatných častí a (O (n) ) počet oddielov (n ) na nepárne číslo samostatných častí.

Pokúšame sa nadviazať vzájomnú korešpondenciu medzi oddielmi týchto dvoch druhov. Takáto korešpondencia nemôže byť samozrejme presná, pretože presná korešpondencia by dokázala, že (E (n) = O (n) ).

Vezmeme graf predstavujúci oddiel (n ) do ľubovoľného počtu nerovnakých častí. Najnižšiu čiaru (AB ) nazývame základňou grafu. Z (C ), krajného severovýchodného uzla, nakreslíme v grafe najdlhšiu možnú juhozápadnú čiaru; toto môže obsahovať iba jeden uzol. Tento riadok (CDE ) sa nazýva krídlo grafu

Spravidla môžeme základňu posunúť do polohy nového krídla (rovnobežne a napravo od „starého“ krídla). Niekedy môžeme vykonať reverznú operáciu (pohyb krídla tak, aby bol nad základňou, pod starou základňou). Keď je opísaná operácia alebo jej obrátenie možné, vedie to z priečky na nepárny počet častí na párny počet častí alebo naopak. Všeobecne teda (E (n) = O (n) ). Dva prípady si však vyžadujú osobitnú pozornosť. Typické sú pre diagramy

a

V týchto prípadoch má (n ) tvar

(k + (k + 1) + cdot cdot cdot + (2k - 1) = dfrac {1} {2} (3k ^ 2 - k) )

a

((k + 1) + (k + 2) + cdot cdot cdot + (2k) = (3k ^ 2 + k) ).

V obidvoch týchto prípadoch existuje prebytok jedného oddielu na párny počet častí alebo jedného na nepárne číslo podľa toho, ako (k ) je párny alebo nepárny počet. Preto (E (n) - O (n) = 0 ), pokiaľ (n = dfrac {1} {2} (3k pm k) ), keď (E (n) - O (n ) = (-1) ^ k ). To dáva Eulerovu vetu.

Teraz od

( sum p (n) x ^ n (1 - x - x ^ 2 + x ^ 5 + x ^ 7 - x ^ {12} - cdot cdot cdot) = 1 )

získame vzťah rekurencie pre (p (n) ), a to

(p (n) = p (n - 1) + p (n - 2) - p (n - 5) - p (n - 7) + p (n - 12) + cdot cdot cdot. )


Pozri si video: ПОДРОБНЫЙ ОБЗОР Minecraft PE (November 2021).