[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Search: a049029 -id:a049029
     Sort: relevance | references | number | modified | created      Format: long | short | data
Row sums of triangle A049029.
+20
8
1, 6, 61, 871, 15996, 358891, 9509641, 290528316, 10051973371, 388433817091, 16579346005806, 774580047063901, 39313104018590221, 2153825039102763846, 126681355435102649161, 7961385691338995966371, 532402860878855993673036
OFFSET
1,2
COMMENTS
Generalized Bell numbers B(5,1;n).
REFERENCES
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, Phys. Lett. A 309 (2003) 198-205.
LINKS
W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem.
FORMULA
E.g.f. exp(-1+1/(1-4*x)^(1/4))-1.
Representation of a(n) as the n-th moment of a positive function on positive half-axis (Stieltjes moment problem), in Maple notation: a(n)=int(x^n*exp(-1)*exp(-1/4*x)*(1/96*x*hypergeom([],[5/4, 3/2, 7/4, 2],1/1024*x)+ 1/8*4^(3/4)*x^(1/4)/Pi*2^(1/2)*GAMMA(3/4)*hypergeom([],[1/4, 1/2,3/4, 5/4],1/1024*x)+1/8*4^(1/2)*x^(1/2)/Pi^(1/2)*hypergeom([],[1/2, 3/4, 5/4,3/2],1/1024*x)+1/24*4^(1/4)*x^(3/4)/GAMMA(3/4)*hypergeom([],[3/4, 5/4, 3/2,7/4],1/1024*x))/x, x=0..infinity),n=1,2... . - Karol A. Penson, Dec 16 2007
a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator (1+x)^5*d/dx. Cf. A000110, A000262, A049118 and A049119. - Peter Bala, Nov 25 2011
MATHEMATICA
With[{nn=20}, CoefficientList[Series[Exp[-1+1/Surd[1-4x, 4]]-1, {x, 0, nn}], x] Range[0, nn]!] (* Harvey P. Dale, Sep 10 2019 *)
CROSSREFS
Cf. A049119, generalized Bell numbers B(4, 1, n). A049118.
KEYWORD
easy,nonn
STATUS
approved
Second column (m=2) of triangle A049029 (S2(5)).
+20
1
1, 15, 255, 5175, 123795, 3427515, 108046575, 3824996175, 150346471275, 6499426608675, 306553491419175, 15668768604864375, 862827112324051875, 50929793720847916875, 3208139019437586609375, 214817175616326677769375, 15237402314816854944646875
OFFSET
0,2
LINKS
FORMULA
a(n) = A049029(n+2,2),n>=0.
E.g.f. with offset n=2: ((-1+(1-4*x)^(-1/4))^2)/2!.
E.g.f.: (6 - 5*(1-4*x)^(1/4))/(1-4*x)^(5/2) (offset n=0).
a(n) = (-4)^n*(8*Sqrt(Pi)/Gamma(-3/2-n)-5*Gamma(-5/4)/Gamma(-5/4-n)). - Benedict W. J. Irwin, Apr 06 2017
MATHEMATICA
FullSimplify@Table[(-4)^n(8Sqrt[Pi]/Gamma[-3/2-n]-5Gamma[-5/4]/Gamma[-5/4-n]), {n, 0, 20}] (* Benedict W. J. Irwin, Apr 06 2017 *)
PROG
(PARI) x='x+O('x^50); Vec(serlaplace((6 - 5*(1-4*x)^(1/4))/(1 -4*x)^(5/2))) \\ G. C. Greubel, May 25 2017
CROSSREFS
First column: A007696 (4-factorials). Third column A143169.
KEYWORD
nonn,easy
AUTHOR
Wolfdieter Lang, Oct 17 2008, Dec 04 2008
STATUS
approved
Duplicate of A049029.
+20
0
1, 5, 1, 45, 15, 1, 585, 255, 30, 1, 9945, 5175, 825, 50, 1, 208845, 123795, 24150
OFFSET
1,2
KEYWORD
dead
STATUS
approved
Alternating row sums of triangle A049029 (S2(5)).
+20
0
1, 4, 31, 359, 5546, 107249, 2492701, 67693534, 2103854581, 73651161959, 2868077514776, 122980857764819, 5758029769553101, 292305762924889804, 15992593021331060611, 938143525674896325299, 58739433900424758545186, 3910020681156059085488189
OFFSET
1,2
FORMULA
a(n) = Sum_{m=1..n} (-1)^(m+1)*A049029(n,m), n>=1.
E.g.f.: (from Jabotinsky structure): 1-exp(1-1/(1-4*x)^(1/4)).
a(n) = y(n), where y(0) = -1, y(1) = 1, y(2) = 4, y(3) = 31, y(4) = 359, and -32*k*(1 + k)*(1 + 2 k)*(1 + 4 k)*(3 + 4 k)*y(k) + (1679 + 5920 k + 8080 k^2 + 5120 k^3 + 1280 k^4)*y(k+1) + (-2550 - 4580 k - 2880 k^2 - 640 k^3)*y(k+2) + (675 + 640 k + 160 k^2)*y(k+3) + (-50 - 20 k)*y(k+4) + y(k+5) = 0. - Benedict W. J. Irwin, Jul 12 2017
MATHEMATICA
Table[DifferenceRoot[Function[{y, k}, {-32 k (1 + k) (1 + 2 k) (1 + 4 k) (3 + 4 k) y[k] + (1679 + 5920 k + 8080 k^2 + 5120 k^3 + 1280 k^4) y[1 + k] + (-2550 - 4580 k - 2880 k^2 - 640 k^3) y[2 + k] + (675 + 640 k + 160 k^2) y[3 + k] + (-50 - 20 k) y[4 + k] + y[5 + k] == 0, y[0] == -1, y[1] == 1, y[2] == 4, y[3] == 31, y[4] == 359}]][n], {n, 1, 20}] (* Benedict W. J. Irwin, Jul 12 2017 *)
CROSSREFS
Cf. A049120 (row sums).
KEYWORD
nonn,easy
AUTHOR
Wolfdieter Lang, Oct 17 2008
STATUS
approved
Triangle read by rows of Stirling numbers of first kind, s(n,k), n >= 1, 1 <= k <= n.
+10
262
1, -1, 1, 2, -3, 1, -6, 11, -6, 1, 24, -50, 35, -10, 1, -120, 274, -225, 85, -15, 1, 720, -1764, 1624, -735, 175, -21, 1, -5040, 13068, -13132, 6769, -1960, 322, -28, 1, 40320, -109584, 118124, -67284, 22449, -4536, 546, -36, 1, -362880, 1026576, -1172700, 723680, -269325, 63273, -9450, 870, -45, 1
OFFSET
1,4
COMMENTS
The unsigned numbers are also called Stirling cycle numbers: |s(n,k)| = number of permutations of n objects with exactly k cycles.
The unsigned numbers (read from right to left) also give the number of permutations of 1..n with complexity k, where the complexity of a permutation is defined to be the sum of the lengths of the cycles minus the number of cycles. In other words, the complexity equals the sum of (length of cycle)-1 over all cycles. For n=5, the numbers of permutations with complexity 0,1,2,3,4 are 1, 10, 35, 50, 24. - N. J. A. Sloane, Feb 08 2019
The unsigned numbers are also the number of permutations of 1..n with k left to right maxima (see Khovanova and Lewis, Smith).
With P(n) = the number of integer partitions of n, T(i,n) = the number of parts of the i-th partition of n, D(i,n) = the number of different parts of the i-th partition of n, p(j,i,n) = the j-th part of the i-th partition of n, m(j,i,n) = multiplicity of the j-th part of the i-th partition of n, Sum_[T(i,n)=k]_{i=1}^{P(n)} = sum running from i=1 to i=p(n) but taking only partitions with T(i,n)=k parts into account, Product_{j=1..T(i,n)} = product running from j=1 to j=T(i,n), Product_{j=1..D(i,n)} = product running from j=1 to j=D(i,n) one has S1(n,k) = Sum_[T(i,n)=k]_{i=1}^{P(n)} (n!/Product_{j=1..T(i,n)} p(j,i,n))* (1/Product_{j=1..D(i,n)} m(j,i,n)!). For example, S1(6,3) = 225 because n=6 has the following partitions with k=3 parts: (114), (123), (222). Their complexions are: (114): (6!/1*1*4)*(1/2!*1!) = 90, (123): (6!/1*2*3)*(1/1!*1!*1!) = 120, (222): (6!/2*2*2)*(1/3!) = 15. The sum of the complexions is 90+120+15 = 225 = S1(6,3). - Thomas Wieder, Aug 04 2005
Row sums equal 0. - Jon Perry, Nov 14 2005
|s(n,k)| enumerates unordered n-vertex forests composed of k increasing non-plane (unordered) trees. Proof from the e.g.f. of the first column and the F. Bergeron et al. reference, especially Table 1, last row (non-plane "recursive"), given in A049029. - Wolfdieter Lang, Oct 12 2007
|s(n,k)| enumerates unordered increasing n-vertex k-forests composed of k unary trees (out-degree r from {0,1}) whose vertices of depth (distance from the root) j >= 0 come in j+1 colors (j=0 for the k roots). - Wolfdieter Lang, Oct 12 2007, Feb 22 2008
A refinement of the unsigned array is A036039. For an association to forests of "naturally grown" rooted non-planar trees, dispositions of flags on flagpoles, and colorings of the vertices of the complete graphs K_n, see A130534. - Tom Copeland, Mar 30 and Apr 05 2014
The Stirling numbers of the first kind were related to the falling factorial and the convolved, or generalized, Bernoulli numbers B_n by Norlund in 1924 through Sum_{k=1..n+1} T(n+1,k) * x^(k-1) = (x-1)!/(x-1-n)! = (x + B.(0))^n = B_n(x), umbrally evaluated with (B.(0))^k = B_k(0) and the associated Appell polynomial B_n(x) defined by the e.g.f. (t/(exp(t) - 1))^(n+1) * exp(x*t) = exp(B.(x)t). - Tom Copeland, Sep 29 2015
With x = e^z, D_x = d/dx, D_z = d/dz, and p_n(x) the row polynomials of this entry, x^n (D_x)^n = p_n(D_z) = (D_z)! / (D_z - n)! = (xD_x)! / (xD_x - n)!. - Tom Copeland, Nov 27 2015
From the operator relation z + Psi(1) + sum_{n > 0} (-1)^n (-1/n) binomial(D,n) = z + Psi(1+D) with D = d/dz and Psi the digamma function, Zeta(n+1) = Sum_{k > n-1} (1/k) |S(k,n)| / k! for n > 0 and Zeta the Riemann zeta function. - Tom Copeland, Aug 12 2016
Let X_1,...,X_n be i.i.d. random variables with exponential distribution having mean = 1. Let Y = max{X_1,...,X_n}. Then (-1)^n*n!/( Sum_{k=1..n+1} a(n+1,k) t^(k-1) ) is the moment generating function of Y. The expectation of Y is the n-th harmonic number. - Geoffrey Critzer, Dec 25 2018
In the Ewens sampling theory describing the multivariate probability distribution of the sizes of the allelic classes in a sample of size n under the Infinite Alleles Model, |s(n,k)| gives the coefficient in the formula for the probability that a sample of n alleles has exactly k distinct types. - Noah A Rosenberg, Feb 10 2019
Named by Nielson (1906) after the Scottish mathematician James Stirling (1692-1770). - Amiram Eldar, Jun 11 2021 and Oct 02 2023
The first few row polynomials along with a recursion formula are found in a manuscript by Newton written in 1664 or 1665 (p. 169 of Turnbull) giving a geometric presentation of the binomial theorem for rational powers. - Tom Copeland, Dec 10 2022
REFERENCES
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 833.
Arthur T. Benjamin and Jennifer Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 93ff.
Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8. English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 32.
George Boole, Finite Differences, 5th ed. New York, NY: Chelsea, 1970.
Louis Comtet, Advanced Combinatorics, Reidel, 1974; Chapter V, also p. 310.
John H. Conway and Richard K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 93.
Florence Nightingale David, Maurice George Kendall and David Elliot Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 226.
Saber N. Elaydi, An Introduction to Difference Equations, 3rd ed. Springer, 2005.
Herman H. Goldstine, A History of Numerical Analysis, Springer-Verlag, 1977; Section 2.7.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 245. In the second edition, see Chapter 6, especially p. 259.
M. Miyata and J. W. Son, On the complexity of permutations and the metric space of bijections, Tensor, 60 (1998), No. 1, 109-116 (MR1768839).
Isaac Newton, A Method whereby to find ye areas of Those Lines wch can be squared, pp. 168-171 of Turnbull below.
John Riordan, An Introduction to Combinatorial Analysis, p. 48.
Robert Sedgewick and Phillipe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.
H. Turnbull (editor), The Correspondence of Isaac Newton Vol. II 1676-1687, Cambridge Univ. Press, 1960.
LINKS
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Nikita Alexeev and Peter Zograf, Hultman numbers, polygon gluings and matrix integrals, arXiv:1111.3061 [math.PR], 2011.
J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
Elena Barcucci, Alberto Del Lungo and Renzo Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, Vol. 159 (1996), pp. 29-42.
Nicolas Behr, Vincent Danos, and Ilias Garnier, Combinatorial Conversion and Moment Bisimulation for Stochastic Rewriting Systems, arXiv:1904.07313 [cs.LO], 2019.
Hacene Belbachir and Mourad Rahmani, Alternating Sums of the Reciprocals of Binomial Coefficients, Journal of Integer Sequences, Vol. 15 (2012), Article 12.2.8.
Edward A. Bender, Central and local limit theorems applied to asymptotic enumeration Journal of Combinatorial Theory, Series A, Vol. 15, No. 1 (1973), pp. 91-111. See Example 5.1.
Federico Castillo, Damian de la Fuente, Nicolas Libedinsky, and David Plaza, On the size of Bruhat intervals, arXiv:2309.08539 [math.CO], 2023.
José Luis Cereceda,, Generalized Akiyama-Tanigawa Algorithm for Hypersums of Powers of Integers, J. Int. Seq., Vol. 16 (2013), Article 13.3.2.
José Luis Cereceda, Iterative Procedure for Hypersums of Powers of Integers, Journal of Integer Sequences, Vol. 17 (2014), Article 14.5.3.
Ricky X. F. Chen, A Note on the Generating Function for the Stirling Numbers of the First Kind, Journal of Integer Sequences, Vol. 18 (2015), Article 15.3.8.
Harry Crane, The ubiquitous Ewens sampling formula, Statistical Science, Vol. 31 (2016), pp. 1-19.
Thierry Dana-Picard and David G. Zeitoun, Sequences of definite integrals, infinite series and Stirling numbers, International Journal of Mathematical Education in Science and Technology, Vol. 43, No. 2 (2012), pp. 219-230.
Sajal K. Das, Joydeep Ghosh and Narsingh Deo, Stirling networks: a versatile combinatorial topology for multiprocessor systems, Discrete Applied Mathematics, Vol. 37 (1992), pp. 119-146.
Askar Dzhumadil’daev and Damir Yeliussizov, Walks, partitions, and normal ordering, Electronic Journal of Combinatorics, Vol. 22, No. 4 (2015), #P4.10.
B. S. El-Desouky, Nenad P. Cakić and Toufik Mansour, Modified approach to generalized Stirling numbers via differential operators, Appl. Math. Lett., Vol. 23, No. 1 (2010), pp. 115-120.
Daniel B. Grünberg, On asymptotics, Stirling numbers, gamma function and polylogs, Results in Mathematics, Vol. 49, No. 1 (2006), pp. 89-125; arXiv preprint, arXiv:math/0607514 [math.CO], 2006.
Jerome Hines, A generalization of the S-Stirling numbers, Math. Mag., Vol. 29, No. 4 (1956), pp. 200-203.
Yoshinari Inaba, Hyper-Sums of Powers of Integers and the Akiyama-Tanigawa Matrix, Journal of Integer Sequences, 8 (2005), Article 05.2.7.
Charles Knessl and Joseph B. Keller, Stirling number asymptotics from recursion equations using the ray method, Stud. Appl. Math., Vol. 84, No. 1 (1991), pp. 43-56.
Tanya Khovanova and Joel Brewster Lewis, Skyscrapers.
Donald E. Knuth, Convolution polynomials, arXiv:math/9207221 [math.CA], 1993; The Mathematica J., 2 (1992), 67-78.
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), Article 00.2.4.
Elliott H. Lieb, Concavity properties and a generating function for Stirling numbers, Journal of Combinatorial Theory, Vol. 5, No. 2 (1968), pp. 203-206.
Daniel E. Loeb, A generalization of Stirling numbers, arXiv:math/9502217 [math.CO], 1995.
Mahid M. Mangontarum and Jacob Katriel, On q-Boson Operators and q-Analogues of the r-Whitney and r-Dowling Numbers, J. Int. Seq., Vol. 18 (2015), Article 15.9.8.
Toufik Mansour, Augustine Munagi and Mark Shattuck, Recurrence Relations and Two-Dimensional Set Partitions, J. Int. Seq., Vol. 14 (2011), Article 11.4.1.
Toufik Mansour, Matthias Schork and Mark Shattuck, The Generalized Stirling and Bell Numbers Revisited, Journal of Integer Sequences, Vol. 15 (2012), Article 12.8.3.
B. H. Margolius, Transient and periodic solution to the time-inhomogeneous quasi-birth death process, Queueing Systems, Volume 56, Numbers 3-4 / August, 2007. [From N. J. A. Sloane, Jul 09 2009]
Dragoslav S. Mitrinović, Sur une relation de récurrence relative aux nombres de Bernoulli, Comptes rendus de l'Académie des sciences de Paris, Vol. 250 (1960), pp. 4266-4267.
Dragoslav S. Mitrinović and Ružica S. Mitrinović, Sur les nombres de Stirling et les nombres de Bernoulli d'ordre supérieur, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., No. 43 (1960), pp. 1-63.
Dragoslav S. Mitrinović and Ružica S. Mitrinović, Sur une classe de nombres se rattachant aux nombres de Stirling--Appendice: Table des nombres de Stirling, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., No. 60 (1961), pp. 1-15 and 17-62.
Dragoslav S. Mitrinović and Ružica S. Mitrinović, Tableaux d'une classe de nombres reliés aux nombres de Stirling, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., No. 77 (1962), pp. 1-77.
Dragoslav S. Mitrinović and Ružica S. Mitrinović, Tableaux d'une classe de nombres reliés aux nombres de Stirling, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., No. 77 (1962), pp. 1-77 [jstor stable version].
Emanuele Munarini, Combinatorial identities involving the central coefficients of a Sheffer matrix, Applicable Analysis and Discrete Mathematics, Vol. 13 (2019), pp. 495-517.
Niels Nielson, Handbuch der theorie der gammafunktion, Teubner, Leipzig, 1906, see p. 67.
Niels Nörlund, Vorlesungen über Differenzenrechnung, Springer, Berlin, 1924.
Niels Nörlund, Vorlesungen über Differenzenrechnung, Chelsea Pub. Co., New York, 1954. [archive.org]
K. A. Penson, P. Blasiak, A. Horzela, G. H. E. Duchamp and A. I. Solomon, Laguerre-type derivatives: Dobinski relations and combinatorial identities, J. Math. Phys. Vol. 50 (2009), 083512.
Grzegorz Rządkowski, Two formulas for Successive Derivatives and Their Applications, J. Int. Seq., Vol. 12 (2009), Article 09.8.2.
Maxie D. Schmidt, Generalized j-Factorial Functions, Polynomials, and Applications, J. Int. Seq., Vol. 13 (2010), Article 10.6.7.
Benjamin Schreyer, Rigged Horse Numbers and their Modular Periodicity, arXiv:2409.03799 [math.CO], 2024. See p. 12.
Raymond Scurr and Gloria Olive, Stirling numbers revisited, Discrete Math., Vol. 189, No. 1-3 (1998), pp. 209-219. MR1637761 (99d:11019).
Mark Shattuck, Convolution identities for Stirling numbers of the first kind via involution, INTEGERS, Vol. 12 (2012), #A59. - From N. J. A. Sloane, Feb 04 2013
Mark Shattuck, Combinatorial Proofs of Some Stirling Number Convolution Formulas, J. Int. Seq., Vol. 25 (2022), Article 22.2.2.
Michael Z. Spivey, A generalized recurrence for Bell Numbers, JIS, Vol. 11 (2008), Article 08.2.5.
Michael Z. Spivey, On Solutions to a General Combinatorial Recurrence, J. Int. Seq., Vol. 14 (2011), Article 11.9.7.
Richard P. Stanley, Ordering events in Minkowski space, arXiv:math/0501256 [math.CO], 2005.
James Stirling, The Differential Method, London, 1749; see p. 10.
Nico M. Temme, Asymptotic Estimates of Stirling Numbers, Studies in Applied Mathematics, Vol. 89, No. 3 (1993), pp. 233-243; Summary by Helmut Prodinger.
A. N. Timashev, On asymptotic expansions of Stirling numbers of the first and second kinds, (Russian) Diskret. Mat. 10(3) (1998), 148-159; translation in Discrete Math. Appl., Vol. 8, No. 5 (1998), pp. 533-544.
Eric Weisstein's World of Mathematics, Permutation Cycle.
Eric Weisstein's World of Mathematics, Stirling Number of the First Kind.
Thomas Wieder, Comments on A008275.
FORMULA
s(n, k) = s(n-1, k-1) - (n-1)*s(n-1, k), n, k >= 1; s(n, 0) = s(0, k) = 0; s(0, 0) = 1.
The unsigned numbers a(n, k)=|s(n, k)| satisfy a(n, k) = a(n-1, k-1) + (n-1)*a(n-1, k), n, k >= 1; a(n, 0) = a(0, k) = 0; a(0, 0) = 1.
E.g.f.: for m-th column (unsigned): ((-log(1-x))^m)/m!.
s(n, k) = T(n-1, k-1), n>1 and k>1, where T(n, k) is the triangle [ -1, -1, -2, -2, -3, -3, -4, -4, -5, -5, -6, -6, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, ...] and DELTA is Deléham's operator defined in A084938. The unsigned numbers are also |s(n, k)| = T(n-1, k-1), for n>0 and k>0, where T(n, k) = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...].
Sum_{i=0..n} (-1)^(n-i) * StirlingS1(n, i) * binomial(i, k) = (-1)^(n-k) * StirlingS1(n+1, k+1). - Carlo Wood (carlo(AT)alinoe.com), Feb 13 2007
G.f.: S(n) = Product_{j=1..n} (x-j) (i.e., (x-1)*(x-2)*(x-3) = x^3 - 6*x^2 + 11*x - 6). - Jon Perry, Nov 14 2005
T(n,k) = A048993(n,k), for k=1..n. - Reinhard Zumkeller, Mar 18 2013
As lower triangular matrices A008277*A008275 = I, the identity matrix. - Tom Copeland, Apr 25 2014
a(n,k) = s(n,k) = lim_{y -> 0} Sum_{j=0..k} (-1)^j*binomial(k,j)*((-j*y)!/(-j*y-n)!)*y^(-k)/k! = Sum_{j=0..k} (-1)^(n-j)*binomial(k,j)*((j*y - 1 + n)!/(j*y-1)!)*y^(-k)/k!. - Tom Copeland, Aug 28 2015
From Daniel Forgues Jan 16 2016: (Start)
Let x_(0) := 1 (empty product), and for n >= 1:
x_(n) := Product_{k=0..n-1} (x-k), called a factorial term (Boole, 1970) or a factorial polynomial (Elaydi, 2005: p. 60), and also x_(-n) := 1 / [Product_{k=0..n-1} (x+k)].
Then, for n >= 1: x_(n) = Sum_{k=1..n} T(n,k) * x^k, 1 / [x_(-n)] = Sum_{k=1..n} |T(n,k)| * x^k, x^n = Sum_{k=1..n} A008277(n,k) * x_(k), where A008277(n,k) are Stirling numbers of the second kind.
The row sums (of either signed or absolute values) are Sum_{k=1..n} T(n,k) = 0^(n-1), Sum_{k=1..n} |T(n,k)| = T(n+1,1) = n!. (End)
s(n,m) = ((-1)^(n-m)/n)*Sum_{i=0..m-1} C(2*n-m-i, m-i-1)*A008517(n-m+1,n-m-i+1). - Vladimir Kruchinin, Feb 14 2018
Orthogonal relation: Sum_{i=0..n} i^p*Sum_{j=k..n} (-1)^(i+j) * binomial(j,i) * Stirling1(j,k)/j! = delta(p,k), i,k,p <= n, n >= 1. - Leonid Bedratyuk, Jul 27 2020
From Zizheng Fang, Dec 28 2020: (Start)
Sum_{k=1..n} (-1)^k * k * T(n, k) = -T(n+1, 2).
Sum_{k=1..n} k * T(n, k) = (-1)^n * (n-2)! = T(n-1, 1) for n>=2. (End)
n-th row polynomial = n!*Sum_{k = 0..2*n} (-1)^(n+k)*binomial(x, k)*binomial(x-1, 2*n-k) = n!*Sum_{k = 0..2*n+1} (-1)^(n+k+1)*binomial(x, k)*binomial(x-1, 2*n+1-k). - Peter Bala, Mar 29 2024
EXAMPLE
|s(3,2)| = 3 for the three unordered 2-forest with 3 vertices and two increasing (nonplane) trees: ((1),(2,3)), ((2),(1,3)), ((3),(1,2)).
Triangle begins:
1
-1, 1
2, -3, 1
-6, 11, -6, 1
24, -50, 35, -10, 1
-120, 274, -225, 85, -15, 1
720, -1764, 1624, -735, 175, -21, 1
-5040, 13068, -13132, 6769, -1960, 322, -28, 1
40320, -109584, 118124, -67284, 22449, -4536, 546, -36, 1
Another version of the same triangle, from Joerg Arndt, Oct 05 2009: (Start)
s(n,k) := number of permutations of n elements with exactly k cycles ("Stirling cycle numbers")
n| total m=1 2 3 4 5 6 7 8 9
-+-----------------------------------------------------
1| 1 1
2| 2 1 1
3| 6 2 3 1
4| 24 6 11 6 1
5| 120 24 50 35 10 1
6| 720 120 274 225 85 15 1
7| 5040 720 1764 1624 735 175 21 1
8| 40320 5040 13068 13132 6769 1960 322 28 1
9| 362880 40320 109584 118124 67284 22449 4536 546 36 1
(End)
|s(4,2)| = 11 for the eleven unordered 2-forest with 4 vertices, composed of two increasing (nonplane) trees: ((1),((23)(24))), ((2),((13)(14))), ((3),((12)(14))), ((4),((12)(13))); ((1),(2,3,4)),((2),(1,2,3)), ((3), (1,2,4)), ((4),(1,2,3)); ((1,2),(3,4)), ((1,3),(2,4)), ((1,4),(2,3)). - Wolfdieter Lang, Feb 22 2008
MAPLE
with (combinat):seq(seq(stirling1(n, k), k=1..n), n=1..10); # Zerinvary Lajos, Jun 03 2007
for i from 0 to 9 do seq(stirling1(i, j), j = 1 .. i) od; # Zerinvary Lajos, Nov 29 2007
MATHEMATICA
Flatten[Table[StirlingS1[n, k], {n, 1, 10}, {k, 1, n}]] (* Jean-François Alcover, May 18 2011 *)
Flatten@Table[Coefficient[Product[x-k, {k, 0, n-1}], x, Range[n]], {n, Range[10]}] (* Oliver Seipel, Jun 11 2024 *)
a[n_, n_] := 1; a[n_, 0] := 0; a[0, k_] := 0;
a[n_, k_] := a[n, k] = a[n-1, k-1] + (n-1) a[n-1, k];
Flatten@Table[(-1)^(n-k) a[n, k], {n, 1, 10}, {k, 1, n}] (* Oliver Seipel, Jun 11 2024 *)
PROG
(PARI) T(n, k)=if(n<1, 0, n!*polcoeff(binomial(x, n), k))
(PARI) T(n, k)=if(n<1, 0, n!*polcoeff(polcoeff((1+x+x*O(x^n))^y, n), k))
(PARI) vecstirling(n)=Vec(factorback(vector(n-1, i, 1-i*'x))) /* (A function that returns all the s(n, k) as a vector) */ \\ Bill Allombert (Bill.Allombert(AT)math.u-bordeaux1.fr), Mar 16 2009
(Maxima) create_list(stirling1(n+1, k+1), n, 0, 30, k, 0, n); /* Emanuele Munarini, Jun 01 2012 */
(Haskell)
a008275 n k = a008275_tabl !! (n-1) !! (k-1)
a008275_row n = a008275_tabl !! (n-1)
a008275_tabl = map tail $ tail a048994_tabl
-- Reinhard Zumkeller, Mar 18 2013
CROSSREFS
Diagonals: A000217, A000914, A001303, A000915, A053567, etc.
Cf. A048994, A008277 (Stirling numbers of second kind), A039814, A039815, A039816, A039817, A048993, A087748.
Cf. A084938, A094216, A008276 (row reversed), A008277, A008278, A094262, A121632, A130534 (unsigned version), A087755 (triangle mod 2), A000142 (row sums of absolute values).
KEYWORD
sign,tabl,nice,core
STATUS
approved
Quartic (or 4-fold) factorial numbers: a(n) = Product_{k = 0..n-1} (4*k + 1).
(Formerly M4001)
+10
81
1, 1, 5, 45, 585, 9945, 208845, 5221125, 151412625, 4996616625, 184874815125, 7579867420125, 341094033905625, 16713607661375625, 885821206052908125, 50491808745015763125, 3080000333445961550625, 200200021673987500790625, 13813801495505137554553125
OFFSET
0,3
COMMENTS
a(n), n >= 1, enumerates increasing quintic (5-ary) trees. See David Callan's comment on A007559 (number of increasing quarterny trees).
Hankel transform is A169619. - Paul Barry, Dec 03 2009
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seq. 3 (2000), Article 00.2.4.
J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations, (m+1)-ary trees, and m-parking functions, arXiv:1403.5962 [math.CO], 2014.
Maxie D. Schmidt, Generalized j-Factorial Functions, Polynomials, and Applications , J. Integer Seq. 13 (2010), Article 10.6.7; see page 39.
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, J. Integer Seq. 9 (2006), Article 06.1.1.
FORMULA
E.g.f.: (1 - 4*x)^(-1/4).
a(n) ~ 2^(5/2) * Pi^(1/2) * Gamma(1/4)^(-1) * n^(3/4) * 2^(2*n) * e^(-n) * n^n * (1 + 23/96 * n^(-1) - ...). - Joe Keane (jgk(AT)jgk.org), Nov 23 2001
a(n) = Sum_{k = 0..n} (-4)^(n-k) * A048994(n, k). - Philippe Deléham, Oct 29 2005
G.f.: 1/(1 - x/(1 - 4*x/(1 - 5*x/(1 - 8*x/(1 - 9*x/(1 - 12*x/(1 - 13*x/(1 - .../(1 - A042948(n+1)*x/(1 -... (continued fraction). - Paul Barry, Dec 03 2009
a(n) = (-3)^n * Sum_{k = 0..n} (4/3)^k * s(n+1, n+1-k), where s(n,k) are the Stirling numbers of the first kind, A048994. - Mircea Merca, May 03 2012
G.f.: 1/T(0), where T(k) = 1 - x * (4*k + 1)/(1 - x * (4*k + 4)/T(k+1)) (continued fraction). - Sergei N. Gladkovskii, Mar 19 2013
G.f.: 1 + x/Q(0), where Q(k) = 1 + x + 2*(2*k - 1)*x - 4*x*(k+1)/Q(k+1) (continued fraction). - Sergei N. Gladkovskii, May 03 2013
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x * (4*k + 1)/(x * (4*k + 1) + 1/G(k+1))) (continued fraction). - Sergei N. Gladkovskii, Jun 04 2013
0 = a(n) * (4*a(n+1) - a(n+2)) + a(n+1) * a(n+1) for all n in Z. - Michael Somos, Jan 17 2014
a(-n) = (-1)^n / A008545(n). - Michael Somos, Jan 17 2014
Let T(x) = 1/(1 - 3*x)^(1/3) be the e.g.f. for the sequence of triple factorial numbers A007559. Then the e.g.f. A(x) for the quartic factorial numbers satisfies T(int_{0..x} A(t) dt) = A(x). (Cf. A007559 and A008548.) - Peter Bala, Jan 02 2015
O.g.f.: hypergeom([1, 1/4], [], 4*x). - Peter Luschny, Oct 08 2015
a(n) = A264781(4*n+1, n). - Alois P. Heinz, Nov 24 2015
a(n) = 4^n * Gamma(n + 1/4)/Gamma(1/4). - Artur Jasinski, Aug 23 2016
D-finite with recurrence: a(n) +(-4*n+3)*a(n-1)=0, n>=1. - R. J. Mathar, Feb 14 2020
Sum_{n>=0} 1/a(n) = 1 + exp(1/4)*(Gamma(1/4) - Gamma(1/4, 1/4))/(2*sqrt(2)). - Amiram Eldar, Dec 18 2022
EXAMPLE
G.f. = 1 + x + 5*x^2 + 45*x^3 + 585*x^4 + 9945*x^5 + 208845*x^6 + ...
MAPLE
x:='x'; G(x):=(1-4*x)^(-1/4): f[0]:=G(x): for n from 1 to 29 do f[n]:=diff(f[n-1], x) od: seq(eval(f[n], x=0), n=0..17); # Zerinvary Lajos, Apr 03 2009
A007696 := n -> mul(k, k = select(k-> k mod 4 = 1, [$ 1 .. 4*n])): seq(A007696(n), n=0..17); # Peter Luschny, Jun 23 2011
MATHEMATICA
a[ n_]:= Pochhammer[ 1/4, n] 4^n; (* Michael Somos, Jan 17 2014 *)
a[ n_]:= If[n < 0, 1 / Product[ -k, {k, 3, -4n-1, 4}], Product[ k, {k, 1, 4n-3, 4}]]; (* Michael Somos, Jan 17 2014 *)
Range[0, 19]! CoefficientList[Series[((1-4x)^(-1/4)), {x, 0, 19}], x] (* Vincenzo Librandi, Oct 08 2015 *)
PROG
(PARI) {a(n) = if( n<0, 1 / prod(k=1, -n, 1 - 4*k), prod(k=1, n, 4*k - 3))}; /* Michael Somos, Jan 17 2014 */
(Maxima) A007696(n):=prod(4*k+1, k, 0, n-1)$
makelist(A007696(n), n, 0, 30); /* Martin Ettl, Nov 05 2012 */
(Magma) [n le 2 select 1 else (4*(n-1)-7)*(Self(n-1) + 4*Self(n-2)): n in [1..20]]; // G. C. Greubel, Aug 15 2019
(Sage) [4^n*rising_factorial(1/4, n) for n in (0..20)] # G. C. Greubel, Aug 15 2019
(GAP) a:=[1, 1];; for n in [3..20] do a[n]:=(4*(n-1)-7)*(a[n-1]+4*a[n-2]); od; a; # G. C. Greubel, Aug 15 2019
CROSSREFS
a(n) = A049029(n, 1) for n >= 1 (first column of triangle).
KEYWORD
nonn
EXTENSIONS
Better description from Wolfdieter Lang, Dec 11 1999
STATUS
approved
The convolution matrix of the double factorial of odd numbers (A001147).
+10
64
1, 3, 1, 15, 9, 1, 105, 87, 18, 1, 945, 975, 285, 30, 1, 10395, 12645, 4680, 705, 45, 1, 135135, 187425, 82845, 15960, 1470, 63, 1, 2027025, 3133935, 1595790, 370125, 43890, 2730, 84, 1, 34459425, 58437855, 33453945, 8998290
OFFSET
1,2
COMMENTS
Previous name was: A triangle of numbers related to the triangle A035324; generalization of Stirling numbers of second kind A008277 and Lah numbers A008297.
If one replaces in the recurrence the '2' by '0', resp. '1', one obtains the Lah-number, resp. Stirling-number of 2nd kind, triangle A008297, resp. A008277.
The product of two lower triangular Jabotinsky matrices (see A039692 for the Knuth 1992 reference) is again such a Jabotinsky matrix: J(n,m) = Sum_{j=m..n} J1(n,j)*J2(j,m). The e.g.f.s of the first columns of these triangular matrices are composed in the reversed order: f(x)=f2(f1(x)). With f1(x)=-(log(1-2*x))/2 for J1(n,m)=|A039683(n,m)| and f2(x)=exp(x)-1 for J2(n,m)=A008277(n,m) one has therefore f2(f1(x))=1/sqrt(1-2*x) - 1 = f(x) for J(n,m)=a(n,m). This proves the matrix product given below. The m-th column of a Jabotinsky matrix J(n,m) has e.g.f. (f(x)^m)/m!, m>=1.
a(n,m) gives the number of forests with m rooted ordered trees with n non-root vertices labeled in an organic way. Organic labeling means that the vertex labels along the (unique) path from the root with label 0 to any leaf (non-root vertex of degree 1) is increasing. Proof: first for m=1 then for m>=2 using the recurrence relation for a(n,m) given below. - Wolfdieter Lang, Aug 07 2007
Also the Bell transform of A001147(n+1) (adding 1,0,0,... as column 0). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 19 2016
LINKS
J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013-2014.
P. Blasiak, K. A. Penson and A. I. Solomon, The Boson Normal Ordering Problem and Generalized Bell Numbers, arXiv:quant-ph/0212072, 2002.
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, arXiv:quant-ph/0402027, 2004.
Richell O. Celeste, Roberto B. Corcino and Ken Joffaniel M. Gonzales. Two Approaches to Normal Order Coefficients. Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.5.
Tom Copeland, Mathemagical Forests, 2008.
A. Dzhumadildaev and D. Yeliussizov, Path decompositions of digraphs and their applications to Weyl algebra, arXiv preprint arXiv:1408.6764v1 [math.CO], 2014. [Version 1 contained many references to the OEIS, which were removed in Version 2. - N. J. A. Sloane, Mar 28 2015]
Askar Dzhumadil'daev and Damir Yeliussizov, Walks, partitions, and normal ordering, Electronic Journal of Combinatorics, 22(4) (2015), #P4.10.
Milan Janjic, Some classes of numbers and derivatives, JIS 12 (2009) #09.8.3.
D. E. Knuth, Convolution polynomials, arXiv:math/9207221 [math.CA]; Mathematica J. 2.1 (1992), no. 4, 67-78.
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
Wolfdieter Lang, First 10 rows.
Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO], 2012.
Toufik Mansour, Matthias Schork and Mark Shattuck, The Generalized Stirling and Bell Numbers Revisited, Journal of Integer Sequences, Vol. 15 (2012), #12.8.3.
Mathias Pétréolle and Alan D. Sokal, Lattice paths and branched continued fractions. II. Multivariate Lah polynomials and Lah symmetric functions, arXiv:1907.02645 [math.CO], 2019.
FORMULA
a(n, m) = Sum_{j=m..n} |A039683(n, j)|*S2(j, m) (matrix product), with S2(j, m) := A008277(j, m) (Stirling2 triangle). Priv. comm. to Wolfdieter Lang by E. Neuwirth, Feb 15 2001; see also the 2001 Neuwirth reference. See the comment on products of Jabotinsky matrices.
a(n, m) = n!*A035324(n, m)/(m!*2^(n-m)), n >= m >= 1; a(n+1, m)= (2*n+m)*a(n, m)+a(n, m-1); a(n, m) := 0, n<m; a(n, 0) := 0, a(1, 1)=1.
E.g.f. of m-th column: ((x*c(x/2)/sqrt(1-2*x))^m)/m!, where c(x) = g.f. for Catalan numbers A000108.
From Vladimir Kruchinin, Mar 30 2011: (Start)
G.f. (1/sqrt(1-2*x) - 1)^k = Sum_{n>=k} (k!/n!)*a(n,k)*x^n.
a(n,k) = 2^(n+k) * n! / (4^n*n*k!) * Sum_{j=0..n-k} (j+k) * 2^(j) * binomial(j+k-1,k-1) * binomial(2*n-j-k-1,n-1). (End)
From Peter Bala, Nov 25 2011: (Start)
E.g.f.: G(x,t) = exp(t*A(x)) = 1 + t*x + (3*t + t^2)*x^2/2! + (15*t + 9*t^2 + t^3)*x^3/3! + ..., where A(x) = -1 + 1/sqrt(1-2*x) satisfies the autonomous differential equation A'(x) = (1+A(x))^3.
The generating function G(x,t) satisfies the partial differential equation t*(dG/dt+G) = (1-2*x)*dG/dx, from which follows the recurrence given above.
The row polynomials are given by D^n(exp(x*t)) evaluated at x = 0, where D is the operator (1+x)^3*d/dx. Cf. A008277 (D = (1+x)*d/dx), A105278 (D = (1+x)^2*d/dx), A035469 (D = (1+x)^4*d/dx) and A049029 (D = (1+x)^5*d/dx). (End)
The n-th row polynomial R(n,x) is given by the Dobinski-type formula R(n,x) = exp(-x)*Sum_{k>=1} k*(k+2)*...*(k+2*n-2)*x^k/k!. - Peter Bala, Jun 22 2014
T(n,k) = 2^(k-n)*hypergeom([k-n,k+1],[k-2*n+1],2)*Gamma(2*n-k)/(Gamma(k)*Gamma(n-k+1)). - Peter Luschny, Mar 31 2015
T(n,k) = 2^n*Sum_{j=1..k} ((-1)^(k-j)*binomial(k, j)*Pochhammer(j/2, n)) / k!. - Peter Luschny, Mar 04 2024
EXAMPLE
Matrix begins:
1;
3, 1;
15, 9, 1;
105, 87, 18, 1;
945, 975, 285, 30, 1;
...
Combinatoric meaning of a(3,2)=9: The nine increasing path sequences for the three rooted ordered trees with leaves labeled with 1,2,3 and the root labels 0 are: {(0,3),[(0,1),(0,2)]}; {(0,3),[(0,2),(0,1)]}; {(0,3),(0,1,2)}; {(0,1),[(0,3),(0,2)]}; [(0,1),[(0,2),(0,3)]]; [(0,2),[(0,1),(0,3)]]; {(0,2),[(0,3),(0,1)]}; {(0,1),(0,2,3)}; {(0,2),(0,1,3)}.
MAPLE
T := (n, k) -> 2^(k-n)*hypergeom([k-n, k+1], [k-2*n+1], 2)*GAMMA(2*n-k)/
(GAMMA(k)*GAMMA(n-k+1)); for n from 1 to 9 do seq(simplify(T(n, k)), k=1..n) od; # Peter Luschny, Mar 31 2015
T := (n, k) -> local j; 2^n*add((-1)^(k-j)*binomial(k, j)*pochhammer(j/2, n), j = 1..k)/k!: for n from 1 to 6 do seq(T(n, k), k=1..n) od; # Peter Luschny, Mar 04 2024
MATHEMATICA
a[n_, k_] := 2^(n+k)*n!/(4^n*n*k!)*Sum[(j+k)*2^(j)*Binomial[j + k - 1, k-1]*Binomial[2*n - j - k - 1, n-1], {j, 0, n-k}]; Flatten[Table[a[n, k], {n, 1, 9}, {k, 1, n}] ] [[1 ;; 40]] (* Jean-François Alcover, Jun 01 2011, after Vladimir Kruchinin *)
PROG
(Maxima) a(n, k):=2^(n+k)*n!/(4^n*n*k!)*sum((j+k)*2^(j)*binomial(j+k-1, k-1)*binomial(2*n-j-k-1, n-1), j, 0, n-k) /* Vladimir Kruchinin, Mar 30 2011 */
(Haskell)
a035342 n k = a035342_tabl !! (n-1) !! (k-1)
a035342_row n = a035342_tabl !! (n-1)
a035342_tabl = map fst $ iterate (\(xs, i) -> (zipWith (+)
([0] ++ xs) $ zipWith (*) [i..] (xs ++ [0]), i + 2)) ([1], 3)
-- Reinhard Zumkeller, Mar 12 2014
(Sage) # uses[bell_matrix from A264428]
# Adds a column 1, 0, 0, 0, ... at the left side of the triangle.
print(bell_matrix(lambda n: A001147(n+1), 9)) # Peter Luschny, Jan 19 2016
CROSSREFS
The column sequences are A001147, A035101, A035119, ...
Row sums: A049118(n), n >= 1.
KEYWORD
easy,nice,nonn,tabl
EXTENSIONS
Simpler name from Peter Luschny, Mar 31 2015
STATUS
approved
Triangle read by rows: T(n,k) = binomial(n,k)*(n-1)!/(k-1)!.
+10
44
1, 2, 1, 6, 6, 1, 24, 36, 12, 1, 120, 240, 120, 20, 1, 720, 1800, 1200, 300, 30, 1, 5040, 15120, 12600, 4200, 630, 42, 1, 40320, 141120, 141120, 58800, 11760, 1176, 56, 1, 362880, 1451520, 1693440, 846720, 211680, 28224, 2016, 72, 1, 3628800, 16329600
OFFSET
1,2
COMMENTS
T(n,k) is the number of partially ordered sets (posets) on n elements that consist entirely of k chains. For example, T(4, 3)=12 since there are exactly 12 posets on {a,b,c,d} that consist entirely of 3 chains. Letting ab denote a<=b and using a slash "/" to separate chains, the 12 posets can be given by a/b/cd, a/b/dc, a/c/bd, a/c/db, a/d/bc, a/d/cb, b/c/ad, b/c/da, b/d/ac, b/d/ca, c/d/ab and c/d/ba, where the listing of the chains is arbitrary (e.g., a/b/cd = a/cd/b =...cd/b/a). - Dennis P. Walsh, Feb 22 2007
Also the matrix product |S1|.S2 of Stirling numbers of both kinds.
This Lah triangle is a lower triangular matrix of the Jabotinsky type. See the column e.g.f. and the D. E. Knuth reference given in A008297. - Wolfdieter Lang, Jun 29 2007
The infinitesimal matrix generator of this matrix is given in A132710. See A111596 for an interpretation in terms of circular binary words and generalized factorials. - Tom Copeland, Nov 22 2007
Three combinatorial interpretations: T(n,k) is (1) the number of ways to split [n] = {1,...,n} into a collection of k nonempty lists ("partitions into sets of lists"), (2) the number of ways to split [n] into an ordered collection of n+1-k nonempty sets that are noncrossing ("partitions into lists of noncrossing sets"), (3) the number of Dyck n-paths with n+1-k peaks labeled 1,2,...,n+1-k in some order. - David Callan, Jul 25 2008
Given matrices A and B with A(n,k) = T(n,k)*a(n-k) and B(n,k) = T(n,k)*b(n-k), then A*B = D where D(n,k) = T(n,k)*[a(.)+b(.)]^(n-k), umbrally. - Tom Copeland, Aug 21 2008
An e.g.f. for the row polynomials of A(n,k) = T(n,k)*a(n-k) is exp[a(.)* D_x * x^2] exp(x*t) = exp(x*t) exp[(.)!*Lag(.,-x*t,1)*a(.)*x], umbrally, where [(.)! Lag(.,x,1)]^n = n! Lag(n,x,1) is a normalized Laguerre polynomial of order 1. - Tom Copeland, Aug 29 2008
Triangle of coefficients from the Bell polynomial of the second kind for f = 1/(1-x). B(n,k){x1,x2,x3,...} = B(n,k){1/(1-x)^2,...,(j-1)!/(1-x)^j,...} = T(n,k)/(1-x)^(n+k). - Vladimir Kruchinin, Mar 04 2011
The triangle, with the row and column offset taken as 0, is the generalized Riordan array (exp(x), x) with respect to the sequence n!*(n+1)! as defined by Wang and Wang (the generalized Riordan array (exp(x), x) with respect to the sequence n! is Pascal's triangle A007318, and with respect to the sequence n!^2 is A021009 unsigned). - Peter Bala, Aug 15 2013
For a relation to loop integrals in QCD, see p. 33 of Gopakumar and Gross and Blaizot and Nowak. - Tom Copeland, Jan 18 2016
Also the Bell transform of (n+1)!. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016
Also the number of k-dimensional flats of the n-dimensional Shi arrangement. - Shuhei Tsujie, Apr 26 2019
The numbers T(n,k) appear as coefficients when expanding the rising factorials (x)^k = x(x+1)...(x+k-1) in the basis of falling factorials (x)_k = x(x-1)...(x-k+1). Specifically, (x)^n = Sum_{k=1..n} T(n,k) (x)_k. - Jeremy L. Martin, Apr 21 2021
LINKS
J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
J-P. Blaizot and M. Nowak, Large N_c confinement and turbulence, arXiv:0801.1859 [hep-th], 2008.
David Callan, Sets, Lists and Noncrossing Partitions, arXiv:0711.4841 [math.CO], 2007-2008.
P. Codara, O. M. D'Antona, and P. Hell, A simple combinatorial interpretation of certain generalized Bell and Stirling numbers, arXiv preprint arXiv:1308.1700 [cs.DM], 2013.
S. Daboul, J. Mangaldan, M. Z. Spivey and P. Taylor, The Lah Numbers and the n-th Derivative of exp(1/x), Math. Mag., 86 (2013), 39-47.
G. H. E. Duchamp et al., Feynman graphs and related Hopf algebras, J. Phys. (Conf Ser) 30 (2006) 107-118.
R. Gopakumar and D. Gross, Mastering the master field, arXiv:hep-th/9411021, 1994.
G. Hetyei, Meixner polynomials of the second kind and quantum algebras representing su(1,1), arXiv preprint arXiv:0909.4352 [math.QA], 2009, p. 4. - From Tom Copeland, Oct 01 2015
Milan Janjic, Some classes of numbers and derivatives, JIS 12 (2009) 09.8.3
D. E. Knuth, Convolution polynomials, The Mathematica J., 2 (1992), 67-78.
Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO]. - From N. J. A. Sloane, Aug 21 2012
MacTutor History of Mathematics archive: Biography of Ivo Lah.
Robert S. Maier, Boson Operator Ordering Identities from Generalized Stirling and Eulerian Numbers, arXiv:2308.10332 [math.CO], 2023. See p. 19.
N. Nakashima and S. Tsujie, Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species, arXiv:1904.09748 [math.CO], 2019.
Mathias Pétréolle and Alan D. Sokal, Lattice paths and branched continued fractions. II. Multivariate Lah polynomials and Lah symmetric functions, arXiv:1907.02645 [math.CO], 2019.
Kornelia Ufniarz and Grzegorz Siudem, Combinatorial origins of the canonical ensemble, arXiv:2008.00244 [math-ph], 2020.
W. Wang and T. Wang, Generalized Riordan arrays, Discrete Mathematics, Vol. 308, No. 24, 6466-6500.
Wikipedia, Lah number
FORMULA
T(n,k) = Sum_{m=n..k} |S1(n,m)|*S2(m,k), k>=n>=1, with Stirling triangles S2(n,m):=A048993 and S1(n,m):=A048994.
T(n,k) = C(n,k)*(n-1)!/(k-1)!.
Sum_{k=1..n} T(n,k) = A000262(n).
n*Sum_{k=1..n} T(n,k) = A103194(n) = Sum_{k=1..n} T(n,k)*k^2.
E.g.f. column k: (x^(k-1)/(1-x)^(k+1))/(k-1)!, k>=1.
Recurrence from Sheffer (here Jabotinsky) a-sequence [1,1,0,...] (see the W. Lang link under A006232): T(n,k)=(n/k)*T(n-1,m-1) + n*T(n-1,m). - Wolfdieter Lang, Jun 29 2007
The e.g.f. is, umbrally, exp[(.)!* L(.,-t,1)*x] = exp[t*x/(1-x)]/(1-x)^2 where L(n,t,1) = Sum_{k=0..n} T(n+1,k+1)*(-t)^k = Sum_{k=0..n} binomial(n+1,k+1)* (-t)^k / k! is the associated Laguerre polynomial of order 1. - Tom Copeland, Nov 17 2007
For this Lah triangle, the n-th row polynomial is given umbrally by
n! C(B.(x)+1+n,n) = (-1)^n C(-B.(x)-2,n), where C(x,n)=x!/(n!(x-n)!),
the binomial coefficient, and B_n(x)= exp(-x)(xd/dx)^n exp(x), the n-th Bell / Touchard / exponential polynomial (cf. A008277). E.g.,
2! C(-B.(-x)-2,2) = (-B.(x)-2)(-B.(x)-3) = B_2(x) + 5*B_1(x) + 6 = 6 + 6x + x^2.
n! C(B.(x)+1+n,n) = n! e^(-x) Sum_{j>=0} C(j+1+n,n)x^j/j! is a corresponding Dobinski relation. See the Copeland link for the relation to inverse Mellin transform. - Tom Copeland, Nov 21 2011
The row polynomials are given by D^n(exp(x*t)) evaluated at x = 0, where D is the operator (1+x)^2*d/dx. Cf. A008277 (D = (1+x)*d/dx), A035342 (D = (1+x)^3*d/dx), A035469 (D = (1+x)^4*d/dx) and A049029 (D = (1+x)^5*d/dx). - Peter Bala, Nov 25 2011
T(n,k) = Sum_{i=k..n} A130534(n-1,i-1)*A008277(i,k). - Reinhard Zumkeller, Mar 18 2013
Let E(x) = Sum_{n >= 0} x^n/(n!*(n+1)!). Then a generating function is exp(t)*E(x*t) = 1 + (2 + x)*t + (6 + 6*x + x^2)*t^2/(2!*3!) + (24 + 36*x + 12*x^2 + x^3)*t^3/(3!*4!) + ... . - Peter Bala, Aug 15 2013
P_n(x) = L_n(1+x) = n!*Lag_n(-(1+x);1), where P_n(x) are the row polynomials of A059110; L_n(x), the Lah polynomials of A105278; and Lag_n(x;1), the Laguerre polynomials of order 1. These relations follow from the relation between the iterated operator (x^2 D)^n and ((1+x)^2 D)^n with D = d/dx. - Tom Copeland, Jul 23 2018
Dividing each n-th diagonal by n!, where the main diagonal is n=1, generates the Narayana matrix A001263. - Tom Copeland, Sep 23 2020
T(n,k) = A089231(n,n-k). - Ron L.J. van den Burg, Dec 12 2021
EXAMPLE
T(1,1) = C(1,1)*0!/0! = 1,
T(2,1) = C(2,1)*1!/0! = 2,
T(2,2) = C(2,2)*1!/1! = 1,
T(3,1) = C(3,1)*2!/0! = 6,
T(3,2) = C(3,2)*2!/1! = 6,
T(3,3) = C(3,3)*2!/2! = 1,
Sheffer a-sequence recurrence: T(6,2)= 1800 = (6/3)*120 + 6*240.
B(n,k) =
1/(1-x)^2;
2/(1-x)^3, 1/(1-x)^4;
6/(1-x)^4, 6/(1-x)^5, 1/(1-x)^6;
24/(1-x)^5, 36/(1-x)^6, 12/(1-x)^7, 1/(1-x)^8;
The triangle T(n,k) begins:
n\k 1 2 3 4 5 6 7 8 9 ...
1: 1
2: 2 1
3: 6 6 1
4: 24 36 12 1
5: 120 240 120 20 1
6: 720 1800 1200 300 30 1
7: 5040 15120 12600 4200 630 42 1
8: 40320 141120 141120 58800 11760 1176 56 1
9: 362880 1451520 1693440 846720 211680 28224 2016 72 1
...
Row n=10: [3628800, 16329600, 21772800, 12700800, 3810240, 635040, 60480, 3240, 90, 1]. - Wolfdieter Lang, Feb 01 2013
MAPLE
The triangle: for n from 1 to 13 do seq(binomial(n, k)*(n-1)!/(k-1)!, k=1..n) od;
the sequence: seq(seq(binomial(n, k)*(n-1)!/(k-1)!, k=1..n), n=1..13);
# The function BellMatrix is defined in A264428.
# Adds (1, 0, 0, 0, ...) as column 0.
BellMatrix(n -> (n+1)!, 9); # Peter Luschny, Jan 27 2016
MATHEMATICA
nn = 9; a = x/(1 - x); f[list_] := Select[list, # > 0 &]; Flatten[Map[f, Drop[Range[0, nn]! CoefficientList[Series[Exp[y a], {x, 0, nn}], {x, y}], 1]]] (* Geoffrey Critzer, Dec 11 2011 *)
nn = 9; Flatten[Table[(j - k)! Binomial[j, k] Binomial[j - 1, k - 1], {j, nn}, {k, j}]] (* Jan Mangaldan, Mar 15 2013 *)
rows = 10;
t = Range[rows]!;
T[n_, k_] := BellY[n, k, t];
Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 23 2018, after Peter Luschny *)
PROG
(Haskell)
a105278 n k = a105278_tabl !! (n-1) !! (k-1)
a105278_row n = a105278_tabl !! (n-1)
a105278_tabl = [1] : f [1] 2 where
f xs i = ys : f ys (i + 1) where
ys = zipWith (+) ([0] ++ xs) (zipWith (*) [i, i + 1 ..] (xs ++ [0]))
-- Reinhard Zumkeller, Sep 30 2014, Mar 18 2013
(Magma) /* As triangle */ [[Binomial(n, k)*Factorial(n-1)/Factorial(k-1): k in [1..n]]: n in [1.. 15]]; // Vincenzo Librandi, Oct 31 2014
(Perl) use ntheory ":all"; say join ", ", map { my $n=$_; map { stirling($n, $_, 3) } 1..$n; } 1..9; # Dana Jacobsen, Mar 16 2017
(GAP) Flat(List([1..10], n->List([1..n], k->Binomial(n, k)*Factorial(n-1)/Factorial(k-1)))); # Muniru A Asiru, Jul 25 2018
CROSSREFS
Triangle of Lah numbers (A008297) unsigned.
Cf. A111596 (signed triangle with extra n=0 row and m=0 column).
Cf. A130561 (for a natural refinement).
Cf. A094638 (for differential operator representation).
Cf. A248045 (central terms), A002868 (row maxima).
Cf, A059110.
Cf. A089231 (triangle with mirrored rows).
Cf. A271703 (triangle with extra n=0 row and m=0 column).
KEYWORD
easy,nonn,tabl
AUTHOR
Miklos Kristof, Apr 25 2005
EXTENSIONS
Stirling comments and e.g.f.s from Wolfdieter Lang, Apr 11 2007
STATUS
approved
Triangle read by rows, the Bell transform of the triple factorial numbers A007559(n+1) without column 0.
+10
38
1, 4, 1, 28, 12, 1, 280, 160, 24, 1, 3640, 2520, 520, 40, 1, 58240, 46480, 11880, 1280, 60, 1, 1106560, 987840, 295960, 40040, 2660, 84, 1, 24344320, 23826880, 8090880, 1296960, 109200, 4928, 112, 1, 608608000, 643843200
OFFSET
1,2
COMMENTS
Previous name was: Triangle of numbers related to triangle A035529; generalization of Stirling numbers of second kind A008277, Lah-numbers A008297 and A035342.
a(n,m) enumerates unordered n-vertex m-forests composed of m plane increasing quartic (4-ary) trees. Proof based on the a(n,m) recurrence. See a D. Callan comment on the m=1 case A007559. See also the F. Bergeron et al. reference, especially Table 1, first row and Example 1 for the e.g.f. for m=1. - Wolfdieter Lang, Sep 14 2007
For the definition of the Bell transform see A264428. - Peter Luschny, Jan 19 2016
REFERENCES
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, in Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1922, pp. 24-48.
LINKS
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, arXiv:quant-ph/0402027, 2004.
Richell O. Celeste, Roberto B. Corcino and Ken Joffaniel M. Gonzales. Two Approaches to Normal Order Coefficients. Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.5.
Tom Copeland, Mathemagical Forests
Milan Janjic, Some classes of numbers and derivatives, JIS 12 (2009) 09.8.3
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
Wolfdieter Lang, First 10 rows.
Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO]. - From N. J. A. Sloane, Aug 21 2012
E. Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 (2001) 33-51.
Mathias Pétréolle and Alan D. Sokal, Lattice paths and branched continued fractions. II. Multivariate Lah polynomials and Lah symmetric functions, arXiv:1907.02645 [math.CO], 2019.
FORMULA
a(n, m) = Sum_{j=m..n} |A051141(n, j)|*S2(j, m) (matrix product), with S2(j, m):=A008277(j, m) (Stirling2 triangle). Priv. comm. to Wolfdieter Lang by E. Neuwirth, Feb 15 2001; see also the 2001 Neuwirth reference. See the general comment on products of Jabotinsky matrices given under A035342.
a(n, m) = n!*A035529(n, m)/(m!*3^(n-m)); a(n+1, m) = (3*n+m)*a(n, m) + a(n, m-1), n >= m >= 1; a(n, m) := 0, n < m; a(n, 0) := 0, a(1, 1)=1;
E.g.f. of m-th column: ((-1+(1-3*x)^(-1/3))^m)/m!.
From Peter Bala, Nov 25 2011: (Start)
E.g.f.: G(x,t) = exp(t*A(x)) = 1 + t*x + (4*t+t^2)*x^2/2! + (28*t + 12*t^2 + t^3)*x^3/3! + ..., where A(x) = -1 + (1-3*x)^(-1/3) satisfies the autonomous differential equation A'(x) = (1+A(x))^4.
The generating function G(x,t) satisfies the partial differential equation t*(dG/dt+G) = (1-3*x)*dG/dx, from which follows the recurrence given above.
The row polynomials are given by D^n(exp(x*t)) evaluated at x = 0, where D is the operator (1+x)^4*d/dx. Cf. A008277 (D = (1+x)*d/dx), A105278 (D = (1+x)^2*d/dx), A035342 (D = (1+x)^3*d/dx) and A049029 (D = (1+x)^5*d/dx).
(End)
Dobinski-type formula for the row polynomials: R(n,x) = exp(-x)*Sum_{k>=0} k*(k+3)*(k+6)*...*(k+3*(n-1))*x^k/k!. - Peter Bala, Jun 23 2014
EXAMPLE
Triangle starts:
{1}
{4, 1}
{28, 12, 1}
{280, 160, 24, 1}
{3640, 2520, 520, 40, 1}
MATHEMATICA
a[n_, m_] /; n >= m >= 1 := a[n, m] = (3(n-1) + m)*a[n-1, m] + a[n-1, m-1]; a[n_, m_] /; n < m = 0; a[_, 0] = 0; a[1, 1] = 1; Flatten[Table[a[n, m], {n, 1, 9}, {m, 1, n}]] (* Jean-François Alcover, Jul 22 2011 *)
rows = 9;
a[n_, m_] := BellY[n, m, Table[Product[3k+1, {k, 0, j}], {j, 0, rows}]];
Table[a[n, m], {n, 1, rows}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jun 22 2018 *)
PROG
(Sage) # uses[bell_matrix from A264428]
# Adds a column 1, 0, 0, 0, ... at the left side of the triangle.
bell_matrix(lambda n: A007559(n+1) , 9) # Peter Luschny, Jan 19 2016
CROSSREFS
a(n, m)=: S2(4, n, m) is the fourth triangle of numbers in the sequence S2(1, n, m) := A008277(n, m) (Stirling 2nd kind), S2(2, n, m) := A008297(n, m) (Lah), S2(3, n, m) := A035342(n, m). a(n, 1)= A007559(n).
Row sums: A049119(n), n >= 1.
Cf. A094638.
KEYWORD
easy,nice,nonn,tabl
EXTENSIONS
New name from Peter Luschny, Jan 19 2016
STATUS
approved
Triangle of numbers related to triangle A049375; generalization of Stirling numbers of second kind A008277, Lah-numbers A008297...
+10
33
1, 6, 1, 66, 18, 1, 1056, 372, 36, 1, 22176, 9240, 1200, 60, 1, 576576, 271656, 42840, 2940, 90, 1, 17873856, 9269568, 1685376, 142800, 6090, 126, 1, 643458816, 360847872, 73313856, 7254576, 386400, 11256, 168, 1, 26381811456, 15799069440
OFFSET
1,2
COMMENTS
a(n,m) := S2(6; n,m) is the sixth triangle of numbers in the sequence S2(k; n,m), k=1..6: A008277 (unsigned Stirling 2nd kind), A008297 (unsigned Lah), A035342, A035469, A049029, respectively. a(n,1)= A008548(n).
a(n,m) enumerates unordered n-vertex m-forests composed of m plane increasing 6-ary trees. Proof based on the a(n,m) recurrence. See also the F. Bergeron et al. reference, especially Table 1, first row and Example 1 for the e.g.f. for m=1. - Wolfdieter Lang, Sep 14 2007
LINKS
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48. Added Mar 01 2014.
F. Bergeron, Philippe Flajolet and Bruno Salvy, Varieties of increasing trees, HAL, Rapport De Recherche Inria. Added Mar 01 2014.
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, arXiv:quant-ph/0402027, 2004.
M. Janjic, Some classes of numbers and derivatives, JIS 12 (2009) 09.8.3
W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
W. Lang, First 10 rows.
Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO]. - From N. J. A. Sloane, Aug 21 2012
E. Neuwirth, Recursively defined combinatorial Functions: Extending Galton's board, Discr. Maths. 239 (2001) 33-51.
FORMULA
a(n, m) = n!*A049375(n, m)/(m!*5^(n-m)); a(n+1, m) = (5*n+m)*a(n, m)+ a(n, m-1), n >= m >= 1; a(n, m) := 0, n<m; a(n, 0) := 0, a(1, 1)=1; E.g.f. of m-th column: ((-1+(1-5*x)^(-1/5))^m)/m!.
a(n, m) = sum(|A051150(n, j)|*S2(j, m), j=m..n) (matrix product), with S2(j, m) := A008277(j, m) (Stirling2 triangle). Priv. comm. to Wolfdieter Lang by E. Neuwirth, Feb 15 2001; see also the 2001 Neuwirth reference. See the general comment on products of Jabotinsky matrices given under A035342.
EXAMPLE
Triangle begins:
{1};
{6,1};
{66,18,1};
{1056,372,36,1};
...
MAPLE
# The function BellMatrix is defined in A264428.
# Adds (1, 0, 0, 0, ..) as column 0.
BellMatrix(n -> mul(5*k+1, k=0..n), 9); # Peter Luschny, Jan 28 2016
MATHEMATICA
a[n_, m_] := n!*Coefficient[Series[((-1 + (1 - 5*x)^(-1/5))^m)/m!, {x, 0, n}], x^n];
Flatten[Table[a[n, m], {n, 1, 9}, {m, 1, n}]][[1 ;; 38]]
(* Jean-François Alcover, Jun 21 2011, after e.g.f. *)
rows = 9;
t = Table[Product[5k+1, {k, 0, n}], {n, 0, rows}];
T[n_, k_] := BellY[n, k, t];
Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 22 2018, after Peter Luschny *)
CROSSREFS
Cf. A049412.
KEYWORD
easy,nonn,tabl
STATUS
approved

Search completed in 0.031 seconds