A094578 -id:A094578 - cp's OEIS frontend

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

Jeffrey Shallit

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.

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

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

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

A094559 Number of words of length n over an alphabet of size 4 that are not "bifix-free".

Original entry on oeis.org

0, 0, 4, 16, 76, 304, 1264, 5056, 20404, 81616, 327184, 1308736, 5237776, 20951104, 83815744, 335262976, 1341097036, 5364388144, 21457733104, 85830932416, 343324451056, 1373297804224, 5493194102464, 21972776409856, 87891117178864

Offset: 0

N. J. A. Sloane, Jun 06 2004

See A019308, A019309 and A003000 for much more information. Cf. A094578.

a:=proc(n) if n=0 or n=1 then 0 elif n mod 2 = 0 then 4*a(n-1)-a(n/2)+4^(n/2) else 4*a(n-1) fi end: seq(a(n),n=0..28); # Emeric Deutsch, Feb 04 2006

Equals 4^n - A019309(n).

a(0)=a(1)=0, a(2n)=4^n + 4a(2n-1) - a(n), a(2n+1)=4a(2n). - Emeric Deutsch, Feb 04 2006

More terms from Emeric Deutsch, Feb 04 2006

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula