公式解説と違う解き方をしたので書く
問題リンク
解答
以降ではボールの番号として$1,\ldots,2N$がついていて、$i$番目のボールと$i+N$番目のボールを同一視することとする。
まずこれを見て最初に思い浮かぶのは写像十二相である。写像十二相については以下のリンクを参照
ここで、①玉を区別する②箱を区別しない③1個以上を満たすものは$S(n,k)$、つまり第二種スターリング数である。今回はこれが大活躍する。
ところで、第二種スターリング数の求め方は普通に漸化式を使えば大丈夫である。
つまり、
$$S(n,k)=S(n - 1,k - 1)+kS(n - 1,k),S(0,0)=1,S(0,k)=0(k\geq 1)$$
からDPをすれば大丈夫である。DPテーブルの大きさは$O(N^2)$くらいなので余裕で間に合う。
さて、ただ単にスターリング数を使うだけで済むほどこの問題は単純じゃない。ここで、$2N$個のボールが全て区別できたら良いのだが、「1～Nのボールが各2個」なので大変である。答えを求めるためにはある程度の対称性の考慮をしなくてはいけない。
ここでは、$X,G$を以下のように定める。
$X$は、「$\{1,\ldots,2N\}\to\{1,\ldots,K\}$という写像であって、全射であるもの全体の集合」とする。
$G$を「$\{1,\ldots,2N\}$の置換のうち、$i,N + i$のスワップによって生成される群」とする。
これに対して、答えは
$$\frac{1}{|G|}\sum_{g\in G}\#\{x\in X;gx=x\}$$
である。ここで、$G\cong (\mathbb{Z}/2\mathbb{Z})^N$に注意。よって$|G|=2^N$である。
$G$の元のうち、$\mathrm{popcount}(g)=j$とおいて$j$ごとに場合分けをする。
ここで$0\leq j\leq N$である。
ここで、$i,i+N$を入れ替える作用に対して不変なものとしては、
①$i,i+N$が同じ箱に入っている
②$i,i+N$が違う箱に入っている
という可能性が考えられる。
ここで、①を満たすボールが$l$組、②を満たすボールが$j-l$組あると仮定する。
ここで、$0\leq l\leq j$である。
このとき、②を満たすグループで固まってなくてはいけない。
例えば1,1+N,2,2+N,3,3+N,4,4+Nというj-l=4組8個のボールが②を満たしていると仮定する。このとき、1が入っている箱の他に入れることができるのは2,2+N,3,3+N,4,4+Nしかありえない。そして仮に1が入っている箱に2+Nと3が同居しているならば、1+Nが入っている箱に2と3+Nが同居している必要がある。すると、結局箱は2つのグループに分けることができる。
ここで、グループAには②を満たすボールしか入っていない。グループBには②を満たすボールが入っていない。という条件を満たしている。
また、グループAは$i$が入っている箱と$i+N$が入っている箱を対応させれば、箱の数は偶数であることがわかる。
ここで、グループAを満たす箱がちょうど$2t$個あったと仮定する。ここで、$0\leq t\leq K$を満たす。
このとき、グループA上の割り当ての場合の数は、$S(j-l,t)\times \max\{2^{j-l-t},1\}$
となる。ここで、$2^{j-l-t}$を掛けているのは、$\{(1,2),(1+N,2+N)\}$と$\{(1,2+N),(1+N,2)\}$といったものを区別するためである。
一方、グループBの割り当ての場合の数は$S(2N-2(j-l)-l,K-2t)$となる。
よって、以下のようになる。
$$\#\{x;gx=x\}=\sum_{l=0}^{j}\sum_{t=0}^{K}S(2N-2j+l,K-2t)S(j-l,t)\max\{2^{j-l-t},1\}{}_{j}C_{l}$$
となる。
よって、最終的は答えは
$$\frac{1}{2^N}\sum_{j=0}^{N}\sum_{l=0}^{j}\sum_{t=0}^{K}S(2N-2j+l,K-2t)S(j-l,t)\max\{2^{j-l-t},1\}\frac{N!}{(N-j)!(j-l)!l!}$$
となる。
ここで、$n\lt k$のときは$S(n,k)=0$と定める。
スターリング数は前述の方法で前計算しておいて、階乗もおなじみのやり方で前計算しておけば$O(N^2K)$で計算することができる。
