|
| |
|
|
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).
|
|
4
| |
|
|
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; internal format)
|
|
|
|
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
| 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.
|
|
|
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 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: A167934 A066739 A066815 * A097097 A206370 A095162
Adjacent sequences: A106179 A106180 A106181 * A106183 A106184 A106185
|
|
|
KEYWORD
| nonn,hard
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Aug 23 2005
|
|
|
EXTENSIONS
| Terms from a(6) onwards from David Applegate (david(AT)research.att.com), Aug 29 2005
Terms a(0)-a(20) confirmed and a(21)-a(25) added by John W. Layman (layman(AT)math.vt.edu), Sep 20 2010
|
| |
|
|
