login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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/(1-x),x]; column k has e.g.f. x^k/(1-x). - 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] = (1-D)^(-1) x^n = (-1)^n * n! * Lag(n,x,-1-n) = sum(j=0,...,n) Binom(n,j) * j! * x^(n-j) = 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(.),-1-n)

3) b(n) = sum(j=0,...,n) (n!/j!) a(j)

4) B(x) = (1-xDx)^(-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(n-k). 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\k|0.....................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*(n-k-1))*A(n-1,k) + A(n-1,k-1), 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)/(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).

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^(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)

(n+1) * n-th 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

1|1,2|1,3,6|1,4,12,24|1,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..k-1} (j-m-1)

for n from -1 to 7 do print(seq(T'(n,n-k),k=-1..n)) od:

(Let G(m,k,p) = (-p)^k prod_{j=0..k-1} (j-m-1/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(n-1,k-1), 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. 101-122.

Othman Echi, Binomial coefficients and Nasir al-Din al-Tusi, Scientific Research and Essays Vol.1 (2), 28-32 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) = (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

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) = (k-1)!/(1-z)^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 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

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

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(n-1,x). The Sheffer identity is R(n,x + y) = sum {k = 0..n} binomial(n,k)*y^(n-k)*R(k,x).

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)

From Tom Copeland, Apr 21 & 26, and Aug 13 2014: (Start)

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.

T = 1/(I - A132440) = {2*I - exp[(A238385-I)]}^(-1) = unsigned exp[(I-A238385)] = exp[A000670(.)*(A238385-I)] = , umbrally, where I = identity matrix.

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).

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).

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!*Binom(xD-1,n) = n!*K(-n,-n,-:xD:) where :AB:^n = A^n*B^n for any two operators. Cf. A235706 and A132159.

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)

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/(1-x),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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 27 21:59 EST 2014. Contains 250286 sequences.