|
| |
|
|
A136126
|
|
Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,k+n} having excedance set {1,2,...,k} (the empty set for k=0; 0<=k<=n-1). The excedance set of a permutation p in S_n is the set of indices i such that p(i)>i.
|
|
1
| |
|
|
1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 15, 31, 15, 1, 1, 31, 115, 115, 31, 1, 1, 63, 391, 675, 391, 63, 1, 1, 127, 1267, 3451, 3451, 1267, 127, 1, 1, 255, 3991, 16275, 25231, 16275, 3991, 255, 1, 1, 511, 12355, 72955, 164731, 164731, 72955, 12355, 511, 1
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,5
|
|
|
COMMENTS
| Columns 1,2,3,4 yield A000225, A091344, A091347, A091348, respectively. Row sums yield A136127.
|
|
|
REFERENCES
| R. Ehrenborg and E. Steingrimsson, The excedance set of a permutation, Advances in Appl. Math., 24, 284-299, 2000 (Proposition 6.5).
|
|
|
FORMULA
| T(n,k)=Sum((-1)^(k+1-i)*i!*i^(n-1-k)*Stirling2(k+1,i0,i=1..k+1) (0<=k<=n-1).
|
|
|
EXAMPLE
| T(4,2)=7 because 3412, 4312, 2413, 2314, 2431, 3421 and 4321 are the only permutations of {1,2,3,4} with excedance set {1,2}.
Triangle starts:
1;
1,1;
1,3,1;
1,7,7,1;
1,15,31,15,1;
1,31,115,115,31,1;
|
|
|
MAPLE
| with(combinat): T:=proc(n, k) if k < n then sum((-1)^(k+1-i)*factorial(i)*i^(n-1-k)*stirling2(k+1, i), i=1..k+1) else 0 end if end proc: for n to 10 do seq(T(n, k), k=0..n-1) end do; # yields sequence in triangular form
|
|
|
CROSSREFS
| Cf. A000225, A091344, A091347, A091348, A136127.
Sequence in context: A193871 A108470 A157152 * A046802 A184173 A022166
Adjacent sequences: A136123 A136124 A136125 * A136127 A136128 A136129
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 17 2008
|
|
|
EXTENSIONS
| Definition corrected. Changed "T(n,k) is the number of permutations of {1,2,...,n}..." to "T(n,k) is the number of permutations of {1,2,...,k+n}..." Karel Casteels (kcasteel(AT)sfu.ca), Feb 17 2010
|
| |
|
|
