login
A194959
Fractalization of (1 + floor(n/2)).
61
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, 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, 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
OFFSET
1,3
COMMENTS
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).
...
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
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.
The interspersion I(P) has the following northwest corner, easily read from f:
1 2 4 7 11 16 22
3 6 10 15 21 28 36
5 8 12 17 23 30 38
9 14 20 27 35 44 54
...
Following is a chart of selected p, f, I(p), and Q(p):
p f I(p) Q(p)
Count odd numbers up to n, then even numbers down from n. - Franklin T. Adams-Watters, Jan 21 2012
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
REFERENCES
Clark Kimberling, "Fractal sequences and interspersions," Ars Combinatoria 45 (1997) 157-168.
LINKS
Paul Lévy, Sur quelques classes de permutations, Compositio Mathematica, Volume 8, 1951, pages 1-48. P_n = g(n).
Eric Weisstein's World of Mathematics, Fractal sequence
Eric Weisstein's World of Mathematics, Interspersion
Wikipedia, Fractal sequence
FORMULA
From Werner Schulte, May 27 2018 and Jul 10 2018: (Start)
Seen as a triangle: It seems that the triangle T(n,k) for 1 <= k <= n (see Example) is the mirror image of A210535.
Seen as a square array A(n,k) and as a triangle T(n,k):
A(n,k) = 2*k-1 for 1 <= k <= n, and A(n,k) = 2*n for 1 <= n < k.
A(n+1,k+1) = A(n,k+1) + A(n,k) - A(n-1,k) for k > 0 and n > 1.
A(n,k) = A(k,n) - 1 for n > k >= 1.
P(n,x) = Sum_{k>0} A(n,k)*x^(k-1) = (1-x^n)*(1-x^2)/(1-x)^3 for n >= 1.
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.
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)).
Sum_{k=1..n} A(n+1-k,k) = Sum_{k=1..n} T(n,k) = A000217(n) for n > 0.
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.
Product_{k=1..n} A(n+1-k,k) = Product_{k=1..n} T(n,k) = A000142(n) for n > 0.
A(n+m,n) = A005408(n-1) for n > 0 and some fixed m >= 0.
A(n,n+m) = A005843(n) for n > 0 and some fixed m > 0.
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.
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).
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)).
Sum_{k=1..n} A(k,n+1-k)*A209229(k) = 2*n-1. (conjectured)
(End)
From Kevin Ryde, Oct 09 2020: (Start)
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)]
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)]
(End)
EXAMPLE
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,...).
From Werner Schulte, May 27 2018: (Start)
This sequence seen as a square array read by antidiagonals:
n\k: 1 2 3 4 5 6 7 8 9 10 11 12 ...
===================================================
1 1 2 2 2 2 2 2 2 2 2 2 2 ... (see A040000)
2 1 3 4 4 4 4 4 4 4 4 4 4 ... (see A113311)
3 1 3 5 6 6 6 6 6 6 6 6 6 ...
4 1 3 5 7 8 8 8 8 8 8 8 8 ...
5 1 3 5 7 9 10 10 10 10 10 10 10 ...
6 1 3 5 7 9 11 12 12 12 12 12 12 ...
7 1 3 5 7 9 11 13 14 14 14 14 14 ...
8 1 3 5 7 9 11 13 15 16 16 16 16 ...
9 1 3 5 7 9 11 13 15 17 18 18 18 ...
10 1 3 5 7 9 11 13 15 17 19 20 20 ...
etc.
This sequence seen as a triangle read by rows:
n\k: 1 2 3 4 5 6 7 8 9 10 11 12 ...
======================================================
1 1
2 1 2
3 1 3 2
4 1 3 4 2
5 1 3 5 4 2
6 1 3 5 6 4 2
7 1 3 5 7 6 4 2
8 1 3 5 7 8 6 4 2
9 1 3 5 7 9 8 6 4 2
10 1 3 5 7 9 10 8 6 4 2
11 1 3 5 7 9 11 10 8 6 4 2
12 1 3 5 7 9 11 12 10 8 6 4 2
etc.
(End)
MATHEMATICA
r = 2; p[n_] := 1 + Floor[n/r]
Table[p[n], {n, 1, 90}] (* A008619 *)
g[1] = {1}; g[n_] := Insert[g[n - 1], n, p[n]]
f[1] = g[1]; f[n_] := Join[f[n - 1], g[n]]
f[20] (* A194959 *)
row[n_] := Position[f[30], n];
u = TableForm[Table[row[n], {n, 1, 5}]]
v[n_, k_] := Part[row[n], k];
w = Flatten[Table[v[k, n - k + 1], {n, 1, 13},
{k, 1, n}]] (* A057027 *)
q[n_] := Position[w, n]; Flatten[
Table[q[n], {n, 1, 80}]] (* A064578 *)
Flatten[FoldList[Insert[#1, #2, Floor[#2/2] + 1] &, {}, Range[10]]] (* Birkas Gyorgy, Jun 30 2012 *)
PROG
(PARI) T(n, k) = min(k<<1-1, (n-k+1)<<1); \\ Kevin Ryde, Oct 09 2020
CROSSREFS
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).
Cf. A003558 (g permutation order), A102417 (index), A330081 (on bits), A057058 (inverse).
Sequence in context: A194968 A194980 A323607 * A194921 A195079 A124458
KEYWORD
nonn,tabl
AUTHOR
Clark Kimberling, Sep 06 2011
EXTENSIONS
Name corrected by Franklin T. Adams-Watters, Jan 21 2012
STATUS
approved