A097356 Number of partitions of n into parts not greater than sqrt(n).

1, 1, 1, 1, 3, 3, 4, 4, 5, 12, 14, 16, 19, 21, 24, 27, 64, 72, 84, 94, 108, 120, 136, 150, 169, 377, 427, 480, 540, 603, 674, 748, 831, 918, 1014, 1115, 2432, 2702, 3009, 3331, 3692, 4070, 4494, 4935, 5427, 5942, 6510, 7104, 7760, 16475, 18138, 19928, 21873, 23961

Offset: 0

Author

Reinhard Zumkeller, Aug 08 2004

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..20000
• Vaclav Kotesovec, Graph - the asymptotic ratio

Crossrefs

Cf. A194020, A000196, A000041, A097355.

Programs

Haskell

a097356 n = p [1..a000196 n] n where
   p [] _ = 0
   p _  0 = 1
   p ks'@(k:ks) m | m < k     = 0
                  | otherwise = p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Aug 12 2011

Maple

b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, b(n, i-1)+b(n-i, min(n-i, i))))
    end:
a:= n-> b(n, (r-> `if`(r*r>n, r-1, r))(isqrt(n))):
seq(a(n), n=0..100);  # Alois P. Heinz, Aug 02 2018

Mathematica

Table[Length[IntegerPartitions[n,Floor[Sqrt[n]]]],{n,70}] (* Harvey P. Dale, May 11 2011 *)
f[n_, 1] := 1; f[1, k_] := 1; f[n_, k_] := f[n, k] = If[k > n, f[n, k - 1], f[n, k - 1] + f[n - k, k]]; Table[ f[n, Floor[Sqrt[n]]], {n, 53}] (* Robert G. Wilson v, Aug 13 2011 *)

PARI

a(n,k=sqrtint(n))=if(min(n,k)<2,1,sum(i=1,min(k,n),a(n-i,i))) \\ Charles R Greathouse IV, Aug 12 2011

Formula

a(n^2) ~ c * d^n / n^2, where d = A258268 = 9.153370192454122461948530292401354... and c = 0.1582087202672504149766310999238... [see A206226, constant c(1)]. The upper bound of a(n) is c * d^sqrt(n) / n, see graph. For the lower bound, the constant c = 0.088154883798697116... (conjectured). - Vaclav Kotesovec, Jan 08 2024