login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,4

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.

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

Table of n, a(n) for n=1..55.

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, Philip B. Zhang, Distributions of mesh patterns of short lengths, arXiv:1811.07679 [math.CO], 2018.

J. Liese, 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.

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.

EXAMPLE

Triangle starts:

   1;

   1,  1;

   3,  2,  1;

  11,  9,  3,  1;

  53, 44, 18,  4,  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 /).

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 *)

CROSSREFS

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

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

Sequence in context: A115080 A222730 A104219 * A117442 A184182 A118435

Adjacent sequences:  A123510 A123511 A123512 * A123514 A123515 A123516

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Oct 02 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 24 19:14 EDT 2020. Contains 334580 sequences. (Running on oeis4.)