cp's OEIS Frontend

A171978 Number of partitions of n into fractions k/(k+1), 0 < k <= n.

%I A171978 #25 Dec 13 2024 09:30:56
%S A171978 1,1,2,4,7,22,37,84,172,454,745,2904,4722,10464,38546,88769,147439,
%T A171978 475153,785894,3140342,10412267,19169464,32132160,125087460,224341028,
%U A171978 394553026,799614318,3108061596,5172450911,21360507716,35407697816,81523452326,238510777299
%N A171978 Number of partitions of n into fractions k/(k+1), 0 < k <= n.
%H A171978 <a href="/index/Par#partN">Index entries for sequences related to partitions</a>
%F A171978 a(n) = q(n, 1) with q(x, k) = if x < k/(k+1) then 0^x else if k > n then 0 else q(x-k/(k+1), k) + q(x, k+1).
%e A171978 a(3) = 4 partitions into parts 1/2, 2/3, or 3/4:
%e A171978   #1: 3/4 + 3/4 + 3/4 + 3/4 = 3,
%e A171978   #2: (3/4 + 3/4) + (1/2 + 1/2 + 1/2) = 3,
%e A171978   #3: (2/3 + 2/3 + 2/3) + (1/2 + 1/2) = 3,
%e A171978   #4: 1/2 + 1/2 + 1/2 + 1/2 + 1/2 + 1/2 = 3;
%e A171978 a(4) = 7 partitions into parts 1/2, 2/3, 3/4, or 4/5:
%e A171978   #1: 4/5 + 4/5 + 4/5 + 4/5 + 4/5 = 4,
%e A171978   #2: (3/4 + 3/4 + 3/4 + 3/4) + (1/2 + 1/2) = 4,
%e A171978   #3: (3/4 + 3/4) + (2/3 + 2/3 + 2/3) + 1/2 = 4,
%e A171978   #4: (3/4 + 3/4) + (1/2 + 1/2 + 1/2 + 1/2 + 1/2) = 4,
%e A171978   #5: 2/3 + 2/3 + 2/3 + 2/3 + 2/3 + 2/3 = 4,
%e A171978   #6: (2/3 + 2/3 + 2/3) + (1/2 + 1/2 + 1/2 + 1/2) = 4,
%e A171978   #7: 1/2 + 1/2 + 1/2 + 1/2 + 1/2 + 1/2 + 1/2 + 1/2 = 4.
%p A171978 b:= proc(n, k) option remember;
%p A171978       `if`(n=0, 1, `if`(k=0 or isprime(k+2) and irem(denom(n),
%p A171978        k+2)=0, 0, b(n, k-1)+`if`(k>k*n+n, 0, b(n-k/(k+1), k))))
%p A171978     end:
%p A171978 a:= n-> b(n, n):
%p A171978 seq(a(n), n=0..16);  # _Alois P. Heinz_, Jul 18 2012
%t A171978 b[n_, k_] := b[n, k] = If[n==0, 1, If[k==0 || PrimeQ[k+2] && Mod[ Denominator[n], k+2]==0, 0, b[n, k-1] + If[k>k*n+n, 0, b[n-k/(k+1), k]]] ]; a[n_] := b[n, n]; Table[a[n], {n, 0, 16}] (* _Jean-François Alcover_, Feb 16 2017, after _Alois P. Heinz_ *)
%o A171978 (Haskell)
%o A171978 -- import Data.Ratio ((%))
%o A171978 a171978 n = q (fromInteger n) $ zipWith (%) [1..n] [2..] where
%o A171978    q 0 _         = 1
%o A171978    q _ []        = 0
%o A171978    q x ks'@(k:ks)
%o A171978      | x < k     = fromEnum (x == 0)
%o A171978      | otherwise = q (x - k) ks' + q x ks
%o A171978 -- _Reinhard Zumkeller_, Apr 01 2012
%K A171978 nonn
%O A171978 0,3
%A A171978 _Reinhard Zumkeller_, Jan 20 2010
%E A171978 Offset corrected and a(16) added by _Reinhard Zumkeller_, Apr 01 2012
%E A171978 a(17)-a(23) from _Alois P. Heinz_, Jul 18 2012
%E A171978 a(24) from _Alois P. Heinz_, Sep 27 2014
%E A171978 a(25)-a(32) from _Jinyuan Wang_, Dec 13 2024