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.

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

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

Alois P. Heinz, Rows n = 0..15, flattened

Wikipedia, Permutation

Wikipedia, Yates Order

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];
Table[T[n], {n, 0, 7}]  // Flatten (* Jean-François Alcover, Feb 13 2023, after Alois P. Heinz *)

Crossrefs

Columns k=0-1 give: A000012, A000225(n-1) for n>=1.

Row sums give A000142.

Row lengths are A011782.

See A152884, A360289 for similar triangles.

Cf. A000027, A029767, A048793, A048794, A263756, A329369.

Sequence in context: A324910 A257100 A152884 * A263756 A204984 A335341

Adjacent sequences: A360285 A360286 A360287 * A360289 A360290 A360291

Keyword

nonn,look,tabf

Author

Alois P. Heinz, Feb 01 2023

Status

approved