A061279 -id:A061279 - cp's OEIS frontend

A065455 Number of (binary) bit strings of length n in which no even block of 0's is followed by an odd block of 1's.

1, 2, 4, 7, 14, 25, 49, 89, 172, 316, 605, 1120, 2131, 3965, 7513, 14026, 26504, 49591, 93538, 175277, 330205, 619369, 1165892, 2188312, 4117045, 7730828, 14539447, 27309529, 51349169, 96468034, 181357036, 340753271, 640539142, 1203616849

Offset: 0

Len Smiley, Nov 24 2001

The limit of the ratio of successive terms as n increases can be shown to be 2*cos(Pi/9). In the opposite direction, as n -> -oo (see A052545), a(n+1)/a(n) approaches 2*cos(5*Pi/9). For example, a(-6)/a(-7) = -92/265, which is close to 2*cos(5*Pi/9). - Richard Locke Peterson, Apr 22 2019

Let P(n, j, m) = Sum_{r=1..m} (2^n*(1-(-1)^r)*cos(Pi*r/(m+1))^n*cot(Pi*r/(2*(m+1)))* sin(j*Pi*r/(m+1)))/(m+1) denote the number of paths of length n starting at the j-th node on the path graph P_m. We have a(n) = P(n, 3, 8). - Herbert Kociemba, Sep 17 2020

			a(5) = 32-7 = 25 because 00111, 00101, 00100, 10010, 01001, 11001, 00001 are forbidden.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,3,1).

Cf. A061279 (forbids odd block 0's-odd block 1's), A065494, A065495, A065497.

Cf. A052545 (this is what we get if n takes negative values).

a:=[1,2,4];; for n in [4..40] do a[n]:=3*a[n-2]+a[n-3]; od; a; # G. C. Greubel, May 31 2019

I:=[1,2,4]; [n le 3 select I[n] else 3*Self(n-2) +Self(n-3): n in [1..40]]; // G. C. Greubel, May 31 2019

LinearRecurrence[{0,3,1}, {1,2,4}, 40] (* G. C. Greubel, May 31 2019 *)
a[n_,j_,m_]:=Sum[(2^(n+1)Cos[Pi r/(m+1)]^n Cot[Pi r/(2(m+1))] Sin[j Pi r/(m+1)])/(m+1),{r,1,m,2}]
Table[a[n,3,8],{n,0,40}]//Round (* Herbert Kociemba, Sep 17 2020 *)
CoefficientList[Series[(1+x)^2/(1-3x^2-x^3),{x,0,50}],x] (* Harvey P. Dale, Jul 16 2021 *)

a(n)=([0,1,0;0,0,1;1,3,0]^n*[1;2;4])[1,1] \\ Charles R Greathouse IV, Jun 11 2015

