A066345 Winning binary "same game" templates of length n as defined below.

1, 1, 4, 7, 20, 39, 96, 191, 432, 863, 1856, 3711, 7744, 15487, 31744, 63487, 128768, 257535, 519168, 1038335, 2085888, 4171775, 8364032, 16728063, 33501184, 67002367, 134103040, 268206079, 536625152, 1073250303, 2146959360

Offset: 1

Author

Frank Ellermann, Dec 23 2001

Keywords

• nonn
• easy

Comments

A "same game template" is a pattern representing the run pattern of a string in a 2 symbol alphabet. Each position in the template represents either an isolated symbol, or a run of two or more identical symbols. Such a template can be represented as a ternary number without digit 0 (A007931), where 2 represents any run of 2 or more identical symbols and ternary 1 represents remaining single bitsymbols, e.g. 211 for 0010, 1101, 00010, etc. A winning template represents an infinite subset of winning binary "same games", e.g. 121 for 0110, 1001, 01110, etc.

Examples

			There are a(3)= 4 winning templates 121, 122, 221, 222 with 3 ternary digits and a(4)= 7 winning templates 1212, 2121, 1222, 2221, 2122, 2212, 2222.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (2,5,-10,-8,16,4,-8).

Crossrefs

a(2*n-1)= A008353(n-1), cf. A035615, A007931, A066067.

Formula

a(2*n-1)= 2^(2*n-1) -n * 2^(n-1), a(2*n)= 2*a(2*n-1) -1.

G.f. x*( 1-x-3*x^2+4*x^3+4*x^4-4*x^5 ) / ( (x-1)*(2*x-1)*(1+x)*(-1+2*x^2)^2 ). - R. J. Mathar, May 07 2013