| Title:
|
An application of Pólya’s enumeration theorem to partitions of subsets of positive integers (English) |
| Author:
|
Wu, Xiaojun |
| Author:
|
Chao, Chong-Yun |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
55 |
| Issue:
|
3 |
| Year:
|
2005 |
| Pages:
|
611-623 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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)$. (English) |
| Keyword:
|
Pólya’s enumeration theorem |
| Keyword:
|
partitions of a positive integer into a non-empty subset of positive integers |
| Keyword:
|
distinct partitions of a positive integer into a non-empty subset of positive integers |
| Keyword:
|
recursive formulas and algorithms |
| MSC:
|
05A15 |
| MSC:
|
05A17 |
| MSC:
|
11P81 |
| idZBL:
|
Zbl 1081.05010 |
| idMR:
|
MR2153086 |
| . |
| Date available:
|
2009-09-24T11:25:58Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128006 |
| . |
| Reference:
|
[1] G. E. Andrews: The Theory of Partitions.Addison-Wesley, Reading, 1976. Zbl 0371.10001, MR 0557013 |
| Reference:
|
[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 |
| Reference:
|
[3] P. Flajolet and M. Soria: Gaussian limiting distributions for the number of components in combinatorial structures.J. Combin. Theory 53 (1990), 165–182. MR 1041444, 10.1016/0097-3165(90)90056-3 |
| Reference:
|
[4] F. Harary and E. M. Palmer: Graphical Enumeration.Academic Press, New York-London, 1973. MR 0357214 |
| Reference:
|
[5] D. E. Knuth: A note on solid partitions.Math. Comp. 24 (1970), 955–961. Zbl 0217.03402, MR 0277401, 10.1090/S0025-5718-1970-0277401-7 |
| Reference:
|
[6] G. Pólya: Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen.Acta Math. 68 (1937), 145–254. 10.1007/BF02546665 |
| Reference:
|
[7] G. Pólya and R. C. Read: Combinatorial Enumeration of Groups, Graphs and Chemical Compounds.Springer-Verlag, New York, 1987. MR 0884155 |
| . |
