|
|
A000681
|
|
Number of n X n matrices with nonnegative entries and every row and column sum 2.
(Formerly M3084 N1250)
|
|
15
|
|
|
1, 1, 3, 21, 282, 6210, 202410, 9135630, 545007960, 41514583320, 3930730108200, 452785322266200, 62347376347779600, 10112899541133589200, 1908371363842760216400, 414517594539154672566000, 102681435747106627787376000, 28772944645196614863048048000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Or, number of labeled 2-regular pseudodigraphs (multiple arcs and loops allowed) of order n.
Also, number of permutations of the multiset {1^2,2^2,...,n^2} with the descent set consisting of multiples of 2. - Max Alekseyev, Apr 28 2014
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 125, #25, a_n.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, section 3.5.10.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.
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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Cor. 5.5.11 (a).
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.
C. B. Tompkins, Methods of successive restrictions in computational problems involving discrete variables. 1963, Proc. Sympos. Appl. Math., Vol. XV pp. 95-106; Amer. Math. Soc., Providence, R.I.
|
|
LINKS
|
S. Cockburn and J. Lesperance, Deranged socks, Mathematics Magazine, 86 (2013), 97-109.
|
|
FORMULA
|
Sum_{n >= 0} a(n) x^n / n!^2 = exp(x/2) / sqrt(1-x).
D-finite with recurrence a(n) = n^2*a(n-1) - (1/2)*n*(n-1)^2*a(n-2).
a(n) is asymptotic to c/sqrt(n)*(n!)^2 where c=0.93019... - Benoit Cloitre, Jun 25 2004
a(n) = sum(i=0..n, 2^(i-2*n) * C(n, i)^2 * (2*n-2*i)! * i! ).
a(n) = 2^(-n) * sum(i=0..n, ((n!)^2*(2*i)!) / ((i!)^2*((n-i)!*2^i)) ). - Shanzhen Gao, Nov 05 2007
In Cloitre's formula is c = exp(1/2)/sqrt(Pi) = 0.9301913671026328586. - Vaclav Kotesovec, Aug 12 2013
With c as used above by Cloitre and Kotesovec, a(n) is asymptotic to c/sqrt(n)*(n!)^2 * (1 + 2/(16*n) + 50/(16*n)^2 + 1100/(16*n)^3 + 32438/(16*n)^4 + 1185660/(16*n)^5 + 50498228/(16*n)^6 + 2438464600/(16*n)^7 + 131323987366/(16*n)^8 + 7782036656108/(16*n)^9 + 501905392385436/(16*n)^10 + ...). - Jon E. Schoenfield, Mar 03 2014
E.g.f.: 2/((2-x)*W(0)), where W(k) = 1 - (2*k+1)*x/(2-x-2*(k+1)*x/W(k+1)); (continued fraction). - Sergei N. Gladkovskii, Nov 25 2014
|
|
EXAMPLE
|
G.f. = 1 + x + 3*x^2 + 21*x^3 + 282*x^4 + 6210*x^5 + 202410*x^6 + 9135630*x^7 + ...
|
|
MAPLE
|
coeftayl( exp(x/2)/sqrt(1-x), x=0, n) ;
%*(n!)^2 ;
end proc:
|
|
MATHEMATICA
|
a[n_] := Sum[ ((2*i)!*n!^2) / (2^i*(i!^2*(n - i)!)), {i, 0, n}]/2^n; Table[ a[n], {n, 0, 17}] (* Jean-François Alcover, Dec 08 2011 *)
a[n_] := n!*HypergeometricPFQ[{1/2, -n}, {}, -2]/2^n; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Aug 08 2012 *)
|
|
PROG
|
(Sage) from sage.combinat.integer_matrices import IntegerMatrices
def a(n): return IntegerMatrices([2]*n, [2]*n).cardinality() # Ralf Stephan, Mar 02 2014
(PARI) Vec( serlaplace(serlaplace( exp(x/2)/sqrt(1-x) )) ) /* Max Alekseyev, Apr 28 2014 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|