二元生成函数

二元生成函数（bivariate generating function）用两个形式变量同时记录组合对象的两种参数。一个变量常记录大小，另一个标记某项统计量。保留第二个变量既能数出每种统计值的对象，也能通过代入和微分提取总数、均值与方差。

以二进制串为例，令 $a_{n,k}$ 为长度 $n$、含 $k$ 个一的串数。长度三时，多项式是 $1+3u+3u^2+u^3$：例如 $u^2$ 对应 $011,101,110$ 三个串。此时 $u$ 只标记一的数量，并不代表某个串中数字一的概率。

两个系数指标

若每个大小 $n$ 只有有限多个对象，定义普通二元生成函数 $$F(x,u)=\sum _{n\ge 0}\sum _{k\ge 0}{a}_{n,k}{x}^n{u}^k,a_{n,k}=[x^n{u}^k]F(x,u).$$ 也可对 $x$ 使用指数形式 $x^n/n!$，但须明确归一化；“二元”只指两个变量，不规定是否带阶乘。

对二进制串，每个位置选零贡献 $x$，选一贡献 $xu$。固定长度 $n$ 的多项式为 $x^n(1+u{)}^n$；对所有长度求和得 $$F(x,u)=\frac{1}{1-x(1+u)}.$$ 也可从追加字符推导：空串贡献一，非空串由旧串追加零或一唯一产生，所以 $F=1+xF+xuF$，移项得同一式。展开 $(1+u{)}^n$，便得 $a_{n,k}=(\genfrac{}{}{0ex}{}{n}{k})$；范围外 $k<0$ 或 $k>n$ 的系数为零。

代入与微分提取统计量

设 $P_n(u)=[x^n]F(x,u)=\sum _k{a}_{n,k}{u}^k$。代入 $u=1$ 得总数 $P_n(1)$。在大小 $n$ 的所有对象中均匀抽取，若总数非零，统计量 $K$ 满足 $$𝔼[K]=\frac{{P_n}^{\prime }(1)}{P_n(1)},𝔼[K(K-1)]=\frac{{P_n}^{″}(1)}{P_n(1)}.$$ 证明只需逐项微分：$\frac{d}{du}{u}^k=k{u}^{k-1}$，在一处给每个对象赋权 $k$；二阶微分则赋权 $k(k-1)$。因此 $$\mathrm{Var}(K)=\frac{{P_n}^{″}(1)+{P_n}^{\prime }(1)}{P_n(1)}-{\left(\frac{{P_n}^{\prime }(1)}{P_n(1)}\right)}^2.$$ 二阶导数直接给的是下降阶乘矩，不能误当作 $𝔼[K^2]$。

例中 $P_n(u)=(1+u{)}^n$，对 $n\ge 2$ 得 $P_n(1)=2^n$、${P_n}^{\prime }(1)=n{2}^{n-1}$、${P_n}^{″}(1)=n(n-1)2^{n-2}$，所以均值为 $n/2$，方差为 $n/4$。$n=0,1$ 可直接从 $1,1+u$ 核对，也符合最后两个公式。长度三时总数八，统计加权和为 $3+6+3=12$，二次加权和为 $3+12+9=24$，于是均值 $3/2$、方差 $24/8-9/4=3/4$。

改变结构约束的变式

现在禁止相邻的一。长度 $n\ge 2$ 的合法串，若末尾是零，就来自任意长度 $n-1$ 合法串；若末尾是一，倒数第二位必须为零，可唯一拆为一个长度 $n-2$ 合法串再接 $01$。于是 $$P_n(u)=P_{n-1}(u)+u{P}_{n-2}(u),P_0=1,P_1=1+u.$$ 将递推乘 $x^n$ 后对 $n\ge 2$ 相加，左边为 $F-1-x(1+u)$，右边为 $x(F-1)+u{x}^{2}F$，所以 $$F(x,u)=\frac{1+xu}{1-x-u{x}^2}.$$ 长度三时 $P_3=1+3u+u^2$，合法串是 $000,001,010,100,101$。其中唯一含两个一的串为 $101$；总数五，均值 $(3+2)/5=1$，方差 $(3+4)/5-1=2/5$。同样长度、不同约束，不能继续把系数当成二项式分布。

形式代入 $u=1$ 要求每个固定大小的统计多项式可求和；本文的有限对象条件保证这一点。若允许同一大小下无限多统计值，代入可能不再是合法形式运算。把微分结果解释为概率还需给出抽样机制；均匀对象抽样与按非均匀权重抽样有不同分母，生成函数本身不会替读者决定概率模型。