Stanley's Theorem

Stanley's theorem states that the total number of 1s that occur among all unordered partitions of a positive integer is equal to the sum of the numbers of distinct members of those partitions. The generalization sometimes known as Elder's theorem was discovered by R. P. Stanley in 1972 and submitted it to the "Problems and Solutions" section of the American Mathematical Monthly, where was rejected with the terse comment "A bit on the easy side, and using only a standard argument," presumably because the editors did not understand the actual statement and solution of the problem (Stanley 2004). The k=1 result was therefore first published as Problem 3.75 in Cohen (1978) after Cohen learned of the result from Stanley. For this reason, the case k=1 is sometimes called "Stanley's theorem."

As an example of the theorem, note that the partitions of 5 are {5}, {4,1}, {3,2}, {3,1,1}, {2,2,1}, {2,1,1,1}, {1,1,1,1,1}. There are a total of 0+1+0+2+1+3+5=12 1s in this list, which is equal to the sums of the numbers of unique terms in each partition: 1+2+2+2+2+2+1=12.

The numbers of 1s occurring in all partitions of n=1, 2, 3, ... are 1, 2, 4, 7, 12, 19, 30, 45, 67, ... (OEIS A000070). The nth term of this sequence is also equal to sum_(k=0)^(n-1)P(k), where P(k) is the partition function P.

See also

Elder's Theorem, Partition

Explore with Wolfram|Alpha


Cohen, D. I. A. Basic Techniques of Combinatorial Theory. New York: Wiley and Sons, 1978.Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer, pp. 6-8, 1985.Sloane, N. J. A. Sequence A000070/M1054 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. Exercise 1.26 in Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, p. 59, 1999.Stanley, R. P. "Errata and Addenda to Enumerative Combinatorics Volume 1, Second Printing." Rev. Feb. 13, 2004.

Referenced on Wolfram|Alpha

Stanley's Theorem

Cite this as:

Weisstein, Eric W. "Stanley's Theorem." From MathWorld--A Wolfram Web Resource.

Subject classifications