

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.


29



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

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
From Tom Copeland, Nov 01 2007: (Start) 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) Binom(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)
From Peter Bala, Jul 10 2008: (Start)
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 analogue 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)
(n+1) * nth row = reversal of triangle A068424: (1; 2,2; 6,6,3;...)  Gary W. Adamson, May 03 2009
From Peter Luschny, Jun 01 2009: (Start)
If the first column is deleted and the triangle read from right to left resulting in
11,21,3,61,4,12,241,5,20,60,120...,
then this triangle T'(m,k) (m>=0,m>=k>=0) has the definition
T'(m,k) = (1)^k prod_{j=0..k1} (jm1)
for n from 1 to 7 do print(seq(T'(n,nk),k=1..n)) od:
(Let G(m,k,p) = (p)^k prod_{j=0..k1} (jm1/p).
For G(m,k,2) see A112292 and for G(m,k,3) see A136214.) (End)
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
T(n,k) = A162995(n1,k1), 2 <= k <= n; T(n,k) = A173333(n,k), 1 <= k <= n.  Reinhard Zumkeller, Jul 05 2012
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


LINKS

Reinhard Zumkeller, Rows n = 0..149 of triangle, flattened
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, 2013
Paul Barry, Combinatorial polynomials as moments, Hankel transforms and exponential Riordan arrays, arXiv:1105.3044, 2011.
Tom Copeland, Goin' with the Flow: Logarithm of the Derivative Operator Part V.
E. Deutsch, L. Ferrari and S. Rinaldi, Production Matrices, Advances in Mathematics, 34 (2005) pp. 101122.
Othman Echi, Binomial coefficients and Nasir alDin alTusi, Scientific Research and Essays Vol.1 (2), 2832 November 2006.
P. Luschny, Variants of Variations.
Dennis Walsh, A note on permutations with cyclic constraints
Wikipedia, Sheffer sequence


FORMULA

T(n, k) = n!/k! if n >= k >= 0 else 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
A094587 = 1 / ((1)*A129184 * A127648 + I), I = Identity matrix.  Gary W. Adamson, May 03 2009
From Johannes W. Meijer, Oct 07 2009: (Start)
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
From Peter Bala, Aug 28 2013: (Start)
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)
From Tom Copeland, Apr 21 & 26, and Aug 13 2014: (Start)
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.
T = 1/(I  A132440) = {2*I  exp[(A238385I)]}^(1) = unsigned exp[(IA238385)] = exp[A000670(.)*(A238385I)] = , umbrally, where I = identity matrix.
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!*Binom(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)


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


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)
 Reinhard Zumkeller, Jul 04 2012


CROSSREFS

Cf. A000166 (alt. row sums), A000522 (row sums).
Cf. A068424.
Sequence in context: A109316 A162980 A162979 * A135878 A121284 A225112
Adjacent sequences: A094584 A094585 A094586 * A094588 A094589 A094590


KEYWORD

easy,nonn,tabl


AUTHOR

Paul Barry, May 13 2004


EXTENSIONS

Edited by Johannes W. Meijer, Oct 07 2009
New description from Dennis P. Walsh, Jan 24 2011


STATUS

approved



