Mostralo$N_j(n,k,r)=\binom{k}{r} \sum_{i=r}^{k} (-1)^{i-r} \binom{k-r}{i-r} \frac{n!}{(j!)^i (n-ij)!} (k-i)^{n-ij}$
La domanda chiede let$N_j(n,k,r)$essere il numero di distribuzioni di$n$palle distinguibili in$k$urne distinguibili, in modo che$r$le urne sono occupate ciascuna da$j$palle. Mostra (sopra l'espressione)
$$ N_j(n,k,r)=\binom{k}{r} \sum_{i=r}^{k} (-1)^{i-r} \binom{k-r}{i-r} \frac{n!}{(j!)^i (n-ij)!} (k-i)^{n-ij} $$
Suppongo che ci sia bisogno di usare il numero di divisioni di un insieme finito con$n$in$r$sottoinsiemi ordinati, es$$C(n,k_1,...,k_{r-1})=\binom{n}{k_1,...,k_{r-1}}=\binom{n}{k_1}\binom{n-k_1}{k_2}...\binom{n-k_1-...-k_{r-2}}{k_{r-1}}=\frac{n!}{k_1!...k_{r-1}!k_r!}$$dove$k_r=n-k_1-...-k_{r-1}$. Sembra con$k_1=k_2=...=k_{r-1}=j$nella sommatoria, il coefficiente diventa$$C(n,j,...,j)=\frac{n!}{(j!)^i(n-ij)!}$$Sembra che ci sia un teorema rilevante, anche se non ampliato. Permettere$A_1,...,A_n$essere insiemi scambiabili di insiemi finiti$\Omega$, quindi il numero$N_{n,k}$di elementi$\Omega$contenuto in$k$fra$n$sottoinsiemi è dato da$$N_{n,k}=\sum_{r=k}^{n}(-1)^{r-k}\binom{r}{k}\binom{n}{r}v_r=\binom{n}{k}\sum_{r=k}^{n}(-1)^{r-k}\binom{n-k}{r-k}v_r$$dove$v_r=\sum N(A_{i_1},...,A_{i_r})$è il numero di distribuzioni di$n$palle distinguibili nel restante$r$urne distinguibili, per una selezione di indici$\{ i_1,...,i_r\}$per i set$\{ 1,...,n\}$. Sembra che il problema possa essere risolto da qui, ma non sono del tutto sicuro di come impostare la somma. Qualsiasi aiuto effettivo sarebbe apprezzato.
Risposte
Ci sono$n!$permutazioni delle sfere. Per ognuno di loro mettiamo il primo$j$palline nella prima urna, nella seconda$j$palline nella seconda urna, e così via, finché non abbiamo messo$j$palle in ciascuno dei primi$i$urne. Non ci interessa l'ordine delle palline all'interno di ciascuna delle prime$i$urne, quindi permutazioni delle palline che hanno le stesse palline in ognuna delle prime$i$blocchi di$j$le palle sono equivalenti. Inoltre, non ci interessa l'ordine dei rimanenti$n-ij$palle, perché le posizioneremo singolarmente, quindi ci sono$\frac{n!}{(j!)^i(n-ij)!}$classi distinguibili di permutazioni delle sfere.
Ora mettiamo ciascuno dei restanti$n-ij$palle in uno dei rimanenti$k-i$urne; questo può essere fatto dentro$(k-i)^{n-ij}$modi. Così,
$$\frac{n!}{(j!)^i(n-ij)!}(k-i)^{n-ij}\tag{1}$$
è il numero di distribuzioni di$n$palle distinguibili in$k$urne distinguibili in modo tale che ognuna delle prime$i$urne ottiene$j$palle. Chiaramente è anche il numero di distribuzioni di$n$palle distinguibili in$k$urne distinguibili in modo tale che ciascuna di qualsiasi serie designata di$i$urne ottiene$j$palle; era semplicemente più facile spiegare il primo fattore nei termini del primo$i$blocchi di$j$palle. Così,$(1)$è il$v_r$della tua espressione finale visualizzata e hai il tuo risultato.
Questo può anche essere fatto usando funzioni di generazione esponenziale. Abbiamo fin dai primi principi che utilizzano EGF
$$n! [z^n] {k\choose r} \left(\frac{z^j}{j!}\right)^r \left(\exp(z) - \frac{z^j}{j!}\right)^{k-r} \\ = n! [z^n] {k\choose r} \left(\frac{z^j}{j!}\right)^r \sum_{q=0}^{k-r} {k-r\choose q} (-1)^q \frac{z^{qj}}{(j!)^q} \exp((k-r-q)z) \\ = n! [z^n] {k\choose r} \left(\frac{z^j}{j!}\right)^r \sum_{q=r}^{k} {k-r\choose q-r} (-1)^{q-r} \frac{z^{(q-r)j}}{(j!)^{q-r}} \exp((k-q)z) \\ = n! [z^n] {k\choose r} \sum_{q=r}^{k} {k-r\choose q-r} (-1)^{q-r} \frac{z^{qj}}{(j!)^q} \exp((k-q)z) \\ = {k\choose r} \sum_{q=r}^{k} {k-r\choose q-r} (-1)^{q-r} [z^{n-qj}] \frac{n!}{(j!)^q} \exp((k-q)z) \\ = {k\choose r} \sum_{q=r}^{\min(k, \lfloor n/j \rfloor)} {k-r\choose q-r} (-1)^{q-r} \frac{n!}{(j!)^q \times (n-qj)!} (k-q)^{n-qj}.$$
Questa è l'affermazione. Qui abbiamo usato la classe combinatoria
$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SEQ}_{=r}(\textsc{SET}_{=j}(\mathcal{Z})) \textsc{SEQ}_{=k-r}(\textsc{SET}_{\ne j}(\mathcal{Z})).$$