login
Number of partitions of n into parts >= 3.
67

%I #150 Aug 03 2024 17:53:23

%S 1,0,0,1,1,1,2,2,3,4,5,6,9,10,13,17,21,25,33,39,49,60,73,88,110,130,

%T 158,191,230,273,331,391,468,556,660,779,927,1087,1284,1510,1775,2075,

%U 2438,2842,3323,3872,4510

%N Number of partitions of n into parts >= 3.

%C a(0) = 1 because the empty partition vacuously has each part >= 3. - _Jason Kimberley_, Jan 11 2011

%C Number of partitions where the largest part occurs at least three times. - _Joerg Arndt_, Apr 17 2011

%C By removing a single part of size 3, an A026796 partition of n becomes an A008483 partition of n - 3.

%C For n >= 3 the sequence counts the isomorphism classes of authentication codes AC(2,n,n) with perfect secrecy and with largest probability 0.5 that an interceptor could deceive with a substituted message. - E. Keith Lloyd (ekl(AT)soton.ac.uk).

%C For n >= 1, also the number of regular graphs of degree 2. - _Mitch Harris_, Jun 22 2005

%C (1 + 0*x + 0*x^2 + x^3 + x^4 + x^5 + 2*x^6 + ...) = (1 + x + 2*x^2 + 3*x^3 + 5*x^4 + ...) * 1 / (1 + x + 2*x^2 + 2*x^3 + 3*x^4 + 3*x^5 + 4*x^6 + 4*x^7 + ...). - _Gary W. Adamson_, Jun 30 2009

%C Because the triangle A051031 is symmetric, a(n) is also the number of (n-3)-regular graphs on n vertices. Since the disconnected (n-3)-regular graph with minimum order is 2K_{n-2}, then for n > 4 there are no disconnected (n-3)-regular graphs on n vertices. Therefore for n > 4, a(n) is also the number of connected (n-3)-regular graphs on n vertices. - _Jason Kimberley_, Oct 05 2009

%C Number of partitions of n+2 such that 2*(number of parts) is a part. - _Clark Kimberling_, Feb 27 2014

%C For n >= 1, a(n) is the number of (1,1)-separable partitions of n, as defined at A239482. For example, the (1,1)-separable partitions of 11 are [10,1], [7,1,2,1], [6,1,3,1], [5,1,4,1], [4,1,2,1,2,1], [3,1,3,1,2,1], so that a(11) = 6. - _Clark Kimberling_, Mar 21 2014

%H Andrew van den Hoeven, <a href="/A008483/b008483.txt">Table of n, a(n) for n = 0..10000</a> (first 301 terms from Vincenzo Librandi)

%H Peter Adams, Saad I. El-Zanati, Peter Florido, and William Turner, <a href="https://doi.org/10.1007/978-3-031-52969-6_28">On 2-Factorizations of the Complete 3-Uniform Hypergraph of Order 12 Minus a 1-Factor</a>, Combinatorics, Graph Theory and Computing (SEICCGTC 2021) Springer Proc. Math. Stat., Vol 448, pp. 383-392. See p. 326.

%H Roland Bacher and P. De La Harpe, <a href="https://hal.archives-ouvertes.fr/hal-01285685/document">Conjugacy growth series of some infinitely generated groups</a>, hal-01285685v2, 2016.

%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 R.-Q. Feng, J. H. Kwak and E. K. Lloyd, <a href="http://journals.cambridge.org/article_S0004972700035942">Isomorphism classes of authentication codes</a>, Bull. Austral. Math. Soc. 69 (2004), no. 2, 203-215.

%H Elisabeth Gaar and Daniel Krenn, <a href="https://arxiv.org/abs/2005.14121">Metamour-regular Polyamorous Relationships and Graphs</a>, arXiv:2005.14121 [math.CO], 2020.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=446">Encyclopedia of Combinatorial Structures 446</a>

%H F. Jouneau-Sion and O. Torres, <a href="https://www.researchgate.net/publication/265161885_In_Fisher&#39;s_net_exact_F-tests_in_semi-parametric_models_with_exchangeable_errors">In Fisher's net: exact F-tests in semi-parametric models with exchangeable errors</a>, August 2014, preprint on ResearchGate.

%H Jason Kimberley, <a href="/wiki/User:Jason_Kimberley/E_k-reg_girth_ge_g_index">Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g</a>.

