q-binomial 学习笔记

· · 个人记录

定义

感觉网上的 q-binomial 定义地比较抽象，这里给一个自己理解的定义。

考虑一个 n 个元素中取出 m 个的方案，记 k 为是否选中构成的 01 序列逆序对数量。

令这一方案的权值为 q ^ k，记所有这样的方案权值总和为 \begin{bmatrix} n \\ m \end{bmatrix}_q，即 q-binomial。

当 q = 1 时，有

\begin{bmatrix} n + m \\ n \end{bmatrix}_1 = \binom{n + m}{m}

性质

很多组合数的性质可以扩展到 q-binomial，这里不加证明地给出。

前面几个都易于组合意义理解，最后一个我还不太会，有没有人教教我 /kel

组合数性质：

\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}

q-binomial 性质：

\begin{bmatrix} n \\ m \end{bmatrix}_q = q ^ m \begin{bmatrix} n - 1 \\ m \end{bmatrix}_q + \begin{bmatrix} n - 1 \\ m - 1 \end{bmatrix}_q

组合数性质：

\binom{n + m}{n} = \binom{n + m}{m}

q-binomial 性质：

\begin{bmatrix} n + m \\ n \end{bmatrix}_q = \begin{bmatrix} n + m \\ m \end{bmatrix}_q

组合数性质：

\binom{n + m}{n} = \sum \limits_{i = 0} ^ n \binom{n}{i} \binom{m}{n - i}

q-binomial 性质：

\begin{bmatrix} n + m \\ n \end{bmatrix}_q = \sum \limits_{i = 0} ^ n q ^ {i(m - n + i)} \begin{bmatrix} n \\ i \end{bmatrix}_q \begin{bmatrix} m \\ n - i \end{bmatrix}_q

组合数性质：

(x + y) ^ n = \sum \limits_{i = 0} ^ n \binom{n}{i} x ^ i y ^ {n - i}

q-binomial 性质:

\prod \limits_{i = 1} ^ {n} (q ^ i x + y) = \sum \limits_{i = 0} ^ n q ^ {\frac{i(i + 1)}{2}} \begin{bmatrix} n \\ i \end{bmatrix}_q x ^ i y ^ {n - i}

组合数性质：

\binom{n}{m} = \dfrac{n!}{m!(n - m)!}

q-binomial 性质（对于 q \ne 1）：

令

[n]_q = \sum \limits_{i = 0} ^ {n - 1} q ^ i = \dfrac{q ^ n - 1}{q - 1} [n]_q! = \prod_{i = 1} ^ n [i]_q

则

\begin{bmatrix} n \\ m \end{bmatrix}_q = \dfrac{[n]_q!}{[m]_q! [n - m]_q!}

化简后，分母上的 q - 1 可以被消去。

生成函数

q-binomial 的生成函数如下：

\prod \limits_{i = 0} ^ n \dfrac{1}{1 - q ^ i x} = \sum \limits_{i = 0} ^ {\infty} \begin{bmatrix} n \\ i \end{bmatrix}_q x ^ i

可以组合意义理解。

习题