Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
Pólya’s enumeration theorem; partitions of a positive integer into a non-empty subset of positive integers; distinct partitions of a positive integer into a non-empty subset of positive integers; recursive formulas and algorithms
Pólya’s enumeration theorem; partitions of a positive integer into a non-empty subset of positive integers; distinct partitions of a positive integer into a non-empty subset of positive integers; recursive formulas and algorithms
Summary:
Let $S$ be a non-empty subset of positive integers. A partition of a positive integer $n$ into $S$ is a finite nondecreasing sequence of positive integers $a_1, a_2, \dots , a_r$ in $S$ with repetitions allowed such that $\sum ^r_{i=1} a_i = n$. Here we apply Pólya’s enumeration theorem to find the number $¶(n;S)$ of partitions of $n$ into $S$, and the number ${\mathrm DP}(n;S)$ of distinct partitions of $n$ into $S$. We also present recursive formulas for computing $¶(n;S)$ and ${\mathrm DP}(n;S)$.
References:
[1] G. E. Andrews: The Theory of Partitions. Addison-Wesley, Reading, 1976. MR 0557013 | Zbl 0371.10001
[2] N. G. De Bruijn: Pólya’s theory of counting. Appl. Combin. Math., E. F. Beckenbach (ed.), Wiley, New York, 1964, pp. 144–184. Zbl 0144.00601
[3] P. Flajolet and M. Soria: Gaussian limiting distributions for the number of components in combinatorial structures. J. Combin. Theory 53 (1990), 165–182. DOI 10.1016/0097-3165(90)90056-3 | MR 1041444
[4] F. Harary and E. M. Palmer: Graphical Enumeration. Academic Press, New York-London, 1973. MR 0357214
[5] D. E. Knuth: A note on solid partitions. Math. Comp. 24 (1970), 955–961. DOI 10.1090/S0025-5718-1970-0277401-7 | MR 0277401 | Zbl 0217.03402
[6] G. Pólya: Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145–254. DOI 10.1007/BF02546665
[7] G. Pólya and R. C. Read: Combinatorial Enumeration of Groups, Graphs and Chemical Compounds. Springer-Verlag, New York, 1987. MR 0884155
Search
Partner of
