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\!\left(n\right) Integer partition function

Specific values

856db2
Table of p ⁣(n)p\!\left(n\right) for 0n2000 \le n \le 200
cebe1b
p ⁣(0)={[]}=1p\!\left(0\right) = \left|\left\{\left[\right]\right\}\right| = 1
e84642
p ⁣(1)={[1]}=1p\!\left(1\right) = \left|\left\{\left[1\right]\right\}\right| = 1
b2583f
p ⁣(2)={[2],[1,1]}=2p\!\left(2\right) = \left|\left\{\left[2\right], \left[1, 1\right]\right\}\right| = 2
7ef291
p ⁣(3)={[3],[2,1],[1,1,1]}=3p\!\left(3\right) = \left|\left\{\left[3\right], \left[2, 1\right], \left[1, 1, 1\right]\right\}\right| = 3
6018a4
p ⁣(4)={[4],[3,1],[2,2],[2,1,1],[1,1,1,1]}=5p\!\left(4\right) = \left|\left\{\left[4\right], \left[3, 1\right], \left[2, 2\right], \left[2, 1, 1\right], \left[1, 1, 1, 1\right]\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 0n300 \le n \le 30

Generating functions

599417
n=0p ⁣(n)qn=1ϕ ⁣(q)\sum_{n=0}^{\infty} p\!\left(n\right) {q}^{n} = \frac{1}{\phi\!\left(q\right)}

Sums and recurrence relations

acdce8
p ⁣(n)=k=1n+1(1)k+1(p ⁣(nk(3k1)2)+p ⁣(nk(3k+1)2))p\!\left(n\right) = \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)=1nk=0n1σ ⁣(nk)p ⁣(k)p\!\left(n\right) = \frac{1}{n} \sum_{k=0}^{n - 1} \sigma\!\left(n - k\right) p\!\left(k\right)

Congruences

d8e37d
p ⁣(5n+4)mod5=0p\!\left(5 n + 4\right) \bmod 5 = 0
89260d
p ⁣(7n+5)mod7=0p\!\left(7 n + 5\right) \bmod 7 = 0
dacd74
p ⁣(11n+6)mod11=0p\!\left(11 n + 6\right) \bmod 11 = 0

Inequalities

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

Asymptotic expansions

7697af
p ⁣(n)eπ2n/34n3,  np\!\left(n\right) \sim \frac{{e}^{\pi \sqrt{2 n / 3}}}{4 n \sqrt{3}}, \; n \to \infty

Hardy-Ramanujan-Rademacher formula

fb7a63
p ⁣(n)=2π(24n1)3/4k=1A ⁣(n,k)kI3/2 ⁣(πk23(n124))p\!\left(n\right) = \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=0k1δ(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π(24n1)3/4k=1NA ⁣(n,k)kI3/2 ⁣(πk23(n124))44π22253N+π275Nn1sinh ⁣(πN2n3)\left|p\!\left(n\right) - \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.

2019-06-18 07:49:59.356594 UTC