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,3

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.

Links

Table of n, a(n) for n=0..44.

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.

Example

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

Prog

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

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.

Sequence in context: A202357 A334378 A329406 * A019731 A363438 A021363

Adjacent sequences: A360438 A360439 A360440 * A360442 A360443 A360444

Keyword

nonn,tabl

Author

William P. Orrick, Mar 08 2023

Status

approved