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

1, 2, 2, 7, 7, 18, 40, 85, 148, 285, 584, 1231, 2516, 5069, 10175, 20306, 40000, 78328, 154233, 307586, 620903, 1262129, 2566697, 5193429, 10424746, 20761986, 41131719, 81358316, 161239595, 320900400, 641688619, 1287937462, 2589941043, 5208522925, 10461756080

Offset: 1

Author

Alois P. Heinz, Nov 11 2011

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Cf. A000079, A199887.

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) - A199887(n).