A001500 Number of stochastic matrices of integers: n X n arrays of nonnegative integers with all row and column sums equal to 3.

1, 1, 4, 55, 2008, 153040, 20933840, 4662857360, 1579060246400, 772200774683520, 523853880779443200, 477360556805016931200, 569060910292172349004800, 868071731152923490921728000, 1663043727673392444887284377600, 3937477620391471128913917360384000

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Also, number of bicubical multigraphs on 2n labeled nodes of two colors [Read, 1958, 1971]. - N. J. A. Sloane, Sep 09 2014

Examples

			a(2) = 4 with: [0 3]    [1 2]    [2 1]    [3 0]
               [3 0],   [2 1],   [1 2],   [0 3]. - _Bernard Schott_, Oct 15 2019
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 125, Problem 25(4), b_n (but beware errors).
• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
• R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements. Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..180
• Esther M. Banaian, Generalized Eulerian Numbers and Multiplex Juggling Sequences, (2016). All College Thesis Program. Paper 24.
• E. Banaian, S. Butler, C. Cox, J. Davis, J. Landgraf and S. Ponce A generalization of Eulerian numbers via rook placements, arXiv:1508.03673 [math.CO], 2015.
• Petter Brändén, Jonathan Leake, Igor Pak, Lower bounds for contingency tables via Lorentzian polynomials, arXiv:2008.05907 [math.CO], 2020.
• I. P. Goulden, D. M. Jackson, and J. W. Reilly, The Hammond series of a symmetric function and its application to P-recursiveness, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 179-193.
• R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence, although there are errors)
• M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements, Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970. [Annotated scanned copy]
• Index entries for sequences related to magic squares

Crossrefs

Row sums of A269743 and of A344379.

Column k=3 of A257493.

Cf. A000681, A246970.

Programs

Mathematica

a[n_] := 6^(-n) Sum[2^j 3^k n!^2 (3n - 2k - 3j)!/(j! k! (n - j - k)!^2 * 6^(n - j - k)), {j, 0, n}, {k, 0, n - j}];
a /@ Range[0, 15] (* Jean-François Alcover, Oct 15 2019, after Shanzhen Gao *)

Formula

From Vladeta Jovovic, Mar 26 2001: (Start)

E.g.f. y(x) = Sum_{n >= 0} a(n)*x^n/(n!)^2 satisfies differential equation 81*x^5*(x^4 - x^2 + x + 4)*(d^4/dx^4)y(x) + 324*x^4*(x^4 - x^2 + x + 4)*(d^3/dx^3)y(x) - 9*x*(x^10 - 4*x^9 + 22*x^8 - 8*x^7 - 22*x^6 + 8*x^5 + 106*x^4 + 234*x^3 + 48*x^2 - 320*x + 64)*(d^2/dx^2)y(x) - 9*(x^10 - 4*x^9 + 22*x^8 - 8*x^7 - 4*x^6 + 8*x^5 + 88*x^4 + 252*x^3 + 120*x^2 - 320*x + 64)*(d/dx)y(x) + (x^11 - 7*x^10 + 30*x^9 - 16*x^8 - 43*x^7 + 51*x^6 + 238*x^5 + 630*x^4 + 36*x^3 - 1944*x^2 - 1152*x + 576)*y(x) = 0.

Recurrence: a(n) = n!*v(n) where v(n) = 1/(576*n)*((-198*n^9 + 8712*n^8 - 165175*n^7 + 1764196*n^6 - 11643772*n^5 + 48965728*n^4 - 130257475*n^3 + 209370724*n^2 - 182126340*n + 64083600)*v(n - 8) + (36*n^10 - 1944*n^9 + 45884*n^8 - 621504*n^7 + 5330892*n^6 - 30123576*n^5 + 112954596*n^4 - 275612976*n^3 + 415021552*n^2 - 343920960*n + 116928000)*v(n - 9) + (-9*n^11 + 585*n^10 - 16800*n^9 + 280800*n^8 - 3027357*n^7 + 22034565*n^6 - 110039130*n^5 + 375129450*n^4 - 849926784*n^3 + 1208298600*n^2 - 958439520*n + 315705600)*v(n - 10) + (-7*n^10 + 385*n^9 - 9240*n^8 + 127050*n^7 - 1104411*n^6 + 6314385*n^5 - 23918510*n^4 + 58866500*n^3 - 89275032*n^2 + 74400480*n - 25401600)*v(n - 11) + (-81*n^7 + 1944*n^6 - 20232*n^5 + 115578*n^4 - 383283*n^3 + 724230*n^2 - 708372*n + 270216)*v(n - 4) + (-72*n^6 + 1440*n^5 - 10890*n^4 + 40500*n^3 - 78678*n^2 + 75780*n - 28080)*v(n - 5) + (81*n^9 - 3321*n^8 + 59004*n^7 - 594054*n^6 + 3718687*n^5 - 14927199*n^4 + 38152096*n^3 - 59311746*n^2 + 50236612*n - 17330160)*v(n - 6) + (72*n^8 - 2520*n^7 + 37347*n^6 - 304479*n^5 + 1484133*n^4 - 4394565*n^3 + 7642248*n^2 - 7039116*n + 2576880)*v(n - 7) + (n^11 - 66*n^10 + 1925*n^9 - 32670*n^8 + 357423*n^7 - 2637558*n^6 + 13339535*n^5 - 45995730*n^4 + 105258076*n^3 - 150917976*n^2 + 120543840*n - 39916800)*v(n - 12) + (2880*n^2 - 5760*n + 3456)*v(n - 1) + (324*n^5 - 3564*n^4 + 14148*n^3 - 26028*n^2 + 21312*n - 6192)*v(n - 2) + (81*n^6 - 1377*n^5 + 7209*n^4 - 13203*n^3 - 3402*n^2 + 32076*n - 21384)*v(n - 3)). (End)

a(n) = 6^(-n) * Sum_{ alpha = 0..n, beta = 0..n-alpha } (2^alpha*3^beta*(n!)^2*(-2*beta+3*n-3*alpha)!)/(alpha!*beta!*(n-alpha-beta)!^2*6^(n-alpha-beta)). - Shanzhen Gao, Nov 05 2007

a(n) ~ sqrt(Pi) * 3^(n + 1/2) * n^(3*n + 1/2) / (2^(2*n - 1/2) * exp(3*n - 2)). - Vaclav Kotesovec, Oct 15 2019

Extensions

More terms from Vladeta Jovovic, Mar 26 2001