login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 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 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.

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: 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 9 22:46 EDT 2020. Contains 335570 sequences. (Running on oeis4.)