Esiste una soluzione $ O (n) $ efficiente e semplice.
Espandendo il polinomio
$$ f_ {n, r } = \ left (x_1 + x_2 + \ cdots + x_r \ right) ^ n = \ sum_ {i_1, i_2, \ ldots, i_r} \ binom {n} {i_1, i_2, \ ldots, i_r} x_1 ^ {i_1} x_2 ^ {i_2} \ cdots x_r ^ {i_r}, $$
per ciascuno dei $ \ binom {r} {y} $ sottoinsiemi di $ y $ delle variabili ci sarà un termine come questo
$$ \ binom {n} {1,1, \ ldots, 1, i_ {y + 1}, \ ldots, i_r} \ left (x_1x_2 \ cdots x_y \ x_ {y + 1} ^ {i_ {y + 1}} \ cdots x_r ^ {i_r} \ right) $$
il cui coefficiente fornisce il numero di volte almeno $ y $ di le variabili vengono visualizzate solo una volta. Questo coefficiente può essere trovato differenziando $ f_ {n, r} $ rispetto a ciascuna di quelle $ y $ variabili, impostando i valori di queste variabili a $ 0 $ e impostando i valori delle rimanenti $ ry $ variabili a $ 1 $ , perché
$$ \ frac {\ partial ^ y} {\ partial x_1 \ partial x_2 \ cdots \ partial x_y} \ left (x_1x_2 \ cdots x_y \ x_ {y + 1} ^ {i_ { y + 1}} \ cdots x_r ^ {i_r} \ right) = x_ {y + 1} ^ {i_ {y + 1}} \ cdots x_r ^ {i_r} $$
restituisce $ 1 $ e tutti gli altri termini hanno almeno una delle prime variabili $ y $ come fattore, da cui valutano $ 0 $.
Calcolo di questa derivata per l'espressione originale di $ f_ {n, r} $ produce (utilizzando la notazione fattoriale decrescente per il coefficiente)
$$ \ eqalign {& \ frac {\ partial ^ y} {\ partial x_1 \ partial x_2 \ cdots \ partial x_y} \ sinistra (x_1 + x_2 + \ cdots + x_r \ destra) ^ n \\ & = n (n-1) \ cdots (n-y + 1) \ sinistra (x_1 + x_2 + \ cdots + x_r \ destra) ^ {ny} \\ & = n _ {(y)} \ left (x_1 + x_2 + \ cdots + x_r \ right) ^ {ny}.} $$
Quando $ y $ di $ x_i $ è uguale a $ 0 $ e il restante $ ry $ uguale $ 1 $, il lato destro restituisce
$$ n _ {(y)} (ry) ^ {ny}. $$
Moltiplicando per $ \ binom {r } {y} $ per tenere conto di tutte le possibili combinazioni di variabili $ y $ e l'applicazione del Principio di esclusione dall'inclusione ("PIE") produce il numero di volte in cui le variabili $ y $ appaiono esattamente una volta, che è
$$ \ binom {r} {y} \ sum_ {j = y} ^ {\ min (r, n)} (-1) ^ {jy} ( rj) ^ {nj} n _ {(j)} \ binom {ry} {jy}. $$
Dividendolo per $ r ^ n $ si ottengono le probabilità associate. Lo sforzo di calcolo è $ O (\ min (r, n) -y) $.
Niente è gratis! Come nella maggior parte delle applicazioni della Torta, questa è una somma alternata di termini che possono variare radicalmente in dimensioni, con il risultato finale molto più piccolo dei termini più grandi. Può esserci una perdita catastrofica di precisione, quindi è necessaria un'aritmetica ad alta precisione (o, meglio ancora, razionale esatto). Con quello disponibile, l'implementazione è notevolmente breve. Eccolo in Mathematica:
p [n_, k_]: = n ^ k; p [n_, 0]: = 1; f [n_, d_, k_]: = Binomiale [d, k] Somma [(- 1) ^ (jk) Binomiale [dk, jk] Fattoriale [n, j] p [ dj, nj], {j, k, Min [d, n]}]
Come esempio, tracciamo la distribuzione completa per un particolare $ n $ e $ r $:
Con [{n = 100, r = 100}, DiscretePlot [f [n, r, y] / r ^ n, {y, 0, Min [n, r]}]]
Come esempio, si consideri il caso $ n = 4 $, $ r = 3 $, e valori di $ y $ da $ 0 $ a $ 3 $. L'espansione di $ f_ {4,3} $ è
$$ x_1 ^ 4 + x_2 ^ 4 + x_3 ^ 4 \\\ color {blue} {+ 4 x_2 x_1 ^ 3 + 4 x_3 x_1 ^ 3 + 4 x_1 x_2 ^ 3 + 4 x_3x_2 ^ 3 + 4 x_1 x_3 ^ 3 + 4 x_2x_3 ^ 3} \\ + 6 x_2 ^ 2 x_1 ^ 2 + 6 x_2 ^ 2 x_3 ^ 2 + 6 x_3 ^ 2 x_1 ^ 2 \\\ colore {rosso} {+ 12 x_1 x_2 x_3 ^ 2 +12 x_1 x_2 ^ 2 x_3 +12 x_1 ^ 2 x_2 x_3}. $$
Considera il calcolo per $ y = 1 $ .
-
I termini contenenti esattamente un $ x_1 $ sono
$$ \ color {blue} {4 x_1 x_2 ^ 3 + 4 x_1 x_3 ^ 3} + \ color {red} {12 x_1 x_2 x_3 ^ 2 +12 x_1 x_2 ^ 2 x_3}. $$
La somma di questi coefficienti è $ 4 + 4 + 12 + 12 = 32 $. Quindi stimeremmo che il numero totale di termini con uno solo di $ x_i $ sarebbe $ 3 \ times 32 = 96 $.
-
Non abbiamo ancora finito. I termini contenenti un $ x_1 $ e un altro $ x_i $ sono
$$ \ color {red} {12 x_1 x_2 x_3 ^ 2 + 12 x_1 x_2 ^ 2 x_3}. $$
Questo ci dice che quando abbiamo contato i termini $ x_1 $ in precedenza, abbiamo sovrastimato di $ 12 + 12 = 24 $. Il conteggio totale quindi è $ 3 \ volte 24 = 72 $.
-
Ora abbiamo finito, perché non sono possibili termini con esattamente un'istanza di tre lati.
Di conseguenza, il count for $ y = 1 $ è
$$ 96 - 72 + 0 = 24. $$
In effetti, questa è la somma dei coefficienti di
$ $ \ color {blu} {4 x_2 x_1 ^ 3 + 4 x_3 x_1 ^ 3 + 4 x_1 x_2 ^ 3 + 4 x_3x_2 ^ 3 + 4 x_1 x_3 ^ 3 + 4 x_2x_3 ^ 3}. $$