login
Number of partitions of n into distinct parts that are not squarefree.
5

%I #25 Dec 31 2016 01:29:25

%S 1,0,0,0,1,0,0,0,1,1,0,0,2,1,0,0,2,1,1,0,3,2,1,0,4,3,1,2,5,4,2,2,6,5,

%T 3,2,9,7,4,4,11,8,5,5,13,13,7,7,17,17,9,9,22,20,15,12,27,26,19,15,33,

%U 33,23,23,41,41,30,29,49,51,39,35,65,63,50,47,79

%N Number of partitions of n into distinct parts that are not squarefree.

%C Conjecture: a(n) > 0 for n > 23.

%H Alois P. Heinz, <a href="/A256012/b256012.txt">Table of n, a(n) for n = 0..10000</a>

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

%e First nonsquarefree numbers: 4,8,9,12,16,18,20,24,25,27,28, ... hence

%e a(20) = #{20, 16+4, 12+8} = 3;

%e a(21) = #{12+9, 9+8+4} = 2;

%e a(22) = #{18+4} = 1;

%e a(23) = #{ } = 0;

%e a(24) = #{24, 20+4, 16+8, 12+8+4} = 4;

%e a(25) = #{25, 16+9, 12+9+4} = 3.

%p with(numtheory):

%p b:= proc(n, i) option remember;

%p `if`(i*(i+1)/2<n, 0, `if`(n=0, 1, b(n, i-1)+

%p `if`(i>n or issqrfree(i), 0, b(n-i, i-1))))

%p end:

%p a:= n-> b(n$2):

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Jun 02 2015

%t b[n_, i_] := b[n, i] = If[i*(i+1)/2<n, 0, If[n==0, 1, b[n, i-1] + If[i>n || SquareFreeQ[i], 0, b[n-i, i-1]]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Oct 22 2015, after _Alois P. Heinz_ *)

%o (Haskell)

%o a256012 = p a013929_list where

%o p _ 0 = 1

%o p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m

%Y Cf. A013929, A114374, A087188.

%K nonn

%O 0,13

%A _Reinhard Zumkeller_, Jun 01 2015