A182309 Triangle T(n,k) with 2 <= k <= floor(2(n+1)/3) gives the number of length-n binary sequences with exactly k zeros and with length two for the longest run of zeros.

1, 2, 3, 2, 4, 6, 1, 5, 12, 6, 6, 20, 18, 3, 7, 30, 40, 16, 1, 8, 42, 75, 50, 10, 9, 56, 126, 120, 45, 4, 10, 72, 196, 245, 140, 30, 1, 11, 90, 288, 448, 350, 126, 15, 12, 110, 405, 756, 756, 392, 90, 5, 13, 132, 550, 1200, 1470, 1008, 357, 50, 1, 14, 156, 726

Offset: 2

Author

Dennis P. Walsh, Apr 23 2012

Keywords

• nonn
• nice
• easy
• tabf

Comments

Triangle T(n,k) captures several well known sequences. In particular, T(n,2)=(n-1), the natural numbers; T(n,3)=(n-2)(n-3)=A002378(n-3), the "oblong" numbers; T(n,4)=(n-3)(n-4)^2/2=A002411(n-4), "pentagonal pyramidal" numbers; and also T(n,5)=(n-4)C(n-4,3)=A004320(n-6). Furthermore, row sums=A000100(n+1).

Examples

			For n=6 and k=3, T(6,3)=12 since there are 12 binary sequences of length 6 that contain 3 zeros and that have a maximum run of zeros of length 2, namely, 011100, 101100, 110100, 011001, 101001, 110010, 010011, 100110, 100101, 001110, 001101, and 001011.
Triangle T(n,k) begins
   1,
   2,
   3,   2,
   4,   6,   1,
   5,  12,   6,
   6,  20,  18,    3,
   7,  30,  40,   16,    1,
   8,  42,  75,   50,   10,
   9,  56, 126,  120,   45,    4,
  10,  72, 196,  245,  140,   30,    1,
  11,  90, 288,  448,  350,  126,   15,
  12, 110, 405,  756,  756,  392,   90,    5,
  13, 132, 550, 1200, 1470, 1008,  357,   50,   1,
  14, 156, 726, 1815, 2640, 2268, 1106,  266,  21,
  15, 182, 936, 2640, 4455, 4620, 2898, 1016, 161, 6,
		

Links

• Dennis Walsh, Notes on binary sequences with a maximum run length of two

Crossrefs

Row sums of triangle T(n,k)=A000100(n+1);

T(n,3)=A002378(n-3); T(n,4)=A002411(n-4);

T(n,5)=A004320(n-6).

Programs

Maple

seq(seq(sum(binomial(n-k+1,j)*binomial(n-k+1-j,k-2*j),j=1..floor(k/2)),k=2..floor(2*(n+1)/3)),n=2..20);

Mathematica

t[n_, k_] := Sum[ Binomial[n-k+1, j]*Binomial[n-k-j+1, k-2*j], {j, 1, k/2}]; Table[t[n, k], {n, 2, 15}, {k, 2, 2*(n+1)/3}] // Flatten (* Jean-François Alcover, Jun 06 2013 *)

Formula

T(n,k) = Sum_{j=1..k/2} binomial(n-k+1,j)*binomial(n-k-j+1,k-2j) for 2 <= k <= 2(n+1)/3.