|
%I #206 Aug 23 2023 10:45:06
%S 1,2,1,6,6,1,24,36,12,1,120,240,120,20,1,720,1800,1200,300,30,1,5040,
%T 15120,12600,4200,630,42,1,40320,141120,141120,58800,11760,1176,56,1,
%U 362880,1451520,1693440,846720,211680,28224,2016,72,1,3628800,16329600
%N Triangle read by rows: T(n,k) = binomial(n,k)*(n-1)!/(k-1)!.
%C 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
%C Also the matrix product |S1|.S2 of Stirling numbers of both kinds.
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%C For a relation to loop integrals in QCD, see p. 33 of Gopakumar and Gross and Blaizot and Nowak. - _Tom Copeland_, Jan 18 2016
%C Also the Bell transform of (n+1)!. For the definition of the Bell transform see A264428. - _Peter Luschny_, Jan 27 2016
%C Also the number of k-dimensional flats of the n-dimensional Shi arrangement. - _Shuhei Tsujie_, Apr 26 2019
%C 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
%H Reinhard Zumkeller, <a href="/A105278/b105278.txt">Rows n = 1..100 of triangle, flattened</a>
%H J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, <a href="http://arxiv.org/abs/1307.2010">Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure</a>, arXiv:1307.2010 [math.CO], 2013.
%H Paul Barry, <a href="http://arxiv.org/abs/1105.3043">Eulerian polynomials as moments, via exponential Riordan arrays</a>, arXiv preprint arXiv:1105.3043 [math.CO], 2011, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry7/barry172.html">J. Int. Seq. 14 (2011) # 11.9.5</a>
%H J-P. Blaizot and M. Nowak, <a href="http://arxiv.org/abs/0801.1859">Large N_c confinement and turbulence</a>, arXiv:0801.1859 [hep-th], 2008.
%H David Callan, <a href="http://arxiv.org/abs/0711.4841">Sets, Lists and Noncrossing Partitions</a>, arXiv:0711.4841 [math.CO], 2007-2008.
%H P. Codara, O. M. D'Antona, and P. Hell, <a href="http://arxiv.org/abs/1308.1700">A simple combinatorial interpretation of certain generalized Bell and Stirling numbers</a>, arXiv preprint arXiv:1308.1700 [cs.DM], 2013.
%H Tom Copeland, <a href="https://tcjpn.wordpress.com/2008/06/12/mathemagical-forests/">Mathemagical Forests</a>, <a href="https://tcjpn.wordpress.com/2010/12/28/14/">Addendum to Mathemagical Forests</a>, <a href="https://tcjpn.wordpress.com/2011/11/16/a-generalized-dobinski-relation-and-the-confluent-hypergeometric-fcts/">The Inverse Mellin Transform, Bell Polynomials, a Generalized Dobinski Relation, and the Confluent Hypergeometric Functions</a>, <a href="http://tcjpn.wordpress.com/2015/08/23/a-class-of-differential-operators-and-the-stirling-numbers/">A Class of Differential Operators and the Stirling Numbers</a>
%H S. Daboul, J. Mangaldan, M. Z. Spivey and P. Taylor, <a href="http://math.pugetsound.edu/~mspivey/Exp.pdf">The Lah Numbers and the n-th Derivative of exp(1/x)</a>, Math. Mag., 86 (2013), 39-47.
%H G. H. E. Duchamp et al., <a href="http://dx.doi.org/10.1088/1742-6596/30/1/014">Feynman graphs and related Hopf algebras</a>, J. Phys. (Conf Ser) 30 (2006) 107-118.
%H R. Gopakumar and D. Gross, <a href="http://arxiv.org/abs/hep-th/9411021">Mastering the master field</a>, arXiv:hep-th/9411021, 1994.
%H G. Hetyei, <a href="http://arxiv.org/abs/0909.4352">Meixner polynomials of the second kind and quantum algebras representing su(1,1)</a>, arXiv preprint arXiv:0909.4352 [math.QA], 2009, p. 4. - From _Tom Copeland_, Oct 01 2015
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Janjic/janjic22.html">Some classes of numbers and derivatives</a>, JIS 12 (2009) 09.8.3
%H D. E. Knuth, <a href="http://arxiv.org/abs/math/9207221">Convolution polynomials</a>, The Mathematica J., 2 (1992), 67-78.
%H Shi-Mei Ma, <a href="http://arxiv.org/abs/1208.3104">Some combinatorial sequences associated with context-free grammars</a>, arXiv:1208.3104v2 [math.CO]. - From _N. J. A. Sloane_, Aug 21 2012
%H MacTutor History of Mathematics archive: <a href="http://www-history.mcs.st-andrews.ac.uk/history/Biographies/Lah.html">Biography of Ivo Lah.</a>
%H Robert S. Maier, <a href="https://arxiv.org/abs/2308.10332">Boson Operator Ordering Identities from Generalized Stirling and Eulerian Numbers</a>, arXiv:2308.10332 [math.CO], 2023. See p. 19.
%H N. Nakashima and S. Tsujie, <a href="https://arxiv.org/abs/1904.09748">Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species</a>, arXiv:1904.09748 [math.CO], 2019.
%H Mathias Pétréolle and Alan D. Sokal, <a href="https://arxiv.org/abs/1907.02645">Lattice paths and branched continued fractions. II. Multivariate Lah polynomials and Lah symmetric functions</a>, arXiv:1907.02645 [math.CO], 2019.
%H Tilman Piesk, <a href="https://commons.wikimedia.org/wiki/File:Lah_numbers.svg">Illustration of the first four rows</a>
%H Kornelia Ufniarz and Grzegorz Siudem, <a href="https://arxiv.org/abs/2008.00244">Combinatorial origins of the canonical ensemble</a>, arXiv:2008.00244 [math-ph], 2020.
%H W. Wang and T. Wang, <a href="https://doi.org/10.1016/j.disc.2007.12.037">Generalized Riordan arrays</a>, Discrete Mathematics, Vol. 308, No. 24, 6466-6500.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lah_number">Lah number</a>
%F 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.
%F T(n,k) = C(n,k)*(n-1)!/(k-1)!.
%F Sum_{k=1..n} T(n,k) = A000262(n).
%F n*Sum_{k=1..n} T(n,k) = A103194(n) = Sum_{k=1..n} T(n,k)*k^2.
%F E.g.f. column k: (x^(k-1)/(1-x)^(k+1))/(k-1)!, k>=1.
%F 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
%F 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
%F For this Lah triangle, the n-th row polynomial is given umbrally by
%F n! C(B.(x)+1+n,n) = (-1)^n C(-B.(x)-2,n), where C(x,n)=x!/(n!(x-n)!),
%F 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.,
%F 2! C(-B.(-x)-2,2) = (-B.(x)-2)(-B.(x)-3) = B_2(x) + 5*B_1(x) + 6 = 6 + 6x + x^2.
%F 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
%F 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
%F T(n,k) = Sum_{i=k..n} A130534(n-1,i-1)*A008277(i,k). - _Reinhard Zumkeller_, Mar 18 2013
%F 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
%F 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
%F Dividing each n-th diagonal by n!, where the main diagonal is n=1, generates the Narayana matrix A001263. - _Tom Copeland_, Sep 23 2020
%F T(n,k) = A089231(n,n-k). - _Ron L.J. van den Burg_, Dec 12 2021
%e T(1,1) = C(1,1)*0!/0! = 1,
%e T(2,1) = C(2,1)*1!/0! = 2,
%e T(2,2) = C(2,2)*1!/1! = 1,
%e T(3,1) = C(3,1)*2!/0! = 6,
%e T(3,2) = C(3,2)*2!/1! = 6,
%e T(3,3) = C(3,3)*2!/2! = 1,
%e Sheffer a-sequence recurrence: T(6,2)= 1800 = (6/3)*120 + 6*240.
%e B(n,k) =
%e 1/(1-x)^2;
%e 2/(1-x)^3, 1/(1-x)^4;
%e 6/(1-x)^4, 6/(1-x)^5, 1/(1-x)^6;
%e 24/(1-x)^5, 36/(1-x)^6, 12/(1-x)^7, 1/(1-x)^8;
%e The triangle T(n,k) begins:
%e n\k 1 2 3 4 5 6 7 8 9 ...
%e 1: 1
%e 2: 2 1
%e 3: 6 6 1
%e 4: 24 36 12 1
%e 5: 120 240 120 20 1
%e 6: 720 1800 1200 300 30 1
%e 7: 5040 15120 12600 4200 630 42 1
%e 8: 40320 141120 141120 58800 11760 1176 56 1
%e 9: 362880 1451520 1693440 846720 211680 28224 2016 72 1
%e ...
%e Row n=10: [3628800, 16329600, 21772800, 12700800, 3810240, 635040, 60480, 3240, 90, 1]. - _Wolfdieter Lang_, Feb 01 2013
%p The triangle: for n from 1 to 13 do seq(binomial(n,k)*(n-1)!/(k-1)!,k=1..n) od;
%p the sequence: seq(seq(binomial(n,k)*(n-1)!/(k-1)!,k=1..n),n=1..13);
%p # The function BellMatrix is defined in A264428.
%p # Adds (1, 0, 0, 0, ...) as column 0.
%p BellMatrix(n -> (n+1)!, 9); # _Peter Luschny_, Jan 27 2016
%t 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 *)
%t nn = 9; Flatten[Table[(j - k)! Binomial[j, k] Binomial[j - 1, k - 1], {j, nn}, {k, j}]] (* _Jan Mangaldan_, Mar 15 2013 *)
%t rows = 10;
%t t = Range[rows]!;
%t T[n_, k_] := BellY[n, k, t];
%t Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jun 23 2018, after _Peter Luschny_ *)
%o (Haskell)
%o a105278 n k = a105278_tabl !! (n-1) !! (k-1)
%o a105278_row n = a105278_tabl !! (n-1)
%o a105278_tabl = [1] : f [1] 2 where
%o f xs i = ys : f ys (i + 1) where
%o ys = zipWith (+) ([0] ++ xs) (zipWith (*) [i, i + 1 ..] (xs ++ [0]))
%o -- _Reinhard Zumkeller_, Sep 30 2014, Mar 18 2013
%o (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
%o (Perl) use ntheory ":all"; say join ", ", map { my $n=$_; map { stirling($n,$_,3) } 1..$n; } 1..9; # _Dana Jacobsen_, Mar 16 2017
%o (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
%Y Cf. A000262, A103194, A105220.
%Y Triangle of Lah numbers (A008297) unsigned.
%Y Cf. A111596 (signed triangle with extra n=0 row and m=0 column).
%Y Cf. A130561 (for a natural refinement).
%Y Cf. A094638 (for differential operator representation).
%Y Cf. A248045 (central terms), A002868 (row maxima).
%Y Cf, A059110.
%Y Cf. A001263, A008277.
%Y Cf. A089231 (triangle with mirrored rows).
%Y Cf. A271703 (triangle with extra n=0 row and m=0 column).
%K easy,nonn,tabl
%O 1,2
%A _Miklos Kristof_, Apr 25 2005
%E Stirling comments and e.g.f.s from _Wolfdieter Lang_, Apr 11 2007
|
