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.

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, 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, 15, 7, 7, 31, 15, 1, 1, 63, 391, 31, 115, 675, 245, 15, 31, 261, 391

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 excedance set of permutation p of [n] is the set of indices i with p(i)>i, a subset of [n-1].

All terms are odd.

Links

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

Wikipedia, Gray code

Wikipedia, Permutation

Example

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.
Triangle T(n,k) begins:
  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;
  ...

Maple

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

Mathematica

a[n_] := If[n < 2, n, BitXor[n, a[Quotient[n, 2]]]];
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[n_] := CoefficientList[b[Range[n], 0], x];
Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Dec 09 2023, after Alois P. Heinz *)

Crossrefs

Columns k=0-1 give: A000012, A000225(n-1) for n>=1.

Row sums give A000142.

Row lengths are A011782.

See A152884, A360288 for similar triangles.

Cf. A000027, A003188, A006068, A227738, A263756, A360287.

Sequence in context: A328718 A362897 A005765 * A343717 A263159 A229142

Adjacent sequences: A360286 A360287 A360288 * A360290 A360291 A360292

Keyword

nonn,look,tabf

Author

Alois P. Heinz, Feb 01 2023

Status

approved