A106182 - OEIS

%I #18 Dec 10 2023 17:42:45

%S 1,2,3,6,8,14,20,32,48,60,109,138,200,296,404,576,776,1170,1480,2144,

%T 2912,3888,5578,7204,10032,13276

%N Number of inequivalent binary sequences of length n, where two sequences are said to be equivalent if they have the same set of phrases in their Ziv-Lempel encodings (the phrases can appear in a different order in the two sequences).

%C The Ziv-Lempel encoding scans the sequence from left to right and inserts a comma when the current phrase is an extension by one bit of an earlier phrase. In any case the scan ends with a comma. The phrases are the segments between the commas.

%C Equivalent sequences necessarily have the same Hamming weight.

%D J. Ziv and A. Lempel, A universal algorithm for sequential data compression. IEEE Trans. Information Theory IT-23 (1977), 337-343.

%H G. Seroussi, <a href="http://www.hpl.hp.com/techreports/2004/HPL-2004-153.html">On universal types</a>, Preprint, 2004.

%H G. Seroussi, <a href="https://arxiv.org/abs/cs/0509046">On the number of t-ary trees with a given path length</a>, Algorithmica 46(3), 557-565, 2006; arXiv:cs/0509046 [cs.DM], 2005-2007.

%F Seroussi shows that a(n) is asymptotically 2^{2cn/log_2(n)(1+o(1))}, where c = 0.11... is the inverse entropy function of 1/2.

%e The Ziv-Lempel encodings of the strings of lengths 1 through 3 are:

%e 0,

%e 1, so a(1)=2;

%e 0,0,

%e 0,1,

%e 1,0, (same phrases as in previous line)

%e 1,1, so a(2)=3;

%e 0,00,

%e 0,01,

%e 0,1,0,

%e 1,0,0, (same phrases as in previous line)

%e 0,1,1,

%e 1,0,1, (same phrases as in previous line)

%e 1,10,

%e 1,11, so a(3)=6; ...

%o (Tcl)

%o proc compress_phrases {vec} {set cur []; foreach v $vec {lappend cur $v

%o if {![info exists phrases($cur)]} {set phrases($cur) 1; set cur []}}

%o set plist [array names phrases]; if {[llength $cur]} {lappend plist $cur}

%o return [lsort $plist]}

%o proc enum {n vec} {if {$n == 0} {global phraselists

%o set phraselists([compress_phrases $vec]) 1} else {incr n -1

%o enum $n [concat $vec [list 0]];enum $n [concat $vec [list 1]]}}

%o proc doit {} {global phraselists; set n 0; while {1} {array unset phraselists

%o enum $n []; puts -nonewline "[array size phraselists],"; flush stdout; incr n}}

%o doit

%o # _David Applegate_

%Y Row sums of A109338. Cf. A109337.

%Y Cf. A095830.

%K nonn,hard

%O 0,2

%A _N. J. A. Sloane_, Aug 23 2005

%E Terms from a(6) onwards from _David Applegate_, Aug 29 2005

%E Terms a(0)-a(20) confirmed and a(21)-a(25) added by _John W. Layman_, Sep 20 2010