|
|
A002135
|
|
Number of terms in a symmetrical determinant: a(n) = n*a(n-1) - (n-1)*(n-2)*a(n-3)/2.
(Formerly M1513 N0594)
|
|
19
|
|
|
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
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
|
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);
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|