Computation of q-Binomial Coefficients with the P(n,m) Integer Partition Function

2022/05/30 by Kronenburg, M. J.
#Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2205.15013

Abstract

Using P(n,m), the number of integer partitions of n into exactly m parts, which was the subject of an earlier paper, P(n,m,p), the number of integer partitions of n into exactly m parts with each part at most p, can be computed in O(n²), and the q-binomial coefficient can be computed in O(n³). Using the definition of the q-binomial coefficient, some properties of the q-binomial coefficient and P(n,m,p) are derived. The q-multinomial coefficient can be computed as a product of q-binomial coefficients. A formula for Q(n,m,p), the number of integer partitions of n into exactly m distinct parts with each part at most p, is given. Some formulas for the number of integer partitions with each part between a minimum and a maximum are derived. A computer algebra program is listed implementing these algorithms using the computer algebra program of the earlier paper.

Related

• Combinatorial Formula for the Partition Function
• Computation of P(n,m), the Number of Integer Partitions of n into Exactly m Parts
• Distinct Partitions and Some q-Binomial Summation Identities
• On alternating sums of binomial coefficients and q-binomial coefficients
• Arithmetic of partitions and the q-bracket operator