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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000246 Number of permutations in the symmetric group S_n that have odd order.
(Formerly M2824 N1137)
22
1, 1, 1, 3, 9, 45, 225, 1575, 11025, 99225, 893025, 9823275, 108056025, 1404728325, 18261468225, 273922023375, 4108830350625, 69850115960625, 1187451971330625, 22561587455281875, 428670161650355625, 9002073394657468125, 189043541287806830625 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

a(n)=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

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

a(n) is the n-th derivative of exp(arctanh(x)) at x = 0.- Michel Lagneau, May 11 2010

a(n) is the absolute value of the Mobius 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

REFERENCES

H.-D. Ebbinghaus et al., Numbers, Springer, 1990, p. 146.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 87.

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

LINKS

T. D. Noe and Alois P. Heinz, Table of n, a(n) for n = 0..450 (first 101 terms from T. D. Noe)

Joel Barnes, Conformal welding of uniform random trees, Ph. D. Dissertation, Univ. Washington, 2014.

A. Edelman, M. La Croix, The Singular Values of the GUE (Less is More), arXiv preprint arXiv:1410.7065 [math.PR], 2014-2015. See Table 1.

A. Ghitza and A. McAndrew, Experimental evidence for Maeda's conjecture on modular forms, arXiv preprint arXiv:1207.3480, 2012.

Dmitry Kruchinin, Integer properties of a composition of exponential generating functions, arXiv:1211.2100

Qingchun Ren, Ordered Partitions and Drawings of Rooted Plane Trees, arXiv preprint arXiv:1301.6327, 2013. See Lemma 15.

J. Sondow, A faster product for Pi and a new integral for ln(Pi/2), Amer. Math. Monthly 112 (2005), 729-734 and 113 (2006), 670.

Index entries for sequences related to groups

FORMULA

E.g.f.: sqrt(1-x^2)/(1-x) = sqrt((1+x)/(1-x)).

a(2*n) = (2*n-1)*a(2*n-1), a(2*n+1) = (2*n+1)*a(2n).

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

a(n) = sum((2k)! * C(n-1, 2k) * a(n-2k-1), k=0 to floor((n-1)/2)) for n>0. - Noam Katz (noamkj(AT)hotmail.com), Feb 27 2001

Also successive denominators of Wallis's approximation to Pi/2 (unreduced): 2/1 * 2/3 * 4/3 * 4/5 * 6/5 * 6/7 * ...

a(n) = a(n-1)+(n-1)*(n-2)*a(n-2). - Benoit Cloitre, Aug 30 2003

a(n) is asymptotic to (n-1)!*sqrt(2*n/Pi). - Benoit Cloitre, Jan 19 2004

a(n) = n! * C(n-1, [(n-1)/2]) / 2^(n-1), n>0. - Ralf Stephan, Mar 22 2004

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

a(n+1) = a(n) + a(n-1) * A002378(n-2). - Reinhard Zumkeller, Feb 27 2012

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

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

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

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

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

MATHEMATICA

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

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

PROG

(PARI) a(n)=if(n<1, !n, a(n-1)*(n+n%2-1))

(PARI) Vec( serlaplace( sqrt( (1+x)/(1-x) + O(x^55) ) ) )

(PARI) a(n)=prod(k=3, n, k+k%2-1) \\ Charles R Greathouse IV, May 01 2015

(PARI) a(n)=(n!/(n\2)!>>(n\2))^2/if(n%2, n, 1) \\ Charles R Greathouse IV, May 01 2015

(Haskell)

a000246 n = a000246_list !! n

a000246_list = 1 : 1 : zipWith (+)

   (tail a000246_list) (zipWith (*) a000246_list a002378_list)

-- Reinhard Zumkeller, Feb 27 2012

(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

CROSSREFS

Cf. A001900, A059838, A002867.

Bisections are A001818 and A079484.

Row sums of unsigned triangle A049218 and of A111594, A262125.

Main diagonal of A262124.

Cf. A002019.

Sequence in context: A262133 A262134 A262135 * A247006 A103620 A138315

Adjacent sequences:  A000243 A000244 A000245 * A000247 A000248 A000249

KEYWORD

nonn

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 May 23 08:43 EDT 2017. Contains 286909 sequences.