A360441 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.

1, 1, 2, 7, 8, 4, 71, 78, 36, 8, 1001, 1072, 504, 128, 16, 18089, 19090, 9080, 2480, 400, 32, 398959, 417048, 199980, 56960, 10320, 1152, 64, 10391023, 10789982, 5204556, 1523480, 295120, 38304, 3136, 128, 312129649, 322520672, 156264304, 46629632, 9436000, 1336832, 130816, 8192, 256

Offset: 0

Author

William P. Orrick, Mar 08 2023

Keywords

• nonn
• tabl

Comments

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.

Examples

			Triangle begins:
         1
         1        2
         7        8       4
        71       78      36       8
      1001     1072     504     128     16
     18089    19090    9080    2480    400    32
    398959   417048  199980   56960  10320  1152   64
  10391023 10789982 5204556 1523480 295120 38304 3136 128
		

Crossrefs

Column 1 is |A002119|.

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

Sum of row n is A001517(n).

Cf. A253667.

Programs

SageMath

def T(n,k):
    return(2^k*sum((-1)^(j-k)*binomial(2*n-j,n)*binomial(n,j)\
     *binomial(j,k)*factorial(n-j) for j in range(k,n+1)))

Formula

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

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)!.

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)!

= (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.