login
Number of partitions of n with no part larger than n/2. Also partitions of n into n/2 or fewer parts.
27

%I #18 Aug 01 2019 00:07:48

%S 1,0,1,1,3,3,7,8,15,18,30,37,58,71,105,131,186,230,318,393,530,653,

%T 863,1060,1380,1686,2164,2637,3345,4057,5096,6158,7665,9228,11395,

%U 13671,16765,20040,24418,29098,35251,41869,50460,59755,71669,84626,101050

%N Number of partitions of n with no part larger than n/2. Also partitions of n into n/2 or fewer parts.

%C Also the number of integer partitions of n that are the vertex-degrees of some set multipartition (multiset of nonempty sets) with no singletons. - _Gus Wiseman_, Oct 30 2018

%F a(n) = A000041(n) - Sum_{i=0..floor((n-1)/2)} A000041(i) = A000041(n) - A000070(floor((n-1)/2)) = A110619(n, 2).

%F a(2*n) = A209816(n). - _Gus Wiseman_, Oct 30 2018

%e a(5) = 3 since 5 can be partitioned as 1+1+1+1+1, 2+1+1+1, or 2+2+1; not counted are 5, 4+1, or 3+2.

%e a(6) = 7 since 6 can be partitioned as 1+1+1+1+1+1, 1+1+1+1+2, 1+1+2+2, 2+2+2, 1+1+1+3, 1+2+3, 3+3; not counted are 1+1+4, 2+4, 1+5, 6.

%e From _Gus Wiseman_, Oct 30 2018: (Start)

%e The a(2) = 1 through a(8) = 15 partitions with no part larger than n/2:

%e (11) (111) (22) (221) (33) (322) (44)

%e (211) (2111) (222) (331) (332)

%e (1111) (11111) (321) (2221) (422)

%e (2211) (3211) (431)

%e (3111) (22111) (2222)

%e (21111) (31111) (3221)

%e (111111) (211111) (3311)

%e (1111111) (4211)

%e (22211)

%e (32111)

%e (41111)

%e (221111)

%e (311111)

%e (2111111)

%e (11111111)

%e The a(2) = 1 through a(8) = 15 partitions into n/2 or fewer parts:

%e (2) (3) (4) (5) (6) (7) (8)

%e (22) (32) (33) (43) (44)

%e (31) (41) (42) (52) (53)

%e (51) (61) (62)

%e (222) (322) (71)

%e (321) (331) (332)

%e (411) (421) (422)

%e (511) (431)

%e (521)

%e (611)

%e (2222)

%e (3221)

%e (3311)

%e (4211)

%e (5111)

%e The a(6) = 7 integer partitions of 6 with no part larger than n/2 together with a realizing set multipartition of each (the parts of the partition count the appearances of each vertex in the set multipartition):

%e (33): {{1,2},{1,2},{1,2}}

%e (321): {{1,2},{1,2},{1,3}}

%e (3111): {{1,2},{1,3},{1,4}}

%e (222): {{1,2,3},{1,2,3}}

%e (2211): {{1,2},{1,2,3,4}}

%e (21111): {{1,2},{1,3,4,5}}

%e (111111): {{1,2,3,4,5,6}}

%e (End)

%p A000070 := proc(n) add( combinat[numbpart](i),i=0..n) ; end proc:

%p A110618 := proc(n) combinat[numbpart](n) - A000070(floor((n-1)/2)) ; end proc: # _R. J. Mathar_, Jan 24 2011

%t f[n_, 1] := 1; f[1, k_] := 1; f[n_, k_] := f[n, k] = If[k > n, f[n, k - 1], f[n, k - 1] + f[n - k, k]]; g[n_] := f[n, Floor[n/2]]; g[0] = 1; g[1] = 0; Array[g, 47, 0] (* _Robert G. Wilson v_, Jan 23 2011 *)

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

%t multhyp[m_]:=Select[mps[m],And[And@@UnsameQ@@@#,Min@@Length/@#>1]&];

%t strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];

%t Table[Length[Select[strnorm[n],multhyp[#]!={}&]],{n,8}] (* _Gus Wiseman_, Oct 30 2018 *)

%o (PARI) a(n) = numbpart(n) - sum(i=0, if (n%2, n\2, n/2-1), numbpart(i)); \\ _Michel Marcus_, Oct 31 2018

%Y Cf. A000070, A000569, A025065, A049311, A096373, A116540, A147878, A209816, A283877, A306005, A320921.

%K nonn

%O 0,5

%A _Henry Bottomley_, Aug 01 2005