OFFSET
0,2
COMMENTS
Original name was: a(n) = Sum_{pi = partition of n} 2^{number of 1's in pi}.
a(n) is the number of compositions of n consisting of two kinds of parts, p and p', when the order of all the primed parts does not matter; or equivalently, when the order of all the unprimed parts does not matter. - Gregory L. Simay, Sep 12 2017
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
Steve Butler, Jeongyoon Choi, Kimyung Kim, Kyuhyeok Seo, Enumerating multiplex juggling patterns, arXiv:1702.05808 [math.CO], 2017.
FORMULA
G.f.: (1/(1-2*x))*Product_{m>=2} 1/(1-x^m). - Vladeta Jovovic, Feb 04 2004
Convolution of A000041 with A011782. In general, Sum_{pi = partition of n} k^{number of 1's in pi} is equal to the convolution of the partitions of n with the compositions of n having parts of (k-1) kinds; this is k=2. - Gregory L. Simay, Sep 15 2017
a(n) ~ c * 2^n, where c = Product_{n>=2} (2^n/(2^n-1)) = 1.7313733097275318... - Vaclav Kotesovec, Sep 17 2017
EXAMPLE
a(4) = 24 because the partitions of 4 are 4(1), 31(2), 22(1), 211(4) and 1111(16). 1+2+1+4+16=24.
a(4) = 24 because the compositions of 4 (when the parts are of two kinds, p and p', and the order of the primed parts does not matter) are 4; 4'; 3,1; 1,3; 3',1 = 1,3'; 3,1' = 1',3; 3'1' = 1'3'; 2,2; 2'2 = 2,2'; 2',2'; 2,1,1; 1,2,1; 1,1,2; 2,1,1'= 2,1',1 = 1',2,1; 2',1,1 = 1,2',1 = 1,1,2'; 2,1',1' = 1',2,1' = 1',1',2; 2',1',1 = 2',1,1'= 1,2',1' = 1',2',1 = 1',1,2' = 1,1',2'; 2',1',1' = 1',2',1' = 1',1',2'; 1,1,1,1; 1',1,1,1 = 1,1',1,1 = 1,1,1',1 = 1,1,1,1'; 1',1',1,1 = 1,1',1,1' = 1',1,1',1 = 1',1,1,1' = 1,1'1',1 = 1,1,1',1'; 1',1',1',1 = 1',1',1,1' = 1',1,1',1', 1,1',1',1'; 1',1',1',1'. - Gregory L. Simay, Sep 12 2017
a(4) = 24 because the convolution of the first 5 partition numbers with the first 5 composition numbers is 1*8 + 1*4 + 2*2 + 3*1 + 5*1 = 24. (Note that the first partition number is A000041(0)=1; and the first composition number is A011782(0)=1.) - Gregory L. Simay, Sep 15 2017
MAPLE
b:= proc(n, i) option remember; `if`(n=0 or i<2, 2^n,
add(b(n-i*j, i-1), j=0..iquo(n, i)))
end:
a:= n-> b(n, n):
seq(a(n), n=0..40); # Alois P. Heinz, Feb 19 2013
MATHEMATICA
c[n_] := Count[n, 1]; f[n_] := Apply[Plus, 2^Map[ c, IntegerPartitions[n] ]]; Table[ f[n], {n, 0, 31}] (* Robert G. Wilson v, Feb 12 2004 *)
b[n_, i_] := b[n, i] = If[n == 0 || i < 2, 2^n, Sum[b[n - i*j, i - 1], {j, 0, Quotient[n, i]}]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Aug 29 2016, after Alois P. Heinz *)
Table[PartitionsP[n] + Sum[2^(k-1)*PartitionsP[n-k], {k, 1, n}], {n, 0, 50}] (* Vaclav Kotesovec, Apr 10 2017 *)
PROG
(Java) import java.math.*; import java.io.*; public class A090764 { public static final int LIMIT = 80; public static final BigInteger TWO = new BigInteger("2"); public static void main(String[] args) throws Exception {BigInteger[] a = new BigInteger[LIMIT];
int i, j; PrintStream out = new PrintStream(new FileOutputStream("A090764.txt")); a[0] = BigInteger.ONE; for (i = 1; i < LIMIT; i++)a[i] = a[i - 1].multiply(TWO); for (j = 2; j < LIMIT; j++)for (i = j; i < LIMIT; i++)
a[i] = a[i - 1].multiply(TWO); for (j = 2; j < LIMIT; j++)for (i = j; i < LIMIT; i++) a[i] = a[i].add(a[i - j]); for (i = 0; i < LIMIT; i++)out.print(a[i] + " "); out.print(" "); }} // David Wasserman, Feb 10 2004
CROSSREFS
KEYWORD
nonn
AUTHOR
Jon Perry, Feb 01 2004
EXTENSIONS
More terms from David Wasserman, Feb 10 2004
a(0) inserted by Alois P. Heinz, Feb 19 2013
New name from Alois P. Heinz, Sep 21 2017
STATUS
approved