Dela ett nummer

En partition av ett naturligt tal är en sådan representation av ett tal som en summa av positiva heltal , som, till skillnad från sammansättning , inte tar hänsyn till ordningen på termerna. Termerna i partitionen kallas delar . I den kanoniska representationen av partitionen listas termerna i icke-ökande ordning. $n$ $n$ ${\displaystyle \lambda _{1}+\lambda _{2}+\dots +\lambda _{m))$ $\lambda_k$

Om , så betecknas partitionen som motsvarar denna uppsättning nummer vanligtvis som { } = . I det här fallet kallas numret för partitionsstyrkan och betecknas , och numret kallas för partitionslängden och betecknas . ${\displaystyle \lambda _{1}\geq \lambda _{2}\dots \geq \lambda _{m))$ ${\displaystyle \lambda _{1},\lambda _{2},\dots \lambda _{m))$ $\lambda$ $n$ $|\lambda|$ $m$ $l(\lambda )$

Antalet partitioner av ett naturligt tal är ett av de grundläggande studieobjekten inom kombinatorik . $p(n)$ $n$

Exempel

Till exempel är {3, 1, 1 } eller {3, 2 } partitioner med 5, eftersom 5 = 3 + 1 + 1 = 3 + 2 . Det finns 5 partitioner totalt: {1, 1, 1, 1, 1 }, {2, 1, 1, 1 }, {2, 2, 1 }, {3, 1, 1 }, {3, 2 } , {4, 1 }, {5}. $p(5)=7$

Vissa värden för antalet partitioner anges i följande tabell [1] : $p(n)$

n	p ( n )	Skiljeväggar
ett	ett	{ett}
2	2	{2}, {1, 1 }
3	3	{3}, {2, 1 }, {1, 1, 1 }
fyra	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	elva
7	femton
åtta	22
9	trettio
tio	42
tjugo	627
femtio	204 226
100	190 569 292
1000	24061467864032622473692149727991
10 000	361672513256362939888204718909536954950160303339315650422081868605887952568754066420592310556914430

Antal partitioner

Genererande funktion

Sekvensen av antalet partitioner har följande genereringsfunktion : $p(n)$

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

Denna formel upptäcktes av Euler 1740.

Eulers femkantiga teorem

Genom att studera sekvensens genererande funktion fokuserade Euler på dess nämnare, det vill säga på produkten . När fästena öppnas tar denna oändliga produkt följande 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öger sida har termerna formen där går igenom alla möjliga heltalsvärden , och i det här fallet kallas talen för generaliserade femkantiga . När de är naturliga kallas de helt enkelt femkantiga. [2] $(-1)^{q}x^{(3q^{2}-q)/2},$ $q$ $(3q^{2}-q)/2$ $q$

Från denna observation antog Euler Pentagonal Theorem :

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

och senare bevisade det. Detta teorem låter dig beräkna antalet partitioner med hjälp av divisionen av formella potensserier .

Asymptotiska formler

Ett asymptotiskt uttryck för antalet partitioner erhölls av Hardy och Ramanujan 1918, och oberoende 1920 av den ryske matematikern 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ögerpil \infty

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

Därefter hittade Hardy och Ramanujan ett mer exakt uttryck i form av en summa, och Rademacher härledde en exakt konvergent serie , från vilken man kan hitta godtyckligt nära asymptotiska representationer:

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

var

A_{k}(n)=\summa _{\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).

Här är summeringen över , coprime med , och är Dedekind-summan . Serien konvergerar väldigt snabbt. $m$ $k$ $s(m,k)$

Återkommande formler

Antalet partitioner av ett tal i termer som inte överstiger uppfyller den rekursiva formeln : $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 initiala värden:

P(0,\;0)=1,

P(i,\;0)=0

för alla

i>0

I det här fallet är antalet möjliga partitioner av numret lika med . $n$ $P(n,\;n)$

Unga diagram

Skiljeväggar representeras bekvämt som visuella geometriska objekt, kallade Young diagrams , för att hedra den engelske matematikern Alfred Young . Partition Young-diagrammet är en delmängd av den första kvadranten av planet, uppdelad i celler, som var och en är en kvadratisk enhet. Celler är ordnade i rader, den första raden är av längd , ovanför den är en rad med längd , och så vidare upp till den -th raden av längd . Raderna är vänsterjusterade. $(k_{1},\;k_{2},\;\ldots ,\;k_{m})$ $k_{1}$ $k_{2}$ $m$ $k_m$

Mer formellt är Young-diagrammet stängningen av uppsättningen punkter så att $(x,\;y)$

x,\ y>0

och

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

där betecknar heltalsdelen . $[x]$ $x$

I engelsk litteratur avbildas unga diagram ofta som reflekterade kring x- axeln .

Ett liknande objekt, som kallas ett Ferrers-diagram , skiljer sig i det

prickar visas istället för celler;
diagrammet transponeras: rader och kolumner är omvända.

Den konjugerade (eller transponerade) partitionen av k är en partition vars Young-diagram är Young-diagrammet för partitionen som reflekteras med avseende på linjen . Till exempel är konjugatet till partitionen (6,4,4,1) partitionen (4,3,3,3,1,1). Den konjugerade partitionen betecknas med . $\lambda$ $\lambda$ $y=x$ $\lambda '$

Summa och produkt av partitioner

Låt det finnas två partitioner och . Sedan definieras följande operationer för dem: $\lambda$ $\mu$

$\lambda +\mu$ : ; ${\displaystyle (\lambda +\mu )_{i}=\lambda _{i}+\mu _{i))$
$\lambda \cup \mu$ : en partition som innehåller delar och i icke strikt fallande ordning; $\lambda$ $\mu$
$\lambda \mu$ : ; ${\displaystyle (\lambda \mu )_{i}=\lambda _{i}\mu _{i))$
$\lambda \times \mu$ : en partition som innehåller delar för alla och alla i en icke strikt fallande ordning. $min(\lambda _{i},\mu _{j})$ $i\leq l(\lambda )$ $j\leq l(\mu )$

Additionsoperationer, som multiplikationsoperationer, är dubbla med avseende på konjugering:

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

;

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

Beställ

Låt det finnas två partitioner och nummer . $\lambda$ $\mu$ $n$

Lexikografisk ordning. Det sägs vara äldre i lexikografisk ordning om det finns ett naturligt tal så att för varje , och även . $\lambda$ $\mu$ $k$ ${\displaystyle \lambda _{i}=\mu _{i))$ $i<k$ ${\displaystyle \lambda _{k}>\mu _{k))$

I tabellen ovan är partitionerna ordnade i lexikografisk ordning.

Naturlig (del)ordning. Den sägs vara äldre i naturlig ordning (betecknad med ) om ojämlikheten gäller för varje . $\lambda$ $\mu$ $\lambda \geq \mu$ $i\geq 1$ $\lambda _{1}+\lambda _{2}+\dots +\lambda _{i}\geq \mu _{1}+\mu _{2}+\dots +\mu _{i }$

Med utgångspunkt från n=6 kan man hitta partitioner som inte kan jämföras i denna mening. Till exempel (3, 1, 1, 1) och (2, 2, 2).

För den naturliga ordningen gäller ekvivalensen:

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

Applikation

Partitioner uppstår naturligtvis i ett antal matematiska problem. Den mest betydelsefulla av dessa är representationsteorin för den symmetriska gruppen , där partitioner naturligt parametriserar alla irreducerbara representationer . Summor över alla partitioner förekommer ofta i kalkyl .

Se även

Anteckningar

↑ Sekvens A000041 i OEIS
↑ Tabachnikov S. L., Fuchs D. B. Mathematical divertissement. - MTSNMO, 2011. - ISBN 978-5-94057-731-7 .
↑ Uspensky, Asymptotiska formler för numeriska funktioner som förekommer i teorin om partitioner, Bull. Acad. sci. URSS 14, 1920, S. 199–218

Litteratur

Andrews G. Fördelningsteori. — M.: Nauka, 1982. — 255 sid.
McDonald I. Symmetriska funktioner och Hall-polynom. — M.: Mir, 1985. — 224 sid.
Vainshtein F.V. Partitionering av nummer // Kvant . - 1988. - Nr 11 . - S. 19-25 .
Fuchs D. Om öppnandet av parentes, om Euler, Gauss, Macdonald och missade möjligheter // Kvant . - 1981. - Nr 8 . - S. 12-20 .
Ny teori bevisar talens natur .
Burman Yu. M. Partitioner och permutationer // Summer School "Modern Mathematics". – 2004.