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

Links

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

Formula

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

Example

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].

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, A199886, A200792.

Sequence in context: A192352 A180001 A204371 * A058876 A214884 A083162

Adjacent sequences: A199884 A199885 A199886 * A199888 A199889 A199890

Keyword

nonn

Author

Alois P. Heinz, Nov 11 2011

Status

approved