|
%I #243 Jul 27 2022 03:04:25
%S 1,1,1,2,2,1,6,6,3,1,24,24,12,4,1,120,120,60,20,5,1,720,720,360,120,
%T 30,6,1,5040,5040,2520,840,210,42,7,1,40320,40320,20160,6720,1680,336,
%U 56,8,1,362880,362880,181440,60480,15120,3024,504,72,9,1,3628800,3628800
%N Triangle of permutation coefficients arranged with 1's on the diagonal. Also, triangle of permutations on n letters with exactly k+1 cycles and with the first k+1 letters in separate cycles.
%C Also, table of Pochhammer sequences read by antidiagonals (see Rudolph-Lilith, 2015). - _N. J. A. Sloane_, Mar 31 2016
%C Reverse of A008279. Row sums are A000522. Diagonal sums are A003470. Rows of inverse matrix begin {1}, {-1,1}, {0,-2,1}, {0,0,-3,1}, {0,0,0,-4,1} ... The signed lower triangular matrix (-1)^(n+k)n!/k! has as row sums the signed rencontres numbers Sum_{k=0..n} (-1)^(n+k)n!/k!. (See A000166). It has matrix inverse 1 1,1 0,2,1 0,0,3,1 0,0,0,4,1,...
%C Exponential Riordan array [1/(1-x),x]; column k has e.g.f. x^k/(1-x). - _Paul Barry_, Mar 27 2007
%C From _Tom Copeland_, Nov 01 2007: (Start)
%C T is the umbral extension of n!*Lag[n,(.)!*Lag[.,x,-1],0] = (1-D)^(-1) x^n = (-1)^n * n! * Lag(n,x,-1-n) = Sum_{j=0..n} binomial(n,j) * j! * x^(n-j) = Sum_{j=0..n} (n!/j!) x^j. The inverse operator is A132013 with generalizations discussed in A132014.
%C b = T*a can be characterized several ways in terms of a(n) and b(n) or their o.g.f.'s A(x) and B(x).
%C 1) b(n) = n! Lag[n,(.)!*Lag[.,a(.),-1],0], umbrally,
%C 2) b(n) = (-1)^n n! Lag(n,a(.),-1-n)
%C 3) b(n) = Sum_{j=0..n} (n!/j!) a(j)
%C 4) B(x) = (1-xDx)^(-1) A(x), formally
%C 5) B(x) = Sum_{j=0,1,...} (xDx)^j A(x)
%C 6) B(x) = Sum_{j=0,1,...} x^j * D^j * x^j A(x)
%C 7) B(x) = Sum_{j=0,1,...} j! * x^j * L(j,-:xD:,0) A(x) where Lag(n,x,m) are the Laguerre polynomials of order m, D the derivative w.r.t. x and (:xD:)^j = x^j * D^j. Truncating the operator series at the j = n term gives an o.g.f. for b(0) through b(n).
%C c = (0!,1!,2!,3!,4!,...) is the sequence associated to T under the list partition transform and the associated operations described in A133314 so T(n,k) = binomial(n,k)*c(n-k). The reciprocal sequence is d = (1,-1,0,0,0,...). (End)
%C From _Peter Bala_, Jul 10 2008: (Start)
%C This array is the particular case P(1,1) of the generalized Pascal triangle P(a,b), a lower unit triangular matrix, shown below:
%C n\k|0.....................1...............2.......3......4
%C ----------------------------------------------------------
%C 0..|1.....................................................
%C 1..|a....................1................................
%C 2..|a(a+b)...............2a..............1................
%C 3..|a(a+b)(a+2b).........3a(a+b).........3a........1......
%C 4..|a(a+b)(a+2b)(a+3b)...4a(a+b)(a+2b)...6a(a+b)...4a....1
%C ...
%C The entries A(n,k) of this array satisfy the recursion A(n,k) = (a+b*(n-k-1))*A(n-1,k) + A(n-1,k-1), which reduces to the Pascal formula when a = 1, b = 0.
%C Various cases are recorded in the database, including: P(1,0) = Pascal's triangle A007318, P(2,0) = A038207, P(3,0) = A027465, P(2,1) = A132159, P(1,3) = A136215 and P(2,3) = A136216.
%C When b <> 0 the array P(a,b) has e.g.f. exp(x*y)/(1-b*y)^(a/b) = 1 + (a+x)*y + (a*(a+b)+2a*x+x^2)*y^2/2! + (a*(a+b)*(a+2b) + 3a*(a+b)*x + 3a*x^2+x^3)*y^3/3! + ...; the array P(a,0) has e.g.f. exp((x+a)*y).
%C We have the matrix identities P(a,b)*P(a',b) = P(a+a',b); P(a,b)^-1 = P(-a,b).
%C An analog of the binomial expansion for the row entries of P(a,b) has been proved by [Echi]. Introduce a (generally noncommutative and nonassociative) product ** on the ring of polynomials in two variables by defining F(x,y)**G(x,y) = F(x,y)G(x,y) + by^2*d/dy(G(x,y)).
%C Define the iterated product F^(n)(x,y) of a polynomial F(x,y) by setting F^(1) = F(x,y) and F^(n)(x,y) = F(x,y)**F^(n-1)(x,y) for n >= 2. Then (x+a*y)^(n) = x^n + C(n,1)*a*x^(n-1)*y + C(n,2)*a*(a+b)*x^(n-2)*y^2 + ... + C(n,n)*a*(a+b)*(a+2b)*...*(a+(n-1)b)*y^n. (End)
%C (n+1) * n-th row = reversal of triangle A068424: (1; 2,2; 6,6,3; ...) - _Gary W. Adamson_, May 03 2009
%C Let G(m, k, p) = (-p)^k*Product_{j=0..k-1}(j - m - 1/p) and T(n,k,p) = G(n-1,n-k,p) then T(n, k, 1) is this sequence, T(n, k, 2) = A112292(n, k) and T(n, k, 3) = A136214. - _Peter Luschny_, Jun 01 2009, revised Jun 18 2019
%C The higher order exponential integrals E(x,m,n) are defined in A163931. For a discussion of the asymptotic expansions of the E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + (n^2+n)/x^2 - (2*n+3*n^2+n^3)/x^3 + (6*n+11*n^2+6*n^3+n^4)/x^3 - ...) see A130534. The asymptotic expansion of E(x,m=1,n) leads for n >= 1 to the left hand columns of the triangle given above. Triangle A165674 is generated by the asymptotic expansions of E(x,m=2,n). - _Johannes W. Meijer_, Oct 07 2009
%C T(n,k) = n!/k! = number of permutations of [n+1] with exactly k+1 cycles and with elements 1,2,...,k+1 in separate cycles. See link and example below. - _Dennis P. Walsh_, Jan 24 2011
%C T(n,k) is the number of n permutations that leave some size k subset of {1,2,...,n} fixed. Sum_{k=0..n}(-1)^k*T(n,k) = A000166(n) (the derangements). - _Geoffrey Critzer_, Dec 11 2011
%C T(n,k) = A162995(n-1,k-1), 2 <= k <= n; T(n,k) = A173333(n,k), 1 <= k <= n. - _Reinhard Zumkeller_, Jul 05 2012
%C The row polynomials form an Appell sequence. The matrix is a special case of a group of general matrices sketched in A132382. - _Tom Copeland_, Dec 03 2013
%C For interpretations in terms of colored necklaces, see A213936 and A173333. - _Tom Copeland_, Aug 18 2016
%C See A008279 for a relation of this entry to the e.g.f.s enumerating the faces of permutahedra and stellahedra. - _Tom Copeland_, Nov 14 2016
%C Also, T(n,k) is the number of ways to arrange n-k nonattacking rooks on the n X (n-k) chessboard. - _Andrey Zabolotskiy_, Dec 16 2016
%C The infinitesimal generator of this triangle is the generalized exponential Riordan array [-log(1-x), x] and equals the unsigned version of A238363. - _Peter Bala_, Feb 13 2017
%C Formulas for exponential and power series infinitesimal generators for this triangle T are given in Copeland's 2012 and 2014 formulas as T = unsigned exp[(I-A238385)] = 1/(I - A132440), where I is the identity matrix. - _Tom Copeland_, Jul 03 2017
%C If A(0) = 1/(1-x), and A(n) = d/dx(A(n-1)), then A(n) = n!/(1-x)^(n+1) = Sum_{k>=0} (n+k)!/k!*x^k = Sum_{k>=0} T(n+k, k)*x^k. - _Michael Somos_, Sep 19 2021
%H Reinhard Zumkeller, <a href="/A094587/b094587.txt">Rows n = 0..149 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="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barry3/barry100r.html">The Restricted Toda Chain, Exponential Riordan Arrays, and Hankel Transforms</a>, J. Int. Seq. 13 (2010) # 10.8.4, example 3.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barry4/barry122.html">Exponential Riordan Arrays and Permutation Enumeration</a>, J. Int. Seq. 13 (2010) # 10.9.1, example 5.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry1/barry97r2.html">Riordan Arrays, Orthogonal Polynomials as Moments, and Hankel Transforms</a>, J. Int. Seq. 14 (2011) # 11.2.2, example 17.
%H Paul Barry, <a href="http://arxiv.org/abs/1105.3044">Combinatorial polynomials as moments, Hankel transforms and exponential Riordan arrays</a>, arXiv:1105.3044 [math.CO], 2011, also <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry5/barry112.html">J. Int. Seq. 14 (2011) 11.6.7</a>.
%H Paul Barry, <a href="https://arxiv.org/abs/1804.06801">A note on number triangles that are almost their own production matrix</a>, arXiv:1804.06801 [math.CO], 2018.
%H Paul Barry, <a href="https://arxiv.org/abs/2101.06713">On the inversion of Riordan arrays</a>, arXiv:2101.06713 [math.CO], 2021.
%H Tom Copeland, <a href="http://tcjpn.wordpress.com/2014/08/03/goin-with-the-flow-logarithm-of-the-derivative/">Goin' with the Flow: Logarithm of the Derivative Operator</a> Part V, 2014.
%H T. Copeland, <a href="https://tcjpn.wordpress.com/2016/11/06/compositional-inverse-operators-and-sheffer-sequences/">Compositional inverse operators and Sheffer sequences</a>, 2016.
%H E. Deutsch, L. Ferrari and S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.aam.2004.05.002">Production Matrices</a>, Advances in Mathematics, 34 (2005) pp. 101-122.
%H Othman Echi, <a href="http://www.academicjournals.org/article/article1380188236_Echi.pdf">Binomial coefficients and Nasir al-Din al-Tusi</a>, Scientific Research and Essays Vol.1 (2), 28-32 November 2006.
%H H. W. Gould, ed. J. Quaintance, <a href="http://www.math.wvu.edu/~gould/Vol.4.PDF">Combinatorial Identities</a>, May 2010 (eqn. 10.35, p.49).
%H A. Hennessy and P. Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry6/barry161.html">Generalized Stirling Numbers, Exponential Riordan Arrays, and Orthogonal Polynomials</a>, J. Int. Seq. 14 (2011) # 11.8.2.
%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 Peter Luschny, <a href="http://www.luschny.de/math/seq/variations.html">Variants of Variations</a>.
%H Michelle Rudolph-Lilith, <a href="http://arxiv.org/abs/1508.07894">On the Product Representation of Number Sequences, with Application to the Fibonacci Family</a>, arXiv preprint arXiv:1508.07894 [math.NT], 2015.
%H M. Z. Spivey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Spivey/spivey31.html">On Solutions to a General Combinatorial Recurrence</a>, J. Int. Seq. 14 (2011) # 11.9.7.
%H Dennis Walsh, <a href="http://frank.mtsu.edu/~dwalsh/PERMCYC1.pdf">A note on permutations with cyclic constraints</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Sheffer_sequence">Sheffer sequence</a>
%F T(n, k) = n!/k! if n >= k >= 0, otherwise 0.
%F T(n, k) = Sum_{i=k..n} |S1(n+1, i+1)*S2(i, k)| * (-1)^i, with S1, S2 the Stirling numbers.
%F T(n,k) = (n-k)*T(n-1,k) + T(n-1,k-1). E.g.f.: exp(x*y)/(1-y) = 1 + (1+x)*y + (2+2*x+x^2)*y^2/2! + (6+6*x+3*x^2+x^3)*y^3/3!+ ... . - _Peter Bala_, Jul 10 2008
%F A094587 = 1 / ((-1)*A129184 * A127648 + I), I = Identity matrix. - _Gary W. Adamson_, May 03 2009
%F From _Johannes W. Meijer_, Oct 07 2009: (Start)
%F The o.g.f. of right hand column k is Gf(z;k) = (k-1)!/(1-z)^k, k => 1.
%F The recurrence relations of the right hand columns lead to Pascal's triangle A007318. (End)
%F Let f(x) = (1/x)*exp(-x). The n-th row polynomial is R(n,x) = (-x)^n/f(x)*(d/dx)^n(f(x)), and satisfies the recurrence equation R(n+1,x) = (x+n+1)*R(n,x)-x*R'(n,x). Cf. A132159. - _Peter Bala_, Oct 28 2011
%F A padded shifted version of this lower triangular matrix with zeros in the first column and row except for a one in the diagonal position is given by integral(t=0 to t=infinity) exp[-t(I-P)] = 1/(I-P) = I + P^2 + P^3 + ... where P is the infinitesimal generator matrix A218234 and I the identity matrix. The non-padded version is given by P replaced by A132440. - _Tom Copeland_, Oct 25 2012
%F From _Peter Bala_, Aug 28 2013: (Start)
%F The row polynomials R(n,x) form a Sheffer sequence of polynomials with associated delta operator equal to d/dx. Thus d/dx(R(n,x)) = n*R(n-1,x). The Sheffer identity is R(n,x + y) = Sum_{k=0..n} binomial(n,k)*y^(n-k)*R(k,x).
%F Let P(n,x) = Product_{k=0..n-1} (x + k) denote the rising factorial polynomial sequence with the convention that P(0,x) = 1. Then this is triangle of connection constants when expressing the basis polynomials P(n,x + 1) in terms of the basis P(n,x). For example, row 3 is (6, 6, 3, 1) so P(3,x + 1) = (x + 1)*(x + 2)*(x + 3) = 6 + 6*x + 3*x*(x + 1) + x*(x + 1)*(x + 2). (End)
%F From _Tom Copeland_, Apr 21 & 26, and Aug 13 2014: (Start)
%F T-I = M = -A021009*A132440*A021009 with e.g.f. y*exp(x*y)/(1-y). Cf. A132440. Dividing the n-th row of M by n generates the (n-1)th row of T.
%F T = 1/(I - A132440) = {2*I - exp[(A238385-I)]}^(-1) = unsigned exp[(I-A238385)] = exp[A000670(.)*(A238385-I)] = , umbrally, where I = identity matrix.
%F The e.g.f. is exp(x*y)/(1-y), so the row polynomials form an Appell sequence with lowering operator d/dx and raising operator x + 1/(1-D).
%F With L(n,m,x)= Laguerre polynomials of order m, the row polynomials are (-1)^n*n!*L(n,-1-n,x) = (-1)^n*(-1!/(-1-n)!)*K(-n,-1-n+1,x) = n!* K(-n,-n,x) where K is Kummer's confluent hypergeometric function (as a limit of n+s as s tends to zero).
%F Operationally, (-1)^n*n!*L(n,-1-n,-:xD:) = (-1)^n*x^(n+1)*:Dx:^n*x^(-1-n) = (-1)^n*x*:xD:^n*x^(-1) = (-1)^n*n!*binomial(xD-1,n) = n!*K(-n,-n,-:xD:) where :AB:^n = A^n*B^n for any two operators. Cf. A235706 and A132159.
%F The n-th row of signed M has the coefficients of d[(-:xD:)^n]/d(:Dx:)= f[d/d(-:xD:)](-:xD:)^n with f(y)=y/(y-1), :Dx:^n= n!L(n,0,-:xD:), and (-:xD:)^n = n!L(n,0,:Dx:). M has the coefficients of [D/(1-D)]x^n. (End)
%F From _Tom Copeland_, Nov 18 2015: (Start)
%F Coefficients of the row polynomials of the e.g.f. Sum_{n>=0} P_n(b1,b2,..,bn;t) x^n/n! = e^(P.(..;t) x) = e^(xt) / (1-b.x) = (1 + b1 x + b2 x^2 + b3 x^3 + ...) e^(xt) = 1 + (b1 + t) x + (2 b2 + 2 b1 t + t^2) x^2/2! + (6 b3 + 6 b2 t + 3 b1 t^2 + t^3) x^3/3! + ... , with lowering operator L = d/dt, i.e., L P_n(..;t) = n * P_(n-1)(..;t), and raising operator R = t + d[log(1 + b1 D + b2 D^2 + ...)]/dD = t - Sum_{n>=1} F(n,b1,..,bn) D^(n-1), i.e., R P_n(..,;t) = P_(n+1)(..;t), where D = d/dt and F(n,b1,..,bn) are the Faber polynomials of A263916.
%F Also P_n(b1,..,bn;t) = CIP_n(t-F(1,b1),-F(2,b1,b2),..,-F(n,b1,..,bn)), the cycle index polynomials A036039.
%F (End)
%F The raising operator R = x + 1/(1-D) = x + 1 + D + D^2 + ... in matrix form acting on an o.g.f. (formal power series) is the transpose of the production matrix M below. The linear term x is the diagonal of ones after transposition. The other transposed diagonals come from D^m x^n = n! / (n-m)! x^(n-m). Then P(n,x) = (1,x,x^2,..) M^n (1,0,0,..)^T is a matrix representation of R P(n-1,x) = P(n,x). - _Tom Copeland_, Aug 17 2016
%F The row polynomials have e.g.f. e^(xt)/(1-t) = exp(t*q.(x)), umbrally. With p_n(x) the row polynomials of A132013, q_n(x) = v_n(p.(u.(x))), umbrally, where u_n(x) = (-1)^n v_n(-x) = (-1)^n Lah_n(x), the Lah polynomials with e.g.f. exp[x*t/(t-1)]. This has the matrix form [T] = [q] = [v]*[p]*[u]. Conversely, p_n(x) = u_n (q.(v.(x))). - _Tom Copeland_, Nov 10 2016
%F From the Appell sequence formalism, 1/(1-b.D) t^n = P_n(b1,b2,..,bn;t), the generalized row polynomials noted in the Nov 18 2015 formulas, consistent with the 2007 comments. - _Tom Copeland_, Nov 22 2016
%F From _Peter Bala_, Feb 18 2017: (Start)
%F G.f.: Sum_{n >= 1} (n*x)^(n-1)/(1 + (n - t)*x)^n = 1 + (1 + t)*x + (2 + 2*t + t^2)*x^2 + ....
%F n-th row polynomial R(n,t) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(x + k)^k*(x + k - t)^(n-k) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(x + k)^(n-k)*(x + k + t)^k, for arbitrary x. The particular case of the latter sum when x = 0 and t = 1 is identity 10.35 in Gould, Vol.4. (End)
%F Rodrigues-type formula for the row polynomials: R(n, x) = -exp(x)*Int(exp(-x)* x^n, x), for n >= 0. Recurrence: R(n, x) = x^n + n*R(n-1, x), for n >= 1, and R(0, x) = 1. d/dx(R(n, x)) = R(n, x) - x^n, for n >= 0 (compare with the formula from _Peter Bala_, Aug 28 2013). - _Wolfdieter Lang_, Dec 23 2019
%F T(n, k) = Sum_{i=0..n-k} A048994(n-k, i) * n^i for 0 <= k <= n. - _Werner Schulte_, Jul 26 2022
%e Rows begin {1}, {1,1}, {2,2,1}, {6,6,3,1}, ...
%e For n=3 and k=1, T(3,1)=6 since there are exactly 6 permutations of {1,2,3,4} with exactly 2 cycles and with 1 and 2 in separate cycles. The permutations are (1)(2 3 4), (1)(2 4 3), (1 3)(2 4), (1 4)(2 3), (1 3 4)(2), and (1 4 3)(2). - _Dennis P. Walsh_, Jan 24 2011
%e Triangle begins:
%e 1,
%e 1, 1,
%e 2, 2, 1,
%e 6, 6, 3, 1,
%e 24, 24, 12, 4, 1,
%e 120, 120, 60, 20, 5, 1,
%e 720, 720, 360, 120, 30, 6, 1,
%e 5040, 5040, 2520, 840, 210, 42, 7, 1
%e The production matrix is:
%e 1, 1,
%e 1, 1, 1,
%e 2, 2, 1, 1,
%e 6, 6, 3, 1, 1,
%e 24, 24, 12, 4, 1, 1,
%e 120, 120, 60, 20, 5, 1, 1,
%e 720, 720, 360, 120, 30, 6, 1, 1,
%e 5040, 5040, 2520, 840, 210, 42, 7, 1, 1,
%e 40320, 40320, 20160, 6720, 1680, 336, 56, 8, 1, 1
%e which is the exponential Riordan array A094587, or [1/(1-x),x], with an extra superdiagonal of 1's.
%e Inverse begins:
%e 1,
%e -1, 1,
%e 0, -2, 1,
%e 0, 0, -3, 1,
%e 0, 0, 0, -4, 1,
%e 0, 0, 0, 0, -5, 1,
%e 0, 0, 0, 0, 0, -6, 1,
%e 0, 0, 0, 0, 0, 0, -7, 1
%p T := proc(n, m): n!/m! end: seq(seq(T(n, m), m=0..n), n=0..9); # _Johannes W. Meijer_, Oct 07 2009, revised Nov 25 2012
%p # Alternative: Note that if you leave out 'abs' you get A021009.
%p T := proc(n, k) option remember; if n = 0 and k = 0 then 1 elif k < 0 or k > n then 0 else abs((n + k)*T(n-1, k) - T(n-1, k-1)) fi end: # _Peter Luschny_, Dec 30 2021
%t Flatten[Table[Table[n!/k!, {k,0,n}], {n,0,10}]] (* _Geoffrey Critzer_, Dec 11 2011 *)
%o (Haskell)
%o a094587 n k = a094587_tabl !! n !! k
%o a094587_row n = a094587_tabl !! n
%o a094587_tabl = map fst $ iterate f ([1], 1)
%o where f (row, i) = (map (* i) row ++ [1], i + 1)
%o -- _Reinhard Zumkeller_, Jul 04 2012
%o (Sage)
%o def A094587_row(n): return (factorial(n)*exp(x).taylor(x,0,n)).list()
%o for n in (0..7): print(A094587_row(n)) # _Peter Luschny_, Sep 28 2017
%Y Cf. A000166 (alt. row sums), A000522 (row sums).
%Y Cf. A068424, A036039, A173333, A213936, A263916.
%Y Cf. A000670, A008279, A021009, A048994, A132013, A132014, A132159, A132440, A133314, A218234, A235706, A238385.
%K easy,nonn,tabl
%O 0,4
%A _Paul Barry_, May 13 2004
%E Edited by _Johannes W. Meijer_, Oct 07 2009
%E New description from _Dennis P. Walsh_, Jan 24 2011
|
