A002033 Number of perfect partitions of n.

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• core
• easy
• nice

Comments

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]

Also number of ordered factorizations of n+1, see A074206.

Also number of gozinta chains from 1 to n (see A034776). - David W. Wilson

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

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

Dirichlet inverse of A153881 (assuming offset 1). - Mats Granvik, Jan 03 2009

Equals row sums of triangle A176917. - Gary W. Adamson, Apr 28 2010

A partition is perfect iff it is complete (A126796) and knapsack (A108917). - Gus Wiseman, Jun 22 2016

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

Examples

			n=0: 1 (the empty partition)
n=1: 1 (1)
n=2: 1 (11)
n=3: 2 (21, 111)
n=4: 1 (1111)
n=5: 3 (311, 221, 11111)
n=6: 1 (111111)
n=7: 4 (4111, 421, 2221, 1111111)
From _Gus Wiseman_, Jul 13 2018: (Start)
The a(11) = 8 series-reduced planted achiral trees with 12 unlabeled leaves:
  (oooooooooooo)
  ((oooooo)(oooooo))
  ((oooo)(oooo)(oooo))
  ((ooo)(ooo)(ooo)(ooo))
  ((oo)(oo)(oo)(oo)(oo)(oo))
  (((ooo)(ooo))((ooo)(ooo)))
  (((oo)(oo)(oo))((oo)(oo)(oo)))
  (((oo)(oo))((oo)(oo))((oo)(oo)))
(End)
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.
• R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.
• D. E. Knuth, The Art of Computer Programming, Pre-Fasc. 3b, Sect. 7.2.1.5, no. 67, p. 25.
• P. A. MacMahon, The theory of perfect partitions and the compositions of multipartite numbers, Messenger Math., 20 (1891), 103-119.
• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 123-124.
• 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).

Links

• T. D. Noe, Table of n, a(n) for n = 0..9999
• Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
• HoKyu Lee, Double perfect partitions, Discrete Math., 306 (2006), 519-525.
• Paul Pollack, On the parity of the number of multiplicative partitions and related problems, Proc. Amer. Math. Soc. 140 (2012), 3793-3803.
• J. Riordan, Letter to N. J. A. Sloane, Dec. 1970
• Eric Weisstein's World of Mathematics, Perfect Partition
• Eric Weisstein's World of Mathematics, Dirichlet Series Generating Function
• Index entries for "core" sequences

Crossrefs

Same as A074206, up to the offset and initial term there.

Cf. A001055, A050324.

a(A002110)=A000670.

Cf. A000123, A100529, A117621.

Cf. A176917.

For parity see A008966.

Cf. A126796, A108917.

Cf. A001678, A003238, A067824, A167865, A214577, A289078, A292504, A316782.

Programs

Maple

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
# alternative
A002033 := proc(n)
    option remember;
    local a;
    if n <= 2 then
        return 1;
    else
        a := 0 ;
        for i from 0 to n-1 do
            if modp(n+1,i+1) = 0 then
                a := a+procname(i);
            end if;
        end do:
    end if;
    a ;
end proc: # R. J. Mathar, May 25 2017

Mathematica

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

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

Python

from functools import lru_cache
from sympy import divisors
@lru_cache(maxsize=None)
def A002033(n):
    if n <= 1:
        return 1
    return sum(A002033(i-1) for i in divisors(n+1,generator=True) if i <= n) # Chai Wah Wu, Jan 12 2022

Formula

From David Wasserman, Nov 14 2006: (Start)

a(n-1) = Sum_{i|d, i < n} a(i-1).

a(p^k-1) = 2^(k-1).

a(n-1) = A067824(n)/2 for n > 1.

a(A122408(n)-1) = A122408(n)/2. (End)

a(A025487(n)-1) = A050324(n). - R. J. Mathar, May 26 2017

a(n) = (A253249(n+1)+1)/4, n > 0. - Geoffrey Critzer, Aug 19 2020

Extensions

Edited by M. F. Hasler, Oct 12 2018