login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A066052 Number of permutations in the symmetric group S_n with order >= 3. 3
0, 0, 2, 14, 94, 644, 4808, 39556, 360260, 3619304, 39881104, 478861448, 6226452296, 87175900720, 1307664018464, 20922743681264, 355687216296688, 6402372708414176, 121645095599130560, 2432901984417975904, 51090942051756747104, 1124000727158723041088, 25852016735627132757376 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Permutations which contain a cycle with length >=3.

For elements of order >= 3 we can show that they can be represented as a product of two involutions. [Proof: Write down the reduced cycle representation of the element. Decompose each sub-cycle of order >=3 into a product of two involutions, and distribute/merge the 1 or 2 factors of the involutions. For sub-cycles of order o>=3 it suffices to show that the reduced cycle (1 2 3 4 ... o), equivalent to the 1-line representation (2 3 4 .. o 1), can be written as a product of 2 involutions, because other cycles are mapped to such a product by a fixed permutation. A constructive proof here is: the reduced cycle (1 2 3 4 ... o) is the product of the two involutions (1 2)(3 o)(4 o-1)(5 o-2)... and (2 o)(3 o-1)... The first involution swaps the first two elements and reverts the ordering of all others from the 3rd on, then the second involution reverts the order of the elements from the 2nd on. The net effect is a cyclic shift of the o elements.] - R. J. Mathar, Jan 04 2017

a(n) is the number of permutations of [n] that are not involutions (see first formula). - Joerg Arndt, Jul 06 2020

LINKS

Table of n, a(n) for n=1..23.

FORMULA

a(n) = n! - A000085(n).

E.g.f.: 1/(1-x) - exp(x*(x+2)/2).

Conjecture: (-n+3)*a(n) +(n^2-2*n-1)*a(n-1) +(-n+1)*a(n-2) -(n-1)*(n-2)^2*a(n-3)=0. - R. J. Mathar, Jan 04 2017

Conjecture: a(n) +(-n-3)*a(n-1) +(2*n-1)*a(n-2) +n*(n-2)*a(n-3) -2*(n-2)*(n-3)*a(n-4)=0. - R. J. Mathar, Jan 04 2017

MATHEMATICA

nn=20; Range[0, nn]! CoefficientList[Series[1/(1-x)-Exp[x+x^2/2], {x, 0, nn}], x]  (* Geoffrey Critzer, Jan 09 2013 *)

CROSSREFS

Cf. A000085, A000142.

Sequence in context: A270063 A033169 A090410 * A122057 A164891 A141146

Adjacent sequences:  A066049 A066050 A066051 * A066053 A066054 A066055

KEYWORD

nonn,easy

AUTHOR

Sharon Sela (sharonsela(AT)hotmail.com), Dec 29 2001

EXTENSIONS

More terms from Vladeta Jovovic, Dec 31 2001

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 9 18:55 EDT 2022. Contains 356026 sequences. (Running on oeis4.)