het aantal delen van grootte k tussen al de partities van n wordt gegeven door : N(n,k)=p(n-k)+p(n-2ˇk)+p(n-3ˇk)... waar p(x) staat voor het aantal partities van x. Zo zal het aantal maal dat het getal 7 voorkomt tussen de 176 partities van 15 gelijk zijn aan: p(15-7)+p(15-2ˇ7)=22+1=23;
Waar kan ik het bewijs vinden van deze formule ?
antoin
Student universiteit België - maandag 17 november 2003
Antwoord
Hoi,
Een Partitie van een verzameling V van n gelijke elementen is een verzameling van k deelverzamelingen (klassen) Ai met de eigenschappen dat geen enkele Ai leeg is EN elk element van V in precies één Ai zit. Een onmiddellijk en nuttig gevolg hiervan is dat #V=sum(Ai:i=1..k).
We zijn geďnteresseerd in het aantal manieren p(n) waarop we een verzameling van n gelijke elementen in een partitie kunnen verdelen of anders gezegd: in het aantal partities van V. Je kan dit ook zien als het aantal manieren waarom we n als een niet-geordende som van natuurlijk getallen kunnen schrijven. Daarom spreken we ook van het aantal partities van n. Bijvoorbeeld voor n=5 hebben we p(n)=7 mogelijke partities: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1 en 1+1+1+1+1. Een partitie stellen we hier dus verkort voor door het aantal elementen van elke klasse.
We zoeken eerst een uitdrukking voor p(n). Laten we daarom p(n,m) definiëren als het aantal partities waarbij we hoogstens m elementen per klasse mogen hebben. Dan gelden volgende betrekkingen:
p(n,1)=1 voor n0 Als we hoogstens 1 element per klasse mogen hebben, is de enige mogelijke partitie die met 1 element per klasse.
p(n,m)=sum[p(n-i,i):i=1..min(n,m)] Als we n als een som van niet-stijgende termen moeten schrijven die niet groter dan m mogen zijn, dan kunnen we beginnen met i=1,2,3, ... tot hoogstens min(n,m). We moeten dan nog een som schrijven voor n-i waarbij we hoogstens i gebruiken. En dit kan op p(n-i,i) manieren. Verzameling-technisch partitioneren we de partities volgens de grootte van de grootste klasse.
Je ziet ook dat: p(n,m)=sum[p(n-i,i):i=1..m]=p(n,m-1)+p(n-m,m) voor mn p(n,m)=p(n,n) voor mn
p(0,m)=1 voor m0 (triviaal geval)
p(n)=p(n,n) en in het bijzonder is p(0)=1.
In de tabel vinden we een overzichtje van p(n,m).
Op Wolfram vinden we de de Partition P, Partition Q en Partition q functies. Stuk voor stuk fantastische formulues... Rademacher, Euler, Erdös, MacMahon, Ramanujan en anderen waren ook geďnteresseerd. De formule die ik hierboven afgeleid heb, vind je er blijkbaar ook terug (Partition Function q).
Met N(n,k) bedoelen we het aantal klassen van k elementen doorheen alle partitities van n elementen. In het voorbeeld van n=5 met k=1 zien we dat er 2 sommen zijn met 1 keer de klasse 1, 1 som met 2 keer de klasse 1, 1 klasse met 3 keer de klasse 1 en 1 som met 5 keer de klasse 1. In totaal staan er dus 2.1+1.2+1.3+1.5=12 klassen 1 en dus is N(5,1)=12. We zien inderdaad dat N(5,1)=p(4)+p(3)+p(2)+p(1)+p(0)=5+3+2+1+1=12.
Voor kn is N(n,k)=0 omdat er onmogelijk een klasse met k elementen kan bestaan. Voor kn kan dit wel. We kunnen alle partities van n elementen in 2 groepen verdelen: de eerste groep bevat minstens 1 klasse van grootte k, de tweede groep bevat geen enkele klasse van grootte k. Voor n=5 bestaat de eerste groep uit: 4+1, 3+1+1, 2+2+1, 2+1+1+1 en 1+1+1+1+1 en de tweede groep uit: 5, 3+2. We zien dat de eerste groep eigenlijk bestaat uit alle partities van 4, aangevuld met de term/klasse 1. In het algemeen geldt dit ook: elke partitie van n-k elementen kunnen we uitbreiden tot een partitie van n elementen die minstens één klasse van k elementen bevat door een klasse k toe te voegen. Omgekeerd kunnen we elke partitie die een klasse k bevat zien als de unie van die klasse met k elementen met een partitie van n-k elementen. We weten dat er p(n-k) partities zijn van n-k elementen. Het aantal keren dat er een klasse van k elementen voorkomt in de partities van n-k elementen is N(n,n-k) en we hebben al p(n-k) klassen van k elementen geďsoleerd. Samengevat hebben we dus dat: N(n,k)=p(n-k)+N(n,n-k), zodat: N(n,k)=sum[p(n-i.k):i=1,2,..n/k] (n/k: gehele deling). (QED)
0
n
n
