Räkneknep för heltalspartitioner? (eng: Integer partitions)

Knep, nja, det går att lista dem systematiskt. 

Tänk att du börjar med talet 7. Det är din första partition.

Du kommer gå från 7 ner till 1. Detta är talet längst till vänster. För varje del, eller "part", så kommer vi gå igenom alla möjligheter från minimum av resten, alltså det som är kvar, och föregående val.

Först får du den enda partitionen 7. Det finns 0 rest, så vi är klara.

$7$.

Sedan börjar du med 6. Det finns 1 rest, så vår enda möjlighet är 6+1. Det finns nu 0 rest, så vi är klara.

$6+1$.

Nu börjar vi med 5 och har 2 kvar i rest. Vi går från minimum(föregående val, rest) = minimum(5, 2) = 2 ner till 1:

- Väljer vi 2 får vi 5+2 med 0 rest och vi är klara.

$5+2$.

- Väljer vi 1 får vi 5+1 med 1 rest och den enda möjligheten är 5+1+1.

$5+1+1$.

Börjar vi på 4 så har vi 3 rest och går från minimum(4, 3) = 3 ner till 1:

- Väljer vi 3 får vi 4+3 med 0 rest och vi är klara.

$4+3$.

- Väljer vi 2 får vi 4+2 med 1 rest och enda möjligheten blir 

$4+2+1$.

- Väljer vi 1 får vi 4+1 med 2 rest. Nu upprepar vi processen rekursivt och går från minimum(föregående val, rest) = minimum(1, 2) = 1 ner till 1, (alltså bara en enda iteration) vilket efter upprepning ger oss den enda möjligheten

$4+1+1+1$.

Börjar vi på 3 har vi 4 rest. Vi går från minimum(3, 4) = 3 ner till 1:

- Väljer vi 3 har vi 1 rest och får enda möjligheten

$3+1+1$.

- Väljer vi 2 har vi 2 rest och går nu från minimum(2, 2) = 2 ner till 1, som leder oss till partitionerna 

$3+2+2$,

$3+2+1+1$.

- Väljer vi 1 kommer vi endast kunna välja 1 i nästkommande val som leder oss till partitionen

$3+1+1+1+1$.

Fortsätter vi på samma sätt kommer vi snart ha listat alla partitioner.

@Gustor, det där var precis vad jag var ute efter - en systematisk metod. Stort tack!

Det kan vara bra att ta reda på partitionerna för alla mindre tal, och sedan använda dem. Det blir dubbletter, men man får se till att bara räkna partitionerna en gång.