|
| |
|
|
A316660
|
|
Number of n-bit binary necklaces (unmarked cyclic n-bit binary strings) containing no runs of length > 2.
|
|
1
|
|
|
|
0, 1, 2, 2, 2, 5, 4, 7, 10, 14, 18, 31, 40, 63, 94, 142, 210, 329, 492, 765, 1170, 1810, 2786, 4341, 6712, 10461, 16274, 25414, 39650, 62075, 97108, 152287, 238838, 375166, 589526, 927555, 1459960, 2300347, 3626242, 5721044, 9030450, 14264309, 22542396, 35646311, 56393862
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
This is the "unmarked" version of sequence A007040. An unmarked cyclic string is a necklace. Notice that we define a(1) = 0 and a(2) = 1 because wrapping around the circle is allowed here (otherwise we would have to let a(1) = 2 and a(2) = 3).
Let q and m be positive integers. We denote by f1(m,q,n) the number of marked cyclic q-ary strings of length n that contain no runs of lengths > m when no wrapping around is allowed, and by f2(m,q,n) when wrapping around is allowed.
It is clear that f1(m,q,n) = f2(m,q,n) for n > m, but f1(m,q,n) = q^n and f2(m,q,n) = q^n - q when 1 <= n <= m.
Burstein and Wilf (1997) and Edlin and Zeilberger (2000) considered f1(m,q,n) while Hadjicostas and Zhang considered f2(m,q,n).
Let g(m, q, x) = (m+1-m*q*x)/(1-q*x+(q-1)*x^(m+1)) - (m+1)/(1-x^(m+1)).
By generalizing Moser (1993), Burstein and Wilf (1997) proved that the g.f. of the numbers f1(m,q,n) is F1(m,q,x) = ((1-x^m)/(1-x))*(q*x + (q-1)*x* g(m, q, x)).
Using the above formula by Burstein and Wilf (1997), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f2(m,q,n) is F2(m,q,x) = ((q-1)*x*(1-x^m)/(1-x))*g(m, q, x).
If f3(m,q,n) is the number of q-ary necklaces (= unmarked cyclic strings) of length n with no runs of length > m (and wrapping around is allowed), then f3(m,q,n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m,q,d), where phi(.) is Euler's totient function. Using this formula and F2(m,q,x), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f3(m,q,n) is given by F3(m,q,x) = -(q-1)*x*(1-x^m)/((1-x)*(1-x^(m+1))) - Sum_{s>=1} (phi(s)/s)*log(1 - (q-1)*(x^s - x^(s*(m+1)))/(1-x^s)).
If A(x) is the g.f. of the current sequence (a(n): n >= 1), we have A(x) = F3(m=2, q=2, x). Also, a(n) = f3(m=2, q=2, n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m=2, q=2, d). Note that f2(m=2, q=2, n=1) = 0 and f2(m=2, q=2, n) = A007040(n) for n >= 2.
|
|
|
LINKS
|
|
|
|
FORMULA
|
For proofs of the following formulae, see the comments above.
a(n) = (1/n)*Sum_{d|n} phi(n/d)*A007040(d)*I(d > 1), where I(condition) = 1 if the condition holds, and 0 otherwise.
a(n) = A000358(n) - A011655(n). (This formula is the "unmarked" version of E. W. Weisstein's formula that can be found in the comments for sequence A007040.)
a(p) = A007040(p)/p for p prime >= 2.
G.f.: A(x) = -x*(1+x)/(1-x^3) - Sum_{s>=1} (phi(s)/s)*log(1 - x^s - x^(2*s)) = (g.f. of A000358) - (g.f. of A011655).
|
|
|
EXAMPLE
|
For n=1 we have no allowable necklaces (because the strings 0 and 1 can be wrapped around themselves on a circle, and thus they contain runs of length > 2).
For n=2, the only allowable necklace is 01 (because 00 and 11 can be wrapped around themselves on a circle, and thus they contain runs of length > 2).
For n=3, the allowable necklaces are 011 and 100.
For n=4, the allowable necklaces are 0011 and 1010.
For n=5, the allowable necklaces are 01010 and 10101.
For n=6, the allowable necklaces are 010101, 001001, 110110, 101001, and 010110.
|
|
|
PROG
|
(PARI) a(n) = (1/n) * sumdiv(n, d, eulerphi(n/d)*(fibonacci(d-1)+fibonacci(d+1))) - sign(n%3); \\ Michel Marcus, Jul 10 2018; using 2nd formula
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
