cp's OEIS Frontend

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.

%I A360289 #43 May 31 2025 15:39:12
%S A360289 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,
%T A360289 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,
%U A360289 15,7,7,31,15,1,1,63,391,31,115,675,245,15,31,261,391
%N 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.
%C A360289 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 A360289 The excedance set of permutation p of [n] is the set of indices i with p(i)>i, a subset of [n-1].
%C A360289 All terms are odd.
%H A360289 Alois P. Heinz, <a href="/A360289/b360289.txt">Rows n = 0..15, flattened</a>
%H A360289 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gray_code">Gray code</a>
%H A360289 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>
%e A360289 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.
%e A360289 Triangle T(n,k) begins:
%e A360289   1;
%e A360289   1;
%e A360289   1,  1;
%e A360289   1,  3,  1, 1;
%e A360289   1,  7,  7, 3, 1,  1,  3, 1;
%e A360289   1, 15, 31, 7, 7, 15, 17, 3, 1, 3, 1, 1, 3, 7, 7, 1;
%e A360289   ...
%p A360289 a:= n-> `if`(n<2, n, Bits[Xor](n, a(iquo(n, 2)))):
%p A360289 b:= proc(s, t) option remember; (m->
%p A360289       `if`(m=0, x^a(t/2), add(b(s minus {i}, t+
%p A360289       `if`(i<m, 2^i, 0)), i=s)))(nops(s))
%p A360289     end:
%p A360289 T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n}, 0)):
%p A360289 seq(T(n), n=0..7);
%t A360289 a[n_] := If[n < 2, n, BitXor[n, a[Quotient[n, 2]]]];
%t A360289 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 A360289 T[n_] := CoefficientList[b[Range[n], 0], x];
%t A360289 Table[T[n], {n, 0, 7}] // Flatten (* _Jean-François Alcover_, Dec 09 2023, after _Alois P. Heinz_ *)
%Y A360289 Columns k=0-1 give: A000012, A000225(n-1) for n>=1.
%Y A360289 Row sums give A000142.
%Y A360289 Row lengths are A011782.
%Y A360289 See A152884, A360288 for similar triangles.
%Y A360289 Cf. A000027, A003188, A006068, A227738, A263756, A360287.
%K A360289 nonn,look,tabf
%O A360289 0,6
%A A360289 _Alois P. Heinz_, Feb 01 2023