A090764 Number of partitions of n with two sorts of part 1.

1, 2, 5, 11, 24, 50, 104, 212, 431, 870, 1752, 3518, 7057, 14138, 28310, 56661, 113377, 226820, 453728, 907561, 1815259, 3630683, 7261576, 14523405, 29047130, 58094643, 116189764, 232380102, 464760912, 929522671, 1859046381, 3718094000, 7436189507, 14872380808

Offset: 0

Author

Jon Perry, Feb 01 2004

Keywords

• nonn

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

Examples

			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
a(4) = 2*a(3) + A000041(4) - A000041(3) = 2*11 + 5 - 3 = 24. - _Gregory L. Simay_, Sep 16 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.

Crossrefs

Cf. A000041, A011782, A259401.

Column k=2 of A292741.

Programs

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

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 *)

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) = 2*a(n-1) + A000041(n) - A000041(n-1). - Gregory L. Simay, Sep 16 2017

a(n) ~ c * 2^n, where c = Product_{n>=2} (2^n/(2^n-1)) = 1.7313733097275318... - Vaclav Kotesovec, Sep 17 2017

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