

A002135


Number of terms in a symmetrical determinant: a(n) = n*a(n1)  (n1)*(n2)*a(n3)/2.
(Formerly M1513 N0594)


18



1, 1, 2, 5, 17, 73, 388, 2461, 18155, 152531, 1436714, 14986879, 171453343, 2134070335, 28708008128, 415017867707, 6416208498137, 105630583492969, 1844908072865290, 34071573484225549, 663368639907213281, 13580208904207073801
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

a(n) is the number of collections of necklaces created by using exactly n different colored beads (to make the entire collection).  Geoffrey Critzer, Apr 19 2009
a(n) is the number of ways that a deck with 2 cards of each of n types may be dealt into n hands of 2 cards each, assuming that the order of the hands and the order of the cards in each hand are irrelevant. See the Art of Problem Solving link for proof.  Joel B. Lewis, Sep 30 2012
From Bruce Westbury, Jan 22 2013: (Start)
It follows from the respective exponential generating functions that A002135 is the binomial transform of A002137:
A002135(n) = Sum_{k=0..n} binomial(n,k)*A002137(k),
2 = 1.1 + 2.0 + 1.1,
5 = 1.1 + 3.0 + 3.1 + 1.1,
17 = 1.1 + 4.0 + 6.1 + 4.1 + 1.6, ...
A002137 arises from looking at the dimension of the space of invariant tensors of the rth tensor power of the adjoint representation of the symplectic group Sp(2n) (for n large compared to r).
(End)
a(n) is the number of representations required for the symbolic central moments of order 2 for the multivariate normal distribution, that is, E[X1^2 X2^2 .. Xn^2mu=0, Sigma] (Phillips 2010). These representations are the uppertriangular, positive integer matrices for which for each i, the sum of the ith row and ith column equals 2, the power of each component. This can be shown starting from the formulation by Joel B Lewis. See "Proof for multivariate normal moments" link below for a proof.  Kem Phillips, Aug 20 2014
Equivalent to Critzer's comment, a(n) is the number of ways to cover n labeled vertices by disjoint undirected cycles, hence the exponential transform of A001710(n  1).  Gus Wiseman, Oct 20 2018


REFERENCES

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 260, #12, a_n.
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 Example 5.2.9 and Problem 5.22.


LINKS

T. D. Noe, Table of n, a(n) for n=0..100
A. C. Aitken, On the number of distinct terms in the expansion of symmetric and skew determinants, Edinburgh Math. Notes, No. 34 (1944), 15.
A. C. Aitken, On the number of distinct terms in the expansion of symmetric and skew determinants, Edinburgh Math. Notes, No. 34 (1944), 15. [Annotated scanned copy]
Art of Problem Solving, Partitioning a deck with 2 cards in n types into pairs
A. Cayley, On the number of distinct terms in a symmetrical or partially symmetrical determinant, Collected Mathematical Papers. Vols. 113, Cambridge Univ. Press, London, 18891897, Vol. 9, pp. 185190. [Annotated scanned copy]
Tomislav Došlic, Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math. 308 (2008), no. 11, 21822212. MR2404544 (2009j:05019)  N. J. A. Sloane, May 01 2012
RuiLi Liu, FengZhen Zhao, New Sufficient Conditions for LogBalancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
P. A. MacMahon, Combinations derived from m identical sets of n different letters and their connexion with general magic squares, Proc. London Math. Soc., 17 (1917), 2541.
T. Muir, The Theory of Determinants in the Historical Order of Development, 4 vols., Macmillan, NY, 19061923. [Annotated scans of selected pages]
K. Phillips, R functions to symbolically compute the central moments of the multivariate normal distribution, Journal of Statistical Software, Feb 2010.
Kem Phillips, Proof for multivariate normal moments
Richard Stanley and J. Riordan, Problem E2297, Amer. Math. Monthly, 79 (1972), 519520.


FORMULA

E.g.f.: (1x)^(1/2)*exp(x/2+x^2/4).
a(n+1) = (n+1)*a(n)  binomial(n, 2)*a(n2). See Comtet.
Asymptotics: a(n) ~ sqrt(2)*exp(3/4n)*n^n*(1+O(1/n)).  Pietro Majer, Oct 27 2009
E.g.f.: G(0)/sqrt(1x) where G(k) = 1 + x*(x+2)/(4*(2*k+1)  4*x*(x+2)*(2*k+1)/(x*(x+2) + 8*(k + 1)/G(k+1) )); (continued fraction).  Sergei N. Gladkovskii, Jan 31 2013
a(n) = Sum_{k=0..n} Sum_{i=0..k} binomial(k,i)*binomial(i1/2,nk)*(3^(ki)*n!)/(4^k*k!)*(1)^(nki).  Emanuele Munarini, Aug 25 2017


EXAMPLE

For n = 3, the a(3) = 5 ways to deal out the deck {1, 1, 2, 2, 3, 3} into three twocard hands are {11, 22, 33}, {12, 12, 33}, {13, 13, 22}, {11, 23, 23}, {12, 13, 23}.  Joel B. Lewis, Sep 30 2012


MAPLE

G:=proc(n) option remember; if n <= 1 then 1 elif n=2 then
2 else n*G(n1)binomial(n1, 2)*G(n3); fi; end;


MATHEMATICA

a[x_]:=Log[1/(1x)^(1/2)]+x/2+x^2/4; Range[0, 20]! CoefficientList[Series[Exp[a[x]], {x, 0, 20}], x]
RecurrenceTable[{a[0]==a[1]==1, a[2]==2, a[n]==n*a[n1](n1)(n2)* a[n3]/2}, a, {n, 30}] (* Harvey P. Dale, Dec 16 2011 *)
Table[Sum[Binomial[k, i] Binomial[i  1/2, n  k] (3^(k  i) n!)/(4^k k!) (1)^(n  k  i), {k, 0, n}, {i, 0, k}], {n, 0, 12}] (* Emanuele Munarini, Aug 25 2017 *)


PROG

(PARI) a(n) = if(n<3, [1, 1, 2][n+1], n*a(n1)  (n1)*(n2)*a(n3)/2 ); /* Joerg Arndt, Apr 07 2013 */
(Maxima)
a(n):=sum(sum(binomial(k, i)*binomial(i1/2, nk)*(3^(ki)*n!)/(4^k*k!)*(1)^(nki), i, 0, k), k, 0, n);
makelist(a(n), n, 0, 12); /* Emanuele Munarini, Aug 25 2017 */


CROSSREFS

A diagonal of A260338.
Row sums of A215771.
Column k=2 of A257463.
Cf. A002137, A059422, A059423, A059424.
Cf. A001147, A007717, A037143, A001710, A215771, A319225, A319226, A320655, A320656.
Sequence in context: A084161 A230960 A102038 * A260337 A217944 A007868
Adjacent sequences: A002132 A002133 A002134 * A002136 A002137 A002138


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane


STATUS

approved



