A002135 Number of terms in a symmetrical determinant: a(n) = n*a(n-1) - (n-1)*(n-2)*a(n-3)/2.

1, 1, 2, 5, 17, 73, 388, 2461, 18155, 152531, 1436714, 14986879, 171453343, 2134070335, 28708008128, 415017867707, 6416208498137, 105630583492969, 1844908072865290, 34071573484225549, 663368639907213281, 13580208904207073801

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

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 r-th 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^2|mu=0, Sigma] (Phillips 2010). These representations are the upper-triangular, positive integer matrices for which for each i, the sum of the i-th row and i-th 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

Examples

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

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), 1-5.
• A. C. Aitken, On the number of distinct terms in the expansion of symmetric and skew determinants, Edinburgh Math. Notes, No. 34 (1944), 1-5. [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. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 9, pp. 185-190. [Annotated scanned copy]
• Tomislav Došlic and Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - _N. J. A. Sloane_, May 01 2012
• Rui-Li Liu and Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, 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), 25-41.
• Toufik Mansour, The length of the initial longest increasing sequence in a permutation, Art Disc. Appl. Math. (2023).
• T. Muir, The Theory of Determinants in the Historical Order of Development, 4 vols., Macmillan, NY, 1906-1923. [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), 519-520.

Crossrefs

A diagonal of A260338.

Row sums of A215771.

Column k=2 of A257463 and A333467.

Cf. A002137, A059422, A059423, A059424.

Cf. A001147, A007717, A037143, A001710, A215771, A319225, A319226, A320655, A320656.

Programs

Maple

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

Mathematica

a[x_]:=Log[1/(1-x)^(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[n-1]-(n-1)(n-2)* a[n-3]/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 *)

Maxima

a(n):=sum(sum(binomial(k,i)*binomial(i-1/2,n-k)*(3^(k-i)*n!)/(4^k*k!)*(-1)^(n-k-i),i,0,k),k,0,n);
makelist(a(n),n,0,12); /* Emanuele Munarini, Aug 25 2017 */

PARI

a(n) = if(n<3, [1,1,2][n+1], n*a(n-1) - (n-1)*(n-2)*a(n-3)/2 ); /* Joerg Arndt, Apr 07 2013 */

Formula

E.g.f.: (1-x)^(-1/2)*exp(x/2+x^2/4).

D-finite with recurrence a(n+1) = (n+1)*a(n) - binomial(n, 2)*a(n-2). See Comtet.

Asymptotics: a(n) ~ sqrt(2)*exp(3/4-n)*n^n*(1+O(1/n)). - Pietro Majer, Oct 27 2009

E.g.f.: G(0)/sqrt(1-x) 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(i-1/2,n-k)*(3^(k-i)*n!)/(4^k*k!)*(-1)^(n-k-i). - Emanuele Munarini, Aug 25 2017