A005990 -id:A005990 - cp's OEIS frontend

A162975 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k doubledescents (0 <= k <= n-2). We say that i is a doubledescent (also called a double fall) of a permutation p if p(i) > p(i+1) > p(i+2).

1, 1, 2, 5, 1, 17, 6, 1, 70, 41, 8, 1, 349, 274, 86, 10, 1, 2017, 2040, 803, 167, 12, 1, 13358, 16346, 8221, 2064, 316, 14, 1, 99377, 143571, 86214, 28143, 4961, 597, 16, 1, 822041, 1365354, 966114, 374166, 88482, 11486, 1138, 18, 1

Offset: 0

Emeric Deutsch, Jul 26 2009

Row n (n>=2) contains n-1 entries.
Sum of entries in row n is n! = A000142(n).
Sum_{k=0..n-2} k*T(n,k) = A005990(n-1).
The first Maple program yields (by straightforward counting) the generating polynomial of a specified row n.

			T(5,2) = 8 because we have 15432, 25431, 35421, 43215, 45321, 53214, 54213, and 54312.
Triangle starts:
    1;
    1;
    2;
    5,   1;
   17,   6,   1;
   70,  41,   8,   1;
  349, 274,  86,  10,   1;

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, New York, 1983.

Alois P. Heinz, Rows n = 0..142, flattened
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-123.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 210
Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015.
Y. Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

Columns k=0..10 give A049774, A274997, A230621, A279292, A279293, A279294, A279295, A279296, A279297, A279298, A279299.

Cf. A000142, A005990, A162976, A242783, A242784.