%H Johan Kok, <a href="https://pisrt.org/psr-press/journals/odam-vol-3-issue-3-2020/degree-affinity-number-of-certain-2-regular-graphs/">Degree affinity number of certain 2-regular graphs</a>, Open J. of Disc. Appl. Math. (2020) Vol. 3, No. 3, 77-84.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Two-RegularGraph.html">Two-Regular Graph</a>.

%F a(n) = p(n) - p(n - 1) - p(n - 2) + p(n - 3) where p(n) is the number of unrestricted partitions of n into positive parts (A000041).

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

%F G.f.: (Sum_{n>=0} x^(3*n)) / (Product_{k=1..n} (1 - x^k)). - _Joerg Arndt_, Apr 17 2011

%F a(n) = A121081(n+3) - A121659(n+3). - _Reinhard Zumkeller_, Aug 14 2006

%F Euler transformation of A179184. a(n) = A179184(n) + A165652(n). - _Jason Kimberley_, Jan 05 2011

%F a(n) ~ Pi^2 * exp(Pi*sqrt(2*n/3)) / (12*sqrt(3)*n^2). - _Vaclav Kotesovec_, Feb 26 2015

%F G.f.: exp(Sum_{k>=1} x^(3*k)/(k*(1 - x^k))). - _Ilya Gutkovskiy_, Aug 21 2018

%F a(n) = Sum_{j=0..floor(n/2)} A008284(n-2*j,j). - _Gregory L. Simay_, Apr 27 2023

%p series(1/product((1-x^i),i=3..50),x,51);

%p ZL := [ B,{B=Set(Set(Z, card>=3))}, unlabeled ]: seq(combstruct[count](ZL, size=n), n=0..46); # _Zerinvary Lajos_, Mar 13 2007

%p with(combstruct):ZL2:=[S,{S=Set(Cycle(Z,card>2))}, unlabeled]:seq(count(ZL2,size=n),n=0..46); # _Zerinvary Lajos_, Sep 24 2007

%p with(combstruct):a:=proc(m) [A,{A=Set(Cycle(Z,card>m))},unlabeled]; end: A008483:=a(2):seq(count(A008483,size=n),n=0..46); # _Zerinvary Lajos_, Oct 02 2007

%t 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, 3], {n, 49}] (* _Robert G. Wilson v_, Jan 31 2011 *)

%t Rest[Table[Count[IntegerPartitions[n], p_ /; MemberQ[p, 2*Length[p]]], {n, 50}]] (* _Clark Kimberling_, Feb 27 2014 *)

%o (Magma) p := NumberOfPartitions; A008483 := func< n | n eq 0 select 1 else n le 2 select 0 else p(n) - p(n-1) - p(n-2) + p(n-3)>; // _Jason Kimberley_, Jan 11 2011

%o (PARI) a(n) = numbpart(n)-numbpart(n-1)-numbpart(n-2)+numbpart(n-3) \\ _Charles R Greathouse IV_, Jul 19 2011

%Y Essentially the same sequence as A026796 and A281356.

%Y From _Jason Kimberley_, Nov 07 2009 and Jan 05 2011 and Feb 03 2011: (Start)

%Y Not necessarily connected simple regular graphs: A005176 (any degree), A051031 (triangular array), specified degree k: A000012 (k=0), A059841 (k=1), this sequence (k=2), A005638 (k=3), A033301 (k=4), A165626 (k=5), A165627 (k=6), A165628 (k=7).

%Y 2-regular simple graphs: A179184 (connected), A165652 (disconnected), this sequence (not necessarily connected).

%Y 2-regular not necessarily connected graphs without multiple edges [partitions without 2 as a part]: this sequence (no loops allowed [without 1 as a part]), A027336 (loops allowed [parts may be 1]).

%Y Not necessarily connected 2-regular graphs with girth at least g [partitions into parts >= g]: A026807 (triangle); chosen g: A000041 (g=1 -- multigraphs with loops allowed), A002865 (g=2 -- multigraphs with loops forbidden), this sequence (g=3), A008484 (g=4), A185325 (g=5), A185326 (g=6), A185327 (g=7), A185328 (g=8), A185329 (g=9).

%Y Not necessarily connected 2-regular graphs with girth exactly g [partitions with smallest part g]: A026794 (triangle); chosen g: A002865 (g=2), A026796 (g=3), A026797 (g=4), A026798 (g=5), A026799 (g=6), A026800(g=7), A026801 (g=8), A026802 (g=9), A026803 (g=10), ... (End)

%Y Cf. A008284.

%K nonn,easy

%O 0,7

%A T. Forbes (anthony.d.forbes(AT)googlemail.com)