Rozdělení čísla

Dělení přirozeného čísla je taková reprezentace čísla jako součet kladných celých čísel , která na rozdíl od složení nebere v úvahu pořadí členů. Termíny v oddílu se nazývají části . V kanonické reprezentaci oddílu jsou termíny uvedeny v nerostoucím pořadí. $n$ $n$ ${\displaystyle \lambda _{1}+\lambda _{2}+\tečky +\lambda _{m))$ $\lambda_k$

Jestliže , pak oddíl odpovídající této sadě čísel je obvykle označen jako { } = . V tomto případě se číslo nazývá výkon oddílu a označuje se , a číslo se nazývá délka oddílu a značí . ${\displaystyle \lambda _{1}\geq \lambda _{2}\tečky \geq \lambda _{m))$ ${\displaystyle \lambda _{1},\lambda _{2},\tečky \lambda _{m))$ $\lambda$ $n$ $|\lambda|$ $m$ $l(\lambda )$

Počet dělení přirozeného čísla je jedním ze základních předmětů studia v kombinatorice . $p(n)$ $n$

Příklady

Například {3, 1, 1 } nebo {3, 2 } jsou oddíly po 5, protože 5 = 3 + 1 + 1 = 3 + 2 . Existuje celkem 5 oddílů: {1, 1, 1, 1, 1 }, {2, 1, 1, 1 }, {2, 2, 1 }, {3, 1, 1 }, {3, 2 } , {4, 1 }, {5}. $p(5)=7$

Některé hodnoty pro počet oddílů jsou uvedeny v následující tabulce [1] : $p(n)$

n	p ( n )	Příčky
jeden	jeden	{jeden}
2	2	{2}, {1, 1 }
3	3	{3}, {2, 1 }, {1, 1, 1 }
čtyři	5	{4}, {3, 1 }, {2, 2 }, {2, 1, 1 }, {1, 1, 1, 1 }
5	7	{5}, {4, 1 }, {3, 2 }, {3, 1, 1 }, {2, 2, 1 }, {2, 1, 1, 1 }, {1, 1, 1, 1 , 1 },
6	jedenáct
7	patnáct
osm	22
9	třicet
deset	42
dvacet	627
padesáti	204 226
100	190 569 292
1000	24061467864032622473692149727991
10 000	3616725132563629398882047189095369549501603033931565042208186860588795256875406642059231055690529105695434

Počet oddílů

Generující funkce

Posloupnost počtu oddílů má následující generující funkci : $p(n)$

\sum _{{n=0}}^{\infty }p(n)x^{n}=\prod _{{k=1}}^{\infty }{\frac {1}{1-x ^{k}}}.

Tento vzorec objevil Euler v roce 1740.

Eulerova pětiúhelníková věta

Při studiu generující funkce posloupnosti se Euler zaměřil na jejího jmenovatele, tedy na součin . Po otevření závorek má tento nekonečný produkt následující podobu: $p(n)$ $(1-x)(1-x^{2})(1-x^{3})...$

(1-x)(1-x^{2})(1-x^{3})\ldots =1-xx^{2}+x^{5}+x^{7}-x ^{12}-x^{15}+x^{22}+x^{26}-x^{35}-x^{40}+\ldots

Na pravé straně mají termíny tvar kde prochází všemi možnými celočíselnými hodnotami a v tomto případě se samotná čísla nazývají zobecněné pětiúhelníkové . Když jsou přirozené , nazývají se jednoduše pětiúhelníkové. [2] $(-1)^{q}x^{(3q^{2}-q)/2},$ $q$ $(3q^{2}-q)/2$ $q$

Z tohoto pozorování Euler předpokládal pětiúhelníkovou větu :

\prod _{k=1}^{\infty }\left(1-x^{k}\right)=\sum _{q=-\infty }^{\infty }(-1)^ {q}x^{(3q^{2}-q)/2},

a později to dokázal. Tato věta umožňuje vypočítat počet oddílů pomocí dělení formálních mocninných řad .

Asymptotické vzorce

Asymptotický výraz pro počet oddílů získali Hardy a Ramanujan v roce 1918 a nezávisle v roce 1920 ruský matematik Uspenskij : [3]

p(n)\sim {\frac {\exp \left(\pi {\sqrt ({\frac {2}{3)))){\sqrt {n-{\frac {1}{24))} }\right)}{4n{\sqrt {3))))

n\rightarrow \infty

Například . $p(1000)\cca 2{,}44\cdot 10^{31}$

Následně Hardy a Ramanujan našli přesnější vyjádření ve formě součtu a Rademacher odvodil přesnou konvergentní řadu , ze které lze najít libovolně blízké asymptotické reprezentace:

p(n)={\frac {1}{\pi {\sqrt {2))))\sum _{k=1}^{\infty }A_{k}(n)\;{\ sqrt {k}}\;{\frac {d}{dn}}\left({\frac {\sinh \left({\frac {\pi }{k}}{\sqrt {{\frac {2} {3}}\left(n-{\frac {1}{24}}\right)}}\right)}{\sqrt {n-{\frac {1}{24}}}}}\right) ,

kde

A_{k}(n)=\sum _{\begin{smallmatrix}0\leqslant m<k\\(m,k)=1\end{smallmatrix}}\exp \left(\pi i\ cdot s(m,k)-2\pi in\cdot m/k\right).

Zde je sumace u konce , spolu s , a je Dedekindovým součtem . Série velmi rychle konverguje. $m$ $k$ $s(m,k)$

Opakující se vzorce

