cp's OEIS Frontend

A106182 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).

%I A106182 #18 Dec 10 2023 17:42:45
%S A106182 1,2,3,6,8,14,20,32,48,60,109,138,200,296,404,576,776,1170,1480,2144,
%T A106182 2912,3888,5578,7204,10032,13276
%N A106182 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 A106182 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 A106182 Equivalent sequences necessarily have the same Hamming weight.
%D A106182 J. Ziv and A. Lempel, A universal algorithm for sequential data compression. IEEE Trans. Information Theory IT-23 (1977), 337-343.
%H A106182 G. Seroussi, <a href="http://www.hpl.hp.com/techreports/2004/HPL-2004-153.html">On universal types</a>, Preprint, 2004.
%H A106182 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 A106182 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 A106182 The Ziv-Lempel encodings of the strings of lengths 1 through 3 are:
%e A106182 0,
%e A106182 1, so a(1)=2;
%e A106182 0,0,
%e A106182 0,1,
%e A106182 1,0, (same phrases as in previous line)
%e A106182 1,1, so a(2)=3;
%e A106182 0,00,
%e A106182 0,01,
%e A106182 0,1,0,
%e A106182 1,0,0, (same phrases as in previous line)
%e A106182 0,1,1,
%e A106182 1,0,1, (same phrases as in previous line)
%e A106182 1,10,
%e A106182 1,11, so a(3)=6; ...
%o A106182 (Tcl)
%o A106182 proc compress_phrases {vec} {set cur []; foreach v $vec {lappend cur $v
%o A106182 if {![info exists phrases($cur)]} {set phrases($cur) 1; set cur []}}
%o A106182 set plist [array names phrases]; if {[llength $cur]} {lappend plist $cur}
%o A106182 return [lsort $plist]}
%o A106182 proc enum {n vec} {if {$n == 0} {global phraselists
%o A106182 set phraselists([compress_phrases $vec]) 1} else {incr n -1
%o A106182 enum $n [concat $vec [list 0]];enum $n [concat $vec [list 1]]}}
%o A106182 proc doit {} {global phraselists; set n 0; while {1} {array unset phraselists
%o A106182 enum $n []; puts -nonewline "[array size phraselists],"; flush stdout; incr n}}
%o A106182 doit
%o A106182 # _David Applegate_
%Y A106182 Row sums of A109338. Cf. A109337.
%Y A106182 Cf. A095830.
%K A106182 nonn,hard
%O A106182 0,2
%A A106182 _N. J. A. Sloane_, Aug 23 2005
%E A106182 Terms from a(6) onwards from _David Applegate_, Aug 29 2005
%E A106182 Terms a(0)-a(20) confirmed and a(21)-a(25) added by _John W. Layman_, Sep 20 2010