Opdeling af et tal

En partition af et naturligt tal er en sådan repræsentation af et tal som en sum af positive heltal , som i modsætning til sammensætning ikke tager hensyn til rækkefølgen af vilkårene. Termerne i partitionen kaldes dele . I den kanoniske repræsentation af partitionen er begreberne opført i ikke-stigende rækkefølge. $n$ $n$ ${\displaystyle \lambda _{1}+\lambda _{2}+\dots +\lambda _{m))$ $\lambda_k$

Hvis , så er den partition, der svarer til dette sæt tal, normalt betegnet som { } = . I dette tilfælde kaldes tallet partitionsstyrken og betegnes , og tallet kaldes partitionslængden og betegnes . ${\displaystyle \lambda _{1}\geq \lambda _{2}\dots \geq \lambda _{m))$ ${\displaystyle \lambda _{1},\lambda _{2},\dots \lambda _{m))$ $\lambda$ $n$ $|\lambda|$ $m$ $l(\lambda )$

Antallet af partitioner af et naturligt tal er et af de grundlæggende genstande for studiet i kombinatorik . $p(n)$ $n$

Eksempler

For eksempel er {3, 1, 1 } eller {3, 2 } partitioner på 5, da 5 = 3 + 1 + 1 = 3 + 2 . Der er 5 partitioner i alt: {1, 1, 1, 1, 1 }, {2, 1, 1, 1 }, {2, 2, 1 }, {3, 1, 1 }, {3, 2 } , {4, 1 }, {5}. $p(5)=7$

Nogle værdier for antallet af partitioner er angivet i følgende tabel [1] : $p(n)$

n	p ( n )	Skillevægge
en	en	{en}
2	2	{2}, {1, 1 }
3	3	{3}, {2, 1 }, {1, 1, 1 }
fire	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	elleve
7	femten
otte	22
9	tredive
ti	42
tyve	627
halvtreds	204 226
100	190 569 292
1000	24061467864032622473692149727991
10.000	3616725132563629398882047189095369549501603033393156504220818686058879525687540664205923105569141430

Antal partitioner

Genererer funktion

Sekvensen af antallet af partitioner har følgende genereringsfunktion : $p(n)$

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

Denne formel blev opdaget af Euler i 1740.

Eulers femkantede sætning

Ved at studere den genererende funktion af sekvensen fokuserede Euler på dens nævner, det vil sige på produktet . Når beslagene åbnes, har dette uendelige produkt følgende 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

På højre side har vilkårene formen, hvor der løber gennem alle mulige heltalsværdier , og i dette tilfælde kaldes tallene i sig selv generaliserede femkantede . Når de er naturlige , kaldes de simpelthen femkantede. [2] $(-1)^{q}x^{(3q^{2}-q)/2},$ $q$ $(3q^{2}-q)/2$ $q$

Ud fra denne observation formodede Euler Pentagonal Theorem :

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

og senere beviste det. Denne teorem giver dig mulighed for at beregne antallet af partitioner ved hjælp af divisionen af formelle potensrækker .

Asymptotiske formler

Et asymptotisk udtryk for antallet af partitioner blev opnået af Hardy og Ramanujan i 1918 og uafhængigt i 1920 af den russiske matematiker Uspensky : [3]

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

på

n\højrepil \infty

For eksempel . $p(1000)\approx 2{,}44\cdot 10^{31}$

Efterfølgende fandt Hardy og Ramanujan et mere præcist udtryk i form af en sum, og Rademacher udledte en nøjagtig konvergent serie , hvorfra man kan finde vilkårligt tætte asymptotiske repræsentationer:

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}}\venstre(n-{\frac {1}{24}}\right)}}\right)}{\sqrt {n-{\frac {1}{24}}}}}\right) ,

hvor

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

Her er summeringen slut , coprime med , og er Dedekind-summen . Serien konvergerer meget hurtigt. $m$ $k$ $s(m,k)$

Tilbagevendende formler

Antallet af partitioner af et tal i termer, der ikke overstiger , opfylder den rekursive formel : $n$ $k$

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

med startværdier:

P(0,\;0)=1,

P(i,\;0)=0

for alle

i>0

I dette tilfælde er antallet af mulige partitioner af nummeret lig med . $n$ $P(n,\;n)$

Unge diagrammer

