Oddíl (teorie čísel) - Partition (number theory)

Mladé diagramy přidružené k oddílům kladných celých čísel 1 až 8. Jsou uspořádány tak, že obrazy pod odrazem kolem hlavní úhlopříčky čtverce jsou sdružené oddíly.

Příčky n s největším přídavkem k

v teorie čísel a kombinatorika, a rozdělit pozitivního celé číslo n, nazývané také celočíselný oddíl, je způsob psaní n jako součet kladných celých čísel. Dvě částky, které se liší pouze v pořadí jejich summands jsou považovány za stejný oddíl. (Pokud záleží na objednávce, částka se změní na složení.) Například 4 lze rozdělit pěti různými způsoby:

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

Závisí na objednávce složení 1 + 3 je stejný oddíl jako 3 + 1, zatímco dvě odlišné skladby 1 + 2 + 1 a 1 + 1 + 2 představují stejný oddíl 2 + 1 + 1.

Summand v oddílu se také nazývá a část. Počet oddílů n je dána funkcí oddílu p(n). Tak p(4) = 5. Zápis λ ⊢ n znamená, že λ je oddíl n.

Oddíly lze graficky vizualizovat pomocí Mladé diagramy nebo Ferrersovy diagramy. Vyskytují se v řadě větví matematika a fyzika, včetně studia symetrické polynomy a symetrická skupina a v teorie reprezentace skupin obecně.

Příklady

Sedm oddílů po 5 je:

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

V některých zdrojích jsou oddíly považovány spíše za posloupnost sčítanců než za výraz se znaménky plus. Například oddíl 2 + 2 + 1 může být místo toho zapsán jako n-tice (2, 2, 1) nebo v ještě kompaktnější podobě (2², 1) kde horní index označuje počet opakování výrazu.

Reprezentace oddílů

Existují dvě běžné diagramové metody, které představují oddíly: jako Ferrersovy diagramy, pojmenované po Norman Macleod Ferrers, a jako Young diagramy, pojmenované po britském matematikovi Alfred Young. Oba mají několik možných konvencí; zde používáme Anglická notace, se schématy zarovnanými v levém horním rohu.

Ferrersův diagram

Oddíl 6 + 4 + 3 + 1 kladného čísla 14 lze znázornit následujícím diagramem:

14 kruhů je seřazeno do 4 řad, přičemž každá má velikost části oddílu. Schémata 5 oddílů čísla 4 jsou uvedena níže:

4	=	3 + 1	=	2 + 2	=	2 + 1 + 1	=	1 + 1 + 1 + 1

Mladý diagram

Alternativní vizuální reprezentace celočíselného oddílu je jeho Mladý diagram (často také nazývaný Ferrersův diagram). Spíše než představovat oddíl s tečkami, jako v Ferrersově diagramu, Youngův diagram používá políčka nebo čtverce. Youngův diagram pro oddíl 5 + 4 + 1 tedy je

zatímco Ferrersův diagram pro stejný oddíl je

I když se tato zdánlivě triviální variace nejeví hodná samostatné zmínky, Young diagramy se ukázaly být velmi užitečné při studiu symetrické funkce a teorie reprezentace skupin: vyplnění polí Youngových diagramů čísly (nebo někdy komplikovanějšími objekty), které se řídí různými pravidly, vede k rodině objektů zvaných Mladé obrazy a tato tablo má kombinatorický a reprezentačně-teoretický význam.^[1] Jako typ tvaru vytvořeného sousedními čtverci spojenými dohromady jsou Youngovy diagramy zvláštním druhem polyomino.^[2]

Funkce oddílu

The funkce oddílu ${ displaystyle p (n)}$ představuje číslo možné oddíly nezáporného celého čísla ${ displaystyle n}$. Například, ${ displaystyle p (4) = 5}$ protože celé číslo ${ displaystyle 4}$ má pět oddílů ${ displaystyle 1 + 1 + 1 + 1}$, ${ displaystyle 1 + 1 + 2}$, ${ displaystyle 1 + 3}$, ${ displaystyle 2 + 2}$, a ${ displaystyle 4}$Hodnoty této funkce pro ${ displaystyle n = 0,1,2, tečky}$ jsou:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... (sekvence A000041 v OEIS ).

Ne uzavřený výraz pro funkci oddílu je známa, ale má obojí asymptotické expanze které to přesně přibližují a relace opakování podle kterého jej lze přesně vypočítat. Roste jako exponenciální funkce z odmocnina jeho argumentu.^[3] The multiplikativní inverzní jeho generující funkce je Eulerova funkce; od Eulera věta o pětiúhelníku tato funkce je střídavým součtem pětiúhelníkové číslo pravomoci jeho argumentu.

