login
Number of partitions of n that do not contain 2 as a part.
39

%I #67 Nov 09 2023 12:13:57

%S 1,1,1,2,3,4,6,8,11,15,20,26,35,45,58,75,96,121,154,193,242,302,375,

%T 463,573,703,861,1052,1282,1555,1886,2277,2745,3301,3961,4740,5667,

%U 6754,8038,9548,11323,13398,15836,18678,22001,25873,30383,35620,41715,48771

%N Number of partitions of n that do not contain 2 as a part.

%C Pairwise sums of sequence A002865 (partitions in which the least part is at least 2).

%C Also number of partitions of n into parts with at most one 1. - _Reinhard Zumkeller_, Oct 25 2004

%C Also number of partitions of n into parts with at least half of the parts having size 1; equivalently (by duality) number of partitions of n where the large part is at least twice as big as the second largest part. - _Franklin T. Adams-Watters_, Jun 08 2005

%C Also number of 2-regular not necessarily connected graphs with loops allowed but no multiple edges. - _Jason Kimberley_, Jan 05 2011

%H Kevin Beanland and Hung Viet Chu, <a href="https://arxiv.org/abs/2311.01926">On Schreier-type Sets, Partitions, and Compositions</a>, arXiv:2311.01926 [math.CO], 2023.

%H P. Chinn and S. Heubach, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Heubach/heubach5.html">Integer Sequences Related to Compositions without 2's</a>, J. Integer Seqs., Vol. 6, 2003.

%H V. Jelinek, T. Mansour, and M. Shattuck, <a href="http://dx.doi.org/10.1016/j.aam.2012.09.002">On multiple pattern avoiding set partitions</a>, Advances in Applied Mathematics Volume 50, Issue 2, February 2013, Pages 292-326. - _N. J. A. Sloane_, Jan 01 2013

%H Jerome Kelleher and Barry O'Sullivan, <a href="http://arxiv.org/abs/0909.2331">Generating All Partitions: A Comparison Of Two Encodings</a>, arXiv:0909.2331 [cs.DS], 2009-2014. [_Peter Luschny_, Oct 24 2010]

%H Krishna Menon and Anurag Singh, <a href="https://arxiv.org/abs/2104.07274">Pattern avoidance and dominating compositions</a>, arXiv:2104.07274 [math.CO], 2021.

%H Mircea Merca, <a href="https://arxiv.org/abs/1903.10797">Fast algorithm for generating ascending compositions</a>, arXiv:1903.10797 [math.CO], 2019.

%F G.f.: (1 - x^2)*Product_{m>=1} 1/(1 - x^m).

%F a(n) = A000041(n) - A000041(n-2).

%F a(n) = p(n) - p(n-2) for n >= 2, where p(n) are the partition numbers (A000041); follows at once from the g.f. - _Emeric Deutsch_, Feb 18 2006

%F a(n) ~ exp(sqrt(2*n/3)*Pi)*Pi / (6*sqrt(2)*n^(3/2)) * (1 - (3*sqrt(3/2)/Pi + 25*Pi/(24*sqrt(6)))/sqrt(n) + (25/8 + 9/(2*Pi^2) + 817*Pi^2/6912)/n). - _Vaclav Kotesovec_, Nov 04 2016

%p with(combinat): a:=proc(n) if n=0 then 1 elif n=1 then 1 else numbpart(n)-numbpart(n-2) fi end: seq(a(n),n=0..49); # _Emeric Deutsch_, Feb 18 2006

%t a[n_] = PartitionsP[n] - PartitionsP[n-2]; a /@ Range[0, 49] (* _Jean-François Alcover_, Jul 13 2011, after _Emeric Deutsch_ *)

%o (PARI) a(n)=if(n<0,0,polcoeff((1-x^2)/eta(x+x*O(x^n)),n))

%o (Magma) A41 := func<n|n ge 0 select NumberOfPartitions(n) else 0>;

%o [A41(n)-A41(n-2):n in [0..49]]; // _Jason Kimberley_, Jan 05 2011

%Y Cf. A000041, A002865, A027337.

%Y 2-regular not necessarily connected graphs: A008483 (simple graphs), A000041 (multigraphs with loops allowed), A002865 (multigraphs with loops forbidden), A027336 (graphs with loops allowed but no multiple edges). - _Jason Kimberley_, Jan 05 2011

%Y Column k=1 of A292622.

%K nonn

%O 0,4

%A _Clark Kimberling_

%E More terms from _Benoit Cloitre_, Dec 10 2002