

A088370


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


6



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

The nth row differs from the prior row only by the presence of n. See A088371 for the positions in the nth 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 0s and 2s.
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) nonaveraging permutations of [n], i.e., a permutation of [n] without 3term arithmetic progressions.  Alois P. Heinz, Dec 05 2017


REFERENCES

Clark Kimberling, "Fractal sequences and interspersions," Ars Combinatoria 45 (1997) 157168.


LINKS

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


FORMULA

T(n,n) = 2^(floor(log(n)/log(2))). Construction. The 2nth 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 (2n1)th row is the concatenation of row n, after multiplying each term by 2 and subtracting 1, with row n1, after multiplying each term by 2.


EXAMPLE

Row 5 is formed from row 3, {1,3,2} and row 2, {1,2}, like so:
{1,5,3, 2,4} = {1*21, 3*21, 2*21}  {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*x1, [T(niquo(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[nq]1, 2*T[q]]; Table[ T[n], {n, 1, 20}] // Flatten (* JeanFranç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((n1)\2, k1n\2) ))}
for(n=0, 20, for(k=0, n, print1(T(n, k), ", ")); print(""))


CROSSREFS

Cf. A003407, A088371.
Diagonal gives A053644. Cf. A049773.  Alois P. Heinz, Oct 28 2011
Sequence in context: A082074 A132283 A256440 * A113787 A115624 A076291
Adjacent sequences: A088367 A088368 A088369 * A088371 A088372 A088373


KEYWORD

nonn,tabl


AUTHOR

Paul D. Hanna, Sep 28 2003


STATUS

approved



