A048574 Self-convolution of 1 2 3 5 7 11 15 22 30 42 56 77 ... (A000041).

1, 4, 10, 22, 43, 80, 141, 240, 397, 640, 1011, 1568, 2395, 3604, 5360, 7876, 11460, 16510, 23588, 33418, 47006, 65640, 91085, 125596, 172215, 234820, 318579, 430060, 577920, 773130, 1030007, 1366644, 1806445, 2378892, 3121835, 4082796

Offset

2,2

Comments

Number of proper partitions of n into parts of two kinds (i.e. both kinds must be present). - Franklin T. Adams-Watters, Feb 08 2006

Links

Reinhard Zumkeller, Table of n, a(n) for n = 2..5000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 804

Formula

From Franklin T. Adams-Watters, Feb 08 2006: (Start)

a(0) = 0, a(n) = A000712(n)-2*A000041(n) for n>0.

a(n) = Sum_{k=1..n-1} A000041(k)*A000041(n-k).

G.f.: ((Product_{k>0} 1/(1-x^k))-1)^2 = (exp(Sum_{k>0} (x^k/(1-x^k)/k))-1)^2. (End)

a(n) ~ exp(2*Pi*sqrt(n/3)) / (4*3^(3/4)*n^(5/4)). - Vaclav Kotesovec, Mar 10 2018

Example

a(4) = 22 because (1,2,3,5)*(5,3,2,1) = 5 + 6 + 6 + 5 = 22

Maple

spec := [S, {C=Sequence(Z, 1 <= card), B=Set(C, 1 <= card), S=Prod(B, B)}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20); # Franklin T. Adams-Watters, Feb 08 2006
# second Maple program:
a:= n-> (p-> add(p(j)*p(n-j), j=1..n-1))(combinat[numbpart]):
seq(a(n), n=2..40);  # Alois P. Heinz, May 26 2018

Mathematica

a[n_] := First[ ListConvolve[ pp = Array[ PartitionsP, n], pp]]; Table[ a[n], {n, 1, 36}] (* Jean-François Alcover, Oct 21 2011 *)
Table[ListConvolve[PartitionsP[Range[n]], PartitionsP[Range[n]]], {n, 40}]// Flatten (* Harvey P. Dale, Oct 29 2020 *)

Prog

(Haskell)
a048574 n = a048574_list !! (n-2)
a048574_list = f (drop 2 a000041_list) [1] where
f (p:ps) rs = (sum $ zipWith (*) rs $ tail a000041_list) : f ps (p : rs)
-- Reinhard Zumkeller, Nov 09 2015
(PARI) a(n) = sum(k=1, n-1, numbpart(k)*numbpart(n-k)); \\ Michel Marcus, Dec 11 2016

Crossrefs

Cf. A000041, A000712, A023626.

Essentially the same as A052837.

Cf. A122768.

Column k=2 of A060642.

Sequence in context: A006001 A034357 A023626 * A052837 A052821 A292445

Adjacent sequences: A048571 A048572 A048573 * A048575 A048576 A048577

Keyword

easy,nice,nonn

Author

Alford Arnold

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Sep 29 2000

Status

approved