A168657 Number of partitions of n such that the number of parts is divisible by the smallest part.

1, 1, 2, 4, 6, 8, 12, 17, 25, 34, 48, 64, 87, 114, 151, 198, 258, 332, 428, 546, 695, 879, 1108, 1388, 1737, 2159, 2680, 3312, 4082, 5009, 6138, 7492, 9126, 11081, 13429, 16228, 19575, 23547, 28277, 33879, 40520, 48354, 57615, 68509, 81337, 96388, 114055

Offset: 1

Author

Vladeta Jovovic, Dec 02 2009

Keywords

• easy
• nonn

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 1..9464 (terms 1..1000 from Alois P. Heinz)

Crossrefs

Cf. A079501, A168655, A168656.

Programs

Maple

b:= proc(n, i, t) option remember;
      `if`(n<1, 0, `if`(i=1, 1, `if`(i<1, 0,
      `if`(irem(n, i)=0 and irem(t+n/i, i)=0, 1, 0)+
            add(b(n-i*j, i-1, t+j), j=0..n/i))))
    end:
a:= n-> b(n, n, 0):
seq(a(n), n=1..60);  # Alois P. Heinz, May 24 2012

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[n<1, 0, If[i==1, 1, If[i<1, 0, If [Mod[n, i]==0 && Mod[t+n/i, i]==0, 1, 0] + Sum[b[n-i*j, i-1, t+j], {j, 0, n/i}]]]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Jul 01 2015, after Alois P. Heinz *)
Table[Count[IntegerPartitions[n],?(Mod[Length[#],#[[-1]]]==0&)],{n,50}] (* _Harvey P. Dale, Jul 16 2025 *)

PARI

my(N=66, x='x+O('x^N)); Vec(sum(i=1, N, sum(j=1, sqrtint(N\i), x^(i*j^2)/prod(k=1, i*j-1, 1-x^k)))) \\ Seiichi Manyama, Jan 21 2022

Formula

G.f.: Sum_{n>=1} Sum_{d|n} x^(n*d)/Product_{k=1..n-1}(1-x^k).

G.f.: Sum_{i>=1} Sum_{j>=1} x^(i*j^2)/Product_{k=1..i*j-1} (1-x^k). - Seiichi Manyama, Jan 21 2022

From Vaclav Kotesovec, Oct 17 2024: (Start)

a(n) ~ exp(Pi*sqrt(2*n/3)) / (4*n*sqrt(3)) * (1 - (sqrt(3/2)/Pi + 13*Pi / (2^(7/2) * 3^(3/2))) / sqrt(n)).

A000041(n) - a(n) ~ Pi * exp(Pi*sqrt(2*n/3)) / (3 * 2^(7/2) * n^(3/2)). (End)