|
| |
|
|
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.
|
|
26
| |
|
|
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; 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 (pbarry(AT)wit.ie), Mar 27 2007
Comments from Tom Copeland (tcjpn(AT)msn.com), 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)
Comments from Peter Bala (pbala(AT)toucansurf.com), Jul 10 2008 (Start): This array is the particular case P(1,1) of the generalised 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;...) [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 03 2009]
Contribution from Peter Luschny (peter(AT)luschny.de), 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)
Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Oct 07 2009: (Start)
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).
(End)
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
|
|
|
REFERENCES
| Paul Barry, Combinatorial polynomials as moments, Hankel transforms and exponential Riordan arrays, Arxiv preprint arXiv:1105.3044, 2011
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 207.
E. Deutsch, L. Ferrari and S. Rinaldi, Production Matrices, Advances in Mathematics, 34 (2005) pp. 101-122.
|
|
|
LINKS
| Othman Echi, Binomial coefficients and Nasir al-Din al-TusiScientific Research and Essays Vol.1 (2), 28-32 November 2006.
P. Luschny, Variants of Variations.
Dennis Walsh, A note on permutations with cyclic constraints
|
|
|
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 (pbala(AT)toucansurf.com), Jul 10 2008
A094587 = 1 / ((-1)*A129184 * A127648 + I), I = Identity matrix. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 03 2009]
Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), 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.
|
|
|
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). Example from 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
| Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Oct 07 2009: (Start)
nmax:=9; for n from 0 to nmax do T(n, 0) := (n)! od: for n from 0 to nmax do T(n, n):=1 od: for n from 2 to nmax do for k from 1 to n-1 do T(n, k) := (n-k)*T(n-1, k) + T(n-1, k-1) od: od: m:=0: for n from 0 to nmax do for k from 0 to n do a(m):=T(n, k): m:=m+1: od: od: seq(a(n), n=0..m-1);
(End)
|
|
|
MATHEMATICA
| Flatten[Table[Table[n!/k!, {k, 0, n}], {n, 0, 10}]] (* Geoffrey Critzer, Dec 11 2011 *)
|
|
|
CROSSREFS
| Cf. A000166 (alt. row sums), A000522 (row sums).
A068424 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 03 2009]
Sequence in context: A109316 A162980 A162979 * A135878 A121284 A108076
Adjacent sequences: A094584 A094585 A094586 * A094588 A094589 A094590
|
|
|
KEYWORD
| easy,nonn,tabl
|
|
|
AUTHOR
| Paul Barry (pbarry(AT)wit.ie), May 13 2004
|
|
|
EXTENSIONS
| Edited by Johannes W. Meijer (meijgia(AT)hotmail.com), Oct 07 2009.
New description from Dennis P. Walsh, Jan 24 2011.
|
| |
|
|
