二項係数
定義
$ \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n}{1} \times \frac{n - 1}{2} \times \cdots \times \frac{n - k + 1}{k}
公式
基本
$ \binom{n}{k} = \binom{n}{n - k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}
$ k\binom{n}{k} = n\binom{n-1}{k-1}
$ \binom{n}{k} = \binom{n}{k - 1} \times \frac{n - k + 1}{k} = \binom{n - 1}{k} \times \frac{n}{n - k}
総和
$ \sum_{k=0}^{n} x^k \binom{n}{k} = (x + 1)^n
$ \sum_{k = 0}^{n} \binom{n}{k} = 2^n
$ \sum_{k = 0}^{n} (-1)^k \binom{n}{k} = 0
$ \sum_{k=0}^{\frac{n}{2}} \binom{n}{2k} = \sum_{k=0}^{\frac{n}{2}} \binom{n}{2k + 1} = 2^{n-1}
$ \sum_{k=1}^{n} k \binom{n}{k} = 2^{n - 1} n
$ \sum_{k=1}^{n} k^2 \binom{n}{k} = 2^{n - 1} \frac{(n + 1) n}{2}
$ \sum_{i = k}^{n} \binom{i}{k} = \binom{n+1}{k+1}（ホッケースティック恒等式）
$ \sum_{k = 0}^{n} \binom{p}{k} \binom{q}{n - k} = \binom{p+q}{n}（ヴァンデルモンドの畳み込み）
二乗和
$ \sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}
Dixon の恒等式
$ \sum_{k=0}^{n} (-1)^k \binom{2n}{n + k}^3 = \frac{(3n)!}{(n!)^3}
Lucasの定理
$ \binom{m}{n} \equiv \prod_{i=0}^{k} \binom{m_i}{n_i} \pmod p
ただし、$ m = \sum_{i=0}^{k} m_i p^i, n = \sum_{i=0}^{k} n_i p^iであり、$ m_i<n_iのとき$ \binom{m_i}{n_i}=0
参考
性質
$ \left.n\middle\vert\binom{n}{k}\right.\quad (1 \lt k \lt n)
$ MODで割ったあまりの計算
$ MODが素数のとき
前計算$ O(n)、クエリ$ O(1)
code:Ruby
class Binom
def initialize(n)
@fac = 1, 1 # @faci = i の階乗 @fin = 1, 1 # @fini = i の階乗の逆元 (2 .. n).each do |i|
@invi = MOD - @invMOD % i * (MOD / i) % MOD # 拡張ユークリッドの互除法 end
end
def binom(n, k)
return 0 if n < k or n < 0 or k < 0
@facn * @fink % MOD * @finn - k % MOD end
end
前処理$ O(k)、クエリ$ O(k)（$ nが固定なら前処理$ O(k)、クエリ$ O(1)）
逆元だけを前計算
code:Ruby
class BinomLargeN
def initialize(k)
(2 .. k).each do |i|
@invi = MOD - @invMOD % i * (MOD / i) % MOD end
end
def binom(n, k)
(1 .. k).inject(1) { |x, i| x * (n - i + 1) % MOD * @invi % MOD } end
end
$ nが固定
code:Ruby
# @returni = binom(n, i) (i <= k) def build_binom(n, k)
(1 .. k).each do |i|
invi = MOD - invMOD % i * (MOD / i) % MOD binom << binom-1 * (n - i + 1) % MOD * invi % MOD end
binom
end
クエリ$ O(k \log MOD)
code:Ruby
def binom(n, k)
(1 .. k).inject(1) { |x, i| x * (n - i + 1) % MOD * i.pow(MOD - 2, MOD) % MOD }
end
$ MODが合成数のとき
逆元が存在しなかったりするので上のやり方だと無理
$ MOD = \prod_i p_i^{e_i}（$ p_iは素数）のとき、各$ iについて$ \binom{n}{k} \bmod p_i^{e_i}を求めて中国剰余定理で復元する
通常母関数
$ \binom{n}{k} = [x^k] (x + 1)^n
指数型母関数
階乗の指数型母関数は$ \frac{1}{1 - x} = \sum_{n = 0}^{\infty} \frac{n!}{n!} x^n
→二項係数の指数型母関数は？
その他
グリッドに思いを馳せる