Fungrim home page

Factorials and binomial coefficients

Table of contents: Specific values - Product representations - Functional equations and recurrence relations - Connection formulas - Sums and generating functions - Bounds and inequalities

81aeba
Symbol: Factorial n!n ! Factorial
def588
Symbol: Binomial (nk){n \choose k} Binomial coefficient
579595
Symbol: RisingFactorial (z)k\left(z\right)_{k} Rising factorial
3c2469
Symbol: FallingFactorial (z)k\left(z\right)^{\underline{k}} Falling factorial
d12aa0
n!=A000142 ⁣(n)n ! = \text{A000142}\!\left(n\right)

Specific values

Related topics: Specific values of factorials and binomial coefficients

3009a7
Table of n!n ! for 0n300 \le n \le 30
fb5d88
Table of (nk){n \choose k} for 0n150 \le n \le 15 and 0k150 \le k \le 15
29741c
Table of (n)k\left(n\right)_{k} for 0n100 \le n \le 10 and 0k100 \le k \le 10
63f368
Table of (n)k\left(n\right)^{\underline{k}} for 0n100 \le n \le 10 and 0k100 \le k \le 10

Product representations

55bf43
n!=k=1nkn ! = \prod_{k=1}^{n} k
788fa4
(zk)=i=1kz+1ii=i=0k1zii+1{z \choose k} = \prod_{i=1}^{k} \frac{z + 1 - i}{i} = \prod_{i=0}^{k - 1} \frac{z - i}{i + 1}
19f13b
(z)k=i=1k(z+i1)=i=0k1(z+i)\left(z\right)_{k} = \prod_{i=1}^{k} \left(z + i - 1\right) = \prod_{i=0}^{k - 1} \left(z + i\right)
a5852d
(z)k=i=1k(zi+1)=i=0k1(zi)\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

4f20ff
n!=n(n1)!n ! = n \left(n - 1\right)!
2362af
(nk)=(nnk){n \choose k} = {n \choose n - k}
081188
(z+1k+1)=(zk)+(zk+1){z + 1 \choose k + 1} = {z \choose k} + {z \choose k + 1}
209fc8
(zk+1)=zkk+1(zk){z \choose k + 1} = \frac{z - k}{k + 1} {z \choose k}
6e1f13
(z+1k+1)=z+1k+1(zk){z + 1 \choose k + 1} = \frac{z + 1}{k + 1} {z \choose k}
56d4ff
(zk)=(1)k(kz1k){z \choose k} = {\left(-1\right)}^{k} {k - z - 1 \choose k}
02ee06
(z)k+m=(z)k(z+k)m\left(z\right)_{k + m} = \left(z\right)_{k} \left(z + k\right)_{m}
d651d1
(z)2k=4k(z2)k(z+12)k\left(z\right)_{2 k} = {4}^{k} \left(\frac{z}{2}\right)_{k} \left(\frac{z + 1}{2}\right)_{k}
c640bf
(z)k=(1)k(zk+1)k\left(-z\right)_{k} = {\left(-1\right)}^{k} \left(z - k + 1\right)_{k}
41f950
(z+1)k=z+kz(z)k\left(z + 1\right)_{k} = \frac{z + k}{z} \left(z\right)_{k}
fe9fb7
(z)k+1=(z+k)(z)k\left(z\right)_{k + 1} = \left(z + k\right) \left(z\right)_{k}

Connection formulas

62c6c9
n!=Γ ⁣(n+1)n ! = \Gamma\!\left(n + 1\right)
e87c43
(zk)=Γ ⁣(z+1)Γ ⁣(k+1)Γ ⁣(zk+1){z \choose k} = \frac{\Gamma\!\left(z + 1\right)}{\Gamma\!\left(k + 1\right) \Gamma\!\left(z - k + 1\right)}
332721
(nk)=n!k!(nk)!{n \choose k} = \frac{n !}{k ! \left(n - k\right)!}
1d5e92
(zk)=(z)kk!{z \choose k} = \frac{\left(z\right)^{\underline{k}}}{k !}
22ee07
(zk)=(zk+1)kk!{z \choose k} = \frac{\left(z - k + 1\right)_{k}}{k !}
c733f7
(z)k=Γ ⁣(z+k)Γ(z)\left(z\right)_{k} = \frac{\Gamma\!\left(z + k\right)}{\Gamma(z)}
e78989
(z)k=(z+k1)k\left(z\right)_{k} = \left(z + k - 1\right)^{\underline{k}}
30652c
(n)k=(n+k1)!(n1)!\left(n\right)_{k} = \frac{\left(n + k - 1\right)!}{\left(n - 1\right)!}

Sums and generating functions

6f7746
k=0n(nk)xkynk=(x+y)n\sum_{k=0}^{n} {n \choose k} {x}^{k} {y}^{n - k} = {\left(x + y\right)}^{n}
7c014b
k=0(zk)xk=(1+x)z\sum_{k=0}^{\infty} {z \choose k} {x}^{k} = {\left(1 + x\right)}^{z}
858c8f
k=0n(nk)=2n\sum_{k=0}^{n} {n \choose k} = {2}^{n}
4d1365
(zk)=i=0ks ⁣(k,i)zik!{z \choose k} = \sum_{i=0}^{k} s\!\left(k, i\right) \frac{{z}^{i}}{k !}
1635f5
ez=k=0zkk!{e}^{z} = \sum_{k=0}^{\infty} \frac{{z}^{k}}{k !}
65c610
ex+y=k=0n=0(n+kk)xkyn(n+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)!}
50f57e
n=0(2nn)xnn!=e2xI0 ⁣(2x)\sum_{n=0}^{\infty} {2 n \choose n} \frac{{x}^{n}}{n !} = {e}^{2 x} I_{0}\!\left(2 x\right)
2b2066
n=0(2nn)xn=114x\sum_{n=0}^{\infty} {2 n \choose n} {x}^{n} = \frac{1}{\sqrt{1 - 4 x}}
c9bcf7
n=01(2nn)xn=2F1 ⁣(1,1,12,x4)=11u+uasin ⁣(u)(1u)3/2   where u=x4\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

bb8a75
n!nnn ! \le {n}^{n}
f9efd0
n!>enn ! > {e}^{n}
25b7bd
n!>Cnn ! > {C}^{n}
6b3af0
(nk)nkk!{n \choose k} \le \frac{{n}^{k}}{k !}
001a0b
(nk)nkkk{n \choose k} \ge \frac{{n}^{k}}{{k}^{k}}
5d6f99
(nk)(ne)kkk{n \choose k} \le \frac{{\left(n e\right)}^{k}}{{k}^{k}}
4e7120
(nk)nnkk(nk)nk{n \choose k} \le \frac{{n}^{n}}{{k}^{k} {\left(n - k\right)}^{n - k}}
fc8d5d
n!<2πnn+1/2enexp ⁣(112n)n ! < \sqrt{2 \pi} {n}^{n + 1 / 2} {e}^{-n} \exp\!\left(\frac{1}{12 n}\right)
1745f5
n!>2πnn+1/2enexp ⁣(112n+1)n ! > \sqrt{2 \pi} {n}^{n + 1 / 2} {e}^{-n} \exp\!\left(\frac{1}{12 n + 1}\right)
d3baaf
(nk)<12πnk(nk)nnkk(nk)nk{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}}
5f7334
(nk)18nk(nk)nnkk(nk)nk{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}}
433d8b
(2nn)<4nπn{2 n \choose n} < \frac{{4}^{n}}{\sqrt{\pi n}}
fa3b53
(nk)2n{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