login
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.
52

%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