简单常用数学定理整合

中国剩余定理

设
[latex] x \equiv a_1 \pmod{m_1} [/latex]
[latex] x \equiv a_2 \pmod{m_2} [/latex]
…
[latex] x \equiv a_n \pmod{m_n} [/latex]
若m ₁ , m ₂ , …, m _n 两两互质, 那么有唯一解x ₀ 满足:
$$ x_0 \equiv x_{1} M_{1}M_{1}^{-1} + x_{2} M_{2}M_{2}^{-1} + … + x_{n} M_{n}M_{n}^{-1} \pmod{\prod_{j=1}^n m_j} $$
其中: [latex] M_{i} = \frac{\prod_{j=1}^n m_j}{m_i}, M_{i}M_{i}^{-1} \equiv 1 \pmod{m_i} [/latex]

Catalan数

公式1:C _n = C(2n, n)/(n+1) = C(2n, n)-C(2n, n-1)
公式2:C ₀ =1,C ₁ =1, C _n = C ₀ *C _n-1 +C ₁ *C _n-2 +…+C _n-1 *C ₀
公式3:C _n = C _n-1 *(4*n-2)/(n+1);

Stirling数

第一类Stirling数:
s(i, j) 表示i个人站成j个循环排列的方案数。
那么有: s(i, j) = s(i-1, j)*(i-1) + s(i-1, j-1)
第二类Stirling数:
s(i, j) 表示把i个有区分物件放到j个非空盒子里的方案数。
递推式: s(i, j) = s(i-1, j)*j + s(i-1, j-1)

Wilson定理

当且仅当p为素数时：[latex]( p -1 )! \equiv -1 \pmod{p}[/latex]