matematikk.net

Hvor mange ulike løsninger finnes det på likningssystemet
[tex]x_1 + x_2 + \cdots + x_n = k[/tex]
Der alle x og k er ikke-negative heltall?

Merk: Her regner vi to løsninger for å være ulike dersom
[tex](x_1, \ldots, x_n) \neq (x_1^\prime, \ldots, x_n^\prime)[/tex]
Så for likningen [tex]x_1 + x_2 = 5[/tex] er (5,0) og (0,5) to ulike løsninger.

Vi tenker oss k prikker fordelt horisontalt med en viss avstand. Hvis vi fordeler n-1 vertikale streker i mellomrom mellom prikkene, deles de k prikkene inn i n kategorier, der antall prikker i kategori nummer j blir xj.
Siden det tillates at en xj også kan være null, må vi velge mellomrom med tilbakelegging når vi skal sette en vertikal strek, og vi må tillate å sette strek både før og etter alle prikkene. Det er altså k+1 steder vi kan sette inn vertikale streker.
Antall måter dette kan gjøres på (uordnet utvalg med tilbakelegging) er

[tex]{(k+1)+(n-1)-1 \choose n-1}={k+n-1\choose n-1}[/tex]

Helt klart! De som har "vokst opp" med Paul Zeitz' "Art and Craft of Problem Solving" vil også kjenne igjen dette som "the balls in urns formula"