Srinivasa Ramanujan nejprve objevil, že funkce oddílu má netriviální vzory v modulární aritmetika, nyní známý jako Ramanujanovy shody. Například kdykoli desítkové vyjádření ${ displaystyle n}$ končí číslicí 4 nebo 9, počtem oddílů ${ displaystyle n}$ bude dělitelná 5.^[4]

Omezené oddíly

V kombinatorice i v teorii čísel se často studují rodiny oddílů podléhajících různým omezením.^[5] Tato část zkoumá několik takových omezení.

Konjugujte a samokonjugujte oddíly

Pokud překlopíme schéma oddílu 6 + 4 + 3 + 1 podél jeho hlavní úhlopříčky, získáme další oddíl 14:

	↔
6 + 4 + 3 + 1	=	4 + 3 + 3 + 2 + 1 + 1

Otočením řádků do sloupců získáme oddíl 4 + 3 + 3 + 2 + 1 + 1 z čísla 14. O těchto oddílech se říká, že jsou sdružené jeden druhého.^[6] V případě čísla 4 jsou oddíly 4 a 1 + 1 + 1 + 1 konjugované páry a oddíly 3 + 1 a 2 + 1 + 1 jsou navzájem konjugované. Zvláště zajímavý je oddíl 2 + 2, který má sám sebe jako konjugát. O takovém oddílu se říká, že je vlastní konjugát.^[7]

Nárok: Počet samostatně konjugovaných oddílů je stejný jako počet oddílů se zřetelnými lichými částmi.

Důkaz (obrys): Zásadní pozorování je, že každá zvláštní část může být “složený"ve středu pro vytvoření samo-konjugovaného diagramu:

↔

Poté lze získat bijekci mezi sadou oddílů se zřetelnými lichými částmi a sadou samo-konjugovaných oddílů, jak ukazuje následující příklad:

	↔
9 + 7 + 3	=	5 + 5 + 4 + 3 + 2
Dist. zvláštní		vlastní konjugát

Zvláštní části a odlišné části

Mezi 22 oddíly čísla 8 je 6, které obsahují pouze liché části:

• 7 + 1
• 5 + 3
• 5 + 1 + 1 + 1
• 3 + 3 + 1 + 1
• 3 + 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Alternativně bychom mohli počítat oddíly, ve kterých se žádné číslo nevyskytuje více než jednou. Takový oddíl se nazývá a oddíl s odlišnými částmi. Pokud spočítáme oddíly 8 s odlišnými částmi, získáme také 6:

• 8
• 7 + 1
• 6 + 2
• 5 + 3
• 5 + 2 + 1
• 4 + 3 + 1

Toto je obecná vlastnost. Pro každé kladné číslo se počet oddílů s lichými částmi rovná počtu oddílů s odlišnými částmi označených q(n).^[8][9] Tento výsledek prokázal Leonhard Euler v roce 1748^[10] a později byl zobecněn jako Glaisherova věta.

Pro každý typ omezeného oddílu existuje odpovídající funkce pro počet oddílů splňujících dané omezení. Důležitým příkladem je q(n). Prvních několik hodnot q(n) jsou (počínaje q(0)=1):

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... (sekvence A000009 v OEIS ).

The generující funkce pro q(n) (oddíly do samostatných částí) je dáno^[11]

${ displaystyle sum _ {n = 0} ^ { infty} q (n) x ^ {n} = prod _ {k = 1} ^ { infty} (1 + x ^ {k}) = prod _ {k = 1} ^ { infty} { frac {1} {1-x ^ {2k-1}}}.}$

The věta o pětiúhelníku dává opakování pro q:^[12]

q(k) = A_k + q(k − 1) + q(k − 2) − q(k − 5) − q(k − 7) + q(k − 12) + q(k − 15) − q(k − 22) − ...

kde A_k je (-1)^m -li k = 3m² − m pro celé číslo m a jinak je 0.

Omezená velikost dílu nebo počet dílů

Tím, že vezme konjugáty, číslo p_k(n) oddílů n přesně k parts is equal to the number of partitions of n ve kterém má největší část velikost k. Funkce p_k(n) uspokojuje opakování

p_k(n) = p_k(n − k) + p_k−1(n − 1)

s počátečními hodnotami p₀(0) = 1 a p_k(n) = 0 -li n ≤ 0 nebo k ≤ 0 a n a k nejsou oba nula.^[13]

Jeden obnoví funkci p(n) od

${ displaystyle p (n) = součet _ {k = 0} ^ {n} p_ {k} (n).}$

Jednou z možných generovacích funkcí pro tyto oddíly, přičemž k pevné a n proměnná, je

${ displaystyle sum _ {n geq 0} p_ {k} (n) x ^ {n} = x ^ {k} cdot prod _ {i = 1} ^ {k} { frac {1} {1-x ^ {i}}}.}$

