%I #34 Apr 06 2020 19:07:35
%S 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,
%T 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,
%U 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
%N Triangle T(n,k), read by rows, where the n-th row is a binary arrangement of the numbers 1 through n.
%C 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.
%C From _Clark Kimberling_, Aug 02 2007: (Start)
%C At A131966, this sequence is cited as the fractal sequence of the Cantor set C.
%C Recall that C is the set of fractions in [0,1] whose base 3 representation consists solely of 0's and 2's.
%C Arrange these fractions as follows:
%C 0
%C 0, .2
%C 0, .02, .2
%C 0, .02, .2, .22
%C 0, .002, .02, .2, .22, etc.
%C Replace each number x by its order of appearance, counting each distinct predecessor of x only once, getting
%C 1;
%C 1, 2;
%C 1, 3, 2;
%C 1, 3, 2, 4;
%C 1, 5, 3, 2, 4;
%C Concatenate these to get the current sequence, which is a fractal sequence as defined in "Fractal sequences and interspersions".
%C One property of such a sequence is that it properly contains itself as a subsequence (infinitely many times). (End)
%C 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
%D Clark Kimberling, "Fractal sequences and interspersions," Ars Combinatoria 45 (1997) 157-168.
%H Alois P. Heinz, <a href="/A088370/b088370.txt">Rows n = 1..141, flattened</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/NonaveragingSequence.html">Nonaveraging Sequence</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Arithmetic_progression">Arithmetic progression</a>
%H <a href="/index/No#non_averaging">Index entries related to non-averaging sequences</a>
%F 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.
%F Sum_{k=1..n} k * A088370(n,k) = A309371(n). - _Alois P. Heinz_, Jul 26 2019
%e Row 5 is formed from row 3, {1,3,2} and row 2, {1,2}, like so:
%e {1,5,3, 2,4} = {1*2-1, 3*2-1, 2*2-1} | {1*2, 2*2}.
%e Triangle begins:
%e 1;
%e 1, 2;
%e 1, 3, 2;
%e 1, 3, 2, 4;
%e 1, 5, 3, 2, 4;
%e 1, 5, 3, 2, 6, 4;
%e 1, 5, 3, 7, 2, 6, 4;
%e 1, 5, 3, 7, 2, 6, 4, 8;
%e 1, 9, 5, 3, 7, 2, 6, 4, 8;
%e 1, 9, 5, 3, 7, 2, 10, 6, 4, 8;
%e 1, 9, 5, 3, 11, 7, 2, 10, 6, 4, 8;
%e 1, 9, 5, 3, 11, 7, 2, 10, 6, 4, 12, 8;
%e 1, 9, 5, 13, 3, 11, 7, 2, 10, 6, 4, 12, 8;
%e 1, 9, 5, 13, 3, 11, 7, 2, 10, 6, 14, 4, 12, 8;
%e 1, 9, 5, 13, 3, 11, 7, 15, 2, 10, 6, 14, 4, 12, 8;
%e 1, 9, 5, 13, 3, 11, 7, 15, 2, 10, 6, 14, 4, 12, 8, 16;
%e 1, 17, 9, 5, 13, 3, 11, 7, 15, 2, 10, 6, 14, 4, 12, 8, 16;
%e ...
%p T:= proc(n) option remember;
%p `if`(n=1, 1, [map(x-> 2*x-1, [T(n-iquo(n,2))])[],
%p map(x-> 2*x, [T( iquo(n,2))])[]][])
%p end:
%p seq(T(n), n=1..20); # _Alois P. Heinz_, Oct 28 2011
%t 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_ *)
%o (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) ))}
%o for(n=0,20,for(k=0,n,print1(T(n,k),", "));print(""))
%Y Cf. A003407, A088371, A309371.
%Y Diagonal gives A053644. Cf. A049773. - _Alois P. Heinz_, Oct 28 2011
%K nonn,tabl
%O 1,3
%A _Paul D. Hanna_, Sep 28 2003