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.
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
Offset: 0
Examples
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
Links
- Reinhard Zumkeller, Rows n = 0..149 of triangle, flattened
- J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
- Paul Barry, The Restricted Toda Chain, Exponential Riordan Arrays, and Hankel Transforms, J. Int. Seq. 13 (2010) # 10.8.4, example 3.
- Paul Barry, Exponential Riordan Arrays and Permutation Enumeration, J. Int. Seq. 13 (2010) # 10.9.1, example 5.
- Paul Barry, Riordan Arrays, Orthogonal Polynomials as Moments, and Hankel Transforms, J. Int. Seq. 14 (2011) # 11.2.2, example 17.
- Paul Barry, Combinatorial polynomials as moments, Hankel transforms and exponential Riordan arrays, arXiv:1105.3044 [math.CO], 2011, also J. Int. Seq. 14 (2011) 11.6.7.
- Paul Barry, A note on number triangles that are almost their own production matrix, arXiv:1804.06801 [math.CO], 2018.
- Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
- Tom Copeland, Goin' with the Flow: Logarithm of the Derivative Operator Part V, 2014.
- T. Copeland, Compositional inverse operators and Sheffer sequences, 2016.
- 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.
- H. W. Gould, ed. J. Quaintance, Combinatorial Identities, May 2010 (eqn. 10.35, p.49).
- A. Hennessy and P. Barry, Generalized Stirling Numbers, Exponential Riordan Arrays, and Orthogonal Polynomials, J. Int. Seq. 14 (2011) # 11.8.2.
- Milan Janjic, Some classes of numbers and derivatives, JIS 12 (2009) 09.8.3.
- Peter Luschny, Variants of Variations.
- Michelle Rudolph-Lilith, On the Product Representation of Number Sequences, with Application to the Fibonacci Family, arXiv preprint arXiv:1508.07894 [math.NT], 2015.
- M. Z. Spivey, On Solutions to a General Combinatorial Recurrence, J. Int. Seq. 14 (2011) # 11.9.7.
- Dennis Walsh, A note on permutations with cyclic constraints
- Wikipedia, Sheffer sequence
Crossrefs
Programs
-
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
-
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(n-1, k) - T(n-1, k-1)) fi end: # Peter Luschny, Dec 30 2021
-
Mathematica
Flatten[Table[Table[n!/k!, {k,0,n}], {n,0,10}]] (* Geoffrey Critzer, Dec 11 2011 *) -
Sage
def A094587_row(n): return (factorial(n)*exp(x).taylor(x,0,n)).list() for n in (0..7): print(A094587_row(n)) # Peter Luschny, Sep 28 2017
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) = (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
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!*binomial(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)
From Tom Copeland, Nov 18 2015: (Start)
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.
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.
(End)
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
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
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
From Peter Bala, Feb 18 2017: (Start)
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 + ....
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)
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
T(n, k) = Sum_{i=0..n-k} A048994(n-k, i) * n^i for 0 <= k <= n. - Werner Schulte, Jul 26 2022
Extensions
Edited by Johannes W. Meijer, Oct 07 2009
New description from Dennis P. Walsh, Jan 24 2011
Comments