|
%I M1513 N0594 #124 Jan 06 2023 17:48:36
%S 1,1,2,5,17,73,388,2461,18155,152531,1436714,14986879,171453343,
%T 2134070335,28708008128,415017867707,6416208498137,105630583492969,
%U 1844908072865290,34071573484225549,663368639907213281,13580208904207073801
%N Number of terms in a symmetrical determinant: a(n) = n*a(n-1) - (n-1)*(n-2)*a(n-3)/2.
%C 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
%C 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
%C From _Bruce Westbury_, Jan 22 2013: (Start)
%C It follows from the respective exponential generating functions that A002135 is the binomial transform of A002137:
%C A002135(n) = Sum_{k=0..n} binomial(n,k)*A002137(k),
%C 2 = 1.1 + 2.0 + 1.1,
%C 5 = 1.1 + 3.0 + 3.1 + 1.1,
%C 17 = 1.1 + 4.0 + 6.1 + 4.1 + 1.6, ...
%C 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).
%C (End)
%C 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
%C 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
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 260, #12, a_n.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.9 and Problem 5.22.
%H T. D. Noe, <a href="/A002135/b002135.txt">Table of n, a(n) for n=0..100</a>
%H A. C. Aitken, <a href="http://dx.doi.org/10.1017/S0950184300000070">On the number of distinct terms in the expansion of symmetric and skew determinants</a>, Edinburgh Math. Notes, No. 34 (1944), 1-5.
%H A. C. Aitken, <a href="/A002135/a002135_2.pdf">On the number of distinct terms in the expansion of symmetric and skew determinants</a>, Edinburgh Math. Notes, No. 34 (1944), 1-5. [Annotated scanned copy]
%H Art of Problem Solving, <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=366633">Partitioning a deck with 2 cards in n types into pairs</a>
%H A. Cayley, <a href="/A260338/a260338.pdf">On the number of distinct terms in a symmetrical or partially symmetrical determinant</a>, Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 9, pp. 185-190. [Annotated scanned copy]
%H Tomislav Došlic and Darko Veljan, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.066">Logarithmic behavior of some combinatorial sequences</a>, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - _N. J. A. Sloane_, May 01 2012
%H Rui-Li Liu and Feng-Zhen Zhao, <a href="https://www.emis.de/journals/JIS/VOL21/Liu/liu19.html">New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
%H P. A. MacMahon, <a href="http://plms.oxfordjournals.org/content/s2-17/1/25.extract">Combinations derived from m identical sets of n different letters and their connexion with general magic squares</a>, Proc. London Math. Soc., 17 (1917), 25-41.
%H Toufik Mansour, <a href="https://doi.org/10.26493/2590-9770.1516.96f">The length of the initial longest increasing sequence in a permutation</a>, Art Disc. Appl. Math. (2023).
%H T. Muir, <a href="/A002135/a002135_1.pdf">The Theory of Determinants in the Historical Order of Development</a>, 4 vols., Macmillan, NY, 1906-1923. [Annotated scans of selected pages]
%H K. Phillips, <a href="http://www.jstatsoft.org/v33/c01/paper">R functions to symbolically compute the central moments of the multivariate normal distribution</a>, Journal of Statistical Software, Feb 2010.
%H Kem Phillips, <a href="/A002135/a002135.pdf">Proof for multivariate normal moments</a>
%H Richard Stanley and J. Riordan, <a href="http://www.jstor.org/stable/2317576">Problem E2297</a>, Amer. Math. Monthly, 79 (1972), 519-520.
%F E.g.f.: (1-x)^(-1/2)*exp(x/2+x^2/4).
%F D-finite with recurrence a(n+1) = (n+1)*a(n) - binomial(n, 2)*a(n-2). See Comtet.
%F Asymptotics: a(n) ~ sqrt(2)*exp(3/4-n)*n^n*(1+O(1/n)). - _Pietro Majer_, Oct 27 2009
%F 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
%F 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
%e 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
%p G:=proc(n) option remember; if n <= 1 then 1 elif n=2 then
%p 2 else n*G(n-1)-binomial(n-1,2)*G(n-3); fi; end;
%t 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]
%t 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 *)
%t 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 *)
%o (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 */
%o (Maxima)
%o 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);
%o makelist(a(n),n,0,12); /* _Emanuele Munarini_, Aug 25 2017 */
%Y A diagonal of A260338.
%Y Row sums of A215771.
%Y Column k=2 of A257463 and A333467.
%Y Cf. A002137, A059422, A059423, A059424.
%Y Cf. A001147, A007717, A037143, A001710, A215771, A319225, A319226, A320655, A320656.
%K nonn,nice,easy
%O 0,3
%A _N. J. A. Sloane_
|
