Bevisa formel för antalet heltalspartitioner av n i k delar

Hej!

Jag förstår inte min boks facit: "Subtract 1 from each part" är det enda som står där.

Uppgiften lyder: "Let $p_k(n)$ denote the number of partitions of $n$ into $k$ parts. Prove that $p_k(n)=p_k(n-k)+p_{k-1}(n-k)+ \dots + p_1(n-k)$ ". (Biggs, Discrete Mathematics, Uppg 12.4.2)

(heltalspartitioner är det vi snackar om här)

Jag hittade ett visuellt bevis för en likande formel p_k(n)=p_{k-1}(n-1)+p_{k}(n-k) som bygger på att ta bort antingen 1 från alla partitioner som innehåller en etta eller k från antalet partitioner av storlek k som inte innehåller en etta, och sen addera dessa för att få totala antalet partitioner: https://www.youtube.com/watch?v=F4zYDx-EfZ

Videon ger mig starka ledtrådar till hur jag ska tänka och tolka bokens facit, men jag kan inte komma hela vägen fram ändå.

Härligt facit.

Du kan kanske tänka så här:

Vi har $n$ saker och ska stoppa dem i $k$ lådor, där ingen låda får vara tom. Låt $p_k(n)$ beteckna antalet olika sätt vi kan göra detta på.

Eftersom ingen låda får vara tom, så börjar vi med att lägga en sak i varje låda. Då har vi $n-k$ saker kvar.

Om vi för stunden låtsas som att lådorna är tomma ("subtract 1 from each part") så kan vi fortsätta på detta vis:

Vi väljer först ett antal korgar, säg $m$ (minst $1\leq m\leq k$ ), låtsas att de är tomma och utför samma procedur som i början men med $n-k$ saker att placera i $m$ lådor, istället för $n$ saker att placera i $k$ lådor. Så för varje val av $m$ får vi $p_m(n-k)$ möjligheter.

Väljer vi en korg att lägga resten i, då får vi $p_1(n-k)$ möjligheter. Väljer vi två korgar finns det $p_2(n-k)$ möjligheter, och väljer vi att fortsätta med alla $k$ korgar får vi $p_k(n-k)$ möjligheter. Sammantaget finns det då

$p_1(n-k) + p_2(n-k) + \dots + p_k(n-k)$

möjligheter att lägga $n$ saker i $k$ lådor (med minst en sak i varje låda).

Tillägg: 13 sep 2025 19:56

Vet inte riktigt varför men jag råkade skriva korg istället för låda på ett par ställen.

Svara