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

Author

Alois P. Heinz, Feb 01 2023

Keywords

• nonn
• look
• tabf

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.

Examples

			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;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..15, flattened
• Wikipedia, Permutation
• Wikipedia, Yates Order

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.

Programs

Maple

b:= proc(s, t) option remember; (m->
      `if`(m=0, x^(t/2), add(b(s minus {i}, t+
      `if`(i (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 *)

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.