login
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)
12

%I M2872 N1154 #68 Apr 24 2018 16:52:44

%S 1,1,3,10,53,265,1700,13097,96796,829080,8009815,75604892,808861988,

%T 9175286549,106167118057,1320388106466,16950041305210,233232366601078,

%U 3243603207488124,47776065074368313,733990397879859192,11515503147927664816,189107783918416912912

%N 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.

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

%C 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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A002873/b002873.txt">Table of n, a(n) for n = 0..514</a>

%H Victor Meally, <a href="/A002868/a002868.pdf">Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders..."</a>, letter to N. J. A. Sloane, N. D.

%H T. S. Motzkin, <a href="/A000262/a000262.pdf">Sorting numbers for cylinders and other classification numbers</a>, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]

%H OEIS Wiki, <a href="http://oeis.org/wiki/Sorting_numbers">Sorting numbers</a>

%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>

%e 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.

%e 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.

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

%Y Maximum row values of A293181.

%K nonn,nice

%O 0,3

%A _N. J. A. Sloane_

%E Name changed and example added by _Jörgen Backelin_, Jan 13 2016

%E a(7)-a(8) from _Sean A. Irvine_, Jun 19 2016

%E a(9)-a(22) from _Andrew Howroyd_, Oct 01 2017