A081924 -id:A081924 - cp's OEIS frontend

A010027 Triangle read by rows: T(n,k) is the number of permutations of [n] having k consecutive ascending pairs (0 <= k <= n-1).

1, 1, 1, 1, 2, 3, 1, 3, 9, 11, 1, 4, 18, 44, 53, 1, 5, 30, 110, 265, 309, 1, 6, 45, 220, 795, 1854, 2119, 1, 7, 63, 385, 1855, 6489, 14833, 16687, 1, 8, 84, 616, 3710, 17304, 59332, 133496, 148329, 1, 9, 108, 924, 6678, 38934, 177996, 600732, 1334961, 1468457, 1

Offset: 1

N. J. A. Sloane

A "consecutive ascending pair" in a permutation p_1, p_2, ..., p_n is a pair p_i, p_{i+1} = p_i + 1.
From Emeric Deutsch, May 15 2010: (Start)
The same triangle, but with rows indexed differently, also arises as follows: U(n,k) = number of permutations of [n] having k blocks (1 <= k <= n), where a block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 5412367 has 4 blocks: 5, 4, 123, and 67.
When seen as coefficients of polynomials with decreasing exponents: evaluations are A001339 (x=2), A081923 (x=3), A081924 (x=4), A087981 (x=-1).
The sum of the entries in row n is n!.
U(n,n) = A000255(n-1) = d(n-1) + d(n), U(n,n-1)=d(n), where d(j)=A000166(j) (derangement numbers). (End)
This is essentially the reversal of the exponential Riordan array [exp(-x)/(1-x)^2,x] (cf. A123513). - Paul Barry, Jun 17 2010
U(n-1, k-2) * n*(n-1)/k = number of permutations of [n] with k elements not fixed by the permutation. - Michael Somos, Aug 19 2018

			Triangle starts:
  1;
  1, 1;
  1, 2,   3;
  1, 3,   9,  11;
  1, 4,  18,  44,   53;
  1, 5,  30, 110,  265,   309;
  1, 6,  45, 220,  795,  1854,   2119;
  1, 7,  63, 385, 1855,  6489,  14833,  16687;
  1, 8,  84, 616, 3710, 17304,  59332, 133496,  148329;
  1, 9, 108, 924, 6678, 38934, 177996, 600732, 1334961, 1468457;
  ...
For n=3, the permutations 123, 132, 213, 231, 312, 321 have respectively 2,0,0,1,1,0 consecutive ascending pairs, so row 3 of the triangle is 3,2,1. - _N. J. A. Sloane_, Apr 12 2014
In the alternative definition, T(4,2)=3 because we have 234.1, 4.123, and 34.12 (the blocks are separated by dots). - _Emeric Deutsch_, May 16 2010

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.

Alois P. Heinz, Rows n = 1..150, flattened
A. N. Myers, Counting permutations by their rigid patterns, J. Combin. Theory, A 99 (2002), 345-357. [_Emeric Deutsch_, May 15 2010]

Diagonals, reading from the right-hand edge: A000255, A000166, A000274, A000313, A001260, A001261. A045943 is another diagonal.
Cf. A123513 (mirror image).
A289632 is the analogous triangle with the additional restriction that all consecutive pairs must be isolated, i.e., must not be back-to-back to form longer consecutive sequences.

U := proc (n, k) options operator, arrow: factorial(k+1)*binomial(n, k)*(sum((-1)^i/factorial(i), i = 0 .. k+1))/n end proc: for n to 10 do seq(U(n, k), k = 1 .. n) end do; # yields sequence in triangular form; # Emeric Deutsch, May 15 2010

