Antalet tal med siffersumman 15 i ett intervall (kombinatorik)

Hej, tänkte be om lite input på min lösning av följande uppgift:

Hur många femsiffriga positiva heltal (d.v.s. heltal $n$ sådana att $10000 \leq n \leq 99999$ ) har siffersumman $15 ?$

Min lösning följer nedan.

Frågeställningen kan konverteras till följande ekvation: $x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 15$ där restriktionerna lyder som följer: $1 \leq x_{1} \leq 9$ , samt $0 \leq x_{i} \leq 9$ där $i = 2, 3, 4, 5$ .

Börjar med att finna antalet icke-negativa lösningar till ekvationen $x_{1}' + x_{2} + x_{3} + x_{4} + x_{5} = 14$ , där $x_{1}' = x_{1} - 1$ , p.g.a. restriktionen att $x_{1} \geq 1$ . Beräknar detta enligt: $(\begin{matrix} 18 \\ 14 \end{matrix}) = 3060$ . Från detta måste sedan antalet lösningar där $x_{i} \geq 10$ subtraheras, vilket ger två olika fall.

Fall 1: $x_{1} \geq 10$

$x_{1}' + x_{2} + x_{3} + x_{4} + x_{5} = 5$ , där $x_{1}' = x_{1} - 10$ p.g.a. restriktionen $x_{1} \geq 10$

Detta ger: $(\begin{matrix} 9 \\ 5 \end{matrix}) = 126$

Fall 2: $x_{1} \geq 1, x_{i} \geq 10$ , för $i = 2, 3, 4, 5$

$x_{1}' + x_{2}' + x_{3} + x_{4} + x_{5} = 4$ , där $x_{1}' = x_{1} - 1, x_{2}' = x_{2} - 10$ p.g.a. restriktionerna $x_{1} \geq 1, x_{2} \geq 10$

Detta ger: $(\begin{matrix} 8 \\ 4 \end{matrix}) = 70$

Eftersom samma resultat erhålls för samtliga $x_{i}$ , där $i = 2, 3, 4, 5$ så kan resultatet multipliceras med fyra.

Det slutgiltiga resultatet ges då av:

$3060 - 126 - (70 * 4) = 2645$

Tänker jag rätt? Det känns som jag gör något tokigt.

Kan du ge ett exempel där $x_1\ge10$ ? Jag tycker det verkar strida mot faktumet att $1\le x_1\le9$ .

Smaragdalena skrev:
Kan du ge ett exempel där $x_1\ge10$ ? Jag tycker det verkar strida mot faktumet att $1\le x_1\le9$ .

I den första ekvationen beräknar jag de lösningar där $x_{1} \geq 1$ samt $x_{2}, x_{3}, x_{4}, x_{5} \geq 0$ alltså även de lösningar där $x_{1} \geq 10$ . Jag vill sedan subtrahera de lösningar där något $x_{i} \geq 10$ för att få fram de giltiga kombinationerna. Jag kanske har fel tillvägagångssätt...

Jag förstår fortfarande inte hur något av talen skulle kunna vara större än eller lika med 10, eftersom du redan tidigare har sagt att alla x_i <10. Jag förstår inte heller varför du räknar med kombinationer, eftersom det inte står att varje tal bara kan användas en gång.

Jag skulle nog helt enkelt göra ett stort träddiagram för att lösa den här uppgiften, eller någon annan sorts tabell.

3060 - 126 - 70*4 är 2654, inte 2645.

Men med ett litet program får jag också svaret 2654.

Smaragdalena skrev:
Jag förstår fortfarande inte hur något av talen skulle kunna vara större än eller lika med 10, eftersom du redan tidigare har sagt att alla x_i <10. Jag förstår inte heller varför du räknar med kombinationer, eftersom det inte står att varje tal bara kan användas en gång.
Jag skulle nog helt enkelt göra ett stort träddiagram för att lösa den här uppgiften, eller någon annan sorts tabell.

Jag har lite svårt att förklara hur jag tänker i det här fallet, men det är den här typen av problem det rör sig om: https://en.m.wikipedia.org/wiki/Stars_and_bars_(combinatorics).

Laguna skrev:
3060 - 126 - 70*4 är 2654, inte 2645.
Men med ett litet program får jag också svaret 2654.

Tack så mycket, då känner jag mig lite tryggare i min lösning! Och såklart är det så, var lite trött när jag skrev inlägget :P

Svara

Visa senaste svar