%I #95 Apr 09 2022 06:43:42
%S 1,1,1,2,3,4,6,8,12,16,22,29,40,52,69,90,118,151,195,248,317,400,505,
%T 632,793,985,1224,1512,1867,2291,2811,3431,4186,5084,6168,7456,9005,
%U 10836,13026,15613,18692,22316,26613,31659,37619,44601,52815,62416,73680,86809,102162
%N Number of cycle types of conjugacy classes of all even permutations of n elements.
%C Also number of partitions of n with even number of even parts. There is no restriction on the odd parts.
%C a(n) = u(n) + v(n), n >= 2, of the Osima reference, p. 383.
%C Also number of partitions of n with largest part congruent to n modulo 2: a(2*n) = A027187(2*n), a(2*n-1) = A027193(2*n-1); a(n) = A000041(n) - A000701(n). - _Reinhard Zumkeller_, Apr 22 2006
%C Equivalently, number of partitions of n with number of parts having the same parity as n. - _Olivier Gérard_, Apr 04 2012
%C Also number of distinct free Young diagrams (Ferrers graphs with n nodes). Free Young diagrams are distinct when none is a rigid transformation (translation, rotation, reflection or glide reflection) of another. - _Jani Melik_, May 08 2016
%C Let the cycle type of an even permutation be represented by the partition A=(O1,O2,...,Oi,E1,E2,...,E2j), where the Os are parts with odd length and the Es are parts with even lengths, and where j may be zero, using Reinhard Zumkeller's observation that the partition associated with a cycle type of an even permutation has an even number of even parts. The set of even cycle types enumerated here can be considered a monoid under a binary operation *: Let A be as above and B=(o1,o2,...,ok,e1,e2,...,e2m). A*B is the partition (O1o1,O1o2,...,O1ok,O1e1,...,O1e2m,O2o1,...,O2e2m,...,Oio1,...,Oie2m,E1o1,...,E1e2m,...,E2je2m). This product has 2im+2jk+4jm even parts, so it represents the cycle type of an even permutation. - _Richard Locke Peterson_, Aug 20 2018
%C From _Gus Wiseman_, Mar 31 2022: (Start)
%C Also the number of integer partitions of n with Heinz number greater than or equal to that of their conjugate, where the Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). These partitions are ranked by A352488. The complement is counted by A000701. For example, the a(n) partitions for n = 1...7 are:
%C (1) (11) (21) (22) (221) (222) (331)
%C (111) (211) (311) (321) (2221)
%C (1111) (2111) (2211) (3211)
%C (11111) (3111) (4111)
%C (21111) (22111)
%C (111111) (31111)
%C (211111)
%C (1111111)
%C Also the number of integer partitions of n with Heinz number less than or equal to their conjugate, ranked by A352489. For example, the a(n) partitions for n = 1...7 are:
%C (1) (2) (3) (4) (5) (6) (7)
%C (21) (22) (32) (33) (43)
%C (31) (41) (42) (52)
%C (311) (51) (61)
%C (321) (322)
%C (411) (421)
%C (511)
%C (4111)
%C (End)
%H Seiichi Manyama, <a href="/A046682/b046682.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1000 from T. D. Noe)
%H George E. Andrews, David Newman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Andrews/andrews5.html">The Minimal Excludant in Integer Partitions</a>, J. Int. Seq., Vol. 23 (2020), Article 20.2.3.
%H J. Huh and B. Kim, <a href="https://doi.org/10.1142/S1793042120500475">The number of equivalence classes arising from partition involutions</a>, Int. J. Number Theory, 16 (2020), 925-939.
%H M. Osima, <a href="http://dx.doi.org/10.4153/CJM-1952-034-x">On the irreducible representations of the symmetric group</a>, Canad. J. Math., 4 (1952), 381-384.
%H Sheila Sundaram, <a href="https://arxiv.org/abs/1808.01416">On a positivity conjecture in the character table of S_n</a>, arXiv:1808.01416 [math.CO], 2018.
%F G.f.: Sum_{n>=0} (-q^2)^(n^2) / Product_{m>=1} (1-q^m ) = ( 1/Product_{m>=1} (1-q^m) + Product_{m>=1} (1+q^(2*m-1) ) ) / 2. - _Mamuka Jibladze_, Sep 07 2003
%F a(n) = (A000041(n) + A000700(n)) / 2.
%F a(n) = A000041(n) - A000701(n). - _Gus Wiseman_, Mar 31 2022
%e 1 + x + x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 6*x^6 + 8*x^7 + 12*x^8 + 16*x^9 + ...
%e a(3)=2 since cycle types of even permutations of 3 elements is (.)(.)(.), (...).
%e a(4)=3 since cycle types of even permutations of 4 elements is (.)(.)(.)(.), (...)(.), (..)(..).
%e a(5)=4 (free Young diagrams):
%e XXXXX XXXX. XXX.. XXX..
%e ..... X.... XX... X....
%e ..... ..... ..... X....
%e ..... ..... ..... .....
%e ..... ..... ..... .....
%p seq(add((-1)^(n-k)*combinat:-numbpart(n,k),k=0..n),n=0..48); # _Peter Luschny_, Aug 03 2015
%t max = 48; f[q_] := Sum[(-q^2)^n^2, {n, 0, max}]/Product[1-q^n, {n, 1, max}]; CoefficientList[ Series[f[q], {q, 0, max}], q] (* _Jean-François Alcover_, Oct 18 2011, after g.f. *)
%t conj[y_]:=If[Length[y]==0,y,Table[Length[Select[y,#>=k&]],{k,1,Max[y]}]];
%t Table[Length[Select[IntegerPartitions[n],Times@@Prime/@#>=Times@@Prime/@conj[#]&]],{n,0,15}] (* _Gus Wiseman_, Mar 31 2022 *)
%o (PARI) list(lim)=my(q='q);Vec(sum(n=0,sqrt(lim),(-q^2)^(n^2))/prod(n=1,lim,1-q^n)+O(q^(lim\1+1))) \\ _Charles R Greathouse IV_, Oct 18 2011
%o (PARI) {a(n) = if( n<0, 0, (numbpart(n) + polcoeff( 1 / prod( k=1, n, 1 + (-x)^k, 1 + x * O(x^n)), n)) / 2)} /* _Michael Somos_, Jul 24 2012 */
%Y Cf. A000701, A006950, A015128.
%Y For the number of conjugacy classes of the alternating group A_n, n>=2, see A000702.
%Y Cf. A118301.
%Y A000041 counts integer partitions.
%Y A000700 counts self-conjugate partitions, ranked by A088902.
%Y A330644 counts non-self-conjugate partitions, ranked by A352486.
%Y Heinz number (rank) and partition:
%Y - A122111 = rank of conjugate.
%Y - A296150 = parts of partition, conjugate A321649.
%Y - A352487 = rank less than conjugate, counted by A000701.
%Y - A352488 = rank greater than or equal to conjugate, counted by A046682.
%Y - A352489 = rank less than or equal to conjugate, counted by A046682.
%Y - A352490 = rank greater than conjugate, counted by A000701.
%Y - A352491 = rank minus conjugate.
%Y Cf. A114088, A115994, A171966, A238352, A258116, A321648, A325039.
%K nonn,nice
%O 0,4
%A _Vladeta Jovovic_