A216708 Number of compositions (ordered partitions) of n into 2 or more distinct nonnegative parts.

0, 2, 2, 10, 10, 18, 48, 56, 86, 124, 298, 336, 540, 722, 1070, 2122, 2614, 3810, 5316, 7496, 9986, 18940, 22558, 33336, 44568, 63074, 82034, 114754, 187642, 234690, 328536, 441872, 602006, 794020, 1072546, 1389408, 2207532, 2706266, 3752462, 4900474, 6681022, 8574906

Offset

0,2

Comments

If permutations are considered equivalent then a(n)=A087135(n)=2*A000009(n) for n>0.

All terms are even. - Alois P. Heinz, Aug 18 2018

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5000

César Eliud Lozada, Illustration for terms up to n=9

Formula

From Joerg Arndt, Sep 17 2012: (Start)

G.f. sum(k>=0, (k+1)!*x^((k^2+k)/2) / prod(j=1..k+1, 1-x^j)) - 1/(1-x);

explanation: the g.f. for partitions into at least two positive parts (A111133) is

sum(k>=0, x^((k^2+k)/2) / prod(j=1..k, 1-x^j)) - 1/(1-x)

(i.e., the g.f. of A000009 minus the g.f. 1/(1-x) for the constant sequence a(n)=1 that counts the single partition n = [n]);

the factor (k+1)! in the g.f. of this function provides for the permutations of the parts, including a zero.

(End)

Example

a(2)=2 because 2 = 0+2 = 2+0 (2 ways)
a(3)=10 because 3 = 0+3 = 1+2 = 2+1 = 3+0 = 0+1+2 = 0+2+1 = 1+0+2 = 1+2+0 = 2+0+1 = 2+1+0 (10 ways)

Maple

b:= proc(n, i, p) option remember; (m-> `if`(m<n, 0, `if`(n=0,
      `if`(p=0, 0, `if`(p=1, 2, p!*(p+2))), b(n, i-1, p)+
        b(n-i, min(n-i, i-1), p+1))))(i*(i+1)/2)
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..42);  # Alois P. Heinz, Aug 18 2018

Mathematica

b[n_, i_, p_] := b[n, i, p] = With[{m = i(i+1)/2}, If[m < n, 0, If[n == 0,
     If[p == 0, 0, If[p == 1, 2, p! (p+2)]], b[n, i-1, p] +
     b[n-i, Min[n-i, i-1], p+1]]]];
a[n_] := b[n, n, 0];
a /@ Range[0, 42] (* Jean-François Alcover, Mar 05 2021, after Alois P. Heinz *)

Prog

(PARI)
N=66;  x='x+O('x^N);
gf=sum(k=0, N, (k+1)!*x^((k^2+k)/2) / prod(j=1, k+1, 1-x^j)) - 1/(1-x);
v=Vec(gf);
vector(#v+1, n, if(n==1, 0, v[n-1]))
/* Joerg Arndt, Sep 17 2012 */

Crossrefs

Cf. A216695, A087135, A000009, A032020.

Sequence in context: A168295 A309751 A249152 * A032005 A147801 A367545

Adjacent sequences: A216705 A216706 A216707 * A216709 A216710 A216711

Keyword

nonn

Author

César Eliud Lozada, Sep 16 2012

Extensions

More terms, Joerg Arndt, Sep 17 2012

Status

approved