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

Author

César Eliud Lozada, Sep 16 2012

Keywords

• nonn

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.

Examples

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

Links

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

Crossrefs

Cf. A000009, A032020, A111133.

Programs

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

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

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

Extensions

More terms from Joerg Arndt, Sep 17 2012