A200928 Number of partitions of n such that the number of parts and the smallest part are coprime.

1, 2, 3, 4, 6, 10, 14, 19, 26, 37, 49, 67, 89, 120, 158, 206, 267, 346, 443, 565, 718, 908, 1142, 1431, 1785, 2221, 2749, 3394, 4175, 5128, 6271, 7652, 9311, 11306, 13687, 16538, 19931, 23977, 28776, 34470, 41203, 49173, 58559, 69625, 82630, 97913, 115816

Offset

1,2

Links

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

Formula

a(n) = A000041(n) - A201025(n).

Example

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

Maple

with (combinat):
b:= proc(n, j, t, s) option remember;
      add (b(n-i, i, irem(t+1, s), s), i=j..iquo(n, 2))+
      `if`(igcd(t, s)=1, 1, 0)
    end:
a:= n-> numbpart(n-1) +`if`(n>1, 1, 0) +add (b(n-i, i, 2, i), i=2..iquo(n, 2)):
seq (a(n), n=1..50);

Mathematica

b[n_, j_, t_, s_] := b[n, j, t, s] = Sum[b[n-i, i, Mod[t+1, s], s], {i, j, Quotient[n, 2]}] + If[GCD[t, s]==1, 1, 0]; a[n_] := PartitionsP[n-1] + If[n>1, 1, 0] + Sum [b[n-i, i, 2, i], {i, 2, Quotient[n, 2]}]; Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Feb 15 2017, translated from Maple *)

Crossrefs

Cf. A000041, A199888, A201025.

Sequence in context: A121152 A229863 A215255 * A318558 A347867 A256248

Adjacent sequences: A200925 A200926 A200927 * A200929 A200930 A200931

Keyword

nonn

Author

Alois P. Heinz, Nov 25 2011

Status

approved