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