Kombinatorikproblem (sträng med begränsat antal förekomster av tecken)

Har lurat lite på ett kombinatorikproblem som jag inte riktigt får till någon snygg formel för. Frågade om det i Frågor om ekvationer och andra naturvetenskapliga uppgifter för ett tag sedan, men fick inget svar så jag gör ett försök med en egen tråd.

Anta att vi har ett alfabete bestående av a stycken olika tecken. Utifrån detta skapar vi en sträng av längden n vars enda begränsning är att den inte får innehålla något tecken fler än m gånger. Hur beräknar man hur många sådana strängar det finns när n, m och a är givna?

Hmm. a^n/m1*m2*m3*+.....+*mn?

Fast öh, lita inte på mig. *förväntar korsfästning av matematikkunniga*

Förstår inte vad du menar? Var kommer plus-tecknen ifrån?

För att sätta dig på spår:

(c_0 + c_1x + c_2x^2 + ... + c_mx^m)^a
Hitta koefficienten framför x^n.

Hmmm... intressant ledtråd. Kommer dock inte riktigt på hur jag ska komma vidare. Som jag förstår det så blir väl koefficienten framför x^n om man utvecklar (1 + x +x^2 + ... + x^m)^a antalet olika strängar om ordningen på tecknen inte har någon betydelse i strängarna. Kan inte komma på något bra sätt att komma vidare och utnyttja dina c:n på något vettigt sätt, men det kan bero på att hjärnan gått i kvällsvila eller något efter en lång dag .

Det enda sättet jag ser är att sätta c_k = 1/(k!) och sen multiplicera den koefficienten framför x^n i det utvecklade polynomet med n!. Men sen är frågan hur man ska utnyttja det..