t[n_, k_] := Binomial[n, k]*Subfactorial[k+1]/n; Table[t[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 07 2014, after Emeric Deutsch *)
T[0,0]:=0; T[1,1]:=1; T[n_,n_]:=T[n,n]=(n-1)T[n-1,n-1]+(n-2)T[n-2,n-2]; T[n_,k_]:=T[n,k]=T[n-1,k] (n-1)/(n-k); Flatten@Table[T[n,k],{n,1,10},{k,1,n}] (* Oliver Seipel, Dec 01 2024 *)

E.g.f.: exp(x*(y-1))/(1-x)^2. - Vladeta Jovovic, Jan 03 2003
From Emeric Deutsch, May 15 2010: (Start)
U(n,k) = binomial(n-1,k-1)*(k-1)!*Sum_{j=0..k-1} (-1)^(k-j-1)*(j+1)/(k-j-1)! (1 <= k <= n).
U(n,k) = (k+1)!*binomial(n,k)*(1/n)*Sum_{i=0..k+1} (-1)^i/i!.
U(n,k) = (1/n)*binomial(n,k)*d(k+1), where d(j)=A000166(j) (derangement numbers). (End)

More terms from Vladeta Jovovic, Jan 03 2003

Original definition from David, Kendall and Barton restored by N. J. A. Sloane, Apr 12 2014

A132159 Lower triangular matrix T(n,j) for double application of an iterated mixed order Laguerre transform inverse to A132014. Coefficients of Laguerre polynomials (-1)^n * n! * L(n,-2-n,x).

Original entry on oeis.org

1, 2, 1, 6, 4, 1, 24, 18, 6, 1, 120, 96, 36, 8, 1, 720, 600, 240, 60, 10, 1, 5040, 4320, 1800, 480, 90, 12, 1, 40320, 35280, 15120, 4200, 840, 126, 14, 1, 362880, 322560, 141120, 40320, 8400, 1344, 168, 16, 1, 3628800, 3265920, 1451520, 423360, 90720, 15120

Offset: 0

Tom Copeland, Nov 01 2007

The matrix operation b = T*a can be characterized several ways in terms of the coefficients a(n) and b(n), their o.g.f.'s A(x) and B(x), or their e.g.f.'s EA(x) and EB(x).
1) b(n) = n! Lag[n,(.)!*Lag[.,a1(.),-1],0], umbrally,
where a1(n) = n! Lag[n,(.)!*Lag[.,a(.),-1],0]
2) b(n) = (-1)^n * n! * Lag(n,a(.),-2-n)
3) b(n) = Sum_{j=0..n} (-1)^j * binomial(n,j) * binomial(-2,j) * j! * a(n-j)
4) b(n) = Sum_{j=0..n} binomial(n,j) * (j+1)! * a(n-j)
5) B(x) = (1-xDx))^(-2) A(x), formally
6) B(x) = Sum_{j>=0} (-1)^j * binomial(-2,j) * (xDx)^j A(x)
= Sum_{j>=0} (j+1) * (xDx)^j A(x)
7) B(x) = Sum_{j>=0} (j+1) * x^j * D^j * x^j A(x)
8) B(x) = Sum_{j>=0} (j+1)! * x^j * Lag(j,-:xD:,0) A(x)
9) EB(x) = Sum_{j>=0} x^j * Lag[j,(.)! * Lag[.,a1(.),-1],0]
10) EB(x) = Sum_{j>=0} Lag[j,a1(.),-1] * (-x)^j / (1-x)^(j+1)
11) EB(x) = Sum_{j>=0} x^n * Sum_{j=0..n} (j+1)!/j! * a(n-j) / (n-j)!
12) EB(x) = Sum_{j>=0} (-x)^j * Lag[j,a(.),-2-j]
13) EB(x) = exp(a(.)*x) / (1-x)^2 = (1-x)^(-2) * EA(x)
14) T = A094587^2 = A132013^(-2) = A132014^(-1)
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 D operator series at the j = n term gives an o.g.f. for b(0) through b(n).
c = (1!,2!,3!,4!,...) is the sequence associated to T under the list partition transform and associated operations described in A133314. Thus T(n,k) = binomial(n,k)*c(n-k) . c are also the coefficients in formulas 4 and 8.
The reciprocal sequence to c is d = (1,-2,2,0,0,0,...), so the inverse of T is TI(n,k) = binomial(n,k)*d(n-k) = A132014. (A121757 is the reverse of T.)
These formulas are easily generalized for m applications of the basic operator n! Lag[n,(.)!*Lag[.,a(.),-1],0] by replacing 2 by m in formulas 2, 3, 5, 6, 12, 13 and 14, or (j+1)! by (m-1+j)!/(m-1)! in 4, 8 and 11. For further discussion of repeated applications of T, see A132014.
The row sums of T = [formula 4 with a(n) all 1] = [binomial transform of c] = [coefficients of B(x) with A(x) = 1/(1-x)] = A001339. Therefore the e.g.f. of A001339 = [formula 13 with a(n) all 1] = exp(x)*(1-x)^(-2) = exp(x)*exp[c(.)*x)] = exp[(1+c(.))*x].
Note the reciprocal is 1/{exp[(1+c(.))*x]} = exp(-x)*(1-x)^2 = e.g.f. of signed A002061 with leading 1 removed], which makes A001339 and the signed, shifted A002061 reciprocal arrays under the list partition transform of A133314.
The e.g.f. for the row polynomials (see A132382) implies they form an Appell sequence (see Wikipedia). - Tom Copeland, Dec 03 2013
As noted in item 12 above and reiterated in the Bala formula below, the e.g.f. is e^(x*t)/(1-x)^2, and the Poisson-Charlier polynomials P_n(t,y) have the e.g.f. (1+x)^y e^(-xt) (Feinsilver, p. 5), so the row polynomials R_n(t) of this entry are (-1)^n P_n(t,-2). The associated Appell sequence IR_n(t) that is the umbral compositional inverse of this entry's polynomials has the e.g.f. (1-x)^2 e^(xt), i.e., the e.g.f. of A132014 (noted above), and, therefore, the row polynomials (-1)^n PC(t,2). As umbral compositional inverses, R_n(IR.(t)) = t^n =  IR_n(R.(t)), where, by definition, P.(t)^n = P_n(t), is the umbral evaluation. - Tom Copeland, Jan 15 2016
T(n,k) is the number of ways to place (n-k) rooks in a 2 x (n-1) Ferrers board (or diagram) under the Goldman-Haglund i-row creation rook mode for i=2. Triangular recurrence relation is given by T(n,k) = T(n-1,k-1) + (n+1-k)*T(n-1,k). - Ken Joffaniel M. Gonzales, Jan 21 2016

			First few rows of the triangle are
    1;
    2,  1;
    6,  4,  1;
   24, 18,  6, 1;
  120, 96, 36, 8, 1;

