A360308 Number T(n,k) of permutations of [n] whose descent 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, 2, 1, 2, 1, 3, 3, 5, 3, 1, 5, 3, 1, 4, 6, 9, 11, 4, 16, 9, 6, 9, 1, 4, 16, 9, 11, 4, 1, 5, 10, 14, 26, 10, 35, 19, 26, 40, 5, 19, 61, 35, 40, 14, 10, 26, 19, 35, 5, 1, 14, 10, 35, 61, 14, 40, 40, 26, 19, 5, 1, 6, 15, 20, 50, 20, 64, 34, 71, 111

Offset: 0

Author

Alois P. Heinz, Feb 03 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 descent set of permutation p of [n] is the set of indices i with p(i)>p(i+1), a subset of [n-1].

Examples

			T(5,5) = 4: there are 4 permutations of [5] with descent set {1,2,3} (the 5th subset in Gray order): 43215, 53214, 54213, 54312.
Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 2, 1, 2;
  1, 3, 3, 5,  3, 1,  5, 3;
  1, 4, 6, 9, 11, 4, 16, 9, 6, 9, 1, 4, 16, 9, 11, 4;
  ...
		

Links

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

Crossrefs

Row sums give A000142.

Row lengths are A011782.

See A060351, A335845, A357611 for similar triangles (same terms, different ordering within each row).

Cf. A003188, A006068, A227738, A360287.

Programs

Maple

a:= proc(n) a(n):= `if`(n<2, n, Bits[Xor](n, a(iquo(n, 2)))) end:
b:= proc(u, o, t) option remember; `if`(u+o=0, x^a(t),
      add(b(u-j, o+j-1, t), j=1..u)+
      add(b(u+j-1, o-j, t+2^(o+u-1)), j=1..o))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..7);

Mathematica

a[n_] := a[n] = If[n<2, n, BitXor[n, a[Quotient[n, 2] ]]];
b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, x^a[t],        Sum[b[u - j, o + j - 1, t], {j, 1, u}] + Sum[b[u + j - 1, o - j, t + 2^(o + u - 1)], {j, 1, o}]];
T[n_] := CoefficientList[b[n, 0, 0], x];
Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Feb 14 2023, after Alois P. Heinz *)