|
| |
|
|
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, 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; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
COMMENTS
| T(n,1)=A000255(n-1); T(n,2)=A000166 (the derangement numbers); T(n,3)=A000274(n); T(n,4)=A000313(n); T(n,5)=A001260(n);
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 GERARD (olivier.gerard(AT)gmail.com), 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
| F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263 (Table 7.5.1).
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).
|
|
|
FORMULA
| 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
| T(4,2)=3 because we have 14/3/2, 2/14/3 and 3/2/14 (the small descents are shown by a /).
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 /).
|
|
|
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
|
|
|
CROSSREFS
| Cf. A000255, A000166, A000274, A000313, A001260.
Cf. A010027, A120434, A001100.
Sequence in context: A077756 A115080 A104219 * A117442 A184182 A118435
Adjacent sequences: A123510 A123511 A123512 * A123514 A123515 A123516
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 02 2006
|
| |
|
|
