A088370 Triangle T(n,k), read by rows, where the n-th row is a binary arrangement of the numbers 1 through n.

1, 1, 2, 1, 3, 2, 1, 3, 2, 4, 1, 5, 3, 2, 4, 1, 5, 3, 2, 6, 4, 1, 5, 3, 7, 2, 6, 4, 1, 5, 3, 7, 2, 6, 4, 8, 1, 9, 5, 3, 7, 2, 6, 4, 8, 1, 9, 5, 3, 7, 2, 10, 6, 4, 8, 1, 9, 5, 3, 11, 7, 2, 10, 6, 4, 8, 1, 9, 5, 3, 11, 7, 2, 10, 6, 4, 12, 8, 1, 9, 5, 13, 3, 11, 7, 2, 10, 6, 4, 12, 8, 1, 9, 5, 13, 3, 11, 7, 2, 10, 6, 14, 4, 12, 8

Offset: 1

Author

Paul D. Hanna, Sep 28 2003

Keywords

• nonn
• tabl

Comments

The n-th row differs from the prior row only by the presence of n. See A088371 for the positions in the n-th row that n is inserted.

From Clark Kimberling, Aug 02 2007: (Start)

At A131966, this sequence is cited as the fractal sequence of the Cantor set C.

Recall that C is the set of fractions in [0,1] whose base 3 representation consists solely of 0's and 2's.

Arrange these fractions as follows:

0

0, .2

0, .02, .2

0, .02, .2, .22

0, .002, .02, .2, .22, etc.

Replace each number x by its order of appearance, counting each distinct predecessor of x only once, getting

1;

1, 2;

1, 3, 2;

1, 3, 2, 4;

1, 5, 3, 2, 4;

Concatenate these to get the current sequence, which is a fractal sequence as defined in "Fractal sequences and interspersions".

One property of such a sequence is that it properly contains itself as a subsequence (infinitely many times). (End)

Row n contains one of A003407(n) non-averaging permutations of [n], i.e., a permutation of [n] without 3-term arithmetic progressions. - Alois P. Heinz, Dec 05 2017

Examples

			Row 5 is formed from row 3, {1,3,2} and row 2, {1,2}, like so:
{1,5,3, 2,4} = {1*2-1, 3*2-1, 2*2-1} | {1*2, 2*2}.
Triangle begins:
  1;
  1,  2;
  1,  3, 2;
  1,  3, 2,  4;
  1,  5, 3,  2,  4;
  1,  5, 3,  2,  6,  4;
  1,  5, 3,  7,  2,  6,  4;
  1,  5, 3,  7,  2,  6,  4,  8;
  1,  9, 5,  3,  7,  2,  6,  4,  8;
  1,  9, 5,  3,  7,  2, 10,  6,  4,  8;
  1,  9, 5,  3, 11,  7,  2, 10,  6,  4,  8;
  1,  9, 5,  3, 11,  7,  2, 10,  6,  4, 12,  8;
  1,  9, 5, 13,  3, 11,  7,  2, 10,  6,  4, 12,  8;
  1,  9, 5, 13,  3, 11,  7,  2, 10,  6, 14,  4, 12,  8;
  1,  9, 5, 13,  3, 11,  7, 15,  2, 10,  6, 14,  4, 12,  8;
  1,  9, 5, 13,  3, 11,  7, 15,  2, 10,  6, 14,  4, 12,  8, 16;
  1, 17, 9,  5, 13,  3, 11,  7, 15,  2, 10,  6, 14,  4, 12,  8, 16;
  ...
		

References

• Clark Kimberling, "Fractal sequences and interspersions," Ars Combinatoria 45 (1997) 157-168.

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• Eric Weisstein's World of Mathematics, Nonaveraging Sequence
• Wikipedia, Arithmetic progression
• Index entries related to non-averaging sequences

Crossrefs

Cf. A003407, A088371, A309371.

Diagonal gives A053644. Cf. A049773. - Alois P. Heinz, Oct 28 2011

Programs

Maple

T:= proc(n) option remember;
      `if`(n=1, 1, [map(x-> 2*x-1, [T(n-iquo(n,2))])[],
                    map(x-> 2*x,   [T(  iquo(n,2))])[]][])
    end:
seq(T(n), n=1..20);  # Alois P. Heinz, Oct 28 2011

Mathematica

T[1] = {1}; T[n_] := T[n] = Join[q = Quotient[n, 2]; 2*T[n-q]-1, 2*T[q]]; Table[ T[n], {n, 1, 20}] // Flatten (* Jean-François Alcover, Feb 26 2015, after Alois P. Heinz *)

PARI

{T(n,k) = if(k==0, 1, if(k<=n\2, 2*T(n\2,k) - 1, 2*T((n-1)\2,k-1-n\2) ))}
for(n=0,20,for(k=0,n,print1(T(n,k),", "));print(""))

Formula

T(n,n) = 2^(floor(log(n)/log(2))). Construction. The 2n-th row is the concatenation of row n, after multiplying each term by 2 and subtracting 1, with row n, after multiplying each term by 2. The (2n-1)-th row is the concatenation of row n, after multiplying each term by 2 and subtracting 1, with row n-1, after multiplying each term by 2.

Sum_{k=1..n} k * A088370(n,k) = A309371(n). - Alois P. Heinz, Jul 26 2019