标签：fr sum gather xF 二维 一类 binom 递推

解一类二维递推

WC 2021 讲课题为例

the following recurrence comes from WC2021
有n个桶和2n − 1个球，其中第i个桶可以装前2i − 1个球，一个
桶只能装一个球问有多少种方案取m个桶，再取m个球，再将这些球分别放在一个桶里;

暴力是下面递推式

	f[0][0]=1;
	fr(i,1,n)fr(j,0,n)f[i][j]=(j?(2i-j)*f[i-1][j-1]:0)+f[i-1][j];

要解出来，题解用的bijective proof.但是现在有暴力方法了

solution 1

idea from https://ac.nowcoder.com/acm/contest/57356/J

first change the index and it is equivalent to solve

f[0][0]=1
fr(i,1,n)fr(j,0,n)f[i][j]=(i+j)f[i-1][j]+(j?f[i-1][j-1]:0)

let \(F_i\) be the ogf. of \(f_{ij}\)

\[\begin{gather} F_i=(i+\vartheta)F_{i-1}+xF_{i-1}\\ F_n=\prod_{i=1}^n(i+\vartheta+x) ~ 1\\ =\sum_k {n+1 \brack k+1} (x+\vartheta)^k ~ 1\\ F_n[x^m]=\sum_k {n+1 \brack k+1} {k\brace m}\\ = \sum_k {n+1 \brack k+1} \frac{1}{m!}\sum_i \binom{m}{i}i^k(-1)^{m-i}\\ =\frac{1}{m!} \sum_i \binom{m}{i}\prod_{k=1}^n(i+k)(-1)^{m-i}\\ =\frac{n!}{m!}\sum_i\binom{i+n}{i}\binom{m}{i}(-1)^{m-i}\\=(n-m)!\binom{n}{m}^2 \end{gather} \]

so originally \(f_{nm}=m!\binom{n}{m}^2\)

solution 2

from https://www.luogu.com.cn/blog/command-block/hdu-duo-xiao-2023-round6-1007-competition

\[\begin{gather} F_i=iF_{i-1}+xF_{i-1}'+xF_{i-1}\\ e^xF_i=x(e^xF_{i-1})'+ie^xF_{i-1}\\ H_i=xH_{i-1}'+iH_{i-1}\\ h_{i,j}=(i+j)h_{i-1,j}=\binom{i+j}{i} \end{gather} \]

之后类似上面

标签：fr,sum,gather,xF,二维,一类,binom,递推
From： https://www.cnblogs.com/pigpigger/p/17614965.html