Nathaniel Johnston, Rows 0..100, flattened
Paul Barry, A note on number triangles that are almost their own production matrix, arXiv:1804.06801 [math.CO], 2018.
P. Feinsilver, Lie algebras, representations, and analytic semigroups through dual vector fields
Jay Goldman and James Haglund, Generalized rook polynomials, J. Combin. Theory A 91 (2000), 509-530.
M. Janjic, Some classes of numbers and derivatives, JIS 12 (2009) 09.8.3.
Wikipedia, Appell sequence
Wikipedia, Sheffer sequence

Cf. A008277, A094587, A132013, A132382.

Columns: A000142 (k=0), A001563 (k=1), A001286 (k=2), A005990 (k=3), A061206 (k=4), A062199 (k=5), A062148 (k=6).

a132159 n k = a132159_tabl !! n !! k
a132159_row n = a132159_tabl !! n
a132159_tabl = map reverse a121757_tabl
-- Reinhard Zumkeller, Mar 06 2014

/* As triangle */ [[Binomial(n,k)*Factorial(n-k+1): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Feb 10 2016

T := proc(n,k) return binomial(n,k)*factorial(n-k+1): end: seq(seq(T(n,k),k=0..n),n=0..10); # Nathaniel Johnston, Sep 28 2011

nn=10;f[list_]:=Select[list,#>0&];Map[f,Range[0,nn]!CoefficientList[Series[Exp[y x]/(1-x)^2,{x,0,nn}],{x,y}]]//Grid  (* Geoffrey Critzer, Feb 15 2013 *)

flatten([[binomial(n,k)*factorial(n-k+1) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, May 19 2021

T(n,k) = binomial(n,k)*c(n-k).
From Peter Bala, Jul 10 2008: (Start)
T(n,k) = binomial(n,k)*(n-k+1)!.
T(n,k) = (n-k+1)*T(n-1,k) + T(n-1,k-1).
E.g.f.: exp(x*y)/(1-y)^2 = 1 + (2+x)*y + (6+4*x+x^2)*y^2/2! + ... .
This array is the particular case P(2,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
  ...
See A094587 for some general properties of these arrays.
Other cases recorded in the database include: P(1,0) = Pascal's triangle A007318, P(1,1) = A094587, P(2,0) = A038207, P(3,0) = A027465, P(1,3) = A136215 and P(2,3) = A136216. (End)
Let f(x) = (1/x^2)*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+2)*R(n,x)-x*R'(n,x). Cf. A094587. - Peter Bala, Oct 28 2011
Exponential Riordan array [1/(1 - y)^2, y]. The row polynomials R(n,x) thus 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). Define a polynomial sequence P(n,x) of binomial type by setting P(n,x) = Product_{k = 0..n-1} (2*x + k) with the convention that P(0,x) = 1. Then the present triangle is the 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 (24, 18, 6, 1) so P(3,x + 1) = (2*x + 2)*(2*x + 3)*(2*x + 4) = 24 + 18*(2*x) + 6*(2*x)*(2*x + 1) + (2*x)*(2*x + 1)*(2*x + 2). Matrix square of triangle A094587. - Peter Bala, Aug 29 2013
From Tom Copeland, Apr 21 2014: (Start)
T = (I-A132440)^(-2) = {2*I - exp[(A238385-I)]}^(-2) = unsigned exp[2*(I-A238385)] = exp[A005649(.)*(A238385-I)], umbrally, where I = identity matrix.
The e.g.f. is exp(x*y)*(1-y)^(-2), so the row polynomials form an Appell sequence with lowering operator D=d/dx and raising operator x+2/(1-D).
With L(n,m,x) = Laguerre polynomials of order m, the row polynomials are (-1)^n * n! * L(n,-2-n,x) = (-1)^n*(-2!/(-2-n)!)*K(-n,-2-n+1,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,-2-n,-:xD:) = (-1)^n*x^(n+2)*:Dx:^n*x^(-2-n) = (-1)^n*x^2*:xD:^n*x^(-2) = (-1)^n*n!*binomial(xD-2,n) = (-1)^n*n!*binomial(-2,n)*K(-n,-2-n+1,-:xD:) where :AB:^n = A^n*B^n for any two operators. Cf. A235706.
The generalized Pascal triangle Bala mentions is a special case of the fundamental generalized factorial matrices in A133314. (End)
From Peter Bala, Jul 26 2021: (Start)
O.g.f: 1/y * Sum_{k >= 0} k!*( y/(1 - x*y) )^k =  1 + (2 + x)*y + (6 + 4*x + x^2)*y^2 + ....
First-order recurrence for the row polynomials: (n - x)*R(n,x) = n*(n - x + 1)*R(n-1,x) - x^(n+1) with R(0,x) = 1.
R(n,x) = (x + n + 1)*R(n-1,x) - (n - 1)*x*R(n-2,x) with R(0,x) = 1 and R(1,x) = 2 + x.
R(n,x) = A087981 (x = -2), A000255 (x = -1), A000142 (x = 0), A001339 (x = 1), A081923 (x = 2) and A081924 (x = 3). (End)

Formula 3) in comments corrected by Tom Copeland, Apr 20 2014

Title modified by Tom Copeland, Apr 23 2014

A081923 Expansion of e.g.f.: exp(2x)/(1-x)^2.

Original entry on oeis.org

1, 4, 18, 92, 536, 3552, 26608, 223456, 2085504, 21450752, 241320704, 2949474816, 38933066752, 552141672448, 8374148696064, 135274709700608, 2318995023429632, 42051109758173184, 804227474125029376

Offset: 0

Paul Barry, Apr 01 2003

Binomial transform of A001339.
Polynomials in A010027 evaluated at 3. - Ralf Stephan, Dec 15 2004
From Dennis P. Walsh, Sep 18 2013: (Start)
a(n) is the number of rooted labeled forests that satisfy the following conditions:
(i) there are 4 roots labeled 1, 2, 3, and 4;
(ii) there are n non-root vertices labeled 5,..., n+4;
(iii) the trees with roots 1 and 2 have width one;
(iv) the trees with roots 3 and 4 have height at most one.
To construct such a forest, for k=0,...,n, we take the following steps:
(1) choose k non-root vertices for trees with roots 1 and 2;
(2) construct width-one trees on roots 1 and 2 with the k non-root vertices;
(3) with the n-k remaining non-root vertices construct trees of height at most one on roots 3 and 4.
Thus a(n) is the sum (over k) of the product of the number of ways to do each step: a(n)=sum(k=0..n, binomial(n,k)*(k+1)!*2^(n-k)).  (End)

			For n=2, the a(2)=18 forests that satisfy the specified conditions are given in the link above. - _Dennis P. Walsh_, Sep 20 2013

Harvey P. Dale, Table of n, a(n) for n = 0..448
Paul Barry, A note on number triangles that are almost their own production matrix, arXiv:1804.06801 [math.CO], 2018.
Dennis P. Walsh, 18 Forests

Cf. A081924. A010842.

Cf. A081923(n) (sum(k=0..n, binomial(n,k)*A000522(n-k)*A000522(k))).

seq(n!*add((k+1)*2^(n-k)/(n-k)!,k=0..n),n=0..40); # Dennis P. Walsh, Sep 18 2013
seq(simplify(KummerU(-n, -n - 1, 2)), n = 0..24); # Peter Luschny, May 10 2022

With[{nn=20},CoefficientList[Series[Exp[2x]/(1-x)^2,{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, May 10 2025 *)

E.g.f.: exp(2*x)/(1-x)^2
E.g.f.: 1/U(0) where U(k)=   1 - 2*x/( 1 + x/(2 - x - 4/( 2 - x*(k+1)/U(k+1)))) ; (continued fraction, 3rd kind, 4-step). - Sergei N. Gladkovskii, Oct 28 2012
Conjecture: a(n) +(-n-3)*a(n-1) +2*(n-1)*a(n-2)=0. - R. J. Mathar, Nov 24 2012
G.f.: 2/x/G(0) - 1/x, where G(k)= 1 + 1/(1 - x*(2*k+2)/(x*(2*k+4) - 1 + x*(2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 31 2013
G.f.: (sum(k>=0, k!*(x/(1-2*x))^k ) - 1)/x = Q(0)/(2*x) - 1/x, where Q(k)= 1 + 1/(1 - x*(k+1)/(x*(k+1) + (1-2*x)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 09 2013
G.f.: W(0)/x - 1/x, where W(k) = 1 - x*(k+1)/( x*(k+3) - 1/(1 - x*(k+1)/( x*(k+1) - 1/W(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 26 2013
a(n) = n!*sum(k=0..n, (k+1)*2^(n-k)/(n-k)!). [Dennis P. Walsh, Sep 18 2013]
a(n) = n!*sum(k=0..n, (n-k+1)*2^k/k!). [Dennis P. Walsh, Sep 18 2013]
From Peter Bala, Sep 25 2013: (Start)
a(n) ~ n!*n*e^2.
Applying Maple's ZeilbergerRecurrence command to the above series of Walsh for a(n) results in the first-order recurrence equation (n - 1)*a(n+1) = n*(n + 1)*a(n) - 2^(n+2) with a(0) = 1 and a(2) = 18. Using this it is easy to verify that a(n) satisfies the second-order recurrence a(n) = (n + 3)*a(n-1) - 2*(n - 1)*a(n-2) conjectured above by Mathar.
The sequence b(n) = n!*(n - 1) satisfies the same second-order recurrence but with the initial conditions b(0) = -1 and b(1) = 0. This leads to the finite continued fraction expansion a(n)/b(n) = 9 - 2*( 4/(6 - 6/(7 - 8/(9 - ... - 2*n/(n + 4)))) ) valid for n >= 2. Letting n tend to infinity produces the infinite continued fraction expansion e^2 = 9 - 2*( 4/(6 - 6/(7 - 8/(9 - ... - 2*n/(n + 4 - ...)))) ). (End)
a(n) = KummerU(-n, -n - 1, 2). - Peter Luschny, May 10 2022

Definition clarified by Harvey P. Dale, May 10 2025

cp's OEIS Frontend

A010027 Triangle read by rows: T(n,k) is the number of permutations of [n] having k consecutive ascending pairs (0 <= k <= n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A132159 Lower triangular matrix T(n,j) for double application of an iterated mixed order Laguerre transform inverse to A132014. Coefficients of Laguerre polynomials (-1)^n * n! * L(n,-2-n,x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Sage

Formula

Extensions

A081923 Expansion of e.g.f.: exp(2x)/(1-x)^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions