Computation of P(n,m), the Number of Integer Partitions of n into Exactly m Parts

2022/05/10 by M. J. Kronenburg, Kronenburg, M. J.
Computer Science · Engineering · Mathematics · #Analytic Number Theory Research #Coding theory and cryptography #FOS: Mathematics #Number Theory (math.NT) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2205.04988

openalex publication_date 2022/05/10 · openalex created_date 2023/02/13 · openalex updated_date 2026/07/28

Abstract

Two algorithms for computing P(n,m), the number of integer partitions of n into exactly m parts, are described, and using a combination of these two algorithms, the resulting algorithm is O(n^3/2). The second algorithm uses a list of P(n), the number of integer partitions of n, which is cached and therefore needs to be computed only once. Computing this list is also O(n^3/2). With these algorithms also Q(n,m), the number of integer partitions of n into exactly m distinct parts, and a list of Q(n), the number of integer partitions of n into distinct parts, can be computed in O(n^3/2). A list of P(n,1)..P(n,n) and P(m,m)..P(n,m) can be computed in O(n²). A computer algebra program is listed implementing these algorithms, and some timings of this program are provided.

Related

• Computation of q-Binomial Coefficients with the P(n,m) Integer Partition Function
• Two Simple Ways of Generating the Partitions of (n+1) from the Partitions of n
• Simple alternative to the Hardy-Ramanujan-Rademacher formula for p(N)
• Number of partitions of n into parts not divisible by m
• Counting Partitions on the Abacus