A199885 Number of compositions of n such that the greatest part is not divisible by the number of parts.

0, 1, 1, 6, 10, 23, 49, 106, 215, 444, 906, 1849, 3759, 7621, 15402, 31091, 62676, 126206, 253860, 510204, 1024665, 2056608, 4125625, 8272436, 16580967, 33223336, 66550937, 133278720, 266857006, 534220745, 1069297319, 2140037990, 4282507048, 8569103770

Offset: 1

Author

Alois P. Heinz, Nov 11 2011

Keywords

• nonn

Examples

			a(4) = 6: [1,1,1,1], [1,1,2], [1,2,1], [1,3], [2,1,1], [3,1].
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..250

Crossrefs

Cf. A000079, A171632, A200727.

Programs

Maple

b:= proc(n, t, g) option remember; `if`(n=0, `if`(irem(g, t)=0, 0, 1), add(b(n-i, t+1, max(i, g)), i=1..n)) end: a:= n-> b(n, 0, 0): seq(a(n), n=1..40);

Mathematica

b[n_, t_, g_] := b[n, t, g] = If[n == 0, If[Mod[g, t] == 0, 0, 1], Sum [b[n-i, t+1, Max[i, g]], {i, 1, n}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Nov 05 2014, after Alois P. Heinz *)

Formula

G.f.: Sum_{n>0} (2^(n-1)*x^n-Sum_{d|n} ((x^(n+1)-x)^d-(x^n-x)^d)/(x-1)^d).

a(n) = A000079(n-1) - A171632(n).