cp's OEIS Frontend

A005045 Number of restricted 3 X 3 matrices with row and column sums n.

%I A005045 M2536 #47 Aug 10 2025 19:49:02
%S A005045 0,0,1,3,6,10,17,25,37,51,70,92,121,153,194,240,296,358,433,515,612,
%T A005045 718,841,975,1129,1295,1484,1688,1917,2163,2438,2732,3058,3406,3789,
%U A005045 4197,4644,5118,5635,6183,6777,7405,8084,8800,9571,10383,11254
%N A005045 Number of restricted 3 X 3 matrices with row and column sums n.
%C A005045 More precisely, consider 3 X 3 matrices with entries chosen from {0, 1, ..., n-1}, in which each row and column sums to n, where n >= 2. Then a(n) is the number of equivalence classes of such matrices under permutions of rows and columns and transpositions.
%D A005045 E. J. Morgan, On 3 X 3 matrices with constant row and column sum, Abstract 763-05-13, Notices Amer. Math. Soc., 26 (1979), page A-27.
%D A005045 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005045 M. F. Hasler, <a href="/A005045/b005045.txt">Table of n, a(n) for n = 0..1000</a>
%H A005045 E. J. Billington (née Morgan) and N. J. A. Sloane, <a href="/A005045/a005045_1.pdf">Correspondence</a>, 1978-1991.
%H A005045 P. Lisonek, <a href="/A005045/a005045_2.pdf">Quasi-polynomials: A case study in experimental combinatorics</a>, RISC-Linz Report Series No. 93-18, 1983. (Annotated scanned copy)
%H A005045 R. J. Mathar, <a href="/A005045/a005045.pdf">OEIS A005045</a> [Proof of g.f. for 3 of the 12 cases]
%H A005045 E. J. Morgan, <a href="https://doi.org/10.1017/S0004972700008546">Construction of Block Designs and Related Results</a>, Ph.D. Dissertation, Univ. Queensland, 1978; Bull. Austral. Math. Soc., Volume 19, Issue 1 August 1978, pp. 139-140.
%H A005045 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A005045 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A005045 <a href="/index/Rec#order_11">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1,0,-2,2,0,1,0,-2,1).
%F A005045 Let n = 3k, 3k-1 or 3k-2 according as n == 0, 2 or 1 mod 3, for n >= 3. Then a(n) = Sum_{i=1..n-k} Sum_{m=max(0,2i-n)..floor(i/2)} Sum_{r=0..floor(i/2)-m} c(i,m,r), where c(i,m,r) = n-2i+m+1 when m+r != i/2, or = floor((n-2i+m+2)/2) when m+r = i/2. [Typos corrected by Peter Pein, May 13 2008]
%F A005045 G.f.: -x^2*(-x^5+x^6-x^3+x+1)/((x^2+1)*(x^2+x+1)*(x+1)^2*(x-1)^5). This was conjectured by _Simon Plouffe_ in his 1992 dissertation and is now known to be correct, although it may be that all the details of the proof have not been written down. See the Mathar link for details.
%e A005045 a(2) = 1:
%e A005045   110
%e A005045   101
%e A005045   011
%e A005045 a(3) = 3:
%e A005045   111 210 210
%e A005045   111 102 111
%e A005045   111 021 012
%p A005045 A005045:=-z**2*(-z**5+z**6-z**3+z+1)/((z**2+1)*(z**2+z+1)*(z+1)**2*(z-1)**5); # conjectured by _Simon Plouffe_ in his 1992 dissertation; see formula lines here for the proof of correctness
%t A005045 a[n_] := Block[{k = Floor[(n + 2)/3]}, Sum[Sum[Sum[If[m + r == i/2, Floor[(n - 2*i + m + 2)/2], n - 2*i + m + 1], {r, 0, Floor[i/2 - m]}], {m, Max[2*i - n, 0], Floor[i/2]}], {i, 1, n - k}]]; Table[a[n], {n, 0, 46}] (* Peter Pein, May 13 2008 *)
%t A005045 LinearRecurrence[{2,0,-1,0,-2,2,0,1,0,-2,1},{0,0,1,3,6,10,17,25,37,51,70},50] (* _Harvey P. Dale_, Nov 15 2018 *)
%o A005045 (PARI)
%o A005045 A005045(n)={sum( i=1,n-(n+2)\3, sum( m=max(0,2*i-n),i\2, sum( r=0,i\2-m, if( m+r!=i/2, n-2*i+m+1, (n-2*i+m+2)\2))))} \\ _M. F. Hasler_, Version 1, May 13 2008
%o A005045 (PARI)
%o A005045 A005045(n)={sum( i=1,(2*n)\3, sum( m=max(0,2*i-n),i\2, (n-2*i+m+1)*((i+1)\2-m)+(i%2==0)*(n-2*i+m+2)\2))} \\ _M. F. Hasler_, Version 2, much faster, May 13 2008
%o A005045 (PARI) concat(vector(2), Vec(x^2*(1 + x - x^3 - x^5 + x^6) / ((1 - x)^5*(1 + x)^2*(1 + x^2)*(1 + x + x^2)) + O(x^60))) \\ _Colin Barker_, Apr 22 2017
%Y A005045 Cf. A002817 for another version.
%K A005045 nonn,nice,easy
%O A005045 0,4
%A A005045 _N. J. A. Sloane_
%E A005045 Edited by _N. J. A. Sloane_, May 12 2008, May 13 2008
%E A005045 More terms from Peter Pein, May 13 2008