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

%I #29 Jan 08 2024 09:28:42

%S 1,1,1,1,3,3,4,4,5,12,14,16,19,21,24,27,64,72,84,94,108,120,136,150,

%T 169,377,427,480,540,603,674,748,831,918,1014,1115,2432,2702,3009,

%U 3331,3692,4070,4494,4935,5427,5942,6510,7104,7760,16475,18138,19928,21873,23961

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

%H Alois P. Heinz, <a href="/A097356/b097356.txt">Table of n, a(n) for n = 0..20000</a>

%H Vaclav Kotesovec, <a href="/A097356/a097356.jpg">Graph - the asymptotic ratio</a>

%F 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

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

%p `if`(i<1, 0, b(n, i-1)+b(n-i, min(n-i, i))))

%p end:

%p a:= n-> b(n, (r-> `if`(r*r>n, r-1, r))(isqrt(n))):

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

%t Table[Length[IntegerPartitions[n,Floor[Sqrt[n]]]],{n,70}] (* _Harvey P. Dale_, May 11 2011 *)

%t 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 *)

%o (Haskell)

%o a097356 n = p [1..a000196 n] n where

%o p [] _ = 0

%o p _ 0 = 1

%o p ks'@(k:ks) m | m < k = 0

%o | otherwise = p ks' (m - k) + p ks m

%o -- _Reinhard Zumkeller_, Aug 12 2011

%o (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

%Y Cf. A194020, A000196, A000041, A097355.

%K nonn

%O 0,5

%A _Reinhard Zumkeller_, Aug 08 2004