cp's OEIS Frontend

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.

%I A360308 #52 Dec 22 2024 16:25:19
%S A360308 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 A360308 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 A360308 35,61,14,40,40,26,19,5,1,6,15,20,50,20,64,34,71,111
%N 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.
%C A360308 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 A360308 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 A360308 Alois P. Heinz, <a href="/A360308/b360308.txt">Rows n = 0..15, flattened</a>
%H A360308 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gray_code">Gray code</a>
%H A360308 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>
%e A360308 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 A360308 Triangle T(n,k) begins:
%e A360308   1;
%e A360308   1;
%e A360308   1, 1;
%e A360308   1, 2, 1, 2;
%e A360308   1, 3, 3, 5,  3, 1,  5, 3;
%e A360308   1, 4, 6, 9, 11, 4, 16, 9, 6, 9, 1, 4, 16, 9, 11, 4;
%e A360308   ...
%p A360308 a:= proc(n) a(n):= `if`(n<2, n, Bits[Xor](n, a(iquo(n, 2)))) end:
%p A360308 b:= proc(u, o, t) option remember; `if`(u+o=0, x^a(t),
%p A360308       add(b(u-j, o+j-1, t), j=1..u)+
%p A360308       add(b(u+j-1, o-j, t+2^(o+u-1)), j=1..o))
%p A360308     end:
%p A360308 T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
%p A360308 seq(T(n), n=0..7);
%t A360308 a[n_] := a[n] = If[n<2, n, BitXor[n, a[Quotient[n, 2] ]]];
%t A360308 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 A360308 T[n_] := CoefficientList[b[n, 0, 0], x];
%t A360308 Table[T[n], {n, 0, 7}] // Flatten (* _Jean-François Alcover_, Feb 14 2023, after _Alois P. Heinz_ *)
%Y A360308 Row sums give A000142.
%Y A360308 Row lengths are A011782.
%Y A360308 See A060351, A335845, A357611 for similar triangles (same terms, different ordering within each row).
%Y A360308 Cf. A003188, A006068, A227738, A360287.
%K A360308 nonn,look,tabf
%O A360308 0,6
%A A360308 _Alois P. Heinz_, Feb 03 2023