((1+x)^2/(1-3*x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 31 2019

G.f.: (1+x)^2/(1-3*x^2-x^3).

A320500 Symmetric array read by antidiagonals: T(m,n) = number of "minimal connected vertex covers" of an m X n grid, for m>=1, n>=1.

Original entry on oeis.org

1, 2, 2, 1, 4, 1, 1, 6, 6, 1, 1, 12, 11, 12, 1, 1, 20, 30, 30, 20, 1, 1, 36, 75, 110, 75, 36, 1, 1, 64, 173, 382, 382, 173, 64, 1, 1, 112, 434, 1270, 1804, 1270, 434, 112, 1, 1, 200, 1054, 4298, 7888, 7888, 4298, 1054, 200, 1

Offset: 1

N. J. A. Sloane, Oct 22 2018, based on email from Don Knuth, Oct 20 2018

Take the m X n grid graph with m*n vertices, each connected to four neighbors [except only two at the corners, otherwise three on the edges]. We ask for a vertex cover that is connected. It should also be minimal: if we leave out any element and it is no longer a connected vertex cover.

			The array begins:
1,   2,    1,     1,      1,        1,         1,          1,           1, ...
2,   4,    6,    12,     20,       36,        64,        112,         200, ...
1,   6,   11,    30,     75,      173,       434,       1054,        2558, ...
1,  12,   30,   110,    382,     1270,      4298,      14560,       49204, ...
1,  20,   75,   382,   1804,     7888,     36627,     166217,      755680, ...
1,  36,  173,  1270,   7888,    46416,    287685,    1751154,    10656814, ...
1,  64,  434,  4298,  36627,   287685,   2393422,   19366411,   157557218, ...
1, 112, 1054, 14560, 166217,  1751154,  19366411,  208975042,  2255742067, ...
1, 200, 2558, 49204, 755680, 10656814, 157557218, 2255742067, 32411910059, ...
...
The T(3,3) = 11 minimal connected vertex covers of a 3 X 3 grid are:
X.X  .X.  X..  X.X  X..  X..  ..X  ...  ...  .X.  ...
...  ...  ..X  ...  ..X  .X.  .X.  .X.  .X.  ...  X.X
X.X  X.X  X..  .X.  X..  ...  ...  X..  ..X  .X.  ...

M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM J. Applied Math., 32 (1977), 826-834. [They call these "connected node covers".]

Row 2 appears to be (essentially) A107383 (or twice A061279).
The main diagonal is A320501.
Rows 3,4,5 are A320482, A320483, A320484.

A065494 Number of (binary) bit strings in which no even length block of 0's is followed by an even length block of 1's.

Original entry on oeis.org

1, 2, 4, 8, 15, 30, 57, 112, 216, 420, 815, 1580, 3069, 5950, 11552, 22408, 43487, 84378, 163725, 317700, 616444, 1196172, 2321007, 4503704, 8738921, 16956954, 32903164, 63845000, 123884479, 240384374, 466440273, 905077080, 1756205088

Offset: 0

Len Smiley, Nov 24 2001

			a(6)=64-7=57 because 000011, 001111, 001100, 001101, 100110, 010011, 110011 are forbidden.

Index entries for linear recurrences with constant coefficients, signature (0,3,2,-1).

Cf. A061279 (forbids odd block 0's - odd block 1's), A065455, A065495, A065497.

O.g.f.: (1+x)^2/(1-3x^2-2x^3+x^4)

A065495 Number of (binary) bit strings of length n in which an odd length block of 0's is followed by an odd length block of 1's.

Original entry on oeis.org

1, 2, 6, 14, 32, 72, 156, 336, 712, 1496, 3120, 6464, 13328, 27360, 55968, 114144, 232192, 471296, 954816, 1931264, 3900800, 7869312, 15858432, 31928832, 64232704, 129128960, 259431936, 520941056, 1045557248, 2097616896

Offset: 2

Len Smiley, Nov 24 2001

			a(4) = 6 because of 0100, 0101, 1010, 1101, 0111, 0001.

Index entries for linear recurrences with constant coefficients, signature (2,2,-2,-4).

Cf. A061279 [=2^n - a(n)], A065455, A065494, A065497.

G.f.: x^2/((1-2*x)*(1-2*x^2-2*x^3)).

A107383 a(n) = 2a(n-2) + 2a(n-3).

Original entry on oeis.org

0, 1, 1, 2, 4, 6, 12, 20, 36, 64, 112, 200, 352, 624, 1104, 1952, 3456, 6112, 10816, 19136, 33856, 59904, 105984, 187520, 331776, 587008, 1038592, 1837568, 3251200, 5752320, 10177536, 18007040, 31859712, 56369152, 99733504, 176457728

Offset: 0

Roger L. Bagula, May 24 2005

Also the number of maximal independent vertex sets (and minimal vertex covers) in the 2 X (n-2) king graph. - Eric W. Weisstein, Aug 07 2017

Michael De Vlieger, Table of n, a(n) for n = 0..4037
Igor Pak, Boris Shapiro, Ilya Smirnov, and Ken-ichi Yoshida, Hilbert-Kunz multiplicity of quadrics via the Ehrhart theory, Stockholm Univ. (Sweden, 2025). See p. 4.
Noriaki Sannomiya, Hosho Katsura, and Yu Nakayama, Supersymmetry breaking and Nambu-Goldstone fermions with cubic dispersion, arXiv:1612.02285 [cond-mat.str-el], 2016. See Table II, line 1.
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover
Index entries for linear recurrences with constant coefficients, signature (0,2,2).

Cf. A061279, A078025.

m = 2; a[0] = 0; a[1] = 1; a[2] = 1; a[3] = 2; a[n_] := a[n] = a[n - 1] + m*a[n - 2] - m*a[n - 4]; Table[a[n], {n, 0, 50}] (* edited and corrected by Harvey P. Dale, May 07 2014 *)
LinearRecurrence[{0, 2, 2}, {0, 1, 1}, 40] (* Harvey P. Dale, May 07 2014 *)
Table[RootSum[-2 - 2 # + #^3 &, 5 #^n + 8 #^(n + 1) + #^(n + 2) &]/19, {n, 20}] (* Eric W. Weisstein, Aug 07 2017 *)
CoefficientList[Series[-((2 (1 + 2 x + x^2))/(-1 + 2 x^2 + 2 x^3)), {x, 0, 20}], x] (* Eric W. Weisstein, Aug 07 2017 *)

G.f.: x*(1+x)/(1-2*x^2-2*x^3).
a(n) = (-1)^(n+1)*A078025(n-1).
Limit_{n->oo} a(n)/a(n-1) = 1.7692923... .
a(n)+a(n+1) = A061279(n). - R. J. Mathar, Dec 01 2011

Definition replaced by recurrence by the Associate Editors of the OEIS, Sep 28 2009

A247595 a(n) = 4a(n-1) - 4a(n-2) + 4*a(n-3) with a(0) = 1, a(1) = 3, a(2) = 10.

Original entry on oeis.org

1, 3, 10, 32, 100, 312, 976, 3056, 9568, 29952, 93760, 293504, 918784, 2876160, 9003520, 28184576, 88228864, 276191232, 864587776, 2706501632, 8472420352, 26522025984, 83024429056, 259899293696, 813587562496, 2546850791424, 7972650090496, 24957547446272

Offset: 0

Michael Somos, Sep 20 2014

nonn

			G.f. = 1 + 3*x + 10*x^2 + 32*x^3 + 100*x^4 + 312*x^5 + 976*x^6 + 3056*x^7 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-4,4).

Cf. A061279, A247594.

a247595 n = a247595_list !! n
a247595_list = 1 : 3 : 10 : map (* 4) (zipWith3 (((+) .) . (-))
   (drop 2 a247595_list) (tail a247595_list) a247595_list)
-- Reinhard Zumkeller, Sep 21 2014

m:=60; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1 - x +2*x^2)/(1-4*x+4*x^2-4*x^3)));  // G. C. Greubel, Aug 04 2018

