A114374 Number of partitions of n into parts that are not squarefree.

1, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 3, 1, 0, 0, 5, 2, 2, 0, 7, 3, 2, 0, 11, 6, 4, 3, 15, 8, 6, 3, 22, 13, 11, 6, 34, 18, 15, 9, 46, 27, 24, 17, 64, 43, 33, 23, 89, 60, 51, 37, 124, 84, 78, 51, 166, 119, 109, 78, 226, 168, 152, 118, 300, 228, 215, 166, 404, 313, 300, 230, 546, 421, 409

Offset

0,9

Comments

a(A078135(n)) = 0; a(A078137(n)) > 0.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Formula

a(n) = A000041(n) - A073576(n) - A117395(n). - Reinhard Zumkeller, Mar 11 2006

G.f.: Product_{k>=1} (1 - mu(k)^2*x^k)/(1 - x^k), where mu(k) is the Moebius function (A008683). - Ilya Gutkovskiy, Dec 30 2016

Example

a(12) = #{2*2*3, 2*2*2 + 2*2, 2*2 + 2*2 + 2*2} = 3;
a(13) = #{3*3 + 2*2} = 1.

Maple

with(numtheory):
b:= proc(n, i) option remember;
      `if`(n=0, 1, `if`(i<1, 0, b(n, i-1)+
      `if`(i>n or issqrfree(i), 0, b(n-i, i))))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 03 2015

Mathematica

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i>n || SquareFreeQ[i], 0, b[n-i, i]]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jun 30 2015, after Alois P. Heinz *)

Prog

(Haskell)
a114374 = p a013929_list where
   p _          0 = 1
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Jun 01 2015

Crossrefs

Cf. A013929, A073576.

Cf. A256012.

Sequence in context: A136263 A105593 A029371 * A111505 A109264 A322393

Adjacent sequences: A114371 A114372 A114373 * A114375 A114376 A114377

Keyword

nonn

Author

Reinhard Zumkeller, Feb 09 2006

Extensions

Offset changed and a(0)=1 prepended by Reinhard Zumkeller, Jun 01 2015

Status

approved