login
Table T(n,k) = number of fractal initial sequences (where new values are successive integers) of length n whose last term is k.
0

%I #11 Apr 12 2014 19:27:20

%S 1,1,1,2,1,1,3,2,2,1,5,4,3,3,1,8,8,5,6,4,1,14,14,10,10,10,5,1,24,25,

%T 21,16,20,15,6,1,43,43,43,28,35,35,21,7,1,77,76,83,56,57,70,56,28,8,1,

%U 140,136,153,120,93,126,126,84,36,9,1,256,248,274,256,165,211,252,210,120,45,10,1

%N Table T(n,k) = number of fractal initial sequences (where new values are successive integers) of length n whose last term is k.

%C A fractal sequence is one where, when the first instance of each integer is removed, the original sequence results. We require also that these first instances occur in order: 1,1,2,3 is OK, but 1,1,3,2 is not. A finite sequence is an initial subsequence of (uncountably many) fractal sequences when the result after removing the first instance of each number is an initial subsequence. The total number of such sequences of length n is 2^{n-1}. At each index after the first, the next value can be either a new value or a uniquely determined repetition of some earlier value. Conjecture: column 1 of this array is A007059.

%H C. Kimberling, <a href="http://faculty.evansville.edu/ck6/integer/fractals.html">Fractal sequences</a>

%F If 2 <= n <= 2k-1, T(n,k) = C(n-2,k-2).

%e For n = 3, the 4 sequences are 1,1,1; 1,1,2; 1,2,1; and 1,2,3. Of these, 2 end in 1, 1 in 2 and 1 in 3, so row 3 is 2,1,1.

%e The table starts:

%e 1

%e 1,1

%e 2,1,1

%e 3,2,2,1

%e 5,4,3,3,1

%e 8,8,5,6,4,1

%t uppertrim[list_] := Fold[DeleteCases[#1, #2, 1, 1] &, list, Range[Max[list]]]; to[list_, 0] := Append[list, Part[list, Length[uppertrim@list] + 1]]; to[list_, 1] := Append[list, Max@list + 1]; allfractal[n_] := Fold[to[#1, #2] &, {1}, #] & /@ Tuples[{0, 1}, n]; k = 10; Flatten[Table[BinCounts[allfractal[k][[All, i]], {1, i + 1}] 2^(i - 1), {i, k + 1}]/2^k] (* _Birkas Gyorgy_, Nov 25 2012 *)

%Y Cf. A007059.

%K nonn,tabl

%O 1,4

%A _Franklin T. Adams-Watters_, Aug 17 2006