login
Triangle T(n,k): the number of binary sequences of n zeros and n ones in which the longest run is of length k.
3

%I #13 Oct 05 2013 05:43:56

%S 2,2,4,2,12,6,2,32,28,8,2,82,110,48,10,2,206,408,224,72,12,2,516,1454,

%T 968,378,100,14,2,1294,5048,4016,1784,578,132,16,2,3252,17244,16202,

%U 7980,2924,830,168,18,2,8194,58290,64058,34570,13810,4464,1140,208,20

%N Triangle T(n,k): the number of binary sequences of n zeros and n ones in which the longest run is of length k.

%C Row n sums to C(2n,n) (A000984).

%H Andrew Woods, <a href="/A229756/b229756.txt">Rows n = 1..50 of triangle, flattened</a>

%F Let h(n,p,k) := sum(j=0..floor((n-p)/k), (-1)^j*C(p,j)*C(n-1-j*k,p-1)) with h(n,p,0) := 0, and let g(n,k) := 2*sum(i=1..n, h(n,i,k)*(h(n,i,k)+h(n,i+1,k))). Then T(n,k) = g(n,k)-g(n,k-1).

%e The triangle begins:

%e 2

%e 2 4

%e 2 12 6

%e 2 32 28 8

%e 2 82 110 48 10

%e The second row counts the sets {0101, 1010} and {0011, 0110, 1001, 1100}.

%o (PARI)

%o h(n,p,k)=if(k==0,0,sum(j=0,floor((n-p)/k),(-1)^j*binomial(p,j)*binomial(n-1-j*k,p-1)))

%o g(n,k)=2*sum(i=1,n,h(n,i,k)*(h(n,i,k)+h(n,i+1,k)))

%o T(n,k)=g(n,k)-g(n,k-1)

%o r(n)=vector(n,x,2*T(n,x))

%K nonn,tabl

%O 1,1

%A _Andrew Woods_, Sep 28 2013