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,2

Links

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

Formula

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

Example

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

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

Crossrefs

Cf. A000079, A199887.

Sequence in context: A318086 A244049 A271229 * A117779 A300952 A195326

Adjacent sequences: A199883 A199884 A199885 * A199887 A199888 A199889

Keyword

nonn

Author

Alois P. Heinz, Nov 11 2011

Status

approved