|
Search: id:A136126
|
|
|
| A136126 |
|
Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,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. |
|
+0
2
|
|
| 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; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
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.
Adjacent sequences: A136123 A136124 A136125 this_sequence A136127 A136128 A136129
Sequence in context: A082039 A063394 A108470 this_sequence A046802 A022166 A058669
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 17 2008
|
|
|
Search completed in 0.002 seconds
|
