CINXE.COM
A002033 - OEIS
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A002033 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A002033" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA002033">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A002033 - OEIS"></a> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> A002033 </div> <div class=seqname> Number of perfect partitions of n. <br><font size=-1>(Formerly M0131 N0053)</font> </div> </div> <div class=scorerefs> 250 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3, 8, 1, 8, 1, 8, 3, 3, 1, 20, 2, 3, 4, 8, 1, 13, 1, 16, 3, 3, 3, 26, 1, 3, 3, 20, 1, 13, 1, 8, 8, 3, 1, 48, 2, 8, 3, 8, 1, 20, 3, 20, 3, 3, 1, 44, 1, 3, 8, 32, 3, 13, 1, 8, 3, 13, 1, 76, 1, 3, 8, 8, 3, 13, 1, 48, 8, 3, 1, 44, 3, 3, 3, 20, 1, 44, 3, 8, 3, 3, 3, 112</div> <div class=seqdatalinks> (<a href="/A002033/list">list</a>; <a href="/A002033/graph">graph</a>; <a href="/search?q=A002033+-id:A002033">refs</a>; <a href="/A002033/listen">listen</a>; <a href="/history?seq=A002033">history</a>; <a href="/search?q=id:A002033&fmt=text">text</a>; <a href="/A002033/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,4</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline>A perfect partition of n is one which contains just one partition of every number less than n when repeated parts are regarded as indistinguishable. Thus 1^n is a perfect partition for every n; and for n = 7, 4 1^3, 4 2 1, 2^3 1 and 1^7 are all perfect partitions. [Riordan]</div> <div class=sectline>Also number of ordered factorizations of n+1, see <a href="/A074206" title="Kalm谩r's [Kalmar's] problem: number of ordered factorizations of n.">A074206</a>.</div> <div class=sectline>Also number of gozinta chains from 1 to n (see <a href="/A034776" title="Gozinta numbers: possible number of gozinta chains for some positive integer.">A034776</a>). - <a href="/wiki/User:David_W._Wilson">David W. Wilson</a></div> <div class=sectline>a(n) is the permanent of the n X n matrix with (i,j) entry = 1 if j|i+1 and = 0 otherwise. For n=3 the matrix is {{1, 1, 0}, {1, 0, 1}, {1, 1, 0}} with permanent = 2. - <a href="/wiki/User:David_Callan">David Callan</a>, Oct 19 2005</div> <div class=sectline>Appears to be the number of permutations that contribute to the determinant that gives the Moebius function. Verified up to a(9). - <a href="/wiki/User:Mats_Granvik">Mats Granvik</a>, Sep 13 2008</div> <div class=sectline>Dirichlet inverse of <a href="/A153881" title="1 followed by -1, -1, -1, ... .">A153881</a> (assuming offset 1). - <a href="/wiki/User:Mats_Granvik">Mats Granvik</a>, Jan 03 2009</div> <div class=sectline>Equals row sums of triangle <a href="/A176917" title="Triangle read by rows, A077049 * the diagonalized version of A002033.">A176917</a>. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Apr 28 2010</div> <div class=sectline>A partition is perfect iff it is complete (<a href="/A126796" title="Number of complete partitions of n.">A126796</a>) and knapsack (<a href="/A108917" title="Number of knapsack partitions of n.">A108917</a>). - <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Jun 22 2016</div> <div class=sectline>a(n) is also the number of series-reduced planted achiral trees with n + 1 unlabeled leaves, where a rooted tree is series-reduced if all terminal subtrees have at least two branches, and achiral if all branches directly under any given node are equal. Also Moebius transform of <a href="/A067824" title="a(1) = 1; for n > 1, a(n) = 1 + Sum_{0 < d < n, d|n} a(d).">A067824</a>. - <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Jul 13 2018</div> </div> </div> <div class=section> <div class=sectname>REFERENCES</div> <div class=sectbody> <div class=sectline>L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.</div> <div class=sectline>R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.</div> <div class=sectline>D. E. Knuth, The Art of Computer Programming, Pre-Fasc. 3b, Sect. 7.2.1.5, no. 67, p. 25.</div> <div class=sectline>P. A. MacMahon, The theory of perfect partitions and the compositions of multipartite numbers, Messenger Math., 20 (1891), 103-119.</div> <div class=sectline>J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 123-124.</div> <div class=sectline>N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).</div> <div class=sectline>N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline>T. D. Noe, <a href="/A002033/b002033.txt">Table of n, a(n) for n = 0..9999</a></div> <div class=sectline>Daniele A. Gewurz and Francesca Merola, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Gewurz/gewurz5.html">Sequences realized as Parker vectors of oligomorphic permutation groups</a>, J. Integer Seqs., Vol. 6, 2003.</div> <div class=sectline>HoKyu Lee, <a href="http://dx.doi.org/10.1016/j.disc.2006.01.007">Double perfect partitions</a>, Discrete Math., 306 (2006), 519-525.</div> <div class=sectline>Paul Pollack, <a href="http://dx.doi.org/10.1090/S0002-9939-2012-11254-7">On the parity of the number of multiplicative partitions and related problems</a>, Proc. Amer. Math. Soc. 140 (2012), 3793-3803.</div> <div class=sectline>J. Riordan, <a href="/A002033/a002033.pdf">Letter to N. J. A. Sloane, Dec. 1970</a></div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerfectPartition.html">Perfect Partition</a></div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DirichletSeriesGeneratingFunction.html">Dirichlet Series Generating Function</a></div> <div class=sectline><a href="/index/Cor#core">Index entries for "core" sequences</a></div> </div> </div> <div class=section> <div class=sectname>FORMULA</div> <div class=sectbody> <div class=sectline>From <a href="/wiki/User:David_Wasserman">David Wasserman</a>, Nov 14 2006: (Start)</div> <div class=sectline>a(n-1) = Sum_{i|d, i < n} a(i-1).</div> <div class=sectline>a(p^k-1) = 2^(k-1).</div> <div class=sectline>a(n-1) = <a href="/A067824" title="a(1) = 1; for n > 1, a(n) = 1 + Sum_{0 < d < n, d|n} a(d).">A067824</a>(n)/2 for n > 1.</div> <div class=sectline>a(<a href="/A122408" title="Numbers n such that A067824(n) = n.">A122408</a>(n)-1) = <a href="/A122408" title="Numbers n such that A067824(n) = n.">A122408</a>(n)/2. (End)</div> <div class=sectline>a(<a href="/A025487" title="Least integer of each prime signature A124832; also products of primorial numbers A002110.">A025487</a>(n)-1) = <a href="/A050324" title="Number of ordered factorizations indexed by prime signatures: A074206(A025487).">A050324</a>(n). - <a href="/wiki/User:R._J._Mathar">R. J. Mathar</a>, May 26 2017</div> <div class=sectline>a(n) = (<a href="/A253249" title="Number of nonempty chains in the divides relation on the divisors of n.">A253249</a>(n+1)+1)/4, n > 0. - <a href="/wiki/User:Geoffrey_Critzer">Geoffrey Critzer</a>, Aug 19 2020</div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>n=0: 1 (the empty partition)</div> <div class=sectline>n=1: 1 (1)</div> <div class=sectline>n=2: 1 (11)</div> <div class=sectline>n=3: 2 (21, 111)</div> <div class=sectline>n=4: 1 (1111)</div> <div class=sectline>n=5: 3 (311, 221, 11111)</div> <div class=sectline>n=6: 1 (111111)</div> <div class=sectline>n=7: 4 (4111, 421, 2221, 1111111)</div> <div class=sectline>From <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Jul 13 2018: (Start)</div> <div class=sectline>The a(11) = 8 series-reduced planted achiral trees with 12 unlabeled leaves:</div> <div class=sectline> (oooooooooooo)</div> <div class=sectline> ((oooooo)(oooooo))</div> <div class=sectline> ((oooo)(oooo)(oooo))</div> <div class=sectline> ((ooo)(ooo)(ooo)(ooo))</div> <div class=sectline> ((oo)(oo)(oo)(oo)(oo)(oo))</div> <div class=sectline> (((ooo)(ooo))((ooo)(ooo)))</div> <div class=sectline> (((oo)(oo)(oo))((oo)(oo)(oo)))</div> <div class=sectline> (((oo)(oo))((oo)(oo))((oo)(oo)))</div> <div class=sectline>(End)</div> </div> </div> <div class=section> <div class=sectname>MAPLE</div> <div class=sectbody> <div class=sectline>a := array(1..150): for k from 1 to 150 do a[k] := 0 od: a[1] := 1: for j from 2 to 150 do for m from 1 to j-1 do if j mod m = 0 then a[j] := a[j]+a[m] fi: od: od: for k from 1 to 150 do printf(`%d, `, a[k]) od: # <a href="/wiki/User:James_A._Sellers">James A. Sellers</a>, Dec 07 2000</div> <div class=sectline># alternative</div> <div class=sectline><a href="/A002033" title="Number of perfect partitions of n.">A002033</a> := proc(n)</div> <div class=sectline> option remember;</div> <div class=sectline> local a;</div> <div class=sectline> if n <= 2 then</div> <div class=sectline> return 1;</div> <div class=sectline> else</div> <div class=sectline> a := 0 ;</div> <div class=sectline> for i from 0 to n-1 do</div> <div class=sectline> if modp(n+1, i+1) = 0 then</div> <div class=sectline> a := a+procname(i);</div> <div class=sectline> end if;</div> <div class=sectline> end do:</div> <div class=sectline> end if;</div> <div class=sectline> a ;</div> <div class=sectline>end proc: # <a href="/wiki/User:R._J._Mathar">R. J. Mathar</a>, May 25 2017</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>a[0] = 1; a[1] = 1; a[n_] := a[n] = a /@ Most[Divisors[n]] // Total; a /@ Range[96] (* <a href="/wiki/User:Jean-Fran莽ois_Alcover">Jean-Fran莽ois Alcover</a>, Apr 06 2011, updated Sep 23 2014. NOTE: This produces <a href="/A074206" title="Kalm谩r's [Kalmar's] problem: number of ordered factorizations of n.">A074206</a>(n) = a(n-1). - <a href="/wiki/User:M._F._Hasler">M. F. Hasler</a>, Oct 12 2018 *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(PARI) <a href="/A002033" title="Number of perfect partitions of n.">A002033</a>(n) = if(n, sumdiv(n+1, i, if(i<=n, <a href="/A002033" title="Number of perfect partitions of n.">A002033</a>(i-1))), 1) \\ <a href="/wiki/User:Michael_B._Porter">Michael B. Porter</a>, Nov 01 2009, corrected by <a href="/wiki/User:M._F._Hasler">M. F. Hasler</a>, Oct 12 2018</div> <div class=sectline>(Python)</div> <div class=sectline>from functools import lru_cache</div> <div class=sectline>from sympy import divisors</div> <div class=sectline>@lru_cache(maxsize=None)</div> <div class=sectline>def <a href="/A002033" title="Number of perfect partitions of n.">A002033</a>(n):</div> <div class=sectline> if n <= 1:</div> <div class=sectline> return 1</div> <div class=sectline> return sum(<a href="/A002033" title="Number of perfect partitions of n.">A002033</a>(i-1) for i in divisors(n+1, generator=True) if i <= n) # <a href="/wiki/User:Chai_Wah_Wu">Chai Wah Wu</a>, Jan 12 2022</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Same as <a href="/A074206" title="Kalm谩r's [Kalmar's] problem: number of ordered factorizations of n.">A074206</a>, up to the offset and initial term there.</div> <div class=sectline>Cf. <a href="/A001055" title="The multiplicative partition function: number of ways of factoring n with all factors greater than 1 (a(1) = 1 by convention).">A001055</a>, <a href="/A050324" title="Number of ordered factorizations indexed by prime signatures: A074206(A025487).">A050324</a>.</div> <div class=sectline>a(<a href="/A002110" title="Primorial numbers (first definition): product of first n primes. Sometimes written prime(n)#.">A002110</a>)=<a href="/A000670" title="Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; o...">A000670</a>.</div> <div class=sectline>Cf. <a href="/A000123" title="Number of binary partitions: number of partitions of 2n into powers of 2.">A000123</a>, <a href="/A100529" title="a(n) = minimal k such that n has a partition into k parts with the property that every number <= m can be partitioned into a...">A100529</a>, <a href="/A117621" title="Number of double-perfect partitions of [1..n].">A117621</a>.</div> <div class=sectline>Cf. <a href="/A176917" title="Triangle read by rows, A077049 * the diagonalized version of A002033.">A176917</a>.</div> <div class=sectline>For parity see <a href="/A008966" title="a(n) = 1 if n is squarefree, otherwise 0.">A008966</a>.</div> <div class=sectline>Cf. <a href="/A126796" title="Number of complete partitions of n.">A126796</a>, <a href="/A108917" title="Number of knapsack partitions of n.">A108917</a>.</div> <div class=sectline>Cf. <a href="/A001678" title="Number of series-reduced planted trees with n nodes.">A001678</a>, <a href="/A003238" title="Number of rooted trees with n vertices in which vertices at the same level have the same degree.">A003238</a>, <a href="/A067824" title="a(1) = 1; for n > 1, a(n) = 1 + Sum_{0 < d < n, d|n} a(d).">A067824</a>, <a href="/A167865" title="Number of partitions of n into distinct parts greater than 1, with each part divisible by the next.">A167865</a>, <a href="/A214577" title="The Matula-Goebel numbers of the generalized Bethe trees. A generalized Bethe tree is a rooted tree in which vertices at the...">A214577</a>, <a href="/A289078" title="Number of orderless same-trees of weight n.">A289078</a>, <a href="/A292504" title="Number of orderless tree-factorizations of n.">A292504</a>, <a href="/A316782" title="Number of achiral tree-factorizations of n.">A316782</a>.</div> <div class=sectline>Sequence in context: <a href="/A300836" title="a(n) is the total number of terms (1-digits) in Zeckendorf representation of all proper divisors of n.">A300836</a> <a href="/A118314" title="Erroneous version of A002033.">A118314</a> <a href="/A349059" title="Number of weakly alternating ordered factorizations of n.">A349059</a> * <a href="/A074206" title="Kalm谩r's [Kalmar's] problem: number of ordered factorizations of n.">A074206</a> <a href="/A173801" title="The number of primitive numbers k such that 1/k is in the Cantor set and the fraction 1/k has period n.">A173801</a> <a href="/A368198" title="a(n) gives the number of ways to go from n to 1 with steps consisting of replacing a positive number without leading zero, s...">A368198</a></div> <div class=sectline>Adjacent sequences: <a href="/A002030" title="Number of connected graphs on n labeled nodes, each node being colored with one of 5 colors, such that no edge joins nodes o...">A002030</a> <a href="/A002031" title="Number of labeled connected digraphs on n nodes where every node has indegree 0 or outdegree 0 and no isolated nodes.">A002031</a> <a href="/A002032" title="Number of n-colored connected graphs on n labeled nodes.">A002032</a> * <a href="/A002034" title="Kempner numbers: smallest positive integer m such that n divides m!.">A002034</a> <a href="/A002035" title="Numbers that contain primes to odd powers only.">A002035</a> <a href="/A002036" title="Compressed primes: a(n) is the nearest integer to prime(n)/log prime(n).">A002036</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="a sequence of nonnegative numbers">nonn</span>,<span title="an important sequence">core</span>,<span title="it is very easy to produce terms of sequence">easy</span>,<span title="an exceptionally nice sequence">nice</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a></div> </div> </div> <div class=section> <div class=sectname>EXTENSIONS</div> <div class=sectbody> <div class=sectline>Edited by <a href="/wiki/User:M._F._Hasler">M. F. Hasler</a>, Oct 12 2018</div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified November 28 23:07 EST 2024. Contains 378208 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>