A360289 Number T(n,k) of permutations of [n] whose excedance set is the k-th finite subset of positive integers in Gray 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, 7, 3, 1, 1, 3, 1, 1, 15, 31, 7, 7, 15, 17, 3, 1, 3, 1, 1, 3, 7, 7, 1, 1, 31, 115, 15, 31, 115, 69, 7, 7, 37, 31, 15, 17, 69, 37, 3, 1, 7, 7, 3, 1, 1, 3, 1, 3, 17, 15, 7, 7, 31, 15, 1, 1, 63, 391, 31, 115, 675, 245, 15, 31, 261, 391

Offset: 0

Author

Alois P. Heinz, Feb 01 2023

Keywords

• nonn
• look
• tabf

Comments

The list of finite subsets of the positive integers in Gray order begins: {}, {1}, {1,2}, {2}, {2,3}, {1,2,3}, {1,3}, {3}, ... cf. A003188, A227738, A360287.

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) = 7: there are 7 permutations of [5] with excedance set {2,3} (the 4th subset in Gray order): 13425, 13524, 13542, 14523, 14532, 15423, 15432.
Triangle T(n,k) begins:
  1;
  1;
  1,  1;
  1,  3,  1, 1;
  1,  7,  7, 3, 1,  1,  3, 1;
  1, 15, 31, 7, 7, 15, 17, 3, 1, 3, 1, 1, 3, 7, 7, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..15, flattened
• Wikipedia, Gray code
• Wikipedia, Permutation

Crossrefs

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

Row sums give A000142.

Row lengths are A011782.

See A152884, A360288 for similar triangles.

Cf. A000027, A003188, A006068, A227738, A263756, A360287.

Programs

Maple

a:= n-> `if`(n<2, n, Bits[Xor](n, a(iquo(n, 2)))):
b:= proc(s, t) option remember; (m->
      `if`(m=0, x^a(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

a[n_] := If[n < 2, n, BitXor[n, a[Quotient[n, 2]]]];
b[s_, t_] := b[s, t] = With[{m = Length[s]}, If[m == 0, x^a[t/2], Sum[b[s  ~Complement~ {i}, t + If[i < m, 2^i, 0]], {i, s}]]];
T[n_] := CoefficientList[b[Range[n], 0], x];
Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Dec 09 2023, after Alois P. Heinz *)