

A094587


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.


48



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, 30, 6, 1, 5040, 5040, 2520, 840, 210, 42, 7, 1, 40320, 40320, 20160, 6720, 1680, 336, 56, 8, 1, 362880, 362880, 181440, 60480, 15120, 3024, 504, 72, 9, 1, 3628800, 3628800
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Also, table of Pochhammer sequences read by antidiagonals (see RudolphLilith, 2015).  N. J. A. Sloane, Mar 31 2016
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,...
Exponential Riordan array [1/(1x),x]; column k has e.g.f. x^k/(1x).  Paul Barry, Mar 27 2007
T is the umbral extension of n!*Lag[n,(.)!*Lag[.,x,1],0] = (1D)^(1) x^n = (1)^n * n! * Lag(n,x,1n) = Sum_{j=0..n} binomial(n,j) * j! * x^(nj) = Sum_{j=0..n} (n!/j!) x^j. The inverse operator is A132013 with generalizations discussed in A132014.
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).
1) b(n) = n! Lag[n,(.)!*Lag[.,a(.),1],0], umbrally,
2) b(n) = (1)^n n! Lag(n,a(.),1n)
3) b(n) = Sum_{j=0..n} (n!/j!) a(j)
4) B(x) = (1xDx)^(1) A(x), formally
5) B(x) = Sum_{j=0,1,...} (xDx)^j A(x)
6) B(x) = Sum_{j=0,1,...} x^j * D^j * x^j A(x)
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 = (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(nk). The reciprocal sequence is d = (1,1,0,0,0,...). (End)
This array is the particular case P(1,1) of the generalized Pascal triangle P(a,b), a lower unit triangular matrix, shown below:
n\k0.....................1...............2.......3......4

0..1.....................................................
1..a....................1................................
2..a(a+b)...............2a..............1................
3..a(a+b)(a+2b).........3a(a+b).........3a........1......
4..a(a+b)(a+2b)(a+3b)...4a(a+b)(a+2b)...6a(a+b)...4a....1
...
The entries A(n,k) of this array satisfy the recursion A(n,k) = (a+b*(nk1))*A(n1,k) + A(n1,k1), which reduces to the Pascal formula when a = 1, b = 0.
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.
When b <> 0 the array P(a,b) has e.g.f. exp(x*y)/(1b*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).
We have the matrix identities P(a,b)*P(a',b) = P(a+a',b); P(a,b)^1 = P(a,b).
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)).
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^(n1)(x,y) for n >= 2. Then (x+a*y)^(n) = x^n + C(n,1)*a*x^(n1)*y + C(n,2)*a*(a+b)*x^(n2)*y^2 + ... + C(n,n)*a*(a+b)*(a+2b)*...*(a+(n1)b)*y^n. (End)
Let G(m, k, p) = (p)^k*Product_{j=0..k1}(j  m  1/p) and T(n,k,p) = G(n1,nk,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
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
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
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
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
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
Also, T(n,k) is the number of ways to arrange nk nonattacking rooks on the n X (nk) chessboard.  Andrey Zabolotskiy, Dec 16 2016
The infinitesimal generator of this triangle is the generalized exponential Riordan array [log(1x), x] and equals the unsigned version of A238363.  Peter Bala, Feb 13 2017
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[(IA238385)] = 1/(I  A132440), where I is the identity matrix.  Tom Copeland, Jul 03 2017
If A(0) = 1/(1x), and A(n) = d/dx(A(n1)), then A(n) = n!/(1x)^(n+1) = Sum_{k>=0} (n+k)!/k!*x^k = Sum_{k>=0} T(n+k, k)*x^k.  Michael Somos, Sep 19 2021


LINKS

E. Deutsch, L. Ferrari and S. Rinaldi, Production Matrices, Advances in Mathematics, 34 (2005) pp. 101122.


FORMULA

T(n, k) = n!/k! if n >= k >= 0, otherwise 0.
T(n, k) = Sum_{i=k..n} S1(n+1, i+1)*S2(i, k) * (1)^i, with S1, S2 the Stirling numbers.
T(n,k) = (nk)*T(n1,k) + T(n1,k1). E.g.f.: exp(x*y)/(1y) = 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
The o.g.f. of right hand column k is Gf(z;k) = (k1)!/(1z)^k, k => 1.
The recurrence relations of the right hand columns lead to Pascal's triangle A007318. (End)
Let f(x) = (1/x)*exp(x). The nth 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
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(IP)] = 1/(IP) = I + P^2 + P^3 + ... where P is the infinitesimal generator matrix A218234 and I the identity matrix. The nonpadded version is given by P replaced by A132440.  Tom Copeland, Oct 25 2012
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(n1,x). The Sheffer identity is R(n,x + y) = Sum_{k=0..n} binomial(n,k)*y^(nk)*R(k,x).
Let P(n,x) = Product_{k=0..n1} (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)
TI = M = A021009*A132440*A021009 with e.g.f. y*exp(x*y)/(1y). Cf. A132440. Dividing the nth row of M by n generates the (n1)th row of T.
The e.g.f. is exp(x*y)/(1y), so the row polynomials form an Appell sequence with lowering operator d/dx and raising operator x + 1/(1D).
With L(n,m,x)= Laguerre polynomials of order m, the row polynomials are (1)^n*n!*L(n,1n,x) = (1)^n*(1!/(1n)!)*K(n,1n+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).
Operationally, (1)^n*n!*L(n,1n,:xD:) = (1)^n*x^(n+1)*:Dx:^n*x^(1n) = (1)^n*x*:xD:^n*x^(1) = (1)^n*n!*binomial(xD1,n) = n!*K(n,n,:xD:) where :AB:^n = A^n*B^n for any two operators. Cf. A235706 and A132159.
The nth row of signed M has the coefficients of d[(:xD:)^n]/d(:Dx:)= f[d/d(:xD:)](:xD:)^n with f(y)=y/(y1), :Dx:^n= n!L(n,0,:xD:), and (:xD:)^n = n!L(n,0,:Dx:). M has the coefficients of [D/(1D)]x^n. (End)
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) / (1b.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_(n1)(..;t), and raising operator R = t + d[log(1 + b1 D + b2 D^2 + ...)]/dD = t  Sum_{n>=1} F(n,b1,..,bn) D^(n1), 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.
Also P_n(b1,..,bn;t) = CIP_n(tF(1,b1),F(2,b1,b2),..,F(n,b1,..,bn)), the cycle index polynomials A036039.
(End)
The raising operator R = x + 1/(1D) = 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! / (nm)! x^(nm). Then P(n,x) = (1,x,x^2,..) M^n (1,0,0,..)^T is a matrix representation of R P(n1,x) = P(n,x).  Tom Copeland, Aug 17 2016
The row polynomials have e.g.f. e^(xt)/(1t) = 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/(t1)]. This has the matrix form [T] = [q] = [v]*[p]*[u]. Conversely, p_n(x) = u_n (q.(v.(x))).  Tom Copeland, Nov 10 2016
From the Appell sequence formalism, 1/(1b.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
G.f.: Sum_{n >= 1} (n*x)^(n1)/(1 + (n  t)*x)^n = 1 + (1 + t)*x + (2 + 2*t + t^2)*x^2 + ....
nth row polynomial R(n,t) = Sum_{k = 0..n} (1)^(nk)*binomial(n,k)*(x + k)^k*(x + k  t)^(nk) = Sum_{k = 0..n} (1)^(nk)*binomial(n,k)*(x + k)^(nk)*(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)
Rodriguestype 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(n1, 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


EXAMPLE

Rows begin {1}, {1,1}, {2,2,1}, {6,6,3,1}, ...
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
Triangle begins:
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, 30, 6, 1,
5040, 5040, 2520, 840, 210, 42, 7, 1
The production matrix is:
1, 1,
1, 1, 1,
2, 2, 1, 1,
6, 6, 3, 1, 1,
24, 24, 12, 4, 1, 1,
120, 120, 60, 20, 5, 1, 1,
720, 720, 360, 120, 30, 6, 1, 1,
5040, 5040, 2520, 840, 210, 42, 7, 1, 1,
40320, 40320, 20160, 6720, 1680, 336, 56, 8, 1, 1
which is the exponential Riordan array A094587, or [1/(1x),x], with an extra superdiagonal of 1's.
Inverse begins:
1,
1, 1,
0, 2, 1,
0, 0, 3, 1,
0, 0, 0, 4, 1,
0, 0, 0, 0, 5, 1,
0, 0, 0, 0, 0, 6, 1,
0, 0, 0, 0, 0, 0, 7, 1


MAPLE

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
# Alternative: Note that if you leave out 'abs' you get A021009.
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(n1, k)  T(n1, k1)) fi end: # Peter Luschny, Dec 30 2021


MATHEMATICA

Flatten[Table[Table[n!/k!, {k, 0, n}], {n, 0, 10}]] (* Geoffrey Critzer, Dec 11 2011 *)


PROG

(Haskell)
a094587 n k = a094587_tabl !! n !! k
a094587_row n = a094587_tabl !! n
a094587_tabl = map fst $ iterate f ([1], 1)
where f (row, i) = (map (* i) row ++ [1], i + 1)
(Sage)
def A094587_row(n): return (factorial(n)*exp(x).taylor(x, 0, n)).list()


CROSSREFS

Cf. A000670, A008279, A021009, A048994, A132013, A132014, A132159, A132440, A133314, A218234, A235706, A238385.


KEYWORD



AUTHOR



EXTENSIONS



STATUS

approved