Počet rozdělení čísla na členy, které nepřesahují, splňuje rekurzivní vzorec : $n$ $k$

P(n,\;k)={\begin{cases}P(n,\;k-1)+P(nk,\;k),&k\leqslant n,\\P(n,\ ;n),&k>n,\end{cases}}

s počátečními hodnotami:

P(0,\;0)=1,

P(i,\;0)=0

pro všechny

i>0

V tomto případě je počet možných oddílů čísla roven . $n$ $P(n,\;n)$

Young diagramy

Příčky jsou vhodně reprezentovány jako vizuální geometrické objekty, nazývané Youngovy diagramy , na počest anglického matematika Alfreda Younga . Youngův diagram rozdělení je podmnožinou prvního kvadrantu roviny, rozdělený na buňky, z nichž každá je jednotkový čtverec. Buňky jsou uspořádány do řad, první řada má délku , nad ní je řada délky a tak dále až do -té řady délky . Řádky jsou zarovnány doleva. $(k_{1},\;k_{2},\;\ldots ,\;k_{m})$ $k_{1}$ $k_{2}$ $m$ $k_m$

Formálněji je Youngův diagram uzavřením množiny bodů tak, že $(x,\;y)$

x,\ y>0

y<\sum _{{j=[x]}}^{{m}}k_{j},

kde označuje celočíselnou část . $[X]$ $X$

V anglické literatuře jsou Youngovy diagramy často zobrazovány jako odražené kolem osy x .

Podobný objekt, nazvaný Ferrersův diagram , se v tom liší

místo buněk se zobrazují tečky;
graf je transponován: řádky a sloupce jsou obráceny.

Konjugovaný (nebo transponovaný) oddíl k je oddíl, jehož Youngův diagram je Youngovým diagramem rozdělení odraženým vzhledem k přímce . Například konjugát k oddílu (6,4,4,1) je oddíl (4,3,3,3,1,1). Konjugovaný oddíl je označen . $\lambda$ $\lambda$ $y=x$ $\lambda '$

Součet a součin oddílů

Nechť jsou dva oddíly a . Poté jsou pro ně definovány následující operace: $\lambda$ $\mu$

$\lambda +\mu$ : ; ${\displaystyle (\lambda +\mu )_{i}=\lambda _{i}+\mu _{i))$
$\lambda \cup \mu$ : oddíl obsahující části a v nepřísném sestupném pořadí; $\lambda$ $\mu$
$\lambda \mu$ : ; ${\displaystyle (\lambda \mu )_{i}=\lambda _{i}\mu _{i))$
$\lambda \times \mu$ : oddíl obsahující části pro všechny a všechny v nepřísném sestupném pořadí. $min(\lambda _{i},\mu _{j})$ $i\leq l(\lambda )$ $j\leq l(\mu )$

Operace sčítání, jako operace násobení, jsou s ohledem na konjugaci duální:

(\lambda \cup \mu )'=\lambda '+\mu '

;

(\lambda \times \mu )'=\lambda '\mu '

Objednávka

Nechť jsou dva oddíly a čísla . $\lambda$ $\mu$ $n$

Lexikografický řád. Říká se, že je starší v lexikografickém pořadí, pokud existuje přirozené číslo takové, že pro každý , a také . $\lambda$ $\mu$ $k$ ${\displaystyle \lambda _{i}=\mu _{i))$ $i<k$ ${\displaystyle \lambda _{k}>\mu _{k))$

Ve výše uvedené tabulce jsou oddíly uspořádány v lexikografickém pořadí.

Přirozený (dílčí) řád. Říká se, že je starší v přirozeném pořadí (označuje se ), pokud nerovnost platí pro každý . $\lambda$ $\mu$ $\lambda \geq \mu$ $i\geq 1$ $\lambda _{1}+\lambda _{2}+\tečky +\lambda _{i}\geq \mu _{1}+\mu _{2}+\tečky +\mu _{i }$

Počínaje n=6 lze najít oddíly, které nelze v tomto smyslu srovnávat. Například (3, 1, 1, 1) a (2, 2, 2).

Pro přirozený řád platí ekvivalence:

\lambda \geq \mu \Leftrightarrow \mu '\geq \lambda'.

Aplikace

Oddíly přirozeně vznikají v řadě matematických problémů. Nejvýznamnější z nich je teorie reprezentace symetrické grupy , kde oddíly přirozeně parametrizují všechny neredukovatelné reprezentace . V počtu se často vyskytují součty přes všechny oddíly .

Viz také

Poznámky

↑ Sekvence A000041 v OEIS
↑ Tabachnikov S. L., Fuchs D. B. Matematická divertissement. - MTSNMO, 2011. - ISBN 978-5-94057-731-7 .
↑ Uspensky, Asymptotické vzorce pro numerické funkce, které se vyskytují v teorii dělení, Bull. Akad. sci. URSS 14, 1920, S. 199–218

Literatura

Andrews G. Teorie oddílů. — M.: Nauka, 1982. — 255 s.
McDonald I. Symetrické funkce a Hallovy polynomy. — M.: Mir, 1985. — 224 s.
Vainshtein F.V. Dělení čísel // Kvant . - 1988. - č. 11 . - S. 19-25 .
Fuchs D. O otevření závorky, o Eulerovi, Gaussovi, Macdonaldovi a promarněných příležitostech // Kvant . - 1981. - č. 8 . - S. 12-20 .
Nová teorie dokazuje povahu čísel .
Burman Yu. M. Partitions and permutations // Summer School "Modern Mathematics". — 2004.