A055005 Number of nonnegative integer 3 X 3 matrices with no zero rows or columns and with sum of elements equal to n.

1, 0, 0, 6, 63, 306, 1038, 2844, 6750, 14437, 28521, 52911, 93258, 157509, 256581, 405171, 622719, 934542, 1373158, 1979820, 2806281, 3916812, 5390496, 7323822, 9833604, 13060251, 17171415, 22366045, 28878876, 36985383, 47007231

Offset

0,4

Links

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

Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Formula

Number of nonnegative integer p X q matrices with no zero rows or columns and with sum of elements equal to n is Sum_{k=0...q} (-1)^k*C(q, k)*m(p, q-k, n) where m(p, q, n)=Sum_{k=0..p} (-1)^k*C(p, k)*C((p-k)*q+n-1, n).

For p=q=3 we get a(n)=C(n + 8, 8) - 6*C(n + 5, 5) + 9*C(n + 3, 3) + 6*C(n + 2, 2) - 18*C(n + 1, 1) + 9=(1/8!)*(n^8 + 36*n^7 + 546*n^6 + 2520*n^5 - 7791*n^4 - 43596*n^3 + 148364*n^2 - 140400*n + 40320).

G.f.: -(9*x^8-54*x^7+132*x^6-171*x^5+135*x^4-78*x^3+36*x^2-9*x+1) / (x-1)^9. - Colin Barker, Jul 13 2013

Prog

(PARI) a(n)=([0, 1, 0, 0, 0, 0, 0, 0, 0; 0, 0, 1, 0, 0, 0, 0, 0, 0; 0, 0, 0, 1, 0, 0, 0, 0, 0; 0, 0, 0, 0, 1, 0, 0, 0, 0; 0, 0, 0, 0, 0, 1, 0, 0, 0; 0, 0, 0, 0, 0, 0, 1, 0, 0; 0, 0, 0, 0, 0, 0, 0, 1, 0; 0, 0, 0, 0, 0, 0, 0, 0, 1; 1, -9, 36, -84, 126, -126, 84, -36, 9]^n*[1; 0; 0; 6; 63; 306; 1038; 2844; 6750])[1, 1] \\ Charles R Greathouse IV, Aug 14 2023

Crossrefs

Cf. A054688, A054974, A054975.

Sequence in context: A158987 A374227 A339239 * A027811 A027950 A184447

Adjacent sequences: A055002 A055003 A055004 * A055006 A055007 A055008

Keyword

easy,nonn

Author

Vladeta Jovovic, May 30 2000

Status

approved