Skillevægge er bekvemt repræsenteret som visuelle geometriske objekter, kaldet Young diagrams , til ære for den engelske matematiker Alfred Young . Partition Young-diagrammet er en delmængde af den første kvadrant af planet, opdelt i celler, som hver er en enhedskvadrant. Celler er arrangeret i rækker, den første række er af længde , over den er en række af længde , og så videre op til den -th række af længden . Rækkerne er venstrejusterede. $(k_{1},\;k_{2},\;\ldots ,\;k_{m})$ $k_{1}$ $k_{2}$ $m$ $k_m$

Mere formelt er Young-diagrammet lukningen af sættet af punkter sådan, at $(x,\;y)$

x,\ y>0

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

hvor angiver heltalsdelen . $[x]$ $x$

I engelsk litteratur er unge diagrammer ofte afbildet som reflekteret omkring x- aksen .

Et lignende objekt, kaldet et Ferrers-kort , adskiller sig i det

prikker vises i stedet for celler;
diagrammet transponeres: rækker og kolonner er vendt om.

Den konjugerede (eller transponerede) partition af k er en partition, hvis Young-diagram er Young-diagrammet for partitionen reflekteret i forhold til linjen . For eksempel er konjugatet til partitionen (6,4,4,1) partitionen (4,3,3,3,1,1). Den konjugerede partition er angivet med . $\lambda$ $\lambda$ $y=x$ $\lambda '$

Sum og produkt af partitioner

Lad der være to partitioner og . Derefter defineres følgende operationer for dem: $\lambda$ $\mu$

$\lambda +\mu$ : ; ${\displaystyle (\lambda +\mu )_{i}=\lambda _{i}+\mu _{i))$
$\lambda \cup \mu$ : en partition, der indeholder dele og i ikke-strengt faldende rækkefølge; $\lambda$ $\mu$
$\lambda \mu$ : ; ${\displaystyle (\lambda \mu )_{i}=\lambda _{i}\mu _{i))$
$\lambda \times \mu$ : en partition, der indeholder dele til alle og enhver i en ikke-strengt faldende rækkefølge. $min(\lambda _{i},\mu _{j})$ $i\leq l(\lambda )$ $j\leq l(\mu )$

Additionsoperationer, ligesom multiplikationsoperationer, er dobbelte med hensyn til konjugation:

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

;

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

Bestil

Lad der være to partitioner og tal . $\lambda$ $\mu$ $n$

Leksikografisk rækkefølge. Det siges at være ældre i leksikografisk rækkefølge, hvis der findes et naturligt tal , således at for hver og også . $\lambda$ $\mu$ $k$ ${\displaystyle \lambda _{i}=\mu _{i))$ $i<k$ ${\displaystyle \lambda _{k}>\mu _{k))$

I tabellen ovenfor er partitionerne arrangeret i leksikografisk rækkefølge.

Naturlig (delvis) orden. Det siges at være ældre i naturlig rækkefølge (benævnt med ), hvis uligheden gælder for hver . $\lambda$ $\mu$ $\lambda \geq \mu$ $i\geq 1$ $\lambda _{1}+\lambda _{2}+\dots +\lambda _{i}\geq \mu _{1}+\mu _{2}+\dots +\mu _{i }$

Startende fra n=6 kan man finde partitioner, der ikke kan sammenlignes i denne forstand. For eksempel (3, 1, 1, 1) og (2, 2, 2).

For den naturlige orden gælder ækvivalensen:

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

Ansøgning

Skillevægge opstår naturligt i en række matematiske problemer. Den mest betydningsfulde af disse er repræsentationsteorien for den symmetriske gruppe , hvor partitioner naturligt parametriserer alle irreducerbare repræsentationer . Summer over alle partitioner forekommer ofte i calculus .

Se også

Noter

↑ Sekvens A000041 i OEIS
↑ Tabachnikov S. L., Fuchs D. B. Matematisk divertissement. - MTSNMO, 2011. - ISBN 978-5-94057-731-7 .
↑ Uspensky, Asymptotiske formler for numeriske funktioner, der forekommer i partitionsteorien, Bull. Acad. sci. URSS 14, 1920, S. 199–218

Litteratur

Andrews G. Partitionsteori. — M.: Nauka, 1982. — 255 s.
McDonald I. Symmetriske funktioner og Hall-polynomier. — M.: Mir, 1985. — 224 s.
Vainshtein F.V. Opdeling af numre // Kvant . - 1988. - Nr. 11 . - S. 19-25 .
Fuchs D. Om åbning af parentes, om Euler, Gauss, Macdonald og forpassede muligheder // Kvant . - 1981. - Nr. 8 . - S. 12-20 .
Ny teori beviser tallenes natur .
Burman Yu. M. Skillevægge og permutationer // Sommerskole "Modern Mathematics". – 2004.