This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002873 The maximal number of partitions of {1..2n} that are invariant under a permutation consisting of n 2-cycles, and which have the same number of nonempty parts.
(Formerly M2872 N1154)
1, 1, 3, 10, 53, 265, 1700, 13097, 96796, 829080, 8009815, 75604892, 808861988, 9175286549, 106167118057, 1320388106466, 16950041305210, 233232366601078, 3243603207488124, 47776065074368313, 733990397879859192, 11515503147927664816, 189107783918416912912 (list; graph; refs; listen; history; text; internal format)



Previous name was: Sorting numbers (see Motzkin article for details).

Since a(n) by definition is the largest among some positive integers, whose sum is A002872(n), we always have the relation a(n) <= A002872(n); and for n > 0 the inequality is strict, since then that sum consists of more than one term. - Jörgen Backelin, Jan 13 2016


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


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

Victor Meally, Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.

T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]

OEIS Wiki, Sorting numbers

Index entries for sequences related to sorting


There are three partitions of {1,2,3,4} into two (nonempty) parts, and which are invariant under the permutation (1,2)(3,4), namely {{1,2}, {3,4}}, {{1,3}, {2,4}}, and {{1,4}, {2,3}}. There are also one such partition with just one part, two with three parts, and one with four parts; but three is the largest of these amounts. Thus, a(2) = 3.

Similarly, there are ten (1,2)(3,4)(5,6) invariant partitions of {1,2,3,4,5,6} into three nonempty parts, and no larger amount into any other given number of parts, whence a(3) = 10.


Cf. A000262 (the parent sequence of this family), A002872.

Maximum row values of A293181.

Sequence in context: A013201 A052446 A290489 * A042171 A133148 A189815

Adjacent sequences:  A002870 A002871 A002872 * A002874 A002875 A002876




N. J. A. Sloane


Name changed and example added by Jörgen Backelin, Jan 13 2016

a(7)-a(8) from Sean A. Irvine, Jun 19 2016

a(9)-a(22) from Andrew Howroyd, Oct 01 2017



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 April 21 10:30 EDT 2019. Contains 322328 sequences. (Running on oeis4.)