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