2021-10-27 yukicoder No.1100 Boxes yukicoder 競技プログラミング 解説 数え上げ 典型 式変形 形式的冪級数 問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個の互いに区別できるボールを個の互いに区別できる箱に入れる入れ方であって，ボールが1個も入っていない箱の個数が奇数であるようなものの数を求めよ．解説 が答えとなる(回の選択のうち，を選ぶと空箱，でボールを何個か選ぶという意味)． NTTによりについてこの値がで求められる．提出プログラムhttps://yukicoder.me/submissions/710608感想
![{\displaystyle\sum_{1\leq m\leq K, m:odd}[x^Ny^m]N!(e^x-1+y)^K}](https://chart.apis.google.com/chart?cht=tx&chl=%7B%5Cdisplaystyle%5Csum_%7B1%5Cleq%20m%5Cleq%20K%2C%20m%3Aodd%7D%5Bx%5ENy%5Em%5DN%21%28e%5Ex-1%2By%29%5EK%7D)
![{\displaystyle[x^Ny^m]N!(e^x-1+y)^K\\
\displaystyle=[x^Ny^m]N!\sum_{i=0}^{K}\binom{K}{i}e^{(K-i)x}\sum_{j=0}^{i}\binom{i}{j}y^{j}(-1)^{i-j}\\
\displaystyle=N!\sum_{i=m}^{K}\binom{K}{i}\frac{(K-i)^N}{N!}\binom{i}{m}(-1)^{i-m}\\
\displaystyle=\frac{K!}{m!}\sum_{i=m}^{K}\frac{(K-i)^N}{(K-i)!}\frac{(-1)^{i-m}}{(i-m)!}\\
\displaystyle=\frac{K!}{m!}\sum_{s+t=K-m}\frac{s^N}{s!}\frac{(-1)^t}{t!}}](https://chart.apis.google.com/chart?cht=tx&chl=%7B%5Cdisplaystyle%5Bx%5ENy%5Em%5DN%21%28e%5Ex-1%2By%29%5EK%5C%5C%0A%5Cdisplaystyle%3D%5Bx%5ENy%5Em%5DN%21%5Csum_%7Bi%3D0%7D%5E%7BK%7D%5Cbinom%7BK%7D%7Bi%7De%5E%7B%28K-i%29x%7D%5Csum_%7Bj%3D0%7D%5E%7Bi%7D%5Cbinom%7Bi%7D%7Bj%7Dy%5E%7Bj%7D%28-1%29%5E%7Bi-j%7D%5C%5C%0A%5Cdisplaystyle%3DN%21%5Csum_%7Bi%3Dm%7D%5E%7BK%7D%5Cbinom%7BK%7D%7Bi%7D%5Cfrac%7B%28K-i%29%5EN%7D%7BN%21%7D%5Cbinom%7Bi%7D%7Bm%7D%28-1%29%5E%7Bi-m%7D%5C%5C%0A%5Cdisplaystyle%3D%5Cfrac%7BK%21%7D%7Bm%21%7D%5Csum_%7Bi%3Dm%7D%5E%7BK%7D%5Cfrac%7B%28K-i%29%5EN%7D%7B%28K-i%29%21%7D%5Cfrac%7B%28-1%29%5E%7Bi-m%7D%7D%7B%28i-m%29%21%7D%5C%5C%0A%5Cdisplaystyle%3D%5Cfrac%7BK%21%7D%7Bm%21%7D%5Csum_%7Bs%2Bt%3DK-m%7D%5Cfrac%7Bs%5EN%7D%7Bs%21%7D%5Cfrac%7B%28-1%29%5Et%7D%7Bt%21%7D%7D)
についてこの値が
で求められる．