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
Links
- Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).
Programs
-
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
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