TOPICS
Search

Elder's Theorem


Elder's theorem is a generalization of Stanley's theorem which states that the total number of occurrences of an integer k among all unordered partitions of n is equal to the number of occasions that a part occurs k or more times in a partition, where a partition which contains r parts that each occur k or more times contributes r to the sum in question.

The general result 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 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." Independent proofs of the general case were given by Kirdar and Skyrme (1982), Paul Elder in 1984 (as reported by Honsberger 1985, p. 8), and Hoare (1986).

As an example of the theorem, note that the partitions of 4 are 4, 3+1, 2+2, 2+1+1, and 1+1+1+1, which contains 0+1+0+2+4=7 ones, 0+0+2+1+0=3 twos, 0+1+0+0+0=1 three, and 1+0+0+0+0=1 four. Similarly, a part occurs 1 or more times on 1+2+1+2+1=7 occasions, 2 or more times on 0+0+1+1+1=3 occasions, 3 or more times on 0+0+0+0+1=1 occasion, and 4 or more times on 0+0+0+0+1=1 occasion.

In general, the numbers of times that 1, 2, ..., n occur in the partitions of n are given by the following triangle:

n\k12345678
11
221
3411
47311
5124211
61984211
7301163211
84519963211

(OEIS A066633).


See also

Partition, Stanley's Theorem

Explore with Wolfram|Alpha

References

Cohen, D. I. A. Basic Techniques of Combinatorial Theory. New York: Wiley and Sons, 1978.Hoare, A. H. M. "An Involution of Blocks in the Partitions of n." Amer. Math. Monthly 93, 475-476, 1986.Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer, pp. 8-9, 1985.Kirdar, M. S. and Skyrme, T. H. R. "On an Identity Related to Partitions and Repetitions of Parts." Canad. J. Math. 34, 194-195, 1982.Sloane, N. J. A. Sequence A066633 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. http://www-math.mit.edu/~rstan/ec/newerr.ps.

Referenced on Wolfram|Alpha

Elder's Theorem

Cite this as:

Weisstein, Eric W. "Elder's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/EldersTheorem.html

Subject classifications