login
Number of integer partitions of n with no part dividing all the others.
24

%I #20 May 09 2021 12:45:18

%S 1,0,0,0,0,1,0,3,2,5,5,13,7,23,21,33,35,65,55,104,97,151,166,252,235,

%T 377,399,549,591,846,858,1237,1311,1749,1934,2556,2705,3659,3991,5090,

%U 5608,7244,7841,10086,11075,13794,15420,19195,21003,26240,29089,35483

%N Number of integer partitions of n with no part dividing all the others.

%C Alternative name: Number of integer partitions of n that are empty or have smallest part not dividing all the others.

%H Andrew Howroyd, <a href="/A338470/b338470.txt">Table of n, a(n) for n = 0..1000</a>

%F a(n) = A000041(n) - Sum_{d|n} A000041(d-1) for n > 0. - _Andrew Howroyd_, Mar 25 2021

%e The a(5) = 1 through a(12) = 7 partitions (empty column indicated by dot):

%e (32) . (43) (53) (54) (64) (65) (75)

%e (52) (332) (72) (73) (74) (543)

%e (322) (432) (433) (83) (552)

%e (522) (532) (92) (732)

%e (3222) (3322) (443) (4332)

%e (533) (5322)

%e (542) (33222)

%e (632)

%e (722)

%e (3332)

%e (4322)

%e (5222)

%e (32222)

%t Table[Length[Select[IntegerPartitions[n],#=={}||!And@@IntegerQ/@(#/Min@@#)&]],{n,0,30}]

%t (* Second program: *)

%t a[n_] := If[n == 0, 1, PartitionsP[n] - Sum[PartitionsP[d-1], {d, Divisors[n]}]];

%t a /@ Range[0, 50] (* _Jean-François Alcover_, May 09 2021, after _Andrew Howroyd_ *)

%o (PARI) a(n)={numbpart(n) - if(n, sumdiv(n, d, numbpart(d-1)))} \\ _Andrew Howroyd_, Mar 25 2021

%Y The complement is A083710 (strict: A097986).

%Y The strict case is A341450.

%Y The Heinz numbers of these partitions are A342193.

%Y The dual version is A343341.

%Y The case with maximum part not divisible by all the others is A343342.

%Y The case with maximum part divisible by all the others is A343344.

%Y A000005 counts divisors.

%Y A000041 counts partitions.

%Y A000070 counts partitions with a selected part.

%Y A001787 count normal multisets with a selected position.

%Y A006128 counts partitions with a selected position.

%Y A015723 counts strict partitions with a selected part.

%Y A167865 counts strict chains of divisors > 1 summing to n.

%Y A276024 counts positive subset sums.

%Y Sequences with similar formulas: A024994, A047966, A047968, A168111.

%Y Cf. A001792, A064391, A064410, A066186, A067824, A083711, A098965, A264401, A339562, A339563.

%K nonn

%O 0,8

%A _Gus Wiseman_, Mar 23 2021