|
%I M2824 N1137 #213 Apr 01 2024 10:31:56
%S 1,1,1,3,9,45,225,1575,11025,99225,893025,9823275,108056025,
%T 1404728325,18261468225,273922023375,4108830350625,69850115960625,
%U 1187451971330625,22561587455281875,428670161650355625,9002073394657468125,189043541287806830625
%N Number of permutations in the symmetric group S_n that have odd order.
%C Michael Reid (mreid(AT)math.umass.edu) points out that the e.g.f. for the number of permutations of odd order can be obtained from the cycle index for S_n, F(Y; X1, X2, X3, ... ) := e^(X1 Y + X2 Y^2/2 + X3 Y^3/3 + ... ) and is F(Y, 1, 0, 1, 0, 1, 0, ... ) = sqrt((1 + Y)/(1 - Y)).
%C a(n) appears to be the number of permutations on [n] whose up-down signature has nonnegative partial sums. For example, the up-down signature of (2,4,5,1,3) is (+1,+1,-1,+1) with nonnegative partial sums 1,2,1,2 and a(3)=3 counts (1,2,3), (1,3,2), (2,3,1). - _David Callan_, Jul 14 2006
%C This conjecture has been confirmed, see Bernardi, Duplantier, Nadeau link.
%C a(n) is the number of permutations of [n] for which all left-to-right minima occur in odd locations in the permutation. For example, a(3)=3 counts 123, 132, 231. Proof: For such a permutation of length 2n, you can append 1,2,..., or 2n+1 (2n+1 choices) and increase by 1 the original entries that weakly exceed the appended entry. This gives all such permutations of length 2n+1. But if the original length is 2n-1, you cannot append 1 (for then 1 would be a left-to-right min in an even location) so you can only append 2,3,..., or 2n (2n-1 choices). This count matches the given recurrence relation a(2n)=(2n-1)a(2n-1), a(2n+1)=(2n+1)a(2n). - _David Callan_, Jul 22 2008
%C a(n) is the n-th derivative of exp(arctanh(x)) at x = 0. - _Michel Lagneau_, May 11 2010
%C a(n) is the absolute value of the Moebius number of the odd partition poset on a set of n+1 points, where the odd partition poset is defined to be the subposet of the partition poset consisting of only partitions using odd part size (as well as the maximum element for n even). - _Kenneth M Monks_, May 06 2012
%C Number of permutations in S_n in which all cycles have odd length. - _Michael Somos_, Mar 17 2019
%D H.-D. Ebbinghaus et al., Numbers, Springer, 1990, p. 146.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 87.
%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).
%H Alois P. Heinz, <a href="/A000246/b000246.txt">Table of n, a(n) for n = 0..450</a> (first 101 terms from T. D. Noe)
%H Joel Barnes, <a href="http://hdl.handle.net/1773/26116">Conformal welding of uniform random trees</a>, Ph. D. Dissertation, Univ. Washington, 2014.
%H Olivier Bernardi, Bertrand Duplantier and Philippe Nadeau, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s63bernadu.html">A Bijection Between Well-Labelled Positive Paths and Matchings</a>, Séminaire Lotharingien de Combinatoire (2010), volume 63, Article B63e.
%H William Y. C. Chen, <a href="http://billchen.org/publications/2023_Cycles/2023_Cycles.pdf">Breaking Cycles, the Odd Versus the Even</a>, 2023.
%H A. Edelman and M. La Croix, <a href="http://arxiv.org/abs/1410.7065">The Singular Values of the GUE (Less is More)</a>, arXiv preprint arXiv:1410.7065 [math.PR], 2014-2015. See Table 1.
%H Steven Finch, <a href="https://arxiv.org/abs/2111.14487">Rounds, Color, Parity, Squares</a>, arXiv:2111.14487 [math.CO], 2021.
%H A. Ghitza and A. McAndrew, <a href="http://arxiv.org/abs/1207.3480">Experimental evidence for Maeda's conjecture on modular forms</a>, arXiv preprint arXiv:1207.3480 [math.NT], 2012.
%H Y. Cha, <a href="http://purl.flvc.org/fsu/fd/FSU_migr_etd-3960">Closed form solutions of difference equations</a> (2011) PhD Thesis, Florida State University, page 24
%H Dmitry Kruchinin, <a href="http://arxiv.org/abs/1211.2100">Integer properties of a composition of exponential generating functions</a>, arXiv:1211.2100 [math.NT], 2012.
%H Zhicong Lin, David G.L. Wang, and Tongyuan Zhao, <a href="https://arxiv.org/abs/2103.04599">A decomposition of ballot permutations, pattern avoidance and Gessel walks</a>, arXiv:2103.04599 [math.CO], 2021.
%H Kenneth M. Monks, <a href="https://www.emis.de/journals/JIS/VOL21/Monks/monks12.html">An Elementary Proof of the Explicit Formula for the Möbius Number of the Odd Partition Poset</a>, J. Int. Seq., Vol. 21 (2018), Article 18.9.6.
%H Qingchun Ren, <a href="http://arxiv.org/abs/1301.6327">Ordered Partitions and Drawings of Rooted Plane Trees</a>, arXiv preprint arXiv:1301.6327 [math.CO], 2013. See Lemma 15.
%H Marko Riedel, et al. <a href="https://math.stackexchange.com/questions/4213063/">From combinatorial class to recurrence to closed form</a>, Mathematics Stack Exchange.
%H Jonathan Sondow, <a href="https://arxiv.org/abs/math/0401406">A faster product for Pi and a new integral for ln(Pi/2)</a>, arXiv:math/0401406 [math.NT], 2004.
%H Jonathan Sondow, <a href="https://www.jstor.org/stable/30037575">A faster product for Pi and a new integral for ln(Pi/2)</a>, Amer. Math. Monthly 112 (2005), 729-734 and 113 (2006), 670.
%H Sam Spiro, <a href="https://arxiv.org/abs/1810.00993">Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic</a>, arXiv:1810.00993 [math.CO], 2018.
%H Allen Wang, <a href="http://math.mit.edu/research/highschool/primes/materials/2018/conf/11-3%20WangAl.pdf">Permutations with Up-Down Signatures of Nonnegative Partial Sums</a>, MIT PRIMES Conference (2018).
%H David G. L. Wang and T. Zhao, <a href="https://arxiv.org/abs/2009.05973">The peak and descent statistics over ballot permutations</a>, arXiv:2009.05973 [math.CO], 2020.
%H <a href="/index/Gre#groups">Index entries for sequences related to groups</a>
%F E.g.f.: sqrt(1-x^2)/(1-x) = sqrt((1+x)/(1-x)).
%F a(2*k) = (2*k-1)*a(2*k-1), a(2*k+1) = (2*k+1)*a(2*k), for k >= 0, with a(0) = 1.
%F Let b(1)=0, b(2)=1, b(k+2)=b(k+1)/k + b(k); then a(n+1) = n!*b(n+2). - _Benoit Cloitre_, Sep 03 2002
%F a(n) = Sum_{k=0..floor((n-1)/2)} (2k)! * C(n-1, 2k) * a(n-2k-1) for n > 0. - Noam Katz (noamkj(AT)hotmail.com), Feb 27 2001
%F Also successive denominators of Wallis's approximation to Pi/2 (unreduced): 1/1 * 2/1 * 2/3 * 4/3 * 4/5 * 6/5 * 6/7 * .., for n >= 1.
%F D-finite with recurrence: a(n) = a(n-1) + (n-1)*(n-2)*a(n-2). - _Benoit Cloitre_, Aug 30 2003
%F a(n) is asymptotic to (n-1)!*sqrt(2*n/Pi). - _Benoit Cloitre_, Jan 19 2004
%F a(n) = n! * binomial(n-1, floor((n-1)/2)) / 2^(n-1), n > 0. - _Ralf Stephan_, Mar 22 2004
%F E.g.f.: e^atanh(x), a(n) = n!*Sum_{m=1..n} Sum_{k=m..n} 2^(k-m)*Stirling1(k,m) *binomial(n-1,k-1)/k!, n > 0, a(0)=1. - _Vladimir Kruchinin_, Dec 12 2011
%F G.f.: G(0) where G(k) = 1 + x*(4*k-1)/((2*k+1)*(x-1) - x*(x-1)*(2*k+1)*(4*k+1)/(x*(4*k+1) + 2*(x-1)*(k+1)/G(k+1))); (continued fraction, 3rd kind, 3-step). - _Sergei N. Gladkovskii_, Jul 24 2012
%F G.f.: 1 + x*(G(0) - 1)/(x-1) where G(k) = 1 - (2*k+1)/(1-x/(x - 1/(1 - (2*k+1)/(1-x/(x - 1/G(k+1) ))))); (continued fraction). - _Sergei N. Gladkovskii_, Jan 15 2013
%F G.f.: G(0), where G(k) = 1 + x*(2*k+1)/(1 - x*(2*k+1)/(x*(2*k+1) + 1/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Jun 07 2013
%F For n >= 1, a(2*n) = (2*n-1)!!^2, a(2*n+1) = (2*n+1)*(2*n-1)!!^2. - _Vladimir Shevelev_, Dec 01 2013
%F E.g.f.: arcsin(x) - sqrt(1-x^2) + 1 for a(0) = 0, a(1) = a(2) = a(3) = 1. - _G. C. Greubel_, May 01 2015
%F Sum_{n>1} 1/a(n) = (L_0(1) + L_1(1))*Pi/2, where L is the modified Struve function. - _Peter McNair_, Mar 11 2022
%F From _Peter Bala_, Mar 29 2024: (Start)
%F a(n) = n! * Sum_{k = 0..n} (-1)^(n+k)*binomial(1/2, k)*binomial(-1/2, n-k).
%F a(n) = (1/4^n) * (2*n)!/n! * hypergeom([-1/2, -n], [1/2 - n], -1).
%F a(n) = n!/2^n * A063886(n). (End)
%e For the Wallis numerators, denominators and partial products see A001900. - _Wolfdieter Lang_, Dec 06 2017
%p a:= proc(n) option remember; `if`(n<2, 1,
%p a(n-1) +(n-1)*(n-2)*a(n-2))
%p end:
%p seq(a(n), n=0..25); # _Alois P. Heinz_, May 14 2018
%t a[n_] := a[n] = a[n-1]*(n+Mod[n, 2]-1); a[0] = 1; Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Nov 21 2011, after Pari *)
%t a[n_] := a[n] = (n-2)*(n-3)*a[n-2] + a[n-1]; a[0] := 0; a[1] := 1; Table[a[i], {i, 0, 20}] (* or *) RecurrenceTable[{a[0]==0, a[1]==1, a[n]==(n-2)*(n-3)a[n-2]+a[n-1]}, a, {n, 20}] (* _G. C. Greubel_, May 01 2015 *)
%t CoefficientList[Series[Sqrt[(1+x)/(1-x)], {x, 0, 50}], x]*Table[k!, {k, 0, 20}] (* _Stefano Spezia_, Oct 07 2018 *)
%o (PARI) a(n)=if(n<1,!n,a(n-1)*(n+n%2-1))
%o (PARI) Vec( serlaplace( sqrt( (1+x)/(1-x) + O(x^55) ) ) )
%o (PARI) a(n)=prod(k=3,n,k+k%2-1) \\ _Charles R Greathouse IV_, May 01 2015
%o (PARI) a(n)=(n!/(n\2)!>>(n\2))^2/if(n%2,n,1) \\ _Charles R Greathouse IV_, May 01 2015
%o (Haskell)
%o a000246 n = a000246_list !! n
%o a000246_list = 1 : 1 : zipWith (+)
%o (tail a000246_list) (zipWith (*) a000246_list a002378_list)
%o -- _Reinhard Zumkeller_, Feb 27 2012
%o (Magma) I:=[1,1]; [n le 2 select I[n] else Self(n-1)+(n^2-5*n+6)*Self(n-2): n in [1..30]]; // _Vincenzo Librandi_, May 02 2015
%Y Cf. A001900, A059838, A002867.
%Y Bisections are A001818 and A079484.
%Y Row sums of unsigned triangle A049218 and of A111594, A262125.
%Y Main diagonal of A262124.
%Y Cf. A002019.
%K nonn,easy
%O 0,4
%A _N. J. A. Sloane_
|
