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

1, 2, 3, 6, 8, 14, 20, 32, 48, 60, 109, 138, 200, 296, 404, 576, 776, 1170, 1480, 2144, 2912, 3888, 5578, 7204, 10032, 13276

Offset

0,2

Comments

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.

Equivalent sequences necessarily have the same Hamming weight.

References

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

Links

Table of n, a(n) for n=0..25.

G. Seroussi, On universal types, Preprint, 2004.

G. Seroussi, On the number of t-ary trees with a given path length, Algorithmica 46(3), 557-565, 2006; arXiv:cs/0509046 [cs.DM], 2005-2007.

Formula

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.

Example

The Ziv-Lempel encodings of the strings of lengths 1 through 3 are:
0,
1, so a(1)=2;
0,0,
0,1,
1,0, (same phrases as in previous line)
1,1, so a(2)=3;
0,00,
0,01,
0,1,0,
1,0,0, (same phrases as in previous line)
0,1,1,
1,0,1, (same phrases as in previous line)
1,10,
1,11, so a(3)=6; ...

Prog

(Tcl)
proc compress_phrases {vec} {set cur []; foreach v $vec {lappend cur $v
if {![info exists phrases($cur)]} {set phrases($cur) 1; set cur []}}
set plist [array names phrases]; if {[llength $cur]} {lappend plist $cur}
return [lsort $plist]}
proc enum {n vec} {if {$n == 0} {global phraselists
set phraselists([compress_phrases $vec]) 1} else {incr n -1
enum $n [concat $vec [list 0]]; enum $n [concat $vec [list 1]]}}
proc doit {} {global phraselists; set n 0; while {1} {array unset phraselists
enum $n []; puts -nonewline "[array size phraselists], "; flush stdout; incr n}}
doit
# David Applegate

Crossrefs

Row sums of A109338. Cf. A109337.

Cf. A095830.

Sequence in context: A321566 A066739 A066815 * A360621 A097097 A283474

Adjacent sequences: A106179 A106180 A106181 * A106183 A106184 A106185

Keyword

nonn,hard

Author

N. J. A. Sloane, Aug 23 2005

Extensions

Terms from a(6) onwards from David Applegate, Aug 29 2005

Terms a(0)-a(20) confirmed and a(21)-a(25) added by John W. Layman, Sep 20 2010

Status

approved