|
| |
|
|
A007040
|
|
Number of (marked) cyclic n-bit binary strings containing no runs of length > 2.
(Formerly M0354)
|
|
8
|
|
|
|
2, 2, 6, 6, 10, 20, 28, 46, 78, 122, 198, 324, 520, 842, 1366, 2206, 3570, 5780, 9348, 15126, 24478, 39602, 64078, 103684, 167760, 271442, 439206, 710646, 1149850, 1860500, 3010348, 4870846, 7881198, 12752042, 20633238, 33385284, 54018520
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
For n >= 3, also the number of maximal independent vertex sets (and minimal vertex covers) in the n-prism graph. - Eric W. Weisstein, Mar 30 and Aug 07 2017
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 (1991, 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).
A necklace is an unmarked cyclic string. If f3(m,q,n) is the number of q-ary necklaces 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)).
For the current sequence, we have q = 2 and m = 2. We have a(n) = f1(m=2, q=2, n) = f2(m=2, q=2, n) for n >= 3, but for a(1) and a(2) it is unclear what approach the author of the sequence is following. He has a(1) = q^1 = 2, but a(2) = q^2 - q = 2^2 - 2 = 2. (Note that, for q = m = 2, we have f1(m=2, q=2, 1) = 2, f1(m=2, q=2, 2) = 4, f2(m=2, q=2, 1) = 0, and f2(m=2, q=2, 2) = 2.)
If A(x) is the g.f. of the current sequence, we have A(x) = F1(m=2,q=2, x) - 2*x^2 = F2(m=2, q=2, x) + 2*x.
When m = 1 and q = 3, we have f1(m=1, q=3, n) = number of marked cyclic words on three letters with no two consecutive like letters. We have f1(m=1, q=3, n) = A092297(n) for n >= 2. This was first stated in the comments of that sequence by G. Critzer.
When m = 1 and q = 4, we have f1(m=1, q=4, n) = number of marked cyclic words on four letters with no two consecutive like letters. We have f1(m=1, q=4, n) = A218034(n) for n >= 1. This was first stated in the comments of that sequence by J. Arndt.
A generalization of the above formula by Burstein and Wilf (1997) was given by Taylor (2014) in Section 5 of his paper. (End)
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
W. O. J. Moser, On cyclic binary n-bit strings, Report from the Department of Mathematics and Statistics, McGill University, 1991. (Annotated scanned copy)
|
|
|
FORMULA
|
a(n) = n*Sum_{k=1..n} binomial(2*k, n-2*k)/k for n > 1 with a(0) = 0 and a(1) = 2. - Vladimir Kruchinin, Oct 12 2011
G.f.: 2*x*(1 + x + 2*x^2 - x^4)/((1 - x - x^2)*(1 + x + x^2)). - Colin Barker, Mar 15 2012
|
|
|
MATHEMATICA
|
Join[{2}, LinearRecurrence[{0, 1, 2, 1}, {2, 6, 6, 10}, 40]] (* Harvey P. Dale, Nov 09 2011 *)
Join[{2}, Table[n Sum[Binomial[2 k, n - 2 k]/k, {k, n}], {n, 2, 40}]] (* Harvey P. Dale, Nov 09 2011 *)
|
|
|
PROG
|
(PARI) a(n)=if(n<3, 2, ([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; 1, 2, 1, 0]^(n-2)*[2; 6; 6; 10])[1, 1]) \\ Charles R Greathouse IV, Jun 15 2015
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
