A199887 Number of compositions of n such that the number of parts and the greatest part are not coprime.

0, 0, 2, 1, 9, 14, 24, 43, 108, 227, 440, 817, 1580, 3123, 6209, 12462, 25536, 52744, 107911, 216702, 427673, 835023, 1627607, 3195179, 6352470, 12792446, 25977145, 52859412, 107195861, 215970512, 432053205, 859546186, 1705026253, 3381411667, 6718113104

Offset: 1

Author

Alois P. Heinz, Nov 11 2011

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Cf. A000079, A199886, A200792.

Programs

Maple

b:= proc(n, t, g) option remember;
      `if`(n=0, `if`(igcd(g, t)<>1, 1, 0),
       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[GCD[g, t] != 1, 1, 0], 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

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