

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 ZivLempel encodings (the phrases can appear in a different order in the two sequences).


5



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

The ZivLempel 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 IT23 (1977), 337343.


LINKS

Table of n, a(n) for n=0..25.
G. Seroussi, On universal types, Preprint, 2004.
G. Seroussi, On the number of tary trees with a given path length, Algorithmica 46(3), 557565, 2006.


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 ZivLempel 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 program from David Applegate) 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


CROSSREFS

Row sums of A109338. Cf. A109337.
Cf. A095830.
Sequence in context: A321566 A066739 A066815 * A097097 A283474 A206370
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



