login
Number of partitions of n into 3 or more parts.
(Formerly M1046)
37

%I M1046 #79 Aug 01 2024 21:50:03

%S 0,0,1,2,4,7,11,17,25,36,50,70,94,127,168,222,288,375,480,616,781,990,

%T 1243,1562,1945,2422,2996,3703,4550,5588,6826,8332,10126,12292,14865,

%U 17958,21618,25995,31165,37317,44562

%N Number of partitions of n into 3 or more parts.

%C Number of (n+1)-vertex spider graphs: trees with n+1 vertices and exactly 1 vertex of degree at least 3 (i.e. branching vertex). There is a trivial bijection with the objects described in the definition. - _Emeric Deutsch_, Feb 22 2014

%C Also the number of graphical partitions of 2n into n parts. - _Gus Wiseman_, Jan 08 2021

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978).

%H T. M. Barnes and C. D. Savage, <a href="https://doi.org/10.37236/1205">A recurrence for counting graphical partitions</a>, Electronic J. Combinatorics, 2 (1995).

%H N. Metropolis and P. R. Stein, <a href="https://doi.org/10.1016/S0195-6698(80)80048-5">The enumeration of graphical partitions</a>, Europ. J. Combin., 1 (1980), 139-1532.

%H P. R. Stein, <a href="/A004250/a004250.pdf">On the number of graphical partitions</a>, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). [Annotated scanned copy]

%H Eric Weisstein's World of Mathematics. <a href="http://mathworld.wolfram.com/SpiderGraph.html">Spider Graph</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Starlike_tree">Starlike tree</a>

%H <a href="/index/Gra#graph_part">Index entries for sequences related to graphical partitions</a>

%F G.f.: Sum_{n>=0} (q^n / Product_{k=1..n+3} (1 - q^k)). - _N. J. A. Sloane_

%F a(n) = A000041(n) - floor((n+2)/2) = A000041(n)-A004526(n+1) = A058984(n)-1. - _Vladeta Jovovic_, Jun 18 2003

%F Let P(n,i) denote the number of partitions of n into i parts. Then a(n) = Sum_{i=3..n} P(n,i). - _Thomas Wieder_, Feb 01 2007

%F a(n) = A259873(n,n). - _Gus Wiseman_, Jan 08 2021

%e a(6)=7 because there are three partitions of n=6 with i=3 parts: [4, 1, 1], [3, 2, 1], [2, 2, 2] and two partitions with i=4 parts: [3, 1, 1, 1], [2, 2, 1, 1] and one partition with i=5 parts: [2, 1, 1, 1, 1] and one partition with i=6 parts: [1, 1, 1, 1, 1, 1].

%e From _Gus Wiseman_, Jan 18 2021: (Start)

%e The a(3) = 1 through a(7) = 11 graphical partitions of 2n into n parts:

%e (222) (2222) (22222) (222222) (2222222)

%e (3221) (32221) (322221) (3222221)

%e (33211) (332211) (3322211)

%e (42211) (333111) (3332111)

%e (422211) (4222211)

%e (432111) (4322111)

%e (522111) (4331111)

%e (4421111)

%e (5222111)

%e (5321111)

%e (6221111)

%e (End)

%p with(combinat);

%p for i from 1 to 15 do pik(i,3) od;

%p pik:= proc(n::integer, k::integer)

%p # _Thomas Wieder_, Jan 30 2007

%p local i, Liste, Result;

%p if k > n or n < 0 or k < 1 then

%p return fail

%p end if;

%p Result := 0;

%p for i from k to n do

%p Liste:= PartitionList(n,i);

%p #print(Liste);

%p Result := Result + nops(Liste);

%p end do;

%p return Result;

%p end proc;

%p PartitionList := proc (n, k)

%p # Authors: Herbert S. Wilf and Joanna Nordlicht. Source: Lecture Notes

%p # "East Side West Side,..." University of Pennsylvania, USA, 2002.

%p # Available at: http://www.cis.upenn.edu/~wilf/lecnotes.html

%p # Calculates the partition of n into k parts.

%p # E.g. PartitionList(5,2) --> [[4, 1], [3, 2]].

%p local East, West;

%p if n < 1 or k < 1 or n < k then

%p RETURN([])

%p elif n = 1 then

%p RETURN([[1]])

%p else if n < 2 or k < 2 or n < k then

%p West := []

%p else

%p West := map(proc (x) options operator, arrow;

%p [op(x), 1] end proc,PartitionList(n-1,k-1)) end if;

%p if k <= n-k then

%p East := map(proc (y) options operator, arrow;

%p map(proc (x) options operator, arrow; x+1 end proc,y) end proc,PartitionList(n-k,k))

%p else East := [] end if;

%p RETURN([op(West), op(East)])

%p end if;

%p end proc;

%p # _Thomas Wieder_, Feb 01 2007

%p ZL :=[S, {S = Set(Cycle(Z),3 <= card)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=1..41); # _Zerinvary Lajos_, Mar 25 2008

%p B:=[S,{S = Set(Sequence(Z,1 <= card),card >=3)},unlabelled]: seq(combstruct[count](B, size=n), n=1..41); # _Zerinvary Lajos_, Mar 21 2009

%t Length /@ Table[Select[Partitions[n], Length[#] > 2 &], {n, 20}] (* _Eric W. Weisstein_, May 16 2007 *)

%t Table[Count[Length /@ Partitions[n], _?(# > 2 &)], {n, 20}] (* _Eric W. Weisstein_, May 16 2017 *)

%t Table[PartitionsP[n] - Floor[n/2] - 1, {n, 20}] (* _Eric W. Weisstein_, May 16 2017 *)

%t Length /@ Table[IntegerPartitions[n, {3, n}], {n, 20}] (* _Eric W. Weisstein_, May 16 2017 *)

%o (PARI) a(n) = numbpart(n) - (n+2)\2; /* _Joerg Arndt_, Apr 03 2013 */

%Y Cf. A004251, A029889, A035300, A095268, A058984.

%Y Rightmost column of A259873.

%Y Central column of A339659.

%Y A000041 counts partitions of 2n into n parts, ranked by A340387.

%Y A000569 counts graphical partitions, ranked by A320922.

%Y A008284 counts partitions by sum and length.

%Y A027187 counts partitions of even length.

%Y A309356 ranks simple covering graphs.

%Y The following count vertex-degree partitions and give their Heinz numbers:

%Y - A209816 counts multigraphical partitions (A320924).

%Y - A320921 counts connected graphical partitions (A320923).

%Y - A339617 counts non-graphical partitions of 2n (A339618).

%Y - A339656 counts loop-graphical partitions (A339658).

%Y Cf. A000070, A000219, A339560, A339561, A339661.

%Y Partial sums of A117995.

%K nonn,easy

%O 1,4

%A _N. J. A. Sloane_

%E Definition corrected by _Thomas Wieder_, Feb 01 2007 and by _Eric W. Weisstein_, May 16 2007