

A002865


Number of partitions of n that do not contain 1 as a part.
(Formerly M0309 N0113)


196



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

Also the number of partitions of n1, n>=2, such that the least part occurs exactly once. See A096373, A097091, A097092, A097093.  Robert G. Wilson v, Jul 24 2004 [Corrected by Wolfdieter Lang, Feb 18 2009]
a(n) = A116449(n) + A116450(n).  Reinhard Zumkeller, Feb 16 2006
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. AdamsWatters, May 01 2006
Number of partitions where the largest part occurs at least twice.  Joerg Arndt, Apr 17 2011
Row sums of triangle A147768.  Gary W. Adamson, Nov 11 2008
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 2regular multigraphs with loops forbidden.  Jason Kimberley, Jan 05 2011
Number of appearances of the multiplicity n, n1, ... , nk in all partitions of n, for k < n/2. (Only populated by multiplicities of large numbers of 1s.)  William Keith, Nov 20 2011
a(n) = A090824(n,1) for n > 0.  Reinhard Zumkeller, Oct 10 2012
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 qCatalan numbers ((1q)/(1q^(n+1)))[2n,n]_q, where [2n,n]_q are the central qbinomial 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 nonisomorphic graphs that can result from the path when the game of edge removal is played.  Lyndsey Wong, Jul 9 2016
The number of different ways to climb a staircase taking at least two stairs at a time.  Mohammad K. Azarian, Nov 20 2016


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

T. D. Noe and Andrew van den Hoeven, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
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].
G. Dahl, T. A. Haufmann, Zeroone completely positive matrices and the A(R,S) classes, Preprint, 2016.
R. P. Gallant, G. Gunther, B. L. Hartnell, D. F. Rall, A game of edge removal on graphs, JCMCC, 57 (2006), 75  82.
Edray Herber Goins and Talitha M. Washington, On the generalized climbing stairs problem, Ars Combin. 117 (2014), 183190. MR3243840 (Reviewed), arXiv:0909.5459 [math.CO], 2009.
H. Gropp, On tactical configurations, regular bipartite graphs and (v,k,even)designs, Discr. Math., 155 (1996), 8198.
R. K. Guy and N. J. A. Sloane, Correspondence, 1988.
Cristiano Husu, The butterfly sequence: the second difference sequence of the numbers of integer partitions with distinct parts, its pentagonal number structure, its combinatorial identities and the cyclotomic polynomials 1x and 1+x+x^2, arXiv:1804.09883 [math.NT], 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 100
Li, Wenwei, Approximation of the Partition Number After Hardy and Ramanujan: An Application of Data Fitting Method in Combinatorics, arXiv preprint arXiv:1612.05526 [math.NT], 20162018.
Wenwei Li, On the Number of Conjugate Classes of Derangements, arXiv:1612.08186 [math.CO], 2016.
J. L. Nicolas and A. Sárközy, On partitions without small parts, Journal de théorie des nombres de Bordeaux, 12 no. 1 (2000), p. 227254.
R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv:math/0606404 [math.CO], 20062007.
H. P. Robinson, Letter to N. J. A. Sloane, Jul 12 1971
H. P. Robinson, Letter to N. J. A. Sloane, Dec 10 1973
H. P. Robinson, Letter to N. J. A. Sloane, Jan 4 1974.
Index entries for related partitioncounting sequences


FORMULA

G.f.: Product_{m>1} 1/(1x^m).
a(0)=1, a(n) = p(n)p(n1), n>=1, with the partition numbers p(n) := A000041(n).
a(n) = A085811(n+3).  James A. Sellers, Dec 06 2005 [Corrected by Gionata Neri, Jun 14 2015]
a(n) = Sum(A008284(nk+1,k1): 1<k<=floor((n+2)/2) for n>0.  Reinhard Zumkeller, Nov 04 2007
G.f.: 1 + sum(n>=2, x^n / prod(k>=n, 1x^k)).  Joerg Arndt, Apr 13 2011
G.f.: sum(n>=0, x^(2*n) / prod(k=1..n, 1x^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


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


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:
a:= proc(n) option remember; `if`(n=0, 1, add(
(numtheory[sigma](j)1)*a(nj), j=1..n)/n)
end:
seq(a(n), n=0..60); # Alois P. Heinz, Sep 17 2017


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


PROG

(PARI) {a(n) = if( n<0, 0, polcoeff( (1  x) / eta(x + x * O(x^n)), n))};
(PARI) a(n)=if(n, numbpart(n)numbpart(n1), 1) \\ Charles R Greathouse IV, Nov 26 2012
(MAGMA) A41 := func<nn ge 0 select NumberOfPartitions(n) else 0>; [A41(n)A41(n1):n in [0..50]]; // Jason Kimberley, Jan 05 2011
(GAP) Concatenation([1], List([1..41], n>NrPartitions(n)NrPartitions(n1))); # Muniru A Asiru, Aug 20 2018


CROSSREFS

First differences of partition numbers A000041. Cf. A053445, A072380, A081094, A081095.
Pairwise sums seem to be in A027336.
Essentially the same as A085811.
Cf. A025147, A147768, A058682, A171239.
A column of A090824 and of A133687 and of A292508 and of A292622. Cf. A229161.
2regular 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 edgedelete game on the path P_{n} the first player does not have a winning strategy: A274161.  Lyndsey Wong, Jul 09 2016
Sequence in context: A035989 A240019 A036000 * A085811 A187219 A317785
Adjacent sequences: A002862 A002863 A002864 * A002866 A002867 A002868


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane


STATUS

approved



