A360308 - OEIS

%I #48 Feb 14 2023 07:41:54

%S 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,

%T 1,5,10,14,26,10,35,19,26,40,5,19,61,35,40,14,10,26,19,35,5,1,14,10,

%U 35,61,14,40,40,26,19,5,1,6,15,20,50,20,64,34,71,111

%N 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.

%C 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.

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

%H Alois P. Heinz, <a href="/A360308/b360308.txt">Rows n = 0..15, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Gray_code">Gray code</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>

%e 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.

%e Triangle T(n,k) begins:

%e   1;

%e   1;

%e   1, 1;

%e   1, 2, 1, 2;

%e   1, 3, 3, 5,  3, 1,  5, 3;

%e   1, 4, 6, 9, 11, 4, 16, 9, 6, 9, 1, 4, 16, 9, 11, 4;

%e   ...

%p a:= proc(n) a(n):= `if`(n<2, n, Bits[Xor](n, a(iquo(n, 2)))) end:

%p b:= proc(u, o, t) option remember; `if`(u+o=0, x^a(t),

%p       add(b(u-j, o+j-1, t), j=1..u)+

%p       add(b(u+j-1, o-j, t+2^(o+u-1)), j=1..o))

%p     end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):

%p seq(T(n), n=0..7);

%t a[n_] := a[n] = If[n<2, n, BitXor[n, a[Quotient[n, 2] ]]];

%t 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 T[n_] := CoefficientList[b[n, 0, 0], x];

%t Table[T[n], {n, 0, 7}] // Flatten (* _Jean-François Alcover_, Feb 14 2023, after _Alois P. Heinz_ *)

%Y Row sums give A000142.

%Y Row lengths are A011782.

%Y See A060351, A335845 for similar triangles.

%Y Cf. A003188, A006068, A227738, A360287.

%K nonn,look,tabf

%O 0,6

%A _Alois P. Heinz_, Feb 03 2023