TOPICS
Search

Perfect Partition


A perfect partition is a partition of a number n whose elements uniquely generate any number 1, 2, ..., n. {1,1,...,1_()_(n)} is always a perfect partition of n, and every perfect partition must contain a 1.

The following table gives the first several perfect partitions for small n.

na(n)perfect partitions
11{1}
21{1,1}
32{2,1}, {1,1,1}
41{1,1,1,1}
53{3,1,1}, {2,2,1}, {1,1,1,1,1}
61{1,1,1,1,1,1}

The numbers of perfect partitions a(n) of n for n=1, 2, ... are given by 1, 1, 2, 1, 3, 1, 4, 2, 3, ... (OEIS A002033). For p^k a prime power, the number of perfect partitions a(p^k-1) is given by

 a(p^k-1)=2^(k-1).

The number of perfect partitions a(n) of n is equal to the number of ordered factorizations H(n+1) of n+1 (Goulden and Jackson 1983, p. 94).


See also

Ordered Factorization, Partition

Explore with Wolfram|Alpha

References

Cohen, D. I. A. Basic Techniques of Combinatorial Theory. New York: Wiley and Sons, p. 97, 1978.Goulden, I. P. and Jackson, D. M. Problem 2.5.12 in Combinatorial Enumeration. New York: Wiley, 1983.Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 140-143, 1985.Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, 1958.Sloane, N. J. A. Sequences A002033/M0131 and A035341 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Perfect Partition

Cite this as:

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

Subject classifications