cp's OEIS Frontend

A002033 Number of perfect partitions of n.

%I A002033 M0131 N0053 #111 Jul 02 2025 16:01:54
%S A002033 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,
%T A002033 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,
%U A002033 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
%N A002033 Number of perfect partitions of n.
%C A002033 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]
%C A002033 Also number of ordered factorizations of n+1, see A074206.
%C A002033 Also number of gozinta chains from 1 to n (see A034776). - _David W. Wilson_
%C A002033 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. - _David Callan_, Oct 19 2005
%C A002033 Appears to be the number of permutations that contribute to the determinant that gives the Moebius function. Verified up to a(9). - _Mats Granvik_, Sep 13 2008
%C A002033 Dirichlet inverse of A153881 (assuming offset 1). - _Mats Granvik_, Jan 03 2009
%C A002033 Equals row sums of triangle A176917. - _Gary W. Adamson_, Apr 28 2010
%C A002033 A partition is perfect iff it is complete (A126796) and knapsack (A108917). - _Gus Wiseman_, Jun 22 2016
%C A002033 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 A067824. - _Gus Wiseman_, Jul 13 2018
%D A002033 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.
%D A002033 R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.
%D A002033 D. E. Knuth, The Art of Computer Programming, Pre-Fasc. 3b, Sect. 7.2.1.5, no. 67, p. 25.
%D A002033 P. A. MacMahon, The theory of perfect partitions and the compositions of multipartite numbers, Messenger Math., 20 (1891), 103-119.
%D A002033 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 123-124.
%D A002033 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002033 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002033 T. D. Noe, <a href="/A002033/b002033.txt">Table of n, a(n) for n = 0..9999</a>
%H A002033 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.
%H A002033 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.
%H A002033 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.
%H A002033 J. Riordan, <a href="/A002033/a002033.pdf">Letter to N. J. A. Sloane, Dec. 1970</a>
%H A002033 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PerfectPartition.html">Perfect Partition</a>
%H A002033 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DirichletSeriesGeneratingFunction.html">Dirichlet Series Generating Function</a>
%H A002033 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A002033 From _David Wasserman_, Nov 14 2006: (Start)
%F A002033 a(n-1) = Sum_{i|d, i < n} a(i-1).
%F A002033 a(p^k-1) = 2^(k-1).
%F A002033 a(n-1) = A067824(n)/2 for n > 1.
%F A002033 a(A122408(n)-1) = A122408(n)/2. (End)
%F A002033 a(A025487(n)-1) = A050324(n). - _R. J. Mathar_, May 26 2017
%F A002033 a(n) = (A253249(n+1)+1)/4, n > 0. - _Geoffrey Critzer_, Aug 19 2020
%e A002033 n=0: 1 (the empty partition)
%e A002033 n=1: 1 (1)
%e A002033 n=2: 1 (11)
%e A002033 n=3: 2 (21, 111)
%e A002033 n=4: 1 (1111)
%e A002033 n=5: 3 (311, 221, 11111)
%e A002033 n=6: 1 (111111)
%e A002033 n=7: 4 (4111, 421, 2221, 1111111)
%e A002033 From _Gus Wiseman_, Jul 13 2018: (Start)
%e A002033 The a(11) = 8 series-reduced planted achiral trees with 12 unlabeled leaves:
%e A002033   (oooooooooooo)
%e A002033   ((oooooo)(oooooo))
%e A002033   ((oooo)(oooo)(oooo))
%e A002033   ((ooo)(ooo)(ooo)(ooo))
%e A002033   ((oo)(oo)(oo)(oo)(oo)(oo))
%e A002033   (((ooo)(ooo))((ooo)(ooo)))
%e A002033   (((oo)(oo)(oo))((oo)(oo)(oo)))
%e A002033   (((oo)(oo))((oo)(oo))((oo)(oo)))
%e A002033 (End)
%p A002033 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: # _James Sellers_, Dec 07 2000
%p A002033 # alternative
%p A002033 A002033 := proc(n)
%p A002033     option remember;
%p A002033     local a;
%p A002033     if n <= 2 then
%p A002033         return 1;
%p A002033     else
%p A002033         a := 0 ;
%p A002033         for i from 0 to n-1 do
%p A002033             if modp(n+1,i+1) = 0 then
%p A002033                 a := a+procname(i);
%p A002033             end if;
%p A002033         end do:
%p A002033     end if;
%p A002033     a ;
%p A002033 end proc: # _R. J. Mathar_, May 25 2017
%t A002033 a[0] = 1; a[1] = 1; a[n_] := a[n] = a /@ Most[Divisors[n]] // Total; a /@ Range[96]  (* _Jean-François Alcover_, Apr 06 2011, updated Sep 23 2014. NOTE: This produces A074206(n) = a(n-1). - _M. F. Hasler_, Oct 12 2018 *)
%o A002033 (PARI) A002033(n) = if(n,sumdiv(n+1,i,if(i<=n,A002033(i-1))),1) \\ _Michael B. Porter_, Nov 01 2009, corrected by _M. F. Hasler_, Oct 12 2018
%o A002033 (Python)
%o A002033 from functools import lru_cache
%o A002033 from sympy import divisors
%o A002033 @lru_cache(maxsize=None)
%o A002033 def A002033(n):
%o A002033     if n <= 1:
%o A002033         return 1
%o A002033     return sum(A002033(i-1) for i in divisors(n+1,generator=True) if i <= n) # _Chai Wah Wu_, Jan 12 2022
%Y A002033 Same as A074206, up to the offset and initial term there.
%Y A002033 Cf. A001055, A050324.
%Y A002033 a(A002110)=A000670.
%Y A002033 Cf. A000123, A100529, A117621.
%Y A002033 Cf. A176917.
%Y A002033 For parity see A008966.
%Y A002033 Cf. A126796, A108917.
%Y A002033 Cf. A001678, A003238, A067824, A167865, A214577, A289078, A292504, A316782.
%K A002033 nonn,core,easy,nice
%O A002033 0,4
%A A002033 _N. J. A. Sloane_
%E A002033 Edited by _M. F. Hasler_, Oct 12 2018