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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A212419 Size of the equivalence class of S_n containing the identity permutation under transformations of positionally adjacent elements of the form abc <--> acb <--> bac <--> cba, where a<b<c. 1
1, 1, 1, 4, 21, 116, 713, 5030, 40301, 362852, 3628744, 39916716, 479001426, 6227020536, 87178290639, 1307674367142, 20922789886141, 355687428093140, 6402373705721708, 121645100408822276, 2432902008176618342, 51090942171709406408, 1124000727777607604418 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Pierrot, Rossin, and West were first to give a formula and the alternate characterization: all permutations in S_n except the alternating permutations in which the elements in odd positions form a decreasing sequence, and the elements in even positions also form a decreasing sequence.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..449

Steven Linton, James Propp, Tom Roby, and Julian West, Equivalence classes of permutations under various relations generated by constrained transpositions, 2011 arXiv:1111.3920 [math.CO], J. Int. Seq. 15 (2012) #12.9.1

A. Pierrot, D. Rossin, and J. West, Adjacent transformations in permutations, FPSAC 2011, Discrete Math. Theor. Comput. Sci. Proc., 2011.

FORMULA

a(n) = 1 for n<3, otherwise: a(n) = n!-C([(n-1)/2]-C([n/2]), where [x] is the floor function and C(n) denotes the n-th Catalan number (A000108).

MAPLE

C:= n-> binomial(2*n, n)/(n+1):

a:= n-> `if`(n<3, 1, n!-C(floor((n-1)/2))-C(floor(n/2))):

seq (a(n), n=0..30);  # Alois P. Heinz, May 20 2012

MATHEMATICA

Join[{1, 1, 1}, Table[n!-CatalanNumber[Floor[(n-1)/2]]-CatalanNumber[ Floor[ n/2]], {n, 3, 30}]] (* Harvey P. Dale, Dec 31 2013 *)

CROSSREFS

Sequence in context: A015554 A024051 A180908 * A020048 A318365 A093426

Adjacent sequences:  A212416 A212417 A212418 * A212420 A212421 A212422

KEYWORD

nonn

AUTHOR

Tom Roby, May 15 2012

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 24 00:12 EDT 2019. Contains 321444 sequences. (Running on oeis4.)