Partition Function Q

Q(n), also denoted q(n) (Abramowitz and Stegun 1972, p. 825), gives the number of ways of writing the integer n as a sum of positive integers without regard to order with the constraint that all integers in a given partition are distinct. For example, Q(10)=10, since the partitions of 10 into distinct parts are {1,2,3,4}, {2,3,5}, {1,4,5}, {1,3,6}, {4,6}, {1,2,7}, {3,7}, {2,8}, {1,9}, {10}. The Q(n) function is implemented in the Wolfram Language as PartitionsQ[n]. Q(0) is generally defined to be 1.

The values for n=1, 2, ... are 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... (OEIS A000009).

The first few prime values of Q(n) are for indices 3, 4, 5, 7, 22, 70, 100, 495, 1247, 2072, 320397, 3335367, 16168775, 37472505, 52940251, 78840125, 81191852, ... (OEIS A035359), corresponding to values 2, 2, 3, 5, 89, 29927, 444793, 602644050950309, ... (OEIS A051005), with no others up to n=10^8 (M. Alekseyev, Jul. 10, 2015).

Q(n) is also the number of partitions of n with odd parts, sometimes denoted p(O,n) (Andrews 1998, p. 237).

The generating function for Q(n) is


where (q;a)_infty and (q)_infty areq-Pochhammer symbols.

This can also be interpreted as another form of the Jacobi triple product, written in terms of the Q-functions as


(Borwein and Borwein 1987, p. 64).

A recurrence relation is given by Q(0)=Q(1)=1 and



 s(n)={sigma_1(n)   for n an integer; 0   otherwise,



is the odd divisor function giving the sum of odd divisors of n: 1, 1, 4, 1, 6, 4, 8, ... (OEIS A000593; Abramowitz and Stegun 1972, p. 826).

Another recurrence relation is given by Q(0)=1 and



 s(n)={(-1)^j   for n=j(3j+/-1)/2; 0   otherwise

(E. Georgiadis, A. V. Sutherland, and K. S. Kedlaya; Sloane).

Q(n) satisfies the inequality


for n>=4. Q(n) has the asymptotic series


(Abramowitz and Stegun 1972, p. 826).

A Rademacher-like convergent series for Q(n) is given by



 A_k(n)=sum_(h=1; (h,k)=1)^ke^(pii[s(h,k)-s(2h,k)])e^(-2piihn/k)

(P. J. Grabner, pers. comm., Sep. 10, 2003; Hagis 1964ab, 1965), where (h,k)=1 means h and k are relatively prime,


is a Dedekind sum, |_x_| is the floor function, and J_0(x) is the zeroth order Bessel function of the first kind. Equation (16) corrects Abramowitz and Stegun (1972, p. 825), which erroneously state to be identical to the analogous expression in the formula for P(n)). (15) can also be written explicitly as


where _0F_1(;a;b;z) is a generalized hypergeometric function.

Let Q(n,k) denote the number of ways of partitioning n into exactly k distinct parts. For example, Q(10,3)=4 since there are four partitions of 10 into three distinct parts: {1,2,7}, {1,3,6}, {1,4,5}, and {2,3,5}. Q(n,k) is given by

 Q(n,k)=P(n-(k; 2),k),

where P(n,k) is the partition function P and (n; k) is a binomial coefficient (Comtet 1974, p. 116). The following table gives the first few values of Q(n,k) (OEIS A008289; Comtet 1974, pp. 115-116).


See also

Integer Sequence Primes, Odd Divisor Function, Partition Function P, Partition Function q, Partition Function Q Congruences

Related Wolfram sites

Explore with Wolfram|Alpha


Abramowitz, M. and Stegun, I. A. (Eds.). "Partitions into Distinct Parts." §24.2.2 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, pp. 825-826, 1972.Andrews, G. E. The Theory of Partitions. Cambridge, England: Cambridge University Press, pp. 7-8, 1998.Borwein, J. M. and Borwein, P. B. Pi & the AGM: A Study in Analytic Number Theory and Computational Complexity. New York: Wiley, 1987.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 114-115, 1974.Hagis, P. Jr. "Partitions Into Odd and Unequal Parts." Amer. J. Math. 86, 317-324, 1964a.Hagis, P. Jr. "On a Class of Partitions with Distinct Summands." Trans. Amer. Math. Soc. 112, 401-415, 1964b.Hagis, P. Jr. "A Correction of Some Theorems on Partitions." Trans. Amer. Math. Soc. 118, 550, 1965.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 58, 1990.Sloane, N. J. A. Sequences A000009/M0281, A000593/M3197, A008289, A035359 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.

Subject classifications