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

0, 0, 1, 2, 4, 7, 11, 17, 25, 36, 50, 70, 94, 127, 168, 222, 288, 375, 480, 616, 781, 990, 1243, 1562, 1945, 2422, 2996, 3703, 4550, 5588, 6826, 8332, 10126, 12292, 14865, 17958, 21618, 25995, 31165, 37317, 44562

Offset

1,4

Comments

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

Also the number of graphical partitions of 2n into n parts. - Gus Wiseman, Jan 08 2021

References

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

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

Links

Table of n, a(n) for n=1..41.

T. M. Barnes and C. D. Savage, A recurrence for counting graphical partitions, Electronic J. Combinatorics, 2 (1995).

N. Metropolis and P. R. Stein, The enumeration of graphical partitions, Europ. J. Combin., 1 (1980), 139-1532.

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). [Annotated scanned copy]

Eric Weisstein's World of Mathematics. Spider Graph

Wikipedia, Starlike tree

Index entries for sequences related to graphical partitions

Formula

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

a(n) = A000041(n) - floor((n+2)/2) = A000041(n)-A004526(n+1) = A058984(n)-1. - Vladeta Jovovic, Jun 18 2003

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

a(n) = A259873(n,n). - Gus Wiseman, Jan 08 2021

Example

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].
From Gus Wiseman, Jan 18 2021: (Start)
The a(3) = 1 through a(7) = 11 graphical partitions of 2n into n parts:
  (222)  (2222)  (22222)  (222222)  (2222222)
         (3221)  (32221)  (322221)  (3222221)
                 (33211)  (332211)  (3322211)
                 (42211)  (333111)  (3332111)
                          (422211)  (4222211)
                          (432111)  (4322111)
                          (522111)  (4331111)
                                    (4421111)
                                    (5222111)
                                    (5321111)
                                    (6221111)
(End)

Maple

with(combinat);
for i from 1 to 15 do pik(i, 3) od;
pik:= proc(n::integer, k::integer)
# Thomas Wieder, Jan 30 2007
local i, Liste, Result;
if k > n or n < 0 or k < 1 then
return fail
end if;
Result := 0;
for i from k to n do
Liste:= PartitionList(n, i);
#print(Liste);
Result := Result + nops(Liste);
end do;
return Result;
end proc;
PartitionList := proc (n, k)
# Authors: Herbert S. Wilf and Joanna Nordlicht. Source: Lecture Notes
# "East Side West Side, ..." University of Pennsylvania, USA, 2002.
# Available at: http://www.cis.upenn.edu/~wilf/lecnotes.html
# Calculates the partition of n into k parts.
# E.g. PartitionList(5, 2) --> [[4, 1], [3, 2]].
local East, West;
if n < 1 or k < 1 or n < k then
RETURN([])
elif n = 1 then
RETURN([[1]])
else if n < 2 or k < 2 or n < k then
West := []
else
West := map(proc (x) options operator, arrow;
[op(x), 1] end proc, PartitionList(n-1, k-1)) end if;
if k <= n-k then
East := map(proc (y) options operator, arrow;
map(proc (x) options operator, arrow; x+1 end proc, y) end proc, PartitionList(n-k, k))
else East := [] end if;
RETURN([op(West), op(East)])
end if;
end proc;
#  Thomas Wieder, Feb 01 2007
ZL :=[S, {S = Set(Cycle(Z), 3 <= card)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=1..41); # Zerinvary Lajos, Mar 25 2008
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

Mathematica

Length /@ Table[Select[Partitions[n], Length[#] > 2 &], {n, 20}] (* Eric W. Weisstein, May 16 2007 *)
Table[Count[Length /@ Partitions[n], _?(# > 2 &)], {n, 20}] (* Eric W. Weisstein, May 16 2017 *)
Table[PartitionsP[n] - Floor[n/2] - 1, {n, 20}] (* Eric W. Weisstein, May 16 2017 *)
Length /@ Table[IntegerPartitions[n, {3, n}], {n, 20}] (* Eric W. Weisstein, May 16 2017 *)

Prog

(PARI) a(n) = numbpart(n) - (n+2)\2; /* Joerg Arndt, Apr 03 2013 */

Crossrefs

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

Rightmost column of A259873.

Central column of A339659.

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

A000569 counts graphical partitions, ranked by A320922.

A008284 counts partitions by sum and length.

A027187 counts partitions of even length.

A309356 ranks simple covering graphs.

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

- A209816 counts multigraphical partitions (A320924).

- A320921 counts connected graphical partitions (A320923).

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

- A339656 counts loop-graphical partitions (A339658).

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

Partial sums of A117995.

Sequence in context: A007000 A073472 A096914 * A289060 A194805 A084842

Adjacent sequences: A004247 A004248 A004249 * A004251 A004252 A004253

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

Definition corrected by Thomas Wieder, Feb 01 2007 and by Eric W. Weisstein, May 16 2007

Status

approved