cp's OEIS Frontend

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

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