Împărțirea unui număr

O partiție a unui număr natural este o astfel de reprezentare a unui număr ca o sumă de numere întregi pozitive , care, spre deosebire de compoziție , nu ia în considerare ordinea termenilor. Termenii din partiție se numesc părți . În reprezentarea canonică a partiției, termenii sunt enumerați în ordine necrescătoare. $n$ $n$ $\lambda _{1}+\lambda _{2}+\dots +\lambda _{m)$ $\lambda_k$

Dacă , atunci partiția corespunzătoare acestui set de numere este de obicei notată ca { } = . În acest caz, numărul se numește puterea partiției și se notează , iar numărul se numește lungimea partiției și se notează . $\lambda _{1}\geq \lambda _{2}\dots \geq \lambda _{m)$ $\lambda _{1},\lambda _{2},\dots \lambda _{m)$ $\lambda$ $n$ $|\lambda|$ $m$ $l(\lambda )$

Numărul de partiții ale unui număr natural este unul dintre obiectele fundamentale de studiu în combinatorică . $p(n)$ $n$

Exemple

De exemplu, {3, 1, 1 } sau {3, 2 } sunt partiții ale lui 5, deoarece 5 = 3 + 1 + 1 = 3 + 2 . Există 5 partiții în total: {1, 1, 1, 1, 1 }, {2, 1, 1, 1 }, {2, 2, 1 }, {3, 1, 1 }, {3, 2 } , {4, 1 }, {5}. $p(5)=7$

Unele valori pentru numărul de partiții sunt date în următorul tabel [1] : $p(n)$

n	p ( n )	Paravane
unu	unu	{unu}
2	2	{2}, {1, 1 }
3	3	{3}, {2, 1 }, {1, 1, 1 }
patru	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	unsprezece
7	cincisprezece
opt	22
9	treizeci
zece	42
douăzeci	627
cincizeci	204 226
100	190 569 292
1000	24061467864032622473692149727991
10000	3616725132563629398882047189095369549501603033931565042208186860588795256875406642059231055605650422081868605887952568754066420592310556056504

Numărul de partiții

Funcție de generare

Secvența numărului de partiții are următoarea funcție de generare : $p(n)$

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

Această formulă a fost descoperită de Euler în 1740.

Teorema pentagonală a lui Euler

Studiind funcția generatoare a secvenței , Euler s-a concentrat pe numitorul acesteia, adică pe produs . Când parantezele sunt deschise, acest produs infinit ia următoarea formă: $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

În partea dreaptă, termenii au forma în care trece prin toate valorile întregi posibile , iar în acest caz numerele în sine sunt numite pentagonale generalizate . Când sunt naturale , ele sunt numite pur și simplu pentagonale. [2] $(-1)^{q}x^{(3q^{2}-q)/2},$ $q$ $(3q^{2}-q)/2$ $q$

Din această observație, Euler a formulat teorema pentagonală :

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

iar ulterior a dovedit-o. Această teoremă vă permite să calculați numărul de partiții folosind împărțirea serii formale de putere .

Formule asimptotice

O expresie asimptotică pentru numărul de partiții a fost obținută de Hardy și Ramanujan în 1918 și, în mod independent, în 1920, de matematicianul rus Uspensky : [3]

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

n\rightarrow \infty

De exemplu, . $p(1000)\aprox 2{,}44\cdot 10^{31}$

Ulterior, Hardy și Ramanujan au găsit o expresie mai precisă sub forma unei sume, iar Rademacher a derivat o serie convergentă exactă , din care se pot găsi reprezentări asimptotice în mod arbitrar apropiate:

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) ,

Unde

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).

Aici suma sa terminat , coprime cu , și este suma Dedekind . Seria converge foarte repede. $m$ $k$ $s(m,k)$

Formule recurente

Numărul de partiții ale unui număr în termeni care nu depășesc satisface formula recursivă : $n$ $k$

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

cu valorile initiale:

P(0,\;0)=1,

P(i,\;0)=0

pentru toți

i>0

În acest caz, numărul de partiții posibile ale numărului este egal cu . $n$ $P(n,\;n)$

Diagrame tinere

Partițiile sunt reprezentate convenabil ca obiecte geometrice vizuale, numite diagrame Young , în onoarea matematicianului englez Alfred Young . Diagrama Young de partiție este un subset al primului cadran al planului, împărțit în celule, fiecare dintre acestea fiind un pătrat unitar. Celulele sunt aranjate în rânduri, primul rând este de lungime , deasupra este un rând de lungime , și așa mai departe până la --lea rând de lungime . Rândurile sunt aliniate la stânga. $(k_{1},\;k_{2},\;\ldots ,\;k_{m})$ $k_{1}$ $k_{2}$ $m$ $k_m$

