|
|
A019310
|
|
Number of words of length n (n >= 1) over a two-letter alphabet having a minimal period of size n-1.
|
|
3
|
|
|
0, 2, 2, 6, 10, 22, 38, 82, 154, 318, 614, 1250, 2462, 4962, 9842, 19766, 39378, 78910, 157502, 315322, 630030, 1260674, 2520098, 5041446, 10080430, 20163322, 40321682, 80648326, 161286810, 322583462, 645147158, 1290314082, 2580588786, 5161216950
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2*a(n-1) + (-1)^n * a(ceiling(n/2)) for n >= 3.
a(n) = a(n-1) + 2*a(n-2) if n >= 4 even. a(n) = a(n-1) + 2*a(n-2) + 2*a((n-1)/2) if n>=7 == 3 (mod 4). - Michael Somos, Jan 23 2014
|
|
EXAMPLE
|
G.f. = 2*x^2 + 2*x^3 + 6*x^4 + 10*x^5 + 22*x^6 + 38*x^7 + 82*x^8 + ...
a(4) = 6 because we have: {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 1, 1}, {1, 1, 0, 1}. These are precisely the binary words of length 4 with autocorrelation polynomial equal to 1 + z^3. - Geoffrey Critzer, Apr 13 2022
|
|
MAPLE
|
f:= proc(n) option remember;
2*procname(n-1)+(-1)^n*procname(ceil(n/2))
end proc:
f(1):= 0: f(2):= 2:
|
|
PROG
|
(PARI) a(n) = if (n==1, 0, if (n==2, 2, 2*a(n-1) + (-1)^n*a(ceil(n/2)))) \\ Michel Marcus, May 25 2013
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|