login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A110618 Number of partitions of n with no part larger than n/2. Also partitions of n into n/2 or fewer parts. 5
1, 0, 1, 1, 3, 3, 7, 8, 15, 18, 30, 37, 58, 71, 105, 131, 186, 230, 318, 393, 530, 653, 863, 1060, 1380, 1686, 2164, 2637, 3345, 4057, 5096, 6158, 7665, 9228, 11395, 13671, 16765, 20040, 24418, 29098, 35251, 41869, 50460, 59755, 71669, 84626, 101050 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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

LINKS

Table of n, a(n) for n=0..46.

FORMULA

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

a(2*n) = A209816(n). - Gus Wiseman, Oct 30 2018

EXAMPLE

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.

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.

From Gus Wiseman, Oct 30 2018: (Start)

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

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

               (211)   (2111)   (222)     (331)      (332)

               (1111)  (11111)  (321)     (2221)     (422)

                                (2211)    (3211)     (431)

                                (3111)    (22111)    (2222)

                                (21111)   (31111)    (3221)

                                (111111)  (211111)   (3311)

                                          (1111111)  (4211)

                                                     (22211)

                                                     (32111)

                                                     (41111)

                                                     (221111)

                                                     (311111)

                                                     (2111111)

                                                     (11111111)

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

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

            (22)  (32)  (33)   (43)   (44)

            (31)  (41)  (42)   (52)   (53)

                        (51)   (61)   (62)

                        (222)  (322)  (71)

                        (321)  (331)  (332)

                        (411)  (421)  (422)

                               (511)  (431)

                                      (521)

                                      (611)

                                      (2222)

                                      (3221)

                                      (3311)

                                      (4211)

                                      (5111)

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):

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

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

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

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

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

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

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

(End)

MAPLE

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

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

MATHEMATICA

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 *)

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

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

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

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

Table[Length[Select[strnorm[n], multhyp[#]!={}&]], {n, 8}] (* Gus Wiseman, Oct 30 2018 *)

PROG

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

CROSSREFS

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

Sequence in context: A241642 A086543 A281616 * A320291 A320294 A304179

Adjacent sequences:  A110615 A110616 A110617 * A110619 A110620 A110621

KEYWORD

nonn

AUTHOR

Henry Bottomley, Aug 01 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 15 01:24 EDT 2021. Contains 342974 sequences. (Running on oeis4.)