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,6

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

Links

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

Wikipedia, Gray code

Wikipedia, Permutation

Example

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

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 *)

Crossrefs

Row sums give A000142.

Row lengths are A011782.

See A060351, A335845 for similar triangles.

Cf. A003188, A006068, A227738, A360287.

Sequence in context: A058753 A282249 A330953 * A325702 A304746 A304748

Adjacent sequences: A360305 A360306 A360307 * A360309 A360310 A360311

Keyword

nonn,look,tabf

Author

Alois P. Heinz, Feb 03 2023

Status

approved