Obecněji, pokud T je sada kladných celých čísel, pak počet oddílů n, jehož všechny části patří T, má generující funkce

${ displaystyle prod _ {t v T} (1-x ^ {t}) ^ {- 1}.}$

To lze použít k řešení problémy se změnami (kde set T určuje dostupné mince). Jako dva konkrétní případy, jeden má počet oddílů n ve kterém jsou všechny části 1 nebo 2 (nebo ekvivalentně počet oddílů n na 1 nebo 2 části) je

${ displaystyle left lfloor { frac {n} {2}} + 1 right rfloor,}$

a počet oddílů n ve kterém jsou všechny části 1, 2 nebo 3 (nebo ekvivalentně počet oddílů n na nejvýše tři části) je nejbližší celé číslo k (n + 3)² / 12.^[14]

Asymptotika

The rychlost asymptotického růstu pro p(n) darováno

${ displaystyle log p (n) sim C { sqrt {n}} { text {as}} n rightarrow infty}$

kde ${ displaystyle C = pi { sqrt { frac {2} {3}}}.}$^[15]. Přesnější asymptotický vzorec

${ displaystyle p (n) sim { frac {1} {4n { sqrt {3}}}} exp left ({ pi { sqrt { frac {2n} {3}}}} že jo)}$ tak jako ${ displaystyle n rightarrow infty}$

byl poprvé získán G. H. Hardy a Ramanujan v roce 1918 a samostatně J. V. Uspensky v roce 1920. Úplná asymptotická expanze byla dána v roce 1937 Hans Rademacher.

Li A je množina přirozených čísel, necháme p_A(n) označte počet oddílů n do prvků A. Li A má pozitivní přirozená hustota α pak

${ displaystyle log p_ {A} (n) sim C { sqrt { alpha n}}}$

a naopak, pokud tato asymptotická vlastnost platí pro p_A(n) pak A má přirozenou hustotu α.^[16] Tento výsledek byl uveden, s náčrtek důkazu, Erdős v roce 1942.^[17][18]

Li A je konečná množina, tato analýza neplatí (hustota konečné množiny je nula). Li A má k prvky, jejichž největší společný dělitel je tedy 1^[19]

${ displaystyle p_ {A} (n) = left ( prod _ {a in A} a ^ {- 1} right) cdot { frac {n ^ {k-1}} {(k- 1)!}} + O (n ^ {k-2}).}$

Přepážky v obdélníku a Gaussovy binomické koeficienty

Lze také současně omezit počet a velikost dílů. Nechat p(N, M; n) označuje počet oddílů n maximálně M části, každá nejvýše o velikosti N. Ekvivalentně se jedná o oddíly, jejichž Youngův diagram zapadá dovnitř M × N obdélník. Existuje relace opakování

${ Displaystyle p (N, M; n) = p (N, M-1; n) + p (N-1, M; n-M)}$

získané pozorováním toho ${ displaystyle p (N, M; n) -p (N, M-1; n)}$ počítá oddíly n přesně M části velikosti nanejvýš Na odečtením 1 od každé části takového oddílu se získá oddíl n − M maximálně M části.^[20]

The Gaussovský binomický koeficient je definován jako:

${ displaystyle {k + ell choose ell} _ {q} = {k + ell choose k} _ {q} = { frac { prod _ {j = 1} ^ {k + ell} (1 -q ^ ​​{j})} { prod _ {j = 1} ^ {k} (1-q ^ {j}) prod _ {j = 1} ^ { ell} (1-q ^ {j })}}.}$

Gaussovský binomický koeficient souvisí s generující funkce z p(N, M; n) rovností

${ displaystyle sum _ {n = 0} ^ {MN} p (N, M; n) q ^ {n} = {M + N zvolte M} _ {q}.}$

Rank a Durfee square

The hodnost oddílu je největší číslo k tak, aby oddíl obsahoval alespoň k části o velikosti alespoň k. Například oddíl 4 + 3 + 3 + 2 + 1 + 1 má hodnocení 3, protože obsahuje 3 části, které jsou ≥ 3, ale neobsahuje 4 části, které jsou ≥ 4. V Ferrersově diagramu nebo Youngově diagramu oddílu hodnosti r, r × r čtverec položek v levém horním rohu je znám jako Náměstí Durfee:

Čtverec Durfee má aplikace v kombinatorice v důkazech různých identit oddílů.^[21] Má také určitý praktický význam v podobě h-index.

Jiná statistika se také někdy nazývá hodnost oddílu (nebo Dysonova hodnost), a to rozdíl ${ displaystyle lambda _ {k} -k}$ pro oddíl o k díly s největší částí ${ displaystyle lambda _ {k}}$. Tato statistika (která nesouvisí s výše popsanou) se objevuje ve studii Ramanujan kongruence.

