A216695 Number of compositions (ordered partitions) of n into at least 2 distinct positive parts.

0, 0, 0, 2, 2, 4, 10, 12, 18, 26, 56, 64, 100, 132, 192, 350, 434, 616, 850, 1176, 1554, 2750, 3296, 4756, 6292, 8760, 11304, 15602, 24314, 30460, 41866, 55740, 74874, 98042, 130808, 168424, 257404, 315972, 431064, 558326, 751490, 958264, 1277866, 1621272, 2123586, 3020630, 3768440

Offset

0,4

Comments

Inspired and generalized from Kakuro game, a Japanese crossword type game where cells must be filled with different digits 1..9 adding up to the clues.

If permutations are considered equivalent then a(n) = A111133(n) = A000009(n) - 1.

Links

Table of n, a(n) for n=0..46.

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

Wikipedia, Kakuro.

Formula

a(n) = A032020(n) - 1.

G.f.: (Sum_{k>=0} k!*x^((k^2+k)/2) / Product_{j=1..k} (1-x^j)) - 1/(1-x). - Joerg Arndt, Sep 17 2012

Example

a(4)=2 because 4 = 1+3 = 3+1 (2 ways).
a(6)=10 because 6 = 1+5 = 2+4 = 4+2 = 5+1 = 1+2+3 = 1+3+2 = 2+1+3 = 2+3+1 = 3+1+2 = 3+2+1 (10 ways).

Mathematica

nc[n_]:=Total[Length[#]!&/@Select[IntegerPartitions[n], Length[#]>1&&Max[ Tally[ #][[All, 2]]]==1&]]; Array[nc, 50, 0] (* Harvey P. Dale, May 27 2018 *)

Prog

(PARI)
N=66;  x='x+O('x^N);
gf=sum(k=0, N, k!*x^((k^2+k)/2) / prod(j=1, k, 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. A000009, A032020, A111133.

Sequence in context: A056919 A052175 A102623 * A320069 A002082 A005304

Adjacent sequences: A216692 A216693 A216694 * A216696 A216697 A216698

Keyword

nonn

Author

César Eliud Lozada, Sep 16 2012

Extensions

More terms from Joerg Arndt, Sep 17 2012

Status

approved