A123513 Triangle read by rows: T(n,k) is the number of permutations of [n] having k small descents (n >= 1; 0 <= k <= n-1). A small descent in a permutation (x_1,x_2,...,x_n) is a position i such that x_i - x_(i+1) = 1.

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

Offset: 1

Author

Emeric Deutsch, Oct 02 2006

Keywords

• nonn
• tabl

Comments

This triangle is essentially A010027 (ascending pairs in permutations of [n]) with a different offset. The same triangle gives the number of permutations of [n] having k unit ascents (n >= 1; 0 <= k <= n-1). For permutations sorted by number of non-unitary (i.e., > 1) descents (also called "big" descents), see A120434. For permutations sorted by number of unitary moves (i.e., ascent or descent), see A001100. - Olivier Gérard, Oct 09 2007

With offsets n=0 (k=0) this is a binomial convolution triangle, a Sheffer triangle of the Appell type: ((exp(-x))/(1-x)^2),x). See the e.g.f. given below.

Examples

			Triangle starts:
     1;
     1,    1;
     3,    2,   1;
    11,    9,   3,   1;
    53,   44,  18,   4,  1;
   309,  265, 110,  30,  5, 1;
  2119, 1854, 795, 220, 45, 6, 1;
  ...
T(4,2)=3 because we have 14/3/2, 2/14/3 and 3/2/14 (the unit descents are shown by a /).
T(4,2)=3 because we have 14/3/2, 2/14/3 and 3/2/14 (the small descents are shown by a /).
		

References

• Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 179, Table 5.4 for S_{n,k} (without row n=1 and column k=0).
• F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263 (Table 7.5.1).

Links

• Alois P. Heinz, Rows n = 1..150, flattened
• Bhadrachalam Chitturi and Krishnaveni K S, Adjacencies in Permutations, arXiv preprint arXiv:1601.04469 [cs.DM], 2016. See Table 0.
• FindStat - Combinatorial Statistic Finder, The number of adjacencies of a permutation
• Sergey Kitaev and Philip B. Zhang, Distributions of mesh patterns of short lengths, arXiv:1811.07679 [math.CO], 2018.
• J. Liese and J. Remmel, Q-analogues of the number of permutations with k-excedances, PU. M. A. Vol. 21 (2010), No. 2, pp. 285-320 (see E_{n,1}(x) in Table 1 p. 291).
• F. Poussin, Énumération des permutations par nombre de marches, RAIRO, Informatique théorique, 13 no. 3, 1979, p. 251-255.

Crossrefs

Cf. A000166, A000255, A000274, A000313, A001260.

Cf. A010027 (mirror image), A120434, A001100.

Programs

Maple

G:=exp(-x+t*x)/(1-x)^2: Gser:=simplify(series(G,x=0,15)): for n from 0 to 10 do P[n+1]:=sort(n!*coeff(Gser,x,n)) od: for n from 1 to 11 do seq(coeff(P[n],t,k),k=0..n-1) od; # yields sequence in triangular form

Mathematica

Needs["Combinatorica`"];
Table[Map[Count[#,1]&,Map[Differences,Permutations[n]]]//Distribution,{n,1,10}]//Grid
(* Geoffrey Critzer, Dec 15 2012 *)
T[n_, k_] := (n-1)! SeriesCoefficient[Exp[-x + t x]/(1-x)^2, {x, 0, n-1}, {t, 0, k}];
Table[T[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Sep 25 2019 *)
T[1,1]:=1;T[0,1]:=0;T[n_,1]:=T[n,1]=(n-1)T[n-1,1]+(n-2)T[n-2,1];T[n_,k_]:=T[n,k]=T[n-1, k-1](n-1)/(k-1);Flatten@Table[T[n,k],{n,1,10},{k,1,n}] (* Oliver Seipel, Dec 01 2024 *)

Formula

T(n,1) = A000255(n-1).

T(n,2) = A000166(n-1) (the derangement numbers).

T(n,3) = A000274(n).

T(n,4) = A000313(n).

T(n,5) = A001260(n);

G.f.: exp(-x+tx)/(1-x)^2 (if offset is 0), i.e., T(n,k)=(n-1)!*[x^(n-1) t^k]exp(-x+tx)/(1-x)^2.

T(n,k) = binomial(n-1,k)*A000255(n-1), n-1 >= k >= 0, else 0.