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

Offset

0,3

Comments

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

References

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

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

Example

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.

Crossrefs

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

Maximum row values of A293181.

Sequence in context: A052446 A362062 A290489 * A309910 A042171 A133148

Adjacent sequences: A002870 A002871 A002872 * A002874 A002875 A002876

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

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

Status

approved