|
|
A001500
|
|
Number of stochastic matrices of integers: n X n arrays of nonnegative integers with all row and column sums equal to 3.
(Formerly M3689 N1507)
|
|
12
|
|
|
1, 1, 4, 55, 2008, 153040, 20933840, 4662857360, 1579060246400, 772200774683520, 523853880779443200, 477360556805016931200, 569060910292172349004800, 868071731152923490921728000, 1663043727673392444887284377600, 3937477620391471128913917360384000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Also, number of bicubical multigraphs on 2n labeled nodes of two colors [Read, 1958, 1971]. - N. J. A. Sloane, Sep 09 2014
|
|
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
|
|
|
FORMULA
|
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
|
|
EXAMPLE
|
a(2) = 4 with: [0 3] [1 2] [2 1] [3 0]
|
|
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}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|