Youngova mříž

Existuje přírodní částečná objednávka na oddílech daných zahrnutím Youngových diagramů. Tato částečně objednaná sada je známá jako Youngova mříž. Mřížka byla původně definována v kontextu teorie reprezentace, kde se používá k popisu neredukovatelné reprezentace z symetrické skupiny S_n pro všechny n, spolu s jejich rozvětvovacími vlastnostmi, v charakteristické nule. Rovněž obdržela významnou studii pro své čistě kombinatorické vlastnosti; je to zejména motivující příklad a diferenciální poset.

Viz také

Poznámky

Reference

• Abramowitz, Milton; Stegun, Irene (1964). Příručka matematických funkcí se vzorci, grafy a matematickými tabulkami. United States Department of Commerce, National Bureau of Standards. ISBN  0-486-61272-4.CS1 maint: ref = harv (odkaz)
• Andrews, George E. (1976). Teorie oddílů. Cambridge University Press. ISBN  0-521-63766-X.CS1 maint: ref = harv (odkaz)
• Andrews, George E .; Eriksson, Kimmo (2004). Celé oddíly. Cambridge University Press. ISBN  0-521-60090-1.
• Apostol, Tom M. (1990) [1976]. Modulární funkce a Dirichletovy řady v teorii čísel. Postgraduální texty z matematiky. 41 (2. vyd.). New York atd .: Springer-Verlag. ISBN  0-387-97127-0. Zbl  0697.10023. (Moderní pedagogický úvod k Rademacherově formuli viz kapitola 5).
• Bóna, Miklósi (2002). Procházka kombinatorikou: Úvod do výčtu a teorie grafů. World Scientific Publishing. ISBN  981-02-4900-4. (základní úvod do tématu celočíselných oddílů, včetně diskuse o grafech Ferrers)
• Hardy, G. H.; Wright, E. M. (2008) [1938]. Úvod do teorie čísel. Revidováno D. R. Heath-Brown a J. H. Silverman. Předmluva Andrew Wiles. (6. vydání). Oxford: Oxford University Press. ISBN  978-0-19-921986-5. PAN  2445243. Zbl  1159.11001.
• Lehmer, D. H. (1939). "O zbytku a konvergenci řady pro funkci oddílu". Trans. Amer. Matematika. Soc. 46: 362–373. doi:10.1090 / S0002-9947-1939-0000410-9. PAN  0000410. Zbl  0022.20401. Poskytuje hlavní vzorec (bez derivátů), zbytek a starší formu pro A_k(n).)
• Gupta, Hansraj; Gwyther, C.E .; Miller, J.C.P. (1962). Royal Society of Math. Tabulky. Svazek 4, Tabulky oddílů. (Má text, téměř úplnou bibliografii, ale oni (a Abramowitz) minul Selbergův vzorec pro A_k(n), který je ve Whitemanu.)
• Macdonald, Ian G. (1979). Symetrické funkce a Hallovy polynomy. Oxfordské matematické monografie. Oxford University Press. ISBN  0-19-853530-9. Zbl  0487.20007. (Viz část I.1)
• Nathanson, M.B. (2000). Základní metody v teorii čísel. Postgraduální texty z matematiky. 195. Springer-Verlag. ISBN  0-387-98912-9. Zbl  0953.11002.CS1 maint: ref = harv (odkaz)
• Rademacher, Hans (1974). Shromážděné dokumenty Hanse Rademachera. v II. MIT Stiskněte. 100–07, 108–22, 460–75.
• Sautoy, Marcus Du. (2003). Hudba prvočísel. New York: Trvalky-HarperCollins.
• Stanley, Richard P. (1999). Enumerativní kombinatorika. Svazky 1 a 2. Cambridge University Press. ISBN  0-521-56069-1.CS1 maint: ref = harv (odkaz)
• Whiteman, A. L. (1956). Součet spojený s řadou pro funkci oddílu. Pacific Journal of Mathematics. 6. str. 159–176. Zbl  0071.04004. (Poskytuje Selbergův vzorec. Starší forma je konečná Fourierova expanze Selberg.)

externí odkazy

• "Rozdělit", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Kalkulačka rozdělení a složení
• Weisstein, Eric W. "Rozdělit". MathWorld.
• Přednášky o celočíselných oddílech autor: Herbert S. Wilf
• Počítání s oddíly s referenčními tabulkami k on-line encyklopedii celočíselných sekvencí
• Celé oddíly záznam v FindStat databáze
• Celé číslo :: Rozdělení Perl modul z CPAN
• Rychlé algoritmy pro generování celých oddílů
• Generování všech oddílů: Porovnání dvou kódování
• Grime, James (28. dubna 2016). "Oddíly - Numberphile" (video). Brady Haran. Citováno 5. května 2016.