|
|
A002033
|
|
Number of perfect partitions of n.
(Formerly M0131 N0053)
|
|
248
|
|
|
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.
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
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
|
|
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
|
|
|
FORMULA
|
a(n-1) = Sum_{i|d, i < n} a(i-1).
a(p^k-1) = 2^(k-1).
|
|
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)
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)
|
|
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 A. Sellers, Dec 07 2000
# alternative
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 ;
|
|
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 *)
|
|
PROG
|
(Python)
from functools import lru_cache
from sympy import divisors
@lru_cache(maxsize=None)
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
|
|
CROSSREFS
|
Same as A074206, up to the offset and initial term there.
|
|
KEYWORD
|
nonn,core,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|