The \(r\)-Stirling numbers. (English) Zbl 0535.05006
Let \(N(n,m,r)\) denote the number of permutations of \(\{1,\ldots,n\}\) with \(m\) cycles and such that the numbers \(1,\ldots,r\) occur in distinct cycles, and let \({\mathcal N}(n,m,r)\) denote the number of partitions of \(\{1,\ldots,n\}\) into \(m\) non-empty disjoint sets such that \(1,\ldots,r\) are in distinct subsets. These \(r\)-Stirling numbers of the first and second kind generalize the ordinary Stirling numbers which are given by \(r=1\). This paper presents a development of their properties, covering recurrence, orthogonality, generating functions and combinatorial identities. Some of the results have already been obtained from a different viewpoint by L. Carlitz [Fibonacci Q. 18, 147–162 (1980; Zbl 0428.05003), ibid. 18, 242–257 (1980; Zbl 0441.05003)].
Reviewer: Ian Anderson (Glasgow)
MSC:
| 11B73 | Bell and Stirling numbers |
| 05A05 | Permutations, words, matrices |
| 05A10 | Factorials, binomial coefficients, combinatorial functions |
| 05A15 | Exact enumeration problems, generating functions |
| 05A17 | Combinatorial aspects of partitions of integers |
| 05A19 | Combinatorial identities, bijective combinatorics |
Keywords:
distinct cycles; r-Stirling numbers of the first and second kind; recurrence; orthogonality; generating functions; combinatorial identitiesOnline Encyclopedia of Integer Sequences:
Unsigned 2-Stirling numbers of the first kind.Unsigned 3-Stirling numbers of the first kind.
Unsigned 4-Stirling numbers of the first kind.
Triangle read by rows: 2-Stirling numbers of the second kind.
Triangle of unsigned 2-Lah numbers.
5-Stirling numbers of the second kind.
2-Fubini numbers.
3-Fubini numbers.
4-Fubini numbers.
References:
| [1] | Broder, A. Z., A general expression for Abelian identities, (Cummings, L. J., Combinatorics on Words, Progress and Perspectives (1983), Academic Press: Academic Press New York) · Zbl 0561.05007 |
| [2] | Carlitz, L., Weighted Stirling numbers of the first and second kind—I, Thd Fibonacci Quarterly, 18, 147-162 (1980) · Zbl 0428.05003 |
| [3] | Carlitz, L., Weighted Stirling numbers of the first and second kind—II, The Fibonacci Quarterly, 18, 242-257 (1980) · Zbl 0441.05003 |
| [4] | Comtet, L., Advanced Combinatorics (1974), Dordrecht/Boston · Zbl 0283.05001 |
| [5] | David, F. N.; Kendall, M. G.; Barton, D. E., Symmetric Functions and Allied Tables (1966), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0152.36002 |
| [6] | Foata, D., Etude algébrique de certain problèmes d’analyse combinatoire et du calcul des probabilités, Publ. Inst. Statist. Univ. Paris, 14, 81-241 (1965) · Zbl 0133.41304 |
| [7] | T. Herriot, Manuscript Add \(6782.111^r\); T. Herriot, Manuscript Add \(6782.111^r\) |
| [8] | Jordan, C., Calculus of Finite Difference (1947), Chelsea: Chelsea New York |
| [9] | Knuth, D. E., (The Art of Computer Programming, Vol. 1 (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0302.68010 |
| [10] | Knuth, D. E., (The Art of Computer Programming, Vol. 2 (1981), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0477.65002 |
| [11] | Knuth, D. E., (The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0302.68010 |
| [12] | D.E. Knuth, The analysis of optimum cacheing, J. Algorithms, to appear.; D.E. Knuth, The analysis of optimum cacheing, J. Algorithms, to appear. |
| [13] | D.E. Knuth, Review of the book “History of Binary and other Nondecimal Numeration” by Anton Glaser, Historia Mathematica, to appear.; D.E. Knuth, Review of the book “History of Binary and other Nondecimal Numeration” by Anton Glaser, Historia Mathematica, to appear. |
| [14] | Knuth, D. E.; Rao, G. S., Activity in an interleaved memory, IEEE Trans. Computers, C-24, 943-944 (1975) |
| [15] | Knuth, D. E.; Schönhage, A., The expected linearity of a simple equivalence algorithm, Theoretical Computer Sci., 6, 281-315 (1978) · Zbl 0377.68024 |
| [16] | Nielsen, N., Die Gammafunktion (1965), New York · JFM 36.0500.01 |
| [17] | Nielsen, N., Traité Élémentaire des Nombres de Bernoulli (1923), Gauthier-Villars: Gauthier-Villars Paris · JFM 50.0170.04 |
| [18] | Marx, I., Transformation of series by a variant of Stirling’s numbers, American Mathematical Monthly, 69, 530-532 (1962) · Zbl 0136.35601 |
| [19] | Moon, J. W., Counting Labelled Trees, (Canadian Mathematical Monographs (1971)) · Zbl 0214.23204 |
| [20] | Riordan, J., An Introduction to Combinatorial Analysis (1958), Wiley: Wiley New York · Zbl 0078.00805 |
| [21] | Riordan, J., Combinatorial Identities (1968), Wiley: Wiley New York · Zbl 0194.00502 |
| [22] | Stirling, J., Methodus Differentialis, (Sive Tractatus De Summatione et Interpolazione Serierum Infinitorum (1730)), London |
| [23] | Stanford Computer Science Department, Qualifying examination in the analysis of algorithms (April 1981) |
| [24] | Tweedie, C.; Stirling, James, A Sketch of his Life and Works (1922), Clarendon Press: Clarendon Press Oxford · JFM 48.0007.03 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
