login
Triangle read by rows: T(n,k) is the number of pairs (c,m), where c is a covering of the 1 X (2n) grid with 1 X 2 rectangles and equal numbers of red and blue 1 X 1 squares and m is a matching between red squares and blue squares, such that exactly k matched pairs are adjacent.
0

%I #8 Mar 31 2023 14:42:27

%S 1,1,2,7,8,4,71,78,36,8,1001,1072,504,128,16,18089,19090,9080,2480,

%T 400,32,398959,417048,199980,56960,10320,1152,64,10391023,10789982,

%U 5204556,1523480,295120,38304,3136,128,312129649,322520672,156264304,46629632,9436000,1336832,130816,8192,256

%N Triangle read by rows: T(n,k) is the number of pairs (c,m), where c is a covering of the 1 X (2n) grid with 1 X 2 rectangles and equal numbers of red and blue 1 X 1 squares and m is a matching between red squares and blue squares, such that exactly k matched pairs are adjacent.

%C If row elements are divided by row sums, one obtains a probability distribution that approaches a Poisson distribution with expected value 1 as n approaches infinity.

%F T(n,k) equals 2^k times the corresponding element of the triangle of A168422.

%F T(n,k) = 2^k * Sum_{j=k..n} (-1)^(j-k) * C(2*n-j,n) * C(n,j) * C(j,k) * (n-j)!.

%F Recurrence: T(n,k) = (1/k!) * Sum_{j=0..k} T(n-j,0) * (-1)^j * C(k,j) * Sum_{t=0..min(j,k-j)} (-1)^(j-t) * C(j,t) * (k-j)! / (k-j-t)!

%F = (1/k!) * Sum_{j=0..k} T(n-j,0) * (-1)^j * C(k,j) * R(k,j) where R(k,j) is an element of the triangle of A253667.

%e Triangle begins:

%e 1

%e 1 2

%e 7 8 4

%e 71 78 36 8

%e 1001 1072 504 128 16

%e 18089 19090 9080 2480 400 32

%e 398959 417048 199980 56960 10320 1152 64

%e 10391023 10789982 5204556 1523480 295120 38304 3136 128

%o (SageMath)

%o def T(n,k):

%o return(2^k*sum((-1)^(j-k)*binomial(2*n-j,n)*binomial(n,j)\

%o *binomial(j,k)*factorial(n-j) for j in range(k,n+1)))

%Y Column 1 is |A002119|.

%Y T(n,k) equals 2^k times the corresponding element of the triangle of A168422.

%Y Sum of row n is A001517(n).

%Y Cf. A253667.

%K nonn,tabl

%O 0,3

%A _William P. Orrick_, Mar 08 2023