A019309 Number of "bifix-free" words of length n over a four-letter alphabet.

1, 4, 12, 48, 180, 720, 2832, 11328, 45132, 180528, 721392, 2885568, 11539440, 46157760, 184619712, 738478848, 2953870260, 11815481040, 47261743632, 189046974528, 756187176720, 3024748706880, 12098991941952

Offset

0,2

Links

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

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.

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.

Formula

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

Mathematica

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

Crossrefs

Cf. A003000, A019308, A094547, A094559, A094578.

Sequence in context: A149383 A149384 A108508 * A056632 A149385 A092898

Adjacent sequences: A019306 A019307 A019308 * A019310 A019311 A019312

Keyword

nonn,easy

Author

Jeffrey Shallit

Status

approved