A376884 Number of binary n-sequences ending in 1 with exactly one more occurrence of 11 than 10.

0, 0, 1, 1, 1, 4, 7, 10, 23, 46, 79, 157, 315, 588, 1137, 2249, 4337, 8402, 16495, 32179, 62707, 122916, 240837, 471456, 925061, 1816610, 3566865, 7010347, 13789477, 27130956, 53409503, 105205514, 207309743, 408672454, 805989367, 1590166915, 3138371715

Offset: 0

Author

Bruce Levin, Oct 07 2024

Keywords

• nonn

Comments

It is easy to prove that this sequence is exactly one-half of sequence A360309. The connection to the number of binary n-sequences ending in 1 with exactly one more occurrence of 11 pairs than 10 pairs appears new and is related to a coin-tossing problem posed by Daniel Litt. In particular, the cumulative sum a(0)+...+a(n-1) gives the number of all binary sequences of length n with strictly more 10 pairs than 11 pairs minus the number of all binary sequences of length n with strictly more 11 pairs than 10 pairs. These results are demonstrated in the Levin link below, where more formulas are given for the number of binary n-sequences ending in 1 (or 0) with exactly s more occurrences of 11 pairs than 10 pairs for any integer s.

Examples

			There are a(5)=4 binary 5-sequences ending in 1 with one more occurrence of 11 than 10. They are 11101, 11011, and 10111 (each with two occurrences of 11 and one occurrence of 10); and 00011 (with one occurrence of 11 and zero occurrences of 10).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..3330
• Bruce Levin, Note on a coin-tossing problem posed by Daniel Litt, arXiv:2409.13087 [math.CO], 2024.

Crossrefs

One-half of A360309(n+1).

Cf. A217615.

Programs

Maple

a:= proc(n) option remember; `if`(n<4, iquo(n, 2), (2*n*a(n-1)
      -(n-1)*a(n-2)+(4*n-2)*a(n-3)-4*(n-2)*a(n-4))/(n+1))
    end:
seq(a(n), n=0..36);  # Alois P. Heinz, Oct 08 2024

Mathematica

a[n_] := Sum[Binomial[n - 2 k, n + 1 - 3 k]*Binomial[2 k, k]/2, {k, 0, Floor[(n + 1)/3]}];
Table[a[n], {n, 0, 36}] (* Robert P. P. McKone, Dec 28 2024 *)

Formula

a(n) = Sum_{k=1..floor((n+1)/3)} binomial((2*k)-1,k) * binomial(n-2*k,k-1).

a(n) = A360309(n+1)/2.