login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A225244 Number of partitions of n into squarefree divisors of n. 10

%I #21 Nov 03 2023 11:09:15

%S 1,1,2,2,3,2,8,2,5,4,11,2,27,2,14,14,9,2,64,2,40,18,20,2,125,6,23,10,

%T 53,2,742,2,17,26,29,26,343,2,32,30,195,2,1654,2,79,136,38,2,729,8,

%U 341,38,92,2,1000,38,265,42,47,2,14188,2,50,184,33,44,5257,2

%N Number of partitions of n into squarefree divisors of n.

%C a(n) <= A018818(n);

%C a(n) = A018818(n) iff n is squarefree: a(A005117(n)) = A018818(A005117(n));

%C a(A000040(n)) = 2.

%H Alois P. Heinz, <a href="/A225244/b225244.txt">Table of n, a(n) for n = 0..10000</a> (300 terms from Reinhard Zumkeller)

%F a(n) = [x^n] Product_{d|n, mu(d) != 0} 1/(1 - x^d), where mu() is the Moebius function (A008683). - _Ilya Gutkovskiy_, Jul 26 2017

%e a(8) = #{2+2+2+2, 2+2+2+1+1, 2+2+1+1+1+1, 2+6x1, 8x1} = 5;

%e a(9) = #{3+3+3, 3+3+1+1+1, 3+1+1+1+1+1+1, 9x1} = 4;

%e a(10) = #{10, 5+5, 5+2+2+1, 5+2+1+1+1, 5+5x1, 2+2+2+2+2, 2+2+2+2+1+1, 2+2+2+1+1+1+1, 2+2+6x1, 2+8x1, 10x1} = 11;

%e a(11) = #{11, 1+1+1+1+1+1+1+1+1+1+1} = 2;

%e a(12) = #{6+6, 6+3+3, 6+3+2+1, 6+3+1+1+1, 6+2+2+2, 6+2+2+1+1, 6+2+1+1+1+1, 6+6x1, 3+3+3+3, 3+3+3+2+1, 3+3+3+1+1+1, 3+3+2+2+2, 3+3+2+2+1+1, 3+3+2+4x1, 3+3+6x1, 3+2+2+2+2+1, 3+2+2+2+1+1+1, 3+2+2+5x1, 3+2+7x1, 3+8x1, 2+2+2+2+2+2, 2+2+2+2+2+1+1, 2+2+2+2+1+1+1+1, 2+2+2+6x1, 2+2+8x1, 2+10x1, 12x1} = 27;

%e a(13) = #{11, 1+1+1+1+1+1+1+1+1+1+1+1+1} = 2;

%e a(14) = #{14, 7+7, 7+2+2+2+1, 7+2+2+1+1+1, 7+2+5x1, 7+7x1, 7x2, 6x2+1+1, 5x2+1+1+1+1, 4x2+6x1, 2+2+2+8x1, 2+2+10x1, 2+12x1, 14x1} = 14;

%e a(15) = #{15, 5+5+5, 5+5+3+1+1, 5+5+5x1, 5+3+3+3+1, 5+3+3+1+1+1+1, 5+3+7x1, 5+10x1, 3+3+3+3+3, 3+3+3+3+1+1+1, 3+3+3+6x1, 3+3+9x1, 3+12x1, 15x1} = 14.

%p with(numtheory):

%p a:= proc(n) local b, l; l:= sort([select(issqrfree, divisors(n))[]]):

%p b:= proc(m, i) option remember; `if`(m=0 or i=1, 1,

%p `if`(i<1, 0, b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i))))

%p end; forget(b):

%p b(n, nops(l))

%p end:

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Feb 05 2014

%t a[0] = 1; a[n_] := Module[{b, l}, l = Select[Divisors[n], SquareFreeQ]; b[m_, i_] := b[m, i] = If[m == 0 || i == 1, 1, If[i < 1, 0, b[m, i - 1] + If[l[[i]] > m, 0, b[m - l[[i]], i]]]]; b[n, Length[l]]]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Oct 27 2015, after _Alois P. Heinz_ *)

%o (Haskell)

%o a225244 n = p (a206778_row n) n where

%o p _ 0 = 1

%o p [] _ = 0

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

%Y Cf. A206778, A005117, A008966, A225245, A073576.

%K nonn

%O 0,3

%A _Reinhard Zumkeller_, May 05 2013

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 04:59 EDT 2024. Contains 371264 sequences. (Running on oeis4.)