Factorials and binomial coefficients

Symbol: Factorial $n !$ Factorial
Symbol: Binomial ${n \choose k}$ Binomial coefficient
Symbol: RisingFactorial $\left(z\right)_{k}$ Rising factorial
Symbol: FallingFactorial $\left(z\right)^{\underline{k}}$ Falling factorial
$n ! = \text{A000142}\!\left(n\right)$

Specific values

Related topics: Specific values of factorials and binomial coefficients

Table of $n !$ for $0 \le n \le 30$
Table of ${n \choose k}$ for $0 \le n \le 15$ and $0 \le k \le 15$
Table of $\left(n\right)_{k}$ for $0 \le n \le 10$ and $0 \le k \le 10$
Table of $\left(n\right)^{\underline{k}}$ for $0 \le n \le 10$ and $0 \le k \le 10$

Product representations

$n ! = \prod_{k=1}^{n} k$
${z \choose k} = \prod_{i=1}^{k} \frac{z + 1 - i}{i} = \prod_{i=0}^{k - 1} \frac{z - i}{i + 1}$
$\left(z\right)_{k} = \prod_{i=1}^{k} \left(z + i - 1\right) = \prod_{i=0}^{k - 1} \left(z + i\right)$
$\left(z\right)^{\underline{k}} = \prod_{i=1}^{k} \left(z - i + 1\right) = \prod_{i=0}^{k - 1} \left(z - i\right)$

Functional equations and recurrence relations

$n ! = n \left(n - 1\right)!$
${n \choose k} = {n \choose n - k}$
${z + 1 \choose k + 1} = {z \choose k} + {z \choose k + 1}$
${z \choose k + 1} = \frac{z - k}{k + 1} {z \choose k}$
${z + 1 \choose k + 1} = \frac{z + 1}{k + 1} {z \choose k}$
${z \choose k} = {\left(-1\right)}^{k} {k - z - 1 \choose k}$
$\left(z\right)_{k + m} = \left(z\right)_{k} \left(z + k\right)_{m}$
$\left(z\right)_{2 k} = {4}^{k} \left(\frac{z}{2}\right)_{k} \left(\frac{z + 1}{2}\right)_{k}$
$\left(-z\right)_{k} = {\left(-1\right)}^{k} \left(z - k + 1\right)_{k}$
$\left(z + 1\right)_{k} = \frac{z + k}{z} \left(z\right)_{k}$
$\left(z\right)_{k + 1} = \left(z + k\right) \left(z\right)_{k}$

Connection formulas

$n ! = \Gamma\!\left(n + 1\right)$
${z \choose k} = \frac{\Gamma\!\left(z + 1\right)}{\Gamma\!\left(k + 1\right) \Gamma\!\left(z - k + 1\right)}$
${n \choose k} = \frac{n !}{k ! \left(n - k\right)!}$
${z \choose k} = \frac{\left(z\right)^{\underline{k}}}{k !}$
${z \choose k} = \frac{\left(z - k + 1\right)_{k}}{k !}$
$\left(z\right)_{k} = \frac{\Gamma\!\left(z + k\right)}{\Gamma(z)}$
$\left(z\right)_{k} = \left(z + k - 1\right)^{\underline{k}}$
$\left(n\right)_{k} = \frac{\left(n + k - 1\right)!}{\left(n - 1\right)!}$

Sums and generating functions

$\sum_{k=0}^{n} {n \choose k} {x}^{k} {y}^{n - k} = {\left(x + y\right)}^{n}$
$\sum_{k=0}^{\infty} {z \choose k} {x}^{k} = {\left(1 + x\right)}^{z}$
$\sum_{k=0}^{n} {n \choose k} = {2}^{n}$
${z \choose k} = \sum_{i=0}^{k} s\!\left(k, i\right) \frac{{z}^{i}}{k !}$
${e}^{z} = \sum_{k=0}^{\infty} \frac{{z}^{k}}{k !}$
${e}^{x + y} = \sum_{k=0}^{\infty} \sum_{n=0}^{\infty} {n + k \choose k} \frac{{x}^{k} {y}^{n}}{\left(n + k\right)!}$
$\sum_{n=0}^{\infty} {2 n \choose n} \frac{{x}^{n}}{n !} = {e}^{2 x} I_{0}\!\left(2 x\right)$
$\sum_{n=0}^{\infty} {2 n \choose n} {x}^{n} = \frac{1}{\sqrt{1 - 4 x}}$
$\sum_{n=0}^{\infty} \frac{1}{{2 n \choose n}} {x}^{n} = \,{}_2F_1\!\left(1, 1, \frac{1}{2}, \frac{x}{4}\right) = \frac{1}{1 - u} + \frac{\sqrt{u} \operatorname{asin}\!\left(\sqrt{u}\right)}{{\left(1 - u\right)}^{3 / 2}}\; \text{ where } u = \frac{x}{4}$

Bounds and inequalities

$n ! \le {n}^{n}$
$n ! > {e}^{n}$
$n ! > {C}^{n}$
${n \choose k} \le \frac{{n}^{k}}{k !}$
${n \choose k} \ge \frac{{n}^{k}}{{k}^{k}}$
${n \choose k} \le \frac{{\left(n e\right)}^{k}}{{k}^{k}}$
${n \choose k} \le \frac{{n}^{n}}{{k}^{k} {\left(n - k\right)}^{n - k}}$
$n ! < \sqrt{2 \pi} {n}^{n + 1 / 2} {e}^{-n} \exp\!\left(\frac{1}{12 n}\right)$
$n ! > \sqrt{2 \pi} {n}^{n + 1 / 2} {e}^{-n} \exp\!\left(\frac{1}{12 n + 1}\right)$
${n \choose k} < \frac{1}{\sqrt{2 \pi}} \sqrt{\frac{n}{k \left(n - k\right)}} \frac{{n}^{n}}{{k}^{k} {\left(n - k\right)}^{n - k}}$
${n \choose k} \ge \frac{1}{\sqrt{8}} \sqrt{\frac{n}{k \left(n - k\right)}} \frac{{n}^{n}}{{k}^{k} {\left(n - k\right)}^{n - k}}$
${2 n \choose n} < \frac{{4}^{n}}{\sqrt{\pi n}}$
${n \choose k} \le {2}^{n}$

Copyright (C) Fredrik Johansson and contributors. Fungrim is provided under the MIT license. The source code is on GitHub.

2021-03-15 19:12:00.328586 UTC