|
| |
|
|
A000246
|
|
Number of permutations in the symmetric group S_n that have odd order.
(Formerly M2824 N1137)
|
|
47
|
|
|
|
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) 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
This conjecture has been confirmed, see Bernardi, Duplantier, Nadeau link.
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 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
Number of permutations in S_n in which all cycles have odd length. - Michael Somos, Mar 17 2019
|
|
|
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
|
|
|
|
FORMULA
|
E.g.f.: sqrt(1-x^2)/(1-x) = sqrt((1+x)/(1-x)).
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.
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_{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
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.
D-finite with recurrence: 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! * binomial(n-1, floor((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
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
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
a(n) = n! * Sum_{k = 0..n} (-1)^(n+k)*binomial(1/2, k)*binomial(-1/2, n-k).
a(n) = (1/4^n) * (2*n)!/n! * hypergeom([-1/2, -n], [1/2 - n], -1).
|
|
|
EXAMPLE
|
|
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<2, 1,
a(n-1) +(n-1)*(n-2)*a(n-2))
end:
|
|
|
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 *)
CoefficientList[Series[Sqrt[(1+x)/(1-x)], {x, 0, 50}], x]*Table[k!, {k, 0, 20}] (* Stefano Spezia, Oct 07 2018 *)
|
|
|
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) ) ) )
(Haskell)
a000246 n = a000246_list !! n
a000246_list = 1 : 1 : zipWith (+)
(tail a000246_list) (zipWith (*) a000246_list a002378_list)
(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
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
