

A002033


Number of perfect partitions of n.
(Formerly M0131 N0053)


79



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


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 ji+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.  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


REFERENCES

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.
R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.
P. A. MacMahon, The theory of perfect partitions and the compositions of multipartite numbers, Messenger Math., 20 (1891), 103119.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 123124.
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), 519525.
Paul Pollack, On the parity of the number of multiplicative partitions and related problems, Proc. Amer. Math. Soc. 140 (2012), 37933803.
Eric Weisstein's World of Mathematics, Perfect Partition
Eric Weisstein's World of Mathematics, Dirichlet Series Generating Function
Index entries for "core" sequences


FORMULA

a(n) = sum of all a(i) such that i divides n and i < n (Clark Kimberling, 1998)  when the sequence is indexed with first term a(1) instead of a(0); otherwise, see Wasserman's formula below.  Clark Kimberling, Oct 20 2011
a(p^k) = 2^(k1).
a(n) = A067824(n)/2 for n>1; a(A122408(n)) = A122408(n)/2.  Reinhard Zumkeller, Sep 03 2006
a(n1) = sum of all a(i1) such that i divides n and i < n. a(p^k1)=2^(k1). a(n1) = A067824(n)/2 for n > 1; a(A122408(n)1) = A122408(n)/2.  David Wasserman, Nov 14 2006


EXAMPLE

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)


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 j1 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 A. Sellers, Dec 07 2000


MATHEMATICA

a[0] = 1; a[1] = 1; a[n_] := a[n] = a /@ Most[Divisors[n]] // Total; a /@ Range[96] (* JeanFrançois Alcover, Apr 06 2011, updated Sep 23 2014 *)


PROG

(PARI) A002033(n) = if(n==1, 1, sumdiv(n, i, if(i==n, 0, A002033(i)))) \\ Michael B. Porter, Nov 01 2009


CROSSREFS

Apart from initial term, same as A074206.
Cf. A001055, A050324.
a(A002110)=A000670.
Cf. A000123, A100529, A117621.
Cf. A176917.
For parity see A008966.
Cf. A126796, A108917.
Sequence in context: A097283 A118314 * A074206 A173801 A108466 A211110
Adjacent sequences: A002030 A002031 A002032 * A002034 A002035 A002036


KEYWORD

nonn,core,easy,nice


AUTHOR

N. J. A. Sloane


STATUS

approved



