login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)
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 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, 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, 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.

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).

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 19:25 EST 2018. Contains 317149 sequences. (Running on oeis4.)