login
Number of compositions (ordered partitions) of n into n parts, allowing zeros, with distinct nonzero parts.
1

%I #14 Jan 29 2014 07:04:22

%S 1,2,9,16,45,186,343,848,1809,8290,13431,33672,66157,143066,591165,

%T 966016,2180913,4281570,8776423,15865400,67586841,101053282,226690047,

%U 420479952,845781625,1476079826,2830894353,10479645568,15758982597,33145324410,60465162751

%N Number of compositions (ordered partitions) of n into n parts, allowing zeros, with distinct nonzero parts.

%H Alois P. Heinz, <a href="/A097965/b097965.txt">Table of n, a(n) for n = 1..1000</a>

%p b:= proc(n, i) option remember; `if`(n=0, [1],

%p `if`(n>i*(i+1)/2, [], zip((x, y)->x+y, b(n, i-1),

%p `if`(i>n, [], [0, b(n-i, i-1)[]]), 0)))

%p end:

%p a:= proc(n) local l; l:= b(n$2);

%p add(l[i+1]*i!*binomial(n, i), i=1..nops(l)-1)

%p end:

%p seq (a(n), n=1..40); # _Alois P. Heinz_, Nov 20 2012

%t zip[f_, x_List, y_List, z_] := With[{m = Max[Length[x], Length[y]]}, Thread[f[PadRight[x, m, z], PadRight[y, m, z]]]]; b[n_, i_] := b[n, i] = If[n == 0, {1}, If[n > i*(i+1)/2, {}, zip[Plus, b[n, i-1], If[i>n, {}, Join[{0}, b[n-i, i-1]]], 0]]]; a[n_] := Module[{l}, l = b[n, n]; Sum[l[[i+1]]*i!*Binomial[n, i], {i, 1, Length[l]-1}]]; Table[a[n], {n, 1, 40}] (* _Jean-François Alcover_, Jan 29 2014, after _Alois P. Heinz_ *)

%Y Cf. A088218, A032020.

%K nonn

%O 1,2

%A _Vladeta Jovovic_, Sep 21 2004