|
%I #23 Apr 28 2017 12:01:19
%S 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,
%T 120,45,4,10,72,196,245,140,30,1,11,90,288,448,350,126,15,12,110,405,
%U 756,756,392,90,5,13,132,550,1200,1470,1008,357,50,1,14,156,726
%N 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.
%C 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).
%H Dennis Walsh, <a href="http://frank.mtsu.edu/~dwalsh/ONEMAX2.pdf">Notes on binary sequences with a maximum run length of two</a>
%F 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.
%e 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.
%e Triangle T(n,k) begins
%e 1,
%e 2,
%e 3, 2,
%e 4, 6, 1,
%e 5, 12, 6,
%e 6, 20, 18, 3,
%e 7, 30, 40, 16, 1,
%e 8, 42, 75, 50, 10,
%e 9, 56, 126, 120, 45, 4,
%e 10, 72, 196, 245, 140, 30, 1,
%e 11, 90, 288, 448, 350, 126, 15,
%e 12, 110, 405, 756, 756, 392, 90, 5,
%e 13, 132, 550, 1200, 1470, 1008, 357, 50, 1,
%e 14, 156, 726, 1815, 2640, 2268, 1106, 266, 21,
%e 15, 182, 936, 2640, 4455, 4620, 2898, 1016, 161, 6,
%p 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);
%t 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 *)
%Y Row sums of triangle T(n,k)=A000100(n+1);
%Y T(n,3)=A002378(n-3); T(n,4)=A002411(n-4);
%Y T(n,5)=A004320(n-6).
%K nonn,nice,easy,tabf
%O 2,2
%A _Dennis P. Walsh_, Apr 23 2012
|
