A019308 Number of "bifix-free" words of length n over a three-letter alphabet.

1, 3, 6, 18, 48, 144, 414, 1242, 3678, 11034, 32958, 98874, 296208, 888624, 2664630, 7993890, 23977992, 71933976, 215790894, 647372682, 1942085088, 5826255264, 17478666918, 52436000754, 157307706054, 471923118162

Offset

0,2

Links

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

E. Barcucci, A. Bernini, S. Bilotta, R. Pinzani, Cross-bifix-free sets in two dimensions, arXiv preprint arXiv:1502.05275 [cs.DM], 2015.

S. Bilotta, E. Pergola and R. Pinzani, A new approach to cross-bifix-free sets, arXiv preprint arXiv:1112.3168 [cs.FL], 2011.

Joshua Cooper and Danny Rorabaugh, Asymptotic Density of Zimin Words, arXiv preprint arXiv:1510.03917

T. Harju and D. Nowotka, Border correlation of binary words.

P. Tolstrup Nielsen, A note on bifix-free sequences, IEEE Trans. Info. Theory IT-19 (1973), 704-706.

D Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, arXiv preprint arXiv:1509.04372, 2015

Formula

a(2n+1) = 3a(2n); a(2n) = 3a(2n-1) - a(n).

Mathematica

a[0]=1; a[n_]:=a[n]=3*a[n-1]-If[EvenQ[n], a[n/2], 0] (* Ed Pegg Jr, Jan 05 2005 *)

Crossrefs

Equals 3*A045694(n) for n>0. Cf. A003000, A019309.

Sequence in context: A108507 A287212 A083337 * A000932 A187124 A369530

Adjacent sequences: A019305 A019306 A019307 * A019309 A019310 A019311

Keyword

nonn

Author

Jeffrey Shallit

Status

approved