numero di permutazioni di due valori di calcolo, con una restrizione piste

Question

I stava pensando a modi per risolvere questa altra domanda circa il conteggio del numero di valori cui cifre somma a un target e deciso di provare il caso in cui l'intervallo è di forma [0, n ^ base). Quindi, in sostanza si ottiene N cifre indipendenti con cui lavorare, che è un problema semplice.

Il numero di modi N numeri naturali può sommare ad un obiettivo T è facile da calcolare. Se si pensa a come collocare N-1 divisori fra i bastoni T, si dovrebbe vedere la risposta è (T + N-1)! / (T! (N-1)!).

Tuttavia, i nostri numeri naturali N sono limitate a [0, base) e quindi ci saranno meno possibilità. Voglio trovare una formula semplice per questo caso.

La prima cosa che ho considerato è stato dedotto il numero di possibilità in cui 'base' dei bastoni erano stati sostituiti con un 'grosso bastone'. Purtroppo, alcune possibilità vengono conteggiati doppia perché hanno più punti di un 'grosso bastone' potrebbe essere inserito.

Tutte le idee?

Answer 1

È possibile utilizzare funzioni generatrici.

Supponendo che le questioni di ordine, allora si sta cercando per il coefficiente di x^T in

(1 + x + x^2 + ... + x^b)(1 + x + x^2 + .. + x^b) ... n times

 = (x^(b+1) - 1)^n/(x-1)^n

Usando teorema binomiale (funziona anche per -n), si dovrebbe essere in grado di scrivere si risponde come somma di prodotti di coefficienti binomiali.

Let b + 1 = B.

Usando teorema binomiale abbiamo

(x^(b+1) - 1)^n = Sum_{r=0}^{n} (-1)^(n-r)* (n choose r) x^(Br)

1/(x-1)^n = Sum (n+s-1 choose s) x^s

Quindi la risposta che ci serve è:

Sum (-1)^(n-r) * (n choose r)*(n+s-1 choose s)

per ogni r e s a condizione che

Br + s = T.