Fungrim home page

Partition function

Table of contents: Specific values - Generating functions - Sums and recurrence relations - Congruences - Inequalities - Asymptotic expansions - Hardy-Ramanujan-Rademacher formula

f5e153
Symbol: PartitionsP — p(n)p(n) — Integer partition function
8eed2c
p(n)=A000041 ⁣(n)p(n) = \text{A000041}\!\left(n\right)

Specific values

856db2
Table of p(n)p(n) for 0≤n≤2000 \le n \le 200
cebe1b
p(0)=#{[]}=1p(0) = \# \left\{\left[\right]\right\} = 1
e84642
p(1)=#{[1]}=1p(1) = \# \left\{\left[1\right]\right\} = 1
b2583f
p(2)=#{[2],[1,1]}=2p(2) = \# \left\{\left[2\right], \left[1, 1\right]\right\} = 2
7ef291
p(3)=#{[3],[2,1],[1,1,1]}=3p(3) = \# \left\{\left[3\right], \left[2, 1\right], \left[1, 1, 1\right]\right\} = 3
6018a4
p(4)=#{[4],[3,1],[2,2],[2,1,1],[1,1,1,1]}=5p(4) = \# \left\{\left[4\right], \left[3, 1\right], \left[2, 2\right], \left[2, 1, 1\right], \left[1, 1, 1, 1\right]\right\} = 5
cd3013
p ⁣(−n)=0p\!\left(-n\right) = 0
9933df
Table of p ⁣(10n)p\!\left({10}^{n}\right) to 50 digits for 0≤n≤300 \le n \le 30

Generating functions

599417
∑n=0∞p(n)qn=1ϕ(q)\sum_{n=0}^{\infty} p(n) {q}^{n} = \frac{1}{\phi(q)}

Sums and recurrence relations

acdce8
p(n)=∑k=1n+1(−1)k+1(p ⁣(n−k(3k−1)2)+p ⁣(n−k(3k+1)2))p(n) = \sum_{k=1}^{n + 1} {\left(-1\right)}^{k + 1} \left(p\!\left(n - \frac{k \left(3 k - 1\right)}{2}\right) + p\!\left(n - \frac{k \left(3 k + 1\right)}{2}\right)\right)
4d2e45
p(n)=1n∑k=0n−1σ1 ⁣(n−k)p(k)p(n) = \frac{1}{n} \sum_{k=0}^{n - 1} \sigma_{1}\!\left(n - k\right) p(k)

Congruences

d8e37d
p ⁣(5n+4)≡0(mod5)p\!\left(5 n + 4\right) \equiv 0 \pmod {5}
89260d
p ⁣(7n+5)≡0(mod7)p\!\left(7 n + 5\right) \equiv 0 \pmod {7}
dacd74
p ⁣(11n+6)≡0(mod11)p\!\left(11 n + 6\right) \equiv 0 \pmod {11}

Inequalities

f7407a
p(n)≤p ⁣(n+1)p(n) \le p\!\left(n + 1\right)
df3c07
p(n)<p ⁣(n+1)p(n) < p\!\left(n + 1\right)
d72123
p(n)≥np(n) \ge n
e1f15b
p(n)≤2np(n) \le {2}^{n}

Asymptotic expansions

7697af
p(n)∼eπ2n/34n3,  n→∞p(n) \sim \frac{{e}^{\pi \sqrt{2 n / 3}}}{4 n \sqrt{3}}, \; n \to \infty

Hardy-Ramanujan-Rademacher formula

fb7a63
p(n)=2π(24n−1)3/4∑k=1∞A ⁣(n,k)kI3/2 ⁣(πk23(n−124))p(n) = \frac{2 \pi}{{\left(24 n - 1\right)}^{3 / 4}} \sum_{k=1}^{\infty} \frac{A\!\left(n, k\right)}{k} I_{3 / 2}\!\left(\frac{\pi}{k} \sqrt{\frac{2}{3} \left(n - \frac{1}{24}\right)}\right)
3eae25
Symbol: HardyRamanujanA — A ⁣(n,k)A\!\left(n, k\right) — Exponential sum in the Hardy-Ramanujan-Rademacher formula
5adbc3
A ⁣(n,k)=∑r=0k−1δ(gcd⁡(r,k),1)exp⁡ ⁣(πi(s ⁣(r,k)−2nrk))A\!\left(n, k\right) = \sum_{r=0}^{k - 1} \delta_{(\gcd\left(r, k\right),1)} \exp\!\left(\pi i \left(s\!\left(r, k\right) - \frac{2 n r}{k}\right)\right)
afd27a
∣p(n)−2π(24n−1)3/4∑k=1NA ⁣(n,k)kI3/2 ⁣(πk23(n−124))∣≤44π22253N+π275Nn−1sinh⁡ ⁣(πN2n3)\left|p(n) - \frac{2 \pi}{{\left(24 n - 1\right)}^{3 / 4}} \sum_{k=1}^{N} \frac{A\!\left(n, k\right)}{k} I_{3 / 2}\!\left(\frac{\pi}{k} \sqrt{\frac{2}{3} \left(n - \frac{1}{24}\right)}\right)\right| \le \frac{44 {\pi}^{2}}{225 \sqrt{3 N}} + \frac{\pi \sqrt{2}}{75} \sqrt{\frac{N}{n - 1}} \sinh\!\left(\frac{\pi}{N} \sqrt{\frac{2 n}{3}}\right)

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