Compositions with distinct parts
Tóm tắt
The number of compositionsC(n) of a positive integern into distinct parts can be considered as a natural analogue of the numberq(n) of distinct partitions ofn. We obtain an asymptotic estimate forC(n) and in addition show that the sequence {C(n, k)} of distinct compositions ofn withk distinct parts is unimodal. Our analysis is more complicated than is usual for composition problems. The results imply however that the behaviour of these functions is of comparable complexity to partition problems.
Tài liệu tham khảo
Erdös, P. andLehner, J.,The distribution of the number of summands in the partitions of a positive integer. Duke Math. J.,8 (1941), 335–345.
Greene, D. H. andKnuth, D. E.,Mathematics for the analysis of algorithms, 2nd ed. Birkhäuser, Boston, 1982.
Knopfmacher, A., Odlyzko, A. M., Richmond, B., Szekeres, G., andWormald, N.,On set partitions with unequal block sizes, preprint.
Roth, K. F. andSzekeres, G.,Some asymptotic formulae in the theory of partitions. Quart. J. Math. Oxford Ser. (2)5 (1954), 241–259.
Stanley, R. P.,Log-concave and unimodal sequences in algebra, combinatorics, and geometry. Ann. New York Acad. Sci.576 (1989), 500–535.
Szekeres, G.,Some asymptotic formulae in the theory of partitions (I). Quart. J. Math. (Oxford) (2),2 (1951), 85–108.
Szekeres, G.,Some asymptotic formulae in the theory of partitions (II). Quart. J. Math. Oxford (2),4 (1953), 96–111.