%I #51 Oct 14 2020 10:51:20

%S 1,1,2,1,3,2,1,3,4,2,1,3,5,4,2,1,3,5,6,4,2,1,3,5,7,6,4,2,1,3,5,7,8,6,

%T 4,2,1,3,5,7,9,8,6,4,2,1,3,5,7,9,10,8,6,4,2,1,3,5,7,9,11,10,8,6,4,2,1,

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

%N Fractalization of (1 + floor(n/2)).

%C Suppose that p(1), p(2), p(3), ... is an integer sequence satisfying 1 <= p(n) <= n for n >= 1. Define g(1)=(1) and for n > 1, form g(n) from g(n-1) by inserting n so that its position in the resulting n-tuple is p(n). The sequence f obtained by concatenating g(1), g(2), g(3), ... is clearly a fractal sequence, here introduced as the fractalization of p. The interspersion associated with f is here introduced as the interspersion fractally induced by p, denoted by I(p); thus, the k-th term in the n-th row of I(p) is the position of the k-th n in f. Regarded as a sequence, I(p) is a permutation of the positive integers; its inverse permutation is denoted by Q(p).

%C ...

%C Example: Let p=(1,2,2,3,3,4,4,5,5,6,6,7,7,...)=A008619. Then g(1)=(1), g(2)=(1,2), g(3)=(1,3,2), so that

%C f=(1,1,2,1,3,2,1,3,4,2,1,3,5,4,2,1,3,5,6,4,2,1,...)=A194959; and I(p)=A057027, Q(p)=A064578.

%C The interspersion I(P) has the following northwest corner, easily read from f:

%C 1 2 4 7 11 16 22

%C 3 6 10 15 21 28 36

%C 5 8 12 17 23 30 38

%C 9 14 20 27 35 44 54

%C ...

%C Following is a chart of selected p, f, I(p), and Q(p):

%C p f I(p) Q(p)

%C A000027 A002260 A000027 A000027

%C A008619 A194959 A057027 A064578

%C A194960 A194961 A194962 A194963

%C A053824 A194965 A194966 A194967

%C A053737 A194973 A194974 A194975

%C A019446 A194968 A194969 A194970

%C A049474 A194976 A194977 A194978

%C A194979 A194980 A194981 A194982

%C A194964 A194983 A194984 A194985

%C A194986 A194987 A194988 A194989

%C Count odd numbers up to n, then even numbers down from n. - _Franklin T. Adams-Watters_, Jan 21 2012

%C This sequence defines the square array A(n,k), n > 0 and k > 0, read by antidiagonals and the triangle T(n,k) = A(n+1-k,k) for 1 <= k <= n read by rows (see Formula and Example). - _Werner Schulte_, May 27 2018

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

%H Paul Lévy, <a href="http://www.numdam.org/item?id=CM_1951__8__1_0">Sur quelques classes de permutations</a>, Compositio Mathematica, Volume 8, 1951, pages 1-48. P_n = g(n).

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FractalSequence.html">Fractal sequence</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Interspersion.html">Interspersion</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Fractal_sequence">Fractal sequence</a>

%F From _Werner Schulte_, May 27 2018 and Jul 10 2018: (Start)

%F Seen as a triangle: It seems that the triangle T(n,k) for 1 <= k <= n (see Example) is the mirror image of A210535.

%F Seen as a square array A(n,k) and as a triangle T(n,k):

%F A(n,k) = 2*k-1 for 1 <= k <= n, and A(n,k) = 2*n for 1 <= n < k.

%F A(n+1,k+1) = A(n,k+1) + A(n,k) - A(n-1,k) for k > 0 and n > 1.

%F A(n,k) = A(k,n) - 1 for n > k >= 1.

%F P(n,x) = Sum_{k>0} A(n,k)*x^(k-1) = (1-x^n)*(1-x^2)/(1-x)^3 for n >= 1.

%F Q(y,k) = Sum_{n>0} A(n,k)*y^(n-1) = 1/(1-y) for k = 1 and Q(y,k) = Q(y,1) + P(k-1,y) for k > 1.

%F G.f.: Sum_{n>0, k>0} A(n,k)*x^(k-1)*y^(n-1) = (1+x)/((1-x)*(1-y)*(1-x*y)).

%F Sum_{k=1..n} A(n+1-k,k) = Sum_{k=1..n} T(n,k) = A000217(n) for n > 0.

%F Sum_{k=1..n} (-1)^(k-1) * A(n+1-k,k) = Sum_{k=1..n} (-1)^(k-1) * T(n,k) = A219977(n-1) for n > 0.

%F Product_{k=1..n} A(n+1-k,k) = Product_{k=1..n} T(n,k) = A000142(n) for n > 0.

%F A(n+m,n) = A005408(n-1) for n > 0 and some fixed m >= 0.

%F A(n,n+m) = A005843(n) for n > 0 and some fixed m > 0.

%F Let A_m be the upper left part of the square array A(n,k) with m rows and m columns. Then det(A_m) = 1 for some fixed m > 0.

