login
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.
0
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,2
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).
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.
EXAMPLE
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,
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 *)
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).
Sequence in context: A325349 A320054 A215228 * A043263 A321326 A118978
KEYWORD
nonn,nice,easy,tabf
AUTHOR
Dennis P. Walsh, Apr 23 2012
STATUS
approved