CoefficientList[Series[(1-x+2*x^2)/(1-4*x+4*x^2-4*x^3), {x, 0, 60}], x] (* G. C. Greubel, Aug 04 2018 *)

{a(n) = if( n<0, polcoeff( (2*x - x^2 + x^3) / (4 - 4*x + 4*x^2 - x^3) + x * O(x^-n), -n), polcoeff( (1 - x + 2*x^2) / (1 - 4*x + 4*x^2 - 4*x^3) + x * O(x^n), n))};

G.f.: (1 - x + 2*x^2) / (1 - 4*x + 4*x^2 - 4*x^3).
0 = a(n) - 4*a(n-1) + 4*a(n-2) - 4*a(n-3) for all n in Z.
a(n) = A061279(2*n) for all n in Z.
Binomial transform of A247594.

cp's OEIS Frontend

A065455 Number of (binary) bit strings of length n in which no even block of 0's is followed by an odd block of 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A320500 Symmetric array read by antidiagonals: T(m,n) = number of "minimal connected vertex covers" of an m X n grid, for m>=1, n>=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A065494 Number of (binary) bit strings in which no even length block of 0's is followed by an even length block of 1's.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A065495 Number of (binary) bit strings of length n in which an odd length block of 0's is followed by an odd length block of 1's.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A107383 a(n) = 2*a(n-2) + 2*a(n-3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A247595 a(n) = 4*a(n-1) - 4*a(n-2) + 4*a(n-3) with a(0) = 1, a(1) = 3, a(2) = 10.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Formula

A107383 a(n) = 2a(n-2) + 2a(n-3).

A247595 a(n) = 4a(n-1) - 4a(n-2) + 4*a(n-3) with a(0) = 1, a(1) = 3, a(2) = 10.