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:
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
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.
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
EXAMPLE
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
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 *)
PROG
(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 */
(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 */
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
STATUS
approved