それを示す $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}$
質問は聞かせて $N_j(n,k,r)$ の分布の数である $n$ 識別可能なボールに $k$ 識別可能な壷、 $r$ 壷はそれぞれによって占められています $j$ボール。表示（式の上）
$$ 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} $$
有限集合の分割数を使用する必要があると思います。 $n$ に $r$ 順序付けられたサブセット、すなわち $$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!}$$ どこ $k_r=n-k_1-...-k_{r-1}$。それは$k_1=k_2=...=k_{r-1}=j$ 合計すると、係数は次のようになります。 $$C(n,j,...,j)=\frac{n!}{(j!)^i(n-ij)!}$$拡張されていませんが、関連する定理があるようです。しましょう$A_1,...,A_n$ 有限集合の交換可能な集合である $\Omega$、次に番号 $N_{n,k}$ 要素の $\Omega$ に含まれます $k$ の中で $n$ サブセットはによって与えられます $$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$$ どこ $v_r=\sum N(A_{i_1},...,A_{i_r})$ の分布の数です $n$ 残りの中に識別可能なボール $r$ インデックスの選択のための識別可能な壷 $\{ i_1,...,i_r\}$ セット用 $\{ 1,...,n\}$。ここから問題は解決できるようですが、合計の設定方法がよくわかりません。実際の助けをいただければ幸いです。
回答
がある $n!$ボールの順列。それらのそれぞれについて、最初に$j$ 最初の壷、2番目の壷にボール $j$ 2番目の壷にボールを入れます。 $j$ 最初のそれぞれにボール $i$壷。最初のそれぞれのボールの順序は気にしません$i$ 壷、したがって、最初のそれぞれに同じボールを持っているボールの順列 $i$ のブロック $j$ボールは同等です。残りの順番も気にしない$n-ij$ ボール、それぞれを個別に配置するので、 $\frac{n!}{(j!)^i(n-ij)!}$ ボールの順列の識別可能なクラス。
今、私たちは残りのそれぞれを置きます $n-ij$ 残りの1つにボール $k-i$壷; これはで行うことができます$(k-i)^{n-ij}$方法。したがって、
$$\frac{n!}{(j!)^i(n-ij)!}(k-i)^{n-ij}\tag{1}$$
の分布の数です $n$ 識別可能なボールに $k$ 識別可能な壷は、最初のそれぞれが $i$ 壷は取得します $j$ボール。明らかにそれはの分布の数でもあります$n$ 識別可能なボールに $k$ 指定されたセットのそれぞれがそのような方法で識別可能な壷 $i$ 壷は取得します $j$ボール; 最初の要素を最初の要素で説明するのが最も簡単でした$i$ のブロック $j$ボール。したがって、$(1)$ それは $v_r$ 最終的に表示された式の結果が得られます。
これは、指数母関数を使用して行うこともできます。私たちは最初の原則から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}.$$
これが主張です。ここでは、組み合わせクラスを使用しました
$$\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})).$$