%F The P(n,x) satisfy the recurrence equation P(n+1,x) = P(n,x) + x^n*P(1,x) for n > 0 and initial value P(1,x) = (1+x)/(1-x).

%F Let B(n,k) be multiplicative with B(n,p^e) = A(n,e+1) for e >= 0 and some fixed n > 0. That yields the Dirichlet g.f.: Sum_{k>0} B(n,k)/k^s = (zeta(s))^3/(zeta(2*s)*zeta(n*s)).

%F Sum_{k=1..n} A(k,n+1-k)*A209229(k) = 2*n-1. (conjectured)

%F (End)

%F From _Kevin Ryde_, Oct 09 2020: (Start)

%F T(n,k) = 2*k-1 if 2*k-1 <= n, or 2*(n+1-k) if 2*k-1 > n. [Lévy, chapter 1 section 1 equations (a),(b)]

%F Fixed points T(n,k)=k for k=1 and k = (2/3)*(n+1) when an integer. [Lévy, chapter 1 section 2 equation (3)]

%F (End)

%e The sequence p=A008619 begins with 1,2,2,3,3,4,4,5,5,..., so that g(1)=(1). To form g(2), write g(1) and append 2 so that in g(2) this 2 has position p(2)=2: g(2)=(1,2). Then form g(3) by inserting 3 at position p(3)=2: g(3)=(1,3,2), and so on. The fractal sequence A194959 is formed as the concatenation g(1)g(2)g(3)g(4)g(5)...=(1,1,2,1,3,2,1,3,4,2,1,3,5,4,2,...).

%e From _Werner Schulte_, May 27 2018: (Start)

%e This sequence seen as a square array read by antidiagonals:

%e n\k: 1 2 3 4 5 6 7 8 9 10 11 12 ...

%e ===================================================

%e 1 1 2 2 2 2 2 2 2 2 2 2 2 ... (see A040000)

%e 2 1 3 4 4 4 4 4 4 4 4 4 4 ... (see A113311)

%e 3 1 3 5 6 6 6 6 6 6 6 6 6 ...

%e 4 1 3 5 7 8 8 8 8 8 8 8 8 ...

%e 5 1 3 5 7 9 10 10 10 10 10 10 10 ...

%e 6 1 3 5 7 9 11 12 12 12 12 12 12 ...

%e 7 1 3 5 7 9 11 13 14 14 14 14 14 ...

%e 8 1 3 5 7 9 11 13 15 16 16 16 16 ...

%e 9 1 3 5 7 9 11 13 15 17 18 18 18 ...

%e 10 1 3 5 7 9 11 13 15 17 19 20 20 ...

%e etc.

%e This sequence seen as a triangle read by rows:

%e n\k: 1 2 3 4 5 6 7 8 9 10 11 12 ...

%e ======================================================

%e 1 1

%e 2 1 2

%e 3 1 3 2

%e 4 1 3 4 2

%e 5 1 3 5 4 2

%e 6 1 3 5 6 4 2

%e 7 1 3 5 7 6 4 2

%e 8 1 3 5 7 8 6 4 2

%e 9 1 3 5 7 9 8 6 4 2

%e 10 1 3 5 7 9 10 8 6 4 2

%e 11 1 3 5 7 9 11 10 8 6 4 2

%e 12 1 3 5 7 9 11 12 10 8 6 4 2

%e etc.

%e (End)

%t r = 2; p[n_] := 1 + Floor[n/r]

%t Table[p[n], {n, 1, 90}] (* A008619 *)

%t g[1] = {1}; g[n_] := Insert[g[n - 1], n, p[n]]

%t f[1] = g[1]; f[n_] := Join[f[n - 1], g[n]]

%t f[20] (* A194959 *)

%t row[n_] := Position[f[30], n];

%t u = TableForm[Table[row[n], {n, 1, 5}]]

%t v[n_, k_] := Part[row[n], k];

%t w = Flatten[Table[v[k, n - k + 1], {n, 1, 13},

%t {k, 1, n}]] (* A057027 *)

%t q[n_] := Position[w, n]; Flatten[

%t Table[q[n], {n, 1, 80}]] (* A064578 *)

%t Flatten[FoldList[Insert[#1, #2, Floor[#2/2] + 1] &, {}, Range[10]]] (* _Birkas Gyorgy_, Jun 30 2012 *)

%o (PARI) T(n,k) = min(k<<1-1,(n-k+1)<<1); \\ _Kevin Ryde_, Oct 09 2020

%Y Cf. A000142, A000217, A005408, A005843, A008619, A057027, A064578, A209229, A210535, A219977; A000012 (col 1), A157532 (col 2), A040000 (row 1), A113311 (row 2); A194029 (introduces the natural fractal sequence and natural interspersion of a sequence - different from those introduced at A194959).

%Y Cf. A003558 (g permutation order), A102417 (index), A330081 (on bits), A057058 (inverse).

%K nonn,tabl

%O 1,3

%A _Clark Kimberling_, Sep 06 2011

%E Name corrected by _Franklin T. Adams-Watters_, Jan 21 2012