A171979 Number of partitions of n such that smaller parts do not occur more frequently than greater parts.

1, 1, 2, 3, 4, 5, 8, 8, 12, 14, 19, 21, 30, 31, 42, 50, 62, 69, 91, 99, 126, 144, 175, 198, 246, 275, 331, 379, 452, 509, 612, 686, 811, 922, 1076, 1219, 1428, 1604, 1863, 2108, 2434, 2739, 3162, 3551, 4075, 4593, 5240, 5885, 6721, 7527, 8556, 9597, 10870

Offset: 0

Author

Reinhard Zumkeller, Jan 20 2010

Keywords

• nonn

Comments

A000009(n) <= a(n) <= A000041(n).

Equivalently, the number of partitions of n such that (maximal multiplicity of parts) = (multiplicity of the maximal part), as in the Mathematica program. - Clark Kimberling, Apr 04 2014

Also the number of integer partitions of n whose greatest part is a mode, meaning it appears at least as many times as each of the others. The name "Number of partitions of n such that smaller parts do not occur more frequently than greater parts" seems to describe A100882 = "Number of partitions of n in which the sequence of frequencies of the summands is nonincreasing," which first differs from this at n = 10 due to the partition (3,3,2,1,1). - Gus Wiseman, May 07 2023

Examples

			a(5) = #{5, 4+1, 3+2, 2+2+1, 5x1} = 5;
a(6) = #{6, 5+1, 4+2, 3+3, 3+2+1, 2+2+2, 2+2+1+1, 6x1} = 8;
a(7) = #{7, 6+1, 5+2, 4+3, 4+2+1, 3+3+1, 2+2+2+1, 7x1} = 8;
a(8) = #{8, 7+1, 6+2, 5+3, 5+2+1, 4+4, 4+3+1, 3+3+2, 3+3+1+1, 2+2+2+2, 2+2+2+1+1, 8x1} = 12.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for sequences related to partitions

Crossrefs

For median instead of mode we have A053263.

The complement is counted by A240302.

The case where the maximum is the only mode is A362612.

A000041 counts integer partitions, strict A000009.

A362608 counts partitions with a unique mode, complement A362607.

A362611 counts modes in prime factorization.

A362614 counts partitions by number of modes.

Cf. A002865, A008284, A098859, A237984, A275870, A325347, A362610.

Programs

Mathematica

z = 60; f[n_] := f[n] = IntegerPartitions[n]; m[p_] := Max[Map[Length, Split[p]]]  (* maximal multiplicity *)
Table[Count[f[n], p_ /; m[p] == Count[p, Max[p]]], {n, 0, z}] (* this sequence *)
Table[Count[f[n], p_ /; m[p] > Count[p, Max[p]]], {n, 0, z}]  (* A240302 *)
(* Clark Kimberling, Apr 04 2014 *)
(* Second program: *)
b[n_, i_, k_] := b[n, i, k] = If[n == 0, If[k == 0, 1, 0],
     If[i < 1, 0, b[n, i - 1, k] + Sum[b[n - i*j, i - 1,
     If[k == -1, j, If[k == 0, 0, If[j > k, 0, k]]]], {j, 1, n/i}]]];
a[n_] := PartitionsP[n] - b[n, n, -1];
a /@ Range[0, 70] (* Jean-François Alcover, Jun 05 2021, after Alois P. Heinz in A240302 *)
Table[Length[Select[IntegerPartitions[n],MemberQ[Commonest[#],Max[#]]&]],{n,0,30}] (* Gus Wiseman, May 07 2023 *)

PARI

{ my(N=53, x='x+O('x^N));
my(gf=1+sum(i=1,N,sum(j=1,floor(N/i),x^(i*j)*prod(k=1,i-1,(1-x^(k*(j+1)))/(1-x^k)))));
Vec(gf) } \\ John Tyler Rascoe, Mar 09 2024

Formula

a(n) = p(n,0,1,1) with p(n,i,j,k) = if k<=n then p(n-k,i,j+1,k) +p(n,max(i,j),1,k+1) else (if j0 then 0 else 1).

a(n) + A240302(n) = A000041(n). - Clark Kimberling, Apr 04 2014.

G.f.: 1 + Sum_{i, j>0} x^(i*j) * Product_{k=1..i-1} ((1 - x^(k*(j+1)))/(1 - x^k)). - John Tyler Rascoe, Mar 09 2024