A167826 a(n) is the number of n-tosses having a run of 3 or more heads and a run of 3 or more tails for a fair coin.

0, 0, 0, 0, 0, 2, 8, 26, 74, 194, 482, 1152, 2674, 6068, 13524, 29704, 64460, 138482, 294988, 623834, 1311086, 2740666, 5702270, 11815752, 24395678, 50209572, 103048168, 210965064, 430938832, 878534170

Offset: 1

Author

V.J. Pohjola, Nov 13 2009

Keywords

• nonn
• easy

Links

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

Crossrefs

Cf. A000045, A000073.

Cf. A008466, A050231, A167821.

Programs

Mathematica

b[1] = 0; b[2] = 1; b[3] = 1; b[n_]: = b[n-1] + b[n-2] + b[n-3]; Table[2^n - 2*(Sum[b[n + 3 - i], {i, 1, 3}] - Fibonacci[n + 1]), {n, 1, 30}]
LinearRecurrence[{4, -3, -3, 0, 3, 2}, {0, 0, 0, 0, 0, 2}, 50] (* G. C. Greubel, Jun 27 2016 *)

Formula

a(n) = 2^n - 2*(tribonacci(n+3) - Fibonacci(n+1)), where tribonacci = A000073.

From R. J. Mathar, Feb 06 2010: (Start)

a(n) = 4*a(n-1) - 3*a(n-2) - 3*a(n-3) + 3*a(n-5) + 2*a(n-6).

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