Mai formal, diagrama Young este închiderea setului de puncte astfel încât $(X y)$

x,\y>0

și

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

unde denotă partea întreagă . $[X]$ $X$

În literatura engleză, diagramele Young sunt adesea descrise ca reflectate în jurul axei x .

Un obiect similar, numit diagramă Ferrers , diferă prin aceasta

punctele sunt afișate în loc de celule;
diagrama este transpusă: rândurile și coloanele sunt inversate.

Partiția conjugată (sau transpusă) a lui k este o partiție a cărei diagramă Young este diagrama Young a partiției reflectate în raport cu linia . De exemplu, conjugatul la partiția (6,4,4,1) este partiția (4,3,3,3,1,1). Partiția conjugată se notează cu . $\lambda$ $\lambda$ $y=x$ $\lambda '$

Suma și produsul partițiilor

Să fie două partiții și . Apoi sunt definite următoarele operații pentru ei: $\lambda$ $\mu$

$\lambda +\mu$ : ; $(\lambda +\mu )_{i}=\lambda _{i}+\mu _{i)$
$\lambda \cup \mu$ : o partiție care conține părți și în ordine descrescătoare nestrictă; $\lambda$ $\mu$
$\lambda \mu$ : ; $(\lambda \mu )_{i}=\lambda _{i}\mu _{i)$
$\lambda \times \mu$ : o partiție care conține părți pentru toată lumea și pentru toată lumea într-o ordine descrescătoare nestrictă. $min(\lambda _{i},\mu _{j})$ $i\leq l(\lambda )$ $j\leq l(\mu )$

Operațiile de adunare, precum operațiile de înmulțire, sunt duale în ceea ce privește conjugarea:

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

;

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

Comanda

Să fie două partiții și numere . $\lambda$ $\mu$ $n$

Ordinea lexicografică. Se spune că este mai vechi în ordine lexicografică dacă există un număr natural astfel încât pentru fiecare , și de asemenea . $\lambda$ $\mu$ $k$ $\lambda _{i}=\mu _{i)$ $i<k$ $\lambda _{k}>\mu _{k)$

În tabelul de mai sus, partițiile sunt aranjate în ordine lexicografică.

Ordine naturală (parțială). Se spune că este mai vechi în ordinea naturală (notat cu ) dacă inegalitatea este valabilă pentru fiecare . $\lambda$ $\mu$ $\lambda \geq \mu$ $i\geq 1$ $\lambda _{1}+\lambda _{2}+\dots +\lambda _{i}\geq \mu _{1}+\mu _{2}+\dots +\mu _{i }$

Începând de la n=6 se pot găsi partiții care nu pot fi comparate în acest sens. De exemplu, (3, 1, 1, 1) și (2, 2, 2).

Pentru ordinea naturală, echivalența este valabilă:

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

Aplicație

Partițiile apar în mod natural într-o serie de probleme matematice. Cea mai semnificativă dintre acestea este teoria reprezentării grupului simetric , unde partițiile parametriză în mod natural toate reprezentările ireductibile . Sumele pentru toate partițiile apar adesea în calcul .

Vezi și

Note

↑ Secvența A000041 în OEIS
↑ Tabachnikov S. L., Fuchs D. B. Divertisment matematic. - MTSNMO, 2011. - ISBN 978-5-94057-731-7 .
^ Uspensky , Formule asimptotice pentru funcțiile numerice care apar în teoria partițiilor, Bull. Acad. sci. URSS 14, 1920, S. 199–218

Literatură

Andrews G. Teoria partiției. — M.: Nauka, 1982. — 255 p.
McDonald I. Funcții simetrice și polinoame Hall. — M.: Mir, 1985. — 224 p.
Vainshtein F.V. Împărțirea numerelor // Kvant . - 1988. - Nr. 11 . - S. 19-25 .
Fuchs D. Despre deschiderea parantezelor, despre Euler, Gauss, Macdonald și ocaziile ratate // Kvant . - 1981. - Nr 8 . - S. 12-20 .
O nouă teorie demonstrează natura numerelor .
Burman Yu. M. Partiții și permutări // Școala de vară „Matematică modernă”. — 2004.