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,3

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

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

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

Example

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

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

Prog

(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(""))

Crossrefs

Cf. A003407, A088371, A309371.

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

Sequence in context: A132283 A307081 A256440 * A328719 A113787 A115624

Adjacent sequences: A088367 A088368 A088369 * A088371 A088372 A088373

Keyword

nonn,tabl

Author

Paul D. Hanna, Sep 28 2003

Status

approved