A360287 -id:A360287 - cp's OEIS frontend

A227738 Irregular table read by rows: each row n (n>=1) lists the positions where the runs of bits change between 0's and 1's in the binary expansion of n, when scanning it from the least significant to the most significant end.

1, 1, 2, 2, 2, 3, 1, 2, 3, 1, 3, 3, 3, 4, 1, 3, 4, 1, 2, 3, 4, 2, 3, 4, 2, 4, 1, 2, 4, 1, 4, 4, 4, 5, 1, 4, 5, 1, 2, 4, 5, 2, 4, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 5, 3, 4, 5, 3, 5, 1, 3, 5, 1, 2, 3, 5, 2, 3, 5, 2, 5, 1, 2, 5, 1, 5, 5, 5, 6, 1, 5, 6, 1, 2, 5, 6

Offset: 1

Antti Karttunen, Jul 25 2013

Row n has A005811(n) terms.
As a sequence, seems to have a particular fractal structure, probably allowing additional formulas.
Row n lists the positions of 1-bits in the binary expansion of the Gray code for n, A003188(n), when 1 is the rightmost position. A003188(17) = 25 = 11001_2 gives row 17: 1,4,5. - Alois P. Heinz, Feb 01 2023

			Table begins as:
  Row  n in    Terms on
   n   binary  that row
   1      1    1;
   2     10    1,2;
   3     11    2;
   4    100    2,3;
   5    101    1,2,3;
   6    110    1,3;
   7    111    3;
   8   1000    3,4;
   9   1001    1,3,4;
  10   1010    1,2,3,4;
  11   1011    2,3,4;
  12   1100    2,4;
  13   1101    1,2,4;
  14   1110    1,4;
  15   1111    4;
  16  10000    4,5;
etc.
The terms also give the partial sums of runlengths, when the binary expansion of n is scanned from the least significant to the most significant end.

Antti Karttunen, The rows 1..1023 of the table, flattened
Wikipedia, Gray code

Each row n (n>=1) contains the initial A005811(n) nonzero terms from the beginning of row n of A227188. A227192(n) gives the sum of terms on row n. A136480 gives the first column.
Cf. also A227188, A227736, A227739.
A318926 is a compressed version. If the order is reversed we get A101211 and A318927.
Cf. A003188, A360287.

T:= n-> (l-> seq(`if`(l[i]=1, i, [][]), i=1..nops(l)))(
                 Bits[Split](Bits[Xor](n, iquo(n, 2)))):
seq(T(n), n=1..50);  # Alois P. Heinz, Feb 01 2023

Table[Rest@FoldList[Plus,0,Length/@Split[Reverse[IntegerDigits[n,2]]]],{n,34}]//Flatten (* Wouter Meeussen, Aug 31 2013 *)

a(n) = A227188(A227737(n),A227740(n)).

Alternatively, if A227740(n) is 0, then a(n) = A227736(n), otherwise a(n) = a(n-1) + A227736(n). [Each row gives cumulative sums of the runlengths of binary representation of 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.

Original entry on oeis.org

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

Alois P. Heinz, Feb 01 2023

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.

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

Alois P. Heinz, Rows n = 0..15, flattened
Wikipedia, Gray code
Wikipedia, Permutation

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.

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 (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n}, 0)):
seq(T(n), n=0..7);

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

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.

Original entry on oeis.org

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

Alois P. Heinz, Feb 03 2023

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

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

Alois P. Heinz, Rows n = 0..15, flattened
Wikipedia, Gray code
Wikipedia, Permutation

Row sums give A000142.
Row lengths are A011782.
See A060351, A335845, A357611 for similar triangles (same terms, different ordering within each row).
Cf. A003188, A006068, A227738, A360287.

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

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

cp's OEIS Frontend

A227738 Irregular table read by rows: each row n (n>=1) lists the positions where the runs of bits change between 0's and 1's in the binary expansion of n, when scanning it from the least significant to the most significant end.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica