|
|
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.
|
|
7
|
|
|
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
|
|
|
FORMULA
|
T(n,2) = A000166(n-1) (the derangement numbers).
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;
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 /).
|
|
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
T[n_, k_] := (n-1)! SeriesCoefficient[Exp[-x + t x]/(1-x)^2, {x, 0, n-1}, {t, 0, k}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|