|
|
A360288
|
|
Number T(n,k) of permutations of [n] whose excedance set is the k-th finite subset of positive integers in standard order; triangle T(n,k), n>=0, 0<=k<=ceiling(2^(n-1))-1, read by rows.
|
|
3
|
|
|
1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 3, 7, 1, 3, 1, 1, 1, 15, 7, 31, 3, 17, 7, 15, 1, 7, 3, 7, 1, 3, 1, 1, 1, 31, 15, 115, 7, 69, 31, 115, 3, 37, 17, 69, 7, 37, 15, 31, 1, 15, 7, 31, 3, 17, 7, 15, 1, 7, 3, 7, 1, 3, 1, 1, 1, 63, 31, 391, 15, 245, 115, 675, 7, 145, 69
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
The list of finite subsets of positive integers in standard statistical (or Yates) order begins: {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, ... cf. A048793, A048794.
The excedance set of permutation p of [n] is the set of indices i with p(i)>i, a subset of [n-1].
All terms are odd.
|
|
LINKS
|
|
|
FORMULA
|
Sum_{k=0..2^(n-1)-1} (k+1) * T(n,k) = A029767(n) for n>=1.
Sum_{k=0..2^(n-1)-1} (2^n-1-k) * T(n,k) = A355258(n+1) for n>=1.
|
|
EXAMPLE
|
T(5,4) = 3: there are 3 permutations of [5] with excedance set {3} (the 4th subset in standard order): 12435, 12534, 12543.
Triangle T(n,k) begins:
1;
1;
1, 1;
1, 3, 1, 1;
1, 7, 3, 7, 1, 3, 1, 1;
1, 15, 7, 31, 3, 17, 7, 15, 1, 7, 3, 7, 1, 3, 1, 1;
...
|
|
MAPLE
|
b:= proc(s, t) option remember; (m->
`if`(m=0, x^(t/2), add(b(s minus {i}, t+
`if`(i<m, 2^i, 0)), i=s)))(nops(s))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n}, 0)):
seq(T(n), n=0..7);
|
|
MATHEMATICA
|
b[s_, t_] := b[s, t] = Function [m, If[m == 0, x^(t/2), Sum[b[s ~Complement~ {i}, t + If[i < m, 2^i, 0]], {i, s}]]][Length[s]];
T[n_] := CoefficientList[b[Range[n], 0], x];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|