|
| |
|
|
A002865
|
|
Number of partitions of n that do not contain 1 as a part.
(Formerly M0309 N0113)
|
|
339
|
|
|
|
1, 0, 1, 1, 2, 2, 4, 4, 7, 8, 12, 14, 21, 24, 34, 41, 55, 66, 88, 105, 137, 165, 210, 253, 320, 383, 478, 574, 708, 847, 1039, 1238, 1507, 1794, 2167, 2573, 3094, 3660, 4378, 5170, 6153, 7245, 8591, 10087, 11914, 13959, 16424, 19196, 22519, 26252, 30701
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
Number of partitions of n+1 where the number of parts is itself a part. Take a partition of n (with k parts) which does not contain 1, remove 1 from each part and add a new part of size k+1. - Franklin T. Adams-Watters, May 01 2006
Number of partitions where the largest part occurs at least twice. - Joerg Arndt, Apr 17 2011
From Lewis Mammel (l_mammel(AT)att.net), Oct 06 2009: (Start)
a(n) is the number of sets of n disjoint pairs of 2n things, called a pairing, disjoint with a given pairing (A053871), that are unique under permutations preserving the given pairing.
Can be seen immediately from a graphical representation which must decompose into even numbered cycles of 4 or more things, as connected by pairs alternating between the pairings. Each thing is in a single cycle, so this is a partition of 2n into even parts greater than 2, equivalent to a partition of n into parts greater than 1. (End)
Convolution product (1, 1, 2, 2, 4, 4, ...) * (1, 2, 3, ...) = A058682 starting (1, 3, 7, 13, 23, 37, ...); with row sums of triangle A171239 = A058682. - Gary W. Adamson, Dec 05 2009
Also the number of 2-regular multigraphs with loops forbidden. - Jason Kimberley, Jan 05 2011
Number of appearances of the multiplicity n, n-1, ..., n-k in all partitions of n, for k < n/2. (Only populated by multiplicities of large numbers of 1's.) - William Keith, Nov 20 2011
Also the number of equivalence classes of n X n binary matrices with exactly 2 1's in each row and column, up to permutations of rows and columns (cf. A133687). - N. J. A. Sloane, Sep 16 2013
The q-Catalan numbers ((1-q)/(1-q^(n+1)))[2n,n]_q, where [2n,n]_q are the central q-binomial coefficients, match this sequence in their initial segment of length n. - William J. Keith, Nov 14 2013
Starting at a(2) this sequence gives the number of vertices on a nim tree created in the game of edge removal for a path P_{n} where n is the number of vertices on the path. This is the number of non-isomorphic graphs that can result from the path when the game of edge removal is played. - Lyndsey Wong, Jul 09 2016
The number of different ways to climb a staircase taking at least two stairs at a time. - Mohammad K. Azarian, Nov 20 2016
Let 1,0,1,1,1,... (offset 0) count unlabeled, connected, loopless 1-regular digraphs. This here is the Euler transform of that sequence, counting unlabeled loopless 1-regular digraphs. A145574 is the associated multiset transformation. A000166 are the labeled loopless 1-regular digraphs. - R. J. Mathar, Mar 25 2019
For n > 1, also the number of partitions with no part greater than the number of ones. - George Beck, May 09 2019 [See A187219 which is the correct sequence for this interpretation for n >= 1. - Spencer Miller, Jan 30 2023]
Conjecture: Also the number of integer partitions of n - 1 that have a consecutive subsequence summing to each positive integer from 1 to n - 1. For example, (32211) is such a partition because we have consecutive subsequences:
1: (1)
2: (2)
3: (3) or (21)
4: (22) or (211)
5: (32) or (221)
6: (2211)
7: (322)
8: (3221)
9: (32211)
(End)
There is a sufficient and necessary condition to characterize the partitions defined by Gus Wiseman. It is that the largest part must be less than or equal to the number of ones plus one. Hence, the number of partitions of n with no part greater than the number of ones is the same as the number of partitions of n-1 that have a consecutive subsequence summing to each integer from 1 to n-1. Gus Wiseman's conjecture can be proved bijectively. - Andrew Yezhou Wang, Dec 14 2019
|
|
|
REFERENCES
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 836.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 115, p*(n).
H. P. Robinson, Letter to N. J. A. Sloane, Jan 04 1974.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
P. G. Tait, Scientific Papers, Cambridge Univ. Press, Vol. 1, 1898, Vol. 2, 1900, see Vol. 1, p. 334.
|
|
|
LINKS
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
|
|
|
FORMULA
|
G.f.: Product_{m>1} 1/(1-x^m).
a(0)=1, a(n) = p(n) - p(n-1), n >= 1, with the partition numbers p(n) := A000041(n).
G.f.: 1 + Sum_{n>=2} x^n / Product_{k>=n} (1 - x^k). - Joerg Arndt, Apr 13 2011
G.f.: Sum_{n>=0} x^(2*n) / Product_{k=1..n} (1 - x^k). - Joerg Arndt, Apr 17 2011
a(n) ~ Pi * exp(sqrt(2*n/3)*Pi) / (12*sqrt(2)*n^(3/2)) * (1 - (3*sqrt(3/2)/Pi + 13*Pi/(24*sqrt(6)))/sqrt(n) + (217*Pi^2/6912 + 9/(2*Pi^2) + 13/8)/n). - Vaclav Kotesovec, Feb 26 2015, extended Nov 04 2016
G.f.: exp(Sum_{k>=1} (sigma_1(k) - 1)*x^k/k). - Ilya Gutkovskiy, Aug 21 2018
G.f.: A(q) = Sum_{n >= 0} q^(n^2)/( (1 - q)*Product_{k = 2..n} (1 - q^k)^2 ).
More generally, A(q) = Sum_{n >= 0} q^(n*(n+r))/( (1 - q) * Product_{k = 2..n} (1 - q^k)^2 * Product_{i = 1..r} (1 - q^(n+i)) ) for r = 0,1,2,.... (End)
|
|
|
EXAMPLE
|
a(6) = 4 from 6 = 4+2 = 3+3 = 2+2+2.
G.f. = 1 + x^2 + x^3 + 2*x^4 + 2*x^5 + 4*x^6 + 4*x^7 + 7*x^8 + 8*x^9 + ...
The a(2) = 1 though a(9) = 8 partitions not containing 1 are the following. The Heinz numbers of these partitions are given by A005408.
(2) (3) (4) (5) (6) (7) (8) (9)
(22) (32) (33) (43) (44) (54)
(42) (52) (53) (63)
(222) (322) (62) (72)
(332) (333)
(422) (432)
(2222) (522)
(3222)
The a(2) = 1 though a(9) = 8 partitions of n - 1 whose least part appears exactly once are the following. The Heinz numbers of these partitions are given by A247180.
(1) (2) (3) (4) (5) (6) (7) (8)
(21) (31) (32) (42) (43) (53)
(41) (51) (52) (62)
(221) (321) (61) (71)
(331) (332)
(421) (431)
(2221) (521)
(3221)
The a(2) = 1 though a(9) = 8 partitions of n + 1 where the number of parts is itself a part are the following. The Heinz numbers of these partitions are given by A325761.
(21) (22) (32) (42) (52) (62) (72) (82)
(311) (321) (322) (332) (333) (433)
(331) (431) (432) (532)
(4111) (4211) (531) (631)
(4221) (4222)
(4311) (4321)
(51111) (4411)
(52111)
The a(2) = 1 though a(8) = 7 partitions of n whose greatest part appears at least twice are the following. The Heinz numbers of these partitions are given by A070003.
(11) (111) (22) (221) (33) (331) (44)
(1111) (11111) (222) (2221) (332)
(2211) (22111) (2222)
(111111) (1111111) (3311)
(22211)
(221111)
(11111111)
Non-isomorphic representatives of the a(2) = 1 through a(6) = 4 2-regular multigraphs with n edges and n vertices are the following.
{12,12} {12,13,23} {12,12,34,34} {12,12,34,35,45} {12,12,34,34,56,56}
{12,13,24,34} {12,13,24,35,45} {12,12,34,35,46,56}
{12,13,23,45,46,56}
{12,13,24,35,46,56}
The a(2) = 1 though a(9) = 8 partitions of n with no part greater than the number of ones are the following. The Heinz numbers of these partitions are given by A325762.
(11) (111) (211) (2111) (2211) (22111) (22211) (33111)
(1111) (11111) (3111) (31111) (32111) (222111)
(21111) (211111) (41111) (321111)
(111111) (1111111) (221111) (411111)
(311111) (2211111)
(2111111) (3111111)
(11111111) (21111111)
(111111111)
(End)
|
|
|
MAPLE
|
with(combstruct): ZL1:=[S, {S=Set(Cycle(Z, card>1))}, unlabeled]: seq(count(ZL1, size=n), n=0..50); # Zerinvary Lajos, Sep 24 2007
G:= {P=Set (Set (Atom, card>1))}: combstruct[gfsolve](G, unlabeled, x): seq (combstruct[count] ([P, G, unlabeled], size=i), i=0..50); # Zerinvary Lajos, Dec 16 2007
with(combstruct):a:=proc(m) [ZL, {ZL=Set(Cycle(Z, card>=m))}, unlabeled]; end: A:=a(2):seq(count(A, size=n), n=0..50); # Zerinvary Lajos, Jun 11 2008
# alternative Maple program:
A002865:= proc(n) option remember; `if`(n=0, 1, add(
(numtheory[sigma](j)-1)*A002865(n-j), j=1..n)/n)
end:
|
|
|
MATHEMATICA
|
Table[ PartitionsP[n + 1] - PartitionsP[n], {n, -1, 50}] (* Robert G. Wilson v, Jul 24 2004 *)
f[1, 1] = 1; f[n_, k_] := f[n, k] = If[n < 0, 0, If[k > n, 0, If[k == n, 1, f[n, k + 1] + f[n - k, k]]]]; Table[ f[n, 2], {n, 50}] (* Robert G. Wilson v *)
Table[SeriesCoefficient[Exp[Sum[x^(2*k)/(k*(1 - x^k)), {k, 1, n}]], {x, 0, n}], {n, 0, 50}] (* Vaclav Kotesovec, Aug 18 2018 *)
CoefficientList[Series[1/QPochhammer[x^2, x], {x, 0, 50}], x] (* G. C. Greubel, Nov 03 2019 *)
Table[Count[IntegerPartitions[n], _?(FreeQ[#, 1]&)], {n, 0, 50}] (* Harvey P. Dale, Feb 12 2023 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<0, 0, polcoeff( (1 - x) / eta(x + x * O(x^n)), n))};
(Magma) A41 := func<n|n ge 0 select NumberOfPartitions(n) else 0>; [A41(n)-A41(n-1):n in [0..50]]; // Jason Kimberley, Jan 05 2011
(GAP) Concatenation([1], List([1..41], n->NrPartitions(n)-NrPartitions(n-1))); # Muniru A Asiru, Aug 20 2018
(Sage)
P.<x> = PowerSeriesRing(ZZ, prec)
return P( 1/product((1-x^(m+2)) for m in (0..60)) ).list()
(Python)
from sympy import npartitions
def A002865(n): return npartitions(n)-npartitions(n-1) if n else 1 # Chai Wah Wu, Mar 30 2023
|
|
|
CROSSREFS
|
Pairwise sums seem to be in A027336.
2-regular not necessarily connected graphs: A008483 (simple graphs), A000041 (multigraphs with loops allowed), this sequence (multigraphs with loops forbidden), A027336 (graphs with loops allowed but no multiple edges). - Jason Kimberley, Jan 05 2011
See also A098743 (parts that do not divide n).
Numbers n such that in the edge-delete game on the path P_{n} the first player does not have a winning strategy: A274161. - Lyndsey Wong, Jul 09 2016
Row suns of characteristic array A145573.
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
