TOPICS
Search

Partition Function q


The number of partitions of n with k or fewer addends, or equivalently, into partitions with no element greater than k. This function is denoted q(n,k) or q_k(n). (Note that if "k or fewer" is changed to "exactly k" and "no element greater than k" to "greatest element equal to k," then the partition function P of two arguments is obtained.)

The q(n,k) such partitions can be enumerated in the Wolfram Language using IntegerPartitions[n, k].

For example, the q(5,3)=5 partitions of 5 of which the largest member is <=3 are {3,2}, {3,1,1}, {2,2,1}, {2,1,1,1}, and {1,1,1,1,1}. Similarly, the five partitions of 5 into three or fewer parts are {5}, {4,1}, {3,2}, {3,1,1}, and {2,2,1}.

The q(n,k) satisfy the recurrence relation

 q(n,k)=q(n,k-1)+q(n-k,k),

with q(n,0)=0, q(1,k)=1, and q(n,k)=P(n) for k>=n. The triangle of q(n,k) is given by

 1
1  2
1  2  3
1  3  4  5
1  3  5  6  7
1  4  7  9  10  11

(OEIS A026820).


See also

Partition Function P, Partition Function Q

Explore with Wolfram|Alpha

References

Sloane, N. J. A. Sequence A026820 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Partition Function q

Cite this as:

Weisstein, Eric W. "Partition Function q." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PartitionFunctionq.html

Subject classifications