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