n := 7: dds := proc (p) local ct, j: ct := 0: for j from 3 to nops(p) do if p[j] < p[j-1] and p[j-1] < p[j-2] then ct := ct+1 else end if end do: ct end proc: with(combinat): P := permute(n): f[n] := sort(add(t^dds(P[i]), i = 1 .. factorial(n)));
# second Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, 1), j=1..u)+
      add(b(u+j-1, o-j, 2)*`if`(t=2, x, 1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Oct 25 2013

nn=10; u=y-1; a=Apply[Plus, Table[Normal[Series[y x^3/(1-y x - y x^2), {x,0,nn}]][[n]]/(n+2)!, {n,1,nn-2}]]/.y->u; Range[0,nn]! CoefficientList[Series[1/(1-x-a), {x,0,nn}], {x,y}]//Grid  (* Geoffrey Critzer, Dec 12 2012 *)

E.g.f.: 1/(1 - x - Sum_{k,n} I(n,k)(y - 1)^k*x^n/n!) where I(n,k) is the coefficient of y^k*x^n in the ordinary generating function expansion of y x^3/(1 - y*x - y*x^2). See Flajolet and Sedgewick reference in Links section. - Geoffrey Critzer, Dec 12 2012

A001754 Lah numbers: a(n) = n!*binomial(n-1,2)/6.

Original entry on oeis.org

0, 0, 1, 12, 120, 1200, 12600, 141120, 1693440, 21772800, 299376000, 4390848000, 68497228800, 1133317785600, 19833061248000, 366148823040000, 7113748561920000, 145120470663168000, 3101950060425216000, 69337707233034240000, 1617879835437465600000

Offset: 1

N. J. A. Sloane

a(n+1) = Sum_{pi in Symm(n)} Sum_{i=1..n} max(pi(i)-i,0)^2, i.e., the sum of the squares of the positive displacement of all letters in all permutations on n letters. - Franklin T. Adams-Watters, Oct 25 2006

Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 156.
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 44.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..300

Column 3 of A008297.
Column m=3 of unsigned triangle A111596.
Cf. A005990, A053495, A260665.
Cf. A001113, A001620, A091725, A099285.

[Factorial(n)*Binomial(n-1, 2)/6: n in [1..25]]; // Vincenzo Librandi, Oct 11 2011

Maple
```
[seq(n!*binomial(n-1,2)/6, n=1..40)];
```

Table[(n-2)*(n-1)*n!/12, {n, 21}] (* Arkadiusz Wesolowski, Nov 26 2012 *)
With[{nn=30},CoefficientList[Series[(x/(1-x))^3/6,{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Oct 04 2017 *)

[factorial(n-1)*binomial(n,3)/2 for n in (1..30)] # G. C. Greubel, May 10 2021

E.g.f.: ((x/(1-x))^3)/3!.
If we define f(n,i,x) = Sum_{k=i..n} (Sum_{j=i..k} binomial(k,j) * Stirling1(n,k) * Stirling2(j,i)*x^(k-j)) then a(n+1) = (-1)^n*f(n,2,-4), n >= 2. - Milan Janjic, Mar 01 2009
a(n) = Sum_{k>=1} k * A260665(n,k). - Alois P. Heinz, Nov 14 2015
D-finite with recurrence (-n+5)*a(n) + (n-2)*(n-3)*a(n-1) = 0, n >= 4. - R. J. Mathar, Jan 06 2021
From Amiram Eldar, May 02 2022: (Start)
Sum_{n>=3} 1/a(n) = 6*(gamma - Ei(1)) + 9, where gamma = A001620 and Ei(1) = A091725.
Sum_{n>=3} (-1)^(n+1)/a(n) = 18*(gamma - Ei(-1)) - 12/e - 9, where Ei(-1) = -A099285 and e = A001113. (End)

A062139 Coefficient triangle of generalized Laguerre polynomials n!*L(n,2,x) (rising powers of x).

Original entry on oeis.org

1, 3, -1, 12, -8, 1, 60, -60, 15, -1, 360, -480, 180, -24, 1, 2520, -4200, 2100, -420, 35, -1, 20160, -40320, 25200, -6720, 840, -48, 1, 181440, -423360, 317520, -105840, 17640, -1512, 63, -1, 1814400, -4838400, 4233600

Offset: 0

Wolfdieter Lang, Jun 19 2001

The row polynomials s(n,x) := n!*L(n,2,x) = Sum_{m=0..n} a(n,m)*x^m have e.g.f. exp(-z*x/(1-z))/(1-z)^3. They are Sheffer polynomials satisfying the binomial convolution identity s(n,x+y) = Sum_{k=0..n} binomial(n,k)*s(k,x)*p(n-k,y), with polynomials p(n,x) = Sum_{m=1..n} |A008297(n,m)|*(-x)^m, n >= 1 and p(0,x)=1 (for Sheffer polynomials see A048854 for S. Roman reference).
This unsigned matrix is embedded in the matrix for n!*L(n,-2,-x). Introduce 0,0 to each unsigned row and then add 1,-1,1 to the array as the first two rows to generate n!*L(n,-2,-x). - Tom Copeland, Apr 20 2014
The unsigned n-th row reverse polynomial equals the numerator polynomial of the finite continued fraction 1 - x/(1 + (n+1)*x/(1 + n*x/(1 + n*x/(1 + ... + 2*x/(1 + 2*x/(1 + x/(1 + x/(1)))))))). Cf. A089231. The denominator polynomial of the continued fraction is the (n+1)-th row polynomial of A144084. An example is given below. - Peter Bala, Oct 06 2019

			Triangle begins:
     1;
     3,    -1;
    12,    -8,    1;
    60,   -60,   15,   -1;
   360,  -480,  180,  -24,  1;
  2520, -4200, 2100, -420, 35, -1;
  ...
2!*L(2,2,x) = 12 - 8*x + x^2.
Unsigned row 3 polynomial in reverse form as the numerator of a continued fraction: 1 - x/(1 + 4*x/(1 + 3*x/(1 + 3*x/(1 + 2*x/(1 + 2*x/(1 + x/(1 + x))))))) = (60*x^3 + 60*x^2 + 15*x + 1)/(24*x^4 + 96*x^3 + 72*x^2 + 16*x + 1). - _Peter Bala_, Oct 06 2019

Indranil Ghosh, Rows 0..125, flattened
Robert S. Maier, Boson Operator Ordering Identities from Generalized Stirling and Eulerian Numbers, arXiv:2308.10332 [math.CO], 2023. See p. 19.
Index entries for sequences related to Laguerre polynomials

For m=0..5 the (unsigned) columns give A001710, A005990, A005461, A062193-A062195. The row sums (signed) give A062197, the row sums (unsigned) give A052852.

Cf. A021009, A062137-A062140, A066667, A089231, A144084.

with(PolynomialTools):
p := n -> (n+2)!*hypergeom([-n],[3],x)/2:
seq(CoefficientList(simplify(p(n)), x), n=0..9); # Peter Luschny, Apr 08 2015

Flatten[Table[((-1)^m)*n!*Binomial[n+2,n-m]/m!,{n,0,8},{m,0,n}]] (* Indranil Ghosh, Feb 24 2017 *)

tabl(nn) = {for (n=0, nn, for (k=0, n, print1(((-1)^k)*n!*binomial(n+2, n-k)/k!, ", ");); print(););} \\ Michel Marcus, May 06 2014

row(n) = Vecrev(n!*pollaguerre(n, 2)); \\ Michel Marcus, Feb 06 2021

import math
f=math.factorial
def C(n,r):return f(n)//f(r)//f(n-r)
i=0
for n in range(16):
    for m in range(n+1):
        i += 1
        print(i,((-1)**m)*f(n)*C(n+2,n-m)//f(m)) # Indranil Ghosh, Feb 24 2017

from functools import cache
@cache
def T(n, k):
    if k < 0 or k > n: return 0
    if k == n: return (-1)**n
    return (n + k + 2) * T(n-1, k) - T(n-1, k-1)
for n in range(7): print([T(n,k) for k in range(n + 1)])
# Peter Luschny, Mar 25 2024

T(n, m) = ((-1)^m)*n!*binomial(n+2, n-m)/m!.
E.g.f. for m-th column sequence: ((-x/(1-x))^m)/(m!*(1-x)^3), m >= 0.
n!*L(n,2,x) = (n+2)!*hypergeom([-n],[3],x)/2. - Peter Luschny, Apr 08 2015
From Werner Schulte, Mar 24 2024: (Start)
T(n, k) = (n+k+2) * T(n-1, k) - T(n-1, k-1) with initial values T(0, 0) = 1 and T(i, j) = 0 if j < 0 or j > i.
T = T^(-1), i.e., T is matrix inverse of T. (End)

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

A061206 a(n) = total number of occurrences of the consecutive pattern 1324 in all permutations of [n+3].

Original entry on oeis.org

1, 10, 90, 840, 8400, 90720, 1058400, 13305600, 179625600, 2594592000, 39956716800, 653837184000, 11333177856000, 207484333056000, 4001483566080000, 81096733605888000, 1723305589125120000, 38318206628782080000, 889833909490606080000, 21543347282404147200000

Offset: 1

Melvin J. Knight (knightmj(AT)juno.com), May 30 2001

nonn

a(n) is the number of sequences of n+3 balls colored with at most n colors such that exactly four balls are the same color as some other ball in the sequence. - Jeremy Dover, Sep 27 2017

			a(4)=840 because 4*(7!)/24 = 4*7*6*5 = 840.

Vincenzo Librandi, Table of n, a(n) for n = 1..300
Milan Janjić, Enumerative Formulas for Some Functions on Finite Sets.

Cf. A000142, A001286, A001339, A001563, A005990, A264173.

Cf. A001620, A091725, A099285.

[n*Factorial(n+3)/24: n in [1..20]]; // Vincenzo Librandi, Oct 11 2011

a := n -> n!*binomial(-n,4): seq(a(n),n=1..20); # Peter Luschny, Apr 29 2016

Array[# (# + 3)!/24 &, 20] (* or *) Array[#!*Binomial[-#, 4] &, 20] (* Michael De Vlieger, Sep 30 2017 *)

a(n) = n*(n+3)!/24; \\ Altug Alkan, Oct 08 2017

[binomial(n,4)*factorial (n-3) for n in range(4, 21)] # Zerinvary Lajos, Jul 07 2009

a(n) = n*(n+3)!/24.
If we define f(n,i,x) = Sum_{k=i..n} Sum_{j=i..k} binomial(k,j)*Stirling1(n,k)*Stirling2(j,i) * x^(k-j), then a(n-3) = (-1)^n*f(n,4,-2), (n >= 4). - Milan Janjic, Mar 01 2009
E.g.f.: x/(1-x)^5. (This was initiated by e-mail exchange with Gary Detlefs.) - Wolfdieter Lang, May 28 2010
a(n) = ((n+4)!/6) * Sum_{k=1..n} (k+2)!/(k+4)!. - Gary Detlefs, Aug 05 2010
a(n) = Sum_{k>0} k * A264173(n+3,k). - Alois P. Heinz, Nov 06 2015
a(n) = n!*binomial(-n,4). - Peter Luschny, Apr 29 2016
From Amiram Eldar, Sep 24 2022: (Start)
Sum_{n>=1} 1/a(n) = 118/3 - 16*e - 4*gamma + 4*Ei(1), where gamma is Euler's constant (A001620) and Ei(1) is the exponential integral at 1 (A091725).
Sum_{n>=1} (-1)^(n+1)/a(n) = 2/3 - 8/e + 4*gamma - 4*Ei(-1), where -Ei(-1) is the negated exponential integral at -1 (A099285). (End)

More terms from Jason Earls, Jun 12 2001
Corrected by Zerinvary Lajos, Jul 07 2009
More precise definition from Alois P. Heinz, Nov 06 2015

A062869 Triangle read by rows: For n >= 0, k >= 0, T(n,k) is the number of permutations pi of n such that the total distance Sum_i abs(i-pi(i)) = 2k. Equivalently, k = Sum_i max(i-pi(i),0).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 1, 3, 7, 9, 4, 1, 4, 12, 24, 35, 24, 20, 1, 5, 18, 46, 93, 137, 148, 136, 100, 36, 1, 6, 25, 76, 187, 366, 591, 744, 884, 832, 716, 360, 252, 1, 7, 33, 115, 327, 765, 1523, 2553, 3696, 4852, 5708, 5892, 5452, 4212, 2844, 1764, 576, 1, 8, 42, 164, 524

Offset: 0

Olivier Gérard, Jun 26 2001

Number of possible values is 1,2,3,5,7,10,13,17,21,... = A033638. Maximum distance divided by 2 is the same minus one, i.e., 0,1,2,4,6,9,12,16,20,... = A002620.

T. Kyle Petersen and Bridget Eileen Tenner proved that T(n,k) is also the number of permutations of n for which the sum of descent differences equals k. - Susanne Wienand, Sep 11 2014

			Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 2,  3;
  1, 3,  7,  9,   4;
  1, 4, 12, 24,  35,  24,  20;
  1, 5, 18, 46,  93, 137, 148, 136, 100,  36;
  1, 6, 25, 76, 187, 366, 591, 744, 884, 832, 716, 360, 252;
  ...
(4,3,1,2) has distances (3,1,2,2), sum is 8 and there are 3 other permutations of degree 4 with this sum.

D. E. Knuth, The Art of Computer Programming, vol. 3, (1998), page 22 (exercise 28) and page 597 (solution and comments).

Daniel Graf and Alois P. Heinz, Rows n = 0..50, flattened (first 31 rows from Alois P. Heinz)
Max Alekseyev, Proof that T(n,k) is even for k>=n, SeqFan Mailing List, Dec 07 2006
Andreas Bärtschi, Barbara Geissmann, Daniel Graf, Tomas Hruz, Paolo Penna, and Thomas Tschager, On computing the total displacement number via weighted Motzkin paths, arXiv:1606.05538 [cs.DS], 2016. See pp. 1, 3-5, 13. - _Daniel Graf_, Jun 20 2016
P. Diaconis and R. L. Graham, Spearman's Footrule as a Measure of Disarray, J. Royal Stat. Soc. B, 39 (1977), 262-268.
FindStat - Combinatorial Statistic Finder, The depth of a permutation., The sum of the descent differences of a permutations.
Mathieu Guay-Paquet and T. Kyle Petersen, The generating function for total displacement, arXiv:1404.4674 [math.CO], 2014.
Mathieu Guay-Paquet and T. Kyle Petersen, The generating function for total displacement, The Electronic Journal of Combinatorics, 21(3) (2014), #P3.37.
Dirk Liebhold, Gabriele Nebe, and Angeles Vazquez-Castro, Network coding and spherical buildings, arXiv preprint arXiv:1612.07177 [cs.IT], 2016. See p. 4.
T. Kyle Petersen and Bridget Eileen Tenner, The depth of a permutation, arXiv:1202.4765 [math.CO], 2012.
Balázs R. Sziklai, Attila Gere, Károly Héberger, and Jochen Staudacher, rSRD: An R package for the Sum of Ranking Differences statistical procedure, arXiv:2502.03208 [math.ST], 2025. See p. 34.

Cf. A005990, A009006, A062866, A062867, A062870, A072949, A301897.
Row sums give A000142.
T(2n,n) gives A072948.
A357329 is a sub-triangle.

# The following program yields the entries of the specified row n
n := 9: with(combinat): P := permute(n): excsum := proc (p) (1/2)*add(abs(p[i]-i), i = 1 .. nops(p)) end proc: f[n] := sort(add(t^excsum(P[j]), j = 1 .. factorial(n))): seq(coeff(f[n], t, j), j = 0 .. floor((1/4)*n^2)); # Emeric Deutsch, Apr 02 2010
# Maple program using the g.f. given by Guay-Paquey and Petersen:
g:= proc(h, n) local i, j; j:= irem(h, 2, 'i');
       1-`if`(h=n, 0, (i+1)*z*t^(i+j)/g(h+1, n))
    end:
T:= n-> (p-> seq(coeff(p, t, k), k=0..degree(p)))
        (coeff(series(1/g(0, n), z, n+1), z, n)):
seq(T(n), n=0..10);  # Alois P. Heinz, May 02 2014

g[h_, n_] := Module[{i, j}, {i, j} = QuotientRemainder[h, 2]; 1 - If[h == n, 0, (i + 1)*z*t^(i + j)/g[h + 1, n]]]; T[n_] := Function[p, Table[ Coefficient[p, t, k], {k, 0, Exponent[p, t]}]][SeriesCoefficient[ 1/g[0, n], {z, 0, n}]]; Table[T[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Jan 07 2016, after Alois P. Heinz *)
f[i_] := If[i == 1, 1, -(i-1)^2 t^(2i - 3) z^2];
g[i_] := 1 - (2i - 1) t^(i-1) z;
cf = ContinuedFractionK[f[i], g[i], {i, 1, 5}];
CoefficientList[#, t]& /@ CoefficientList[cf + O[z]^10, z] // Rest // Flatten (* Jean-François Alcover, Nov 25 2018, after Mathieu Guay-Paquet *)

# The following Sage program
# yields the entries of the first n rows
# as a list of lists
def get_first_rows(n):
    R, t = PolynomialRing(ZZ, 't').objgen()
    S, z = PowerSeriesRing(R, 'z').objgen()
    gf = S(1).add_bigoh(1)
    for i in srange(n, 0, -1):
        a = (i+1) // 2
        b = i // 2
        gf = 1 / (1 - a * t^b * z * gf)
    return [list(row) for row in gf.shift(-1)]
# Mathieu Guay-Paquet, Apr 30 2014

From Mathieu Guay-Paquet, Apr 30 2014: (Start)
G.f.: 1/(1-z/(1-t*z/(1-2*t*z/(1-2*t^2*z/(1-3*t^2*z/(1-3*t^3*z/(1-4*t^3*z/(1-4*t^4*z/(...
This is a continued fraction where the (2i)th numerator is (i+1)*t^i*z, and the (2i+1)st numerator is (i+1)*t^(i+1)*z for i >= 0. The coefficient of z^n gives row n, n >= 1, and the coefficient of t^k gives column k, k >= 0. (End)
From Alois P. Heinz, Oct 02 2022: (Start)
Sum_{k=0..floor(n^2/4)} k * T(n,k) = A005990(n).
Sum_{k=0..floor(n^2/4)} (-1)^k * T(n,k) = A009006(n). (End).

T(0,0)=1 prepended by Alois P. Heinz, Oct 03 2022

A052571 E.g.f. x^3/(1-x)^2.

Original entry on oeis.org

0, 0, 0, 6, 48, 360, 2880, 25200, 241920, 2540160, 29030400, 359251200, 4790016000, 68497228800, 1046139494400, 16999766784000, 292919058432000, 5335311421440000, 102437979291648000, 2067966706950144000

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

For n >= 3, a(n) = number whose factorial base representation (A007623) begins with digit {n-2} followed by n-1 zeros. Viewed in that base, this sequence looks like this: 0, 0, 0, 100, 2000, 30000, 400000, 5000000, 60000000, 700000000, 8000000000, 90000000000, A00000000000, B000000000000, ... (where "digits" A and B stand for placeholder values 10 and 11 respectively). - Antti Karttunen, May 07 2015

Vincenzo Librandi, Table of n, a(n) for n = 0..300
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 514.
Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint, arXiv:1406.3081 [math.CO], 2014-2015.
Index entries for sequences related to factorial base representation

Column 5 of A257503 (apart from zero terms. Equally, row 5 of A257505).
Cf. A000142, A007623, A005990, A090672.
Cf. sequences with formula (n + k)*n! listed in A282466.
Cf. A001113, A001620, A091725, A099285.

[0,0] cat [n*(n+1)*(n+2)*Factorial(n): n in [0..20]]; // Vincenzo Librandi, Oct 11 2011

spec := [S,{S=Prod(Z,Z,Z,Sequence(Z),Sequence(Z))},labeled]: seq(combstruct[count](spec,size=n), n=0..20);
[seq (n*(n+1)*(n+2)*n!,n=0..17)]; # Zerinvary Lajos, Nov 25 2006
a:=n->add((n!),j=1..n-2):seq(a(n), n=0..21); # Zerinvary Lajos, Aug 27 2008
G(x):=x^3/(1-x)^2: f[0]:=G(x): for n from 1 to 21 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n],n=0..19); # Zerinvary Lajos, Apr 01 2009

Table[Sum[n!, {i, 3, n}], {n, 0, 19}] (* Zerinvary Lajos, Jul 12 2009 *)
With[{nn=20},CoefficientList[Series[x^3/(1-x)^2,{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Feb 27 2025 *)

(define (A052571 n) (if (< n 2) 0 (* (- n 2) (A000142 n)))) ;; Antti Karttunen, May 07 2015

E.g.f.: x^3/(-1+x)^2.
Recurrence: {a(1)=0, a(0)=0, a(2)=0, a(3)=6, (1-n^2)*a(n)+(-2+n)*a(n+1)=0}.
For n >= 2, a(n) = (n-2)*n!.
a(n+2) = n*(n+1)*(n+2)*n!. - Zerinvary Lajos, Nov 25 2006
a(n) = 3*A090672(n-2) = 6*A005990(n-2). - Zerinvary Lajos, May 11 2007
From Amiram Eldar, Jan 14 2021: (Start)
Sum_{n>=3} 1/a(n) = 9/4 - e - gamma/2 + Ei(1)/2 = 9/4 - A001113 - (1/2)*A001620 + (1/2)*A091725.
Sum_{n>=3} (-1)^(n+1)/a(n) = -1/4 + gamma/2 - Ei(-1)/2 = -1/4 + (1/2)*A001620 + (1/2)*A099285. (End)

A090672 a(n) = (n^2-1)*n!/3.

Original entry on oeis.org

0, 2, 16, 120, 960, 8400, 80640, 846720, 9676800, 119750400, 1596672000, 22832409600, 348713164800, 5666588928000, 97639686144000, 1778437140480000, 34145993097216000, 689322235650048000, 14597412049059840000, 323575967087493120000, 7493338185184051200000

Offset: 1

N. J. A. Sloane, Dec 18 2003

nonn

a(n) = Sum_{pi in Symm(n)} Sum_{i=1..n} |pi(i)-i|, i.e., the total displacement of all letters in all permutations on n letters.
a(n) = number of entries between the entries 1 and 2 in all permutations of {1,2,...,n+1}. Example: a(2)=2 because we have 123, 1(3)2, 213, 2(3)1, 312, 321; the entries between 1 and 2 are surrounded by parentheses. - Emeric Deutsch, Apr 06 2008
a(n) = Sum_{k=0..n-1} k*A138770(n+1,k). - Emeric Deutsch, Apr 06 2008
a(n) is also the number of peaks in all permutations of {1,2,...,n+1}. Example: a(3)=16 because the permutations 1234, 4123, 3124, 4312, 2134, 4213, 3214, and 4321 have no peaks and each of the remaining 16 permutations of {1,2,3,4} has exactly one peak. - Emeric Deutsch, Jul 26 2009
a(n), for n>=2, is the number of (n+2)-node tournaments that have exactly one triad. Proven by Kadane (1966), see link. - Ian R Harris, Sep 26 2022

D. Daly and P. Vojtechovsky, Displacement of permutations, preprint, 2003.

Vincenzo Librandi, Table of n, a(n) for n = 1..300
Ian R. Harris and Ryan P. A. McShane, Counting Tournaments with a Specified Number of Circular Triads, Journal of Integer Sequences, Vol. 27 (2024), Article 24.8.7. See pages 2, 23.
J. B. Kadane, Some equivalence classes in paired comparisons, The Annals of Mathematical Statistics, 37 (1966), 488-494.

Twice A005990.
Cf. A138770.
Cf. A001113, A001620, A091725, A099285.

[(n^2-1)*Factorial(n)/3: n in [1..25]]; // Vincenzo Librandi, Oct 11 2011

nn=20;Drop[Range[0,nn]!CoefficientList[Series[ x^3/3/(1-x)^2,{x,0,nn}],x],2]  (* Geoffrey Critzer, Mar 04 2013 *)

a(n) = A052571(n+2)/3 = 2*A005990(n). - Zerinvary Lajos, May 11 2007
a(n) = (n+3)! * Sum_{k=1..n} (k+1)!/(k+3)!, with offset 0. - Gary Detlefs, Aug 05 2010
E.g.f.: (x^3 - 3*x^2)/(3*(x-1)^3). - Geoffrey Critzer, Mar 04 2013
From Amiram Eldar, May 14 2022: (Start)
Sum_{n>=2} 1/a(n) = (3/2)*(Ei(1) - gamma) - 3*e + 27/4, where Ei(1) = A091725, gamma = A001620, and e = A001113.
Sum_{n>=2} (-1)^n/a(n) = (3/2)*(gamma - Ei(-1)) - 3/4, where Ei(-1) = -A099285. (End)

A291722 Number T(n,k) of permutations p of [n] such that in 0p the sum of all jumps equals k + n; triangle T(n,k), n >= 0, 0 <= k <= n*(n-1)/2, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 1, 6, 6, 5, 4, 1, 1, 1, 10, 20, 20, 26, 15, 15, 6, 5, 1, 1, 1, 15, 50, 70, 105, 106, 104, 90, 65, 51, 27, 21, 7, 6, 1, 1, 1, 21, 105, 210, 350, 497, 554, 644, 567, 574, 420, 386, 238, 203, 105, 85, 35, 28, 8, 7, 1, 1

Offset: 0

Alois P. Heinz, Aug 30 2017

An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here.
From David B. Wilson, Dec 14 2018: (Start)
T(n,k) equals the number of permutations p of [n] such that twice the sum of the leftward-down-jumps of p plus the number of descents of p equals k.
T(n,k) equals the number of cover-inclusive Dyck tilings whose lower boundary is the zig-zag path of order n (UD)^n, and which have k tiles.
A leftward-down-jump j occurs at position i in p if p_{i} > p_{i+1} and there are j positions k for which k p_k > p_{i+1}.
Cover-inclusive Dyck tilings are defined in the Kenyon and Wilson link below. (End)

Examples

T(4,0) = 1: 1234. T(4,1) = 6: 1243, 1324, 1342, 2134, 2314, 2341. T(4,2) = 6: 1432, 2143, 2431, 3214, 3241, 3421. T(4,3) = 5: 1423, 2413, 3124, 3412, 4321. T(4,4) = 4: 3142, 4213, 4231, 4312. T(4,5) = 1: 4123. T(4,6) = 1: 4132. T(5,5) = 15: 15234, 25134, 31542, 35124, 41235, 42153, 42531, 43152, 45123, 53214, 53241, 53421, 54213, 54231, 54312. Triangle T(n,k) begins: 1; 1; 1, 1; 1, 3, 1, 1; 1, 6, 6, 5, 4, 1, 1; 1, 10, 20, 20, 26, 15, 15, 6, 5, 1, 1; 1, 15, 50, 70, 105, 106, 104, 90, 65, 51, 27, 21, 7, 6, 1, 1;

Links

Alois P. Heinz, Rows n = 0..50, flattened

R. W. Kenyon, D. B. Wilson, Double-dimer pairings and skew Young diagrams, The Electronic Journal of Combinatorics 18(1) #P130, 2011.

J. S. Kim, K. Mészáros, G. Panova, and D. B. Wilson. Dyck tilings, increasing trees, descents, and inversions, Journal of Combinatorial Theory A 122:9-27, 2014.

Crossrefs

Columns k=0-3 give: A000012, A000217(n-1) for n>0, A002415(n-1) for n>0, A291288(n-3) for n>0.

Row sums give A000142.

T(n,n) gives A289489.

Cf. A005990, A008292, A123125, A173018, A258829, A263776, A316292, A316293.

Programs

Maple

b:= proc(u, o) option remember; expand(`if`(u+o=0, 1, add(b(u-j, o+j-1)*x^(j-1), j=1..u)+ add(b(u+j-1, o-j)*x^(j-1), j=1..o))) end: T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(0, n)): seq(T(n), n=0..10);

Mathematica

(* Generating function for tiles for Dyck tilings above the zigzag path of order n *) (* Computed by looking at descents in the insertion sequence for the Dyck-tiling-ribbon bijection, described in the Kim-Meszaros-Panova-Wilson reference *) (* Since it's above the zigzag, all insertion positions are even *) (* When the second argument is specified, refines by position of last insertion *) tilegen[n_, sn_] := tilegen[n, sn] = If[n == 0 || n == 1, 1, Sum[tilegen[n - 1, j] If[j >= sn, t^(j - sn + 1), 1] // Expand, {j, 0, 2 (n - 2), 2}] ]; tilegen[n_] := tilegen[n + 1, 2 n]; T[n_, k_] := Coefficient[tilegen[n], t, k]; (* David B. Wilson, Dec 14 2018 *)

Formula

Sum_{k>=0} k * T(n,k) = A005990(n).

cp's OEIS Frontend

A162975 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k doubledescents (0 <= k <= n-2). We say that i is a doubledescent (also called a double fall) of a permutation p if p(i) > p(i+1) > p(i+2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A001754 Lah numbers: a(n) = n!*binomial(n-1,2)/6.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

A062139 Coefficient triangle of generalized Laguerre polynomials n!*L(n,2,x) (rising powers of x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Formula

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

A061206 a(n) = total number of occurrences of the consecutive pattern 1324 in all permutations of [n+3].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A062869 Triangle read by rows: For n >= 0, k >= 0, T(n,k) is the number of permutations pi of n such that the total distance Sum_i abs(i-pi(i)) = 2k. Equivalently, k = Sum_i max(i-pi(i),0).

Views

Author

Keywords