cp's OEIS Frontend

A269926 Number of partitions of n into rational parts i/j such that 1 <= i,j <= n and gcd(i,j) = 1.

%I A269926 #53 Dec 20 2024 13:03:50
%S A269926 1,1,4,33,385,11483,305684,24306812,1472403740,247008653639,
%T A269926 34519470848749,12828108172960015,1928570926371392597,
%U A269926 1431184075250830915405,670210514199929067110226,1159071708111028412649897690,702243565303276226975262410876,1815785932270337215073101716635095
%N A269926 Number of partitions of n into rational parts i/j such that 1 <= i,j <= n and gcd(i,j) = 1.
%C A269926 A018805 is the number of rational parts i/j, such that 1 <= i,j <= n and gcd(i,j) = 1.
%e A269926 For n = 2, the rational parts i/j, such that 1 <= i,j <= n and gcd(i,j) = 1, are: { 1/1, 1/2, 2/1 }. a(2) = 4 because 2 can be partitioned into the following 4 partitions: { 1/2, 1/2, 1/2, 1/2 }, { 1/1, 1/2, 1/2 }, { 1/1, 1/1 }, { 2/1 }.
%p A269926 a:= proc(n) option remember; local l, b; l, b:=
%p A269926       sort([{seq(seq(x/y, y=1..n), x=1..n)}[]]),
%p A269926       proc(r, i) option remember; `if`(r=0, 1,
%p A269926         `if`(i<1, 0, add(b(r-l[i]*j, i-1), j=
%p A269926         `if`(i=1, r/l[i], 0..r/l[i]))))
%p A269926       end; b(n, nops(l))
%p A269926     end:
%p A269926 seq(a(n), n=0..7);  # _Alois P. Heinz_, Mar 14 2020
%t A269926 a[n_] := a[n] = Module[{l, b}, l = Union@ Flatten@ Table[x/y, {y, 1, n}, {x, 1, n}]; b[r_, i_] := b[r, i] = If[r == 0, 1, If[i < 1, 0, Sum[b[r - l[[i]] j, i - 1], {j, If[i == 1, r/l[[i]], Range[0, r/l[[i]]]]}]]]; b[n, Length[l]]];
%t A269926 a /@ Range[0, 7] (* _Jean-François Alcover_, Nov 29 2020, after _Alois P. Heinz_ *)
%o A269926 (Sage)
%o A269926 from itertools import combinations_with_replacement
%o A269926 seq = []
%o A269926 for n in range( 1, 5 ):
%o A269926     rationals = set()
%o A269926     for a in range( 1, n+1 ):
%o A269926         for b in range( 1, n+1 ):
%o A269926             rational = Rational( (a, b) )
%o A269926             rationals.add( rational )
%o A269926     partition_count = 0
%o A269926     for r in range( 1, n^2 + 1 ):
%o A269926         for partition in combinations_with_replacement( rationals, r ):
%o A269926             if sum( partition ) == n:
%o A269926                 partition_count += 1
%o A269926     seq.append( partition_count )
%o A269926 print(seq)
%o A269926 (Sage)# Faster version
%o A269926 def count_combinations( n, values, r ):
%o A269926     combo = [ None ] * r
%o A269926     level = 0
%o A269926     min_index = 0
%o A269926     count = 0
%o A269926     return get_count( n, values, r, combo, level, min_index, count )
%o A269926 def get_count( n, values, r, combo, level, min_index, count ):
%o A269926     if level < r:
%o A269926         for i in range( min_index, len( values ) ):
%o A269926             combo[level] = values[i]
%o A269926             if sum( combo[0:level] ) < n:
%o A269926                 count = get_count( n, values, r, combo, level+1, i, count )
%o A269926     else:
%o A269926         if sum( combo ) == n:
%o A269926             count += 1
%o A269926     return count
%o A269926 seq = []
%o A269926 for n in range( 1, 5 ):
%o A269926     rational_set = set()
%o A269926     for a in range( 1, n+1 ):
%o A269926         for b in range( 1, n+1 ):
%o A269926             rational = Rational( (a, b) )
%o A269926             rational_set.add( rational )
%o A269926     rationals = sorted( list( rational_set ) )
%o A269926     partition_count = 0
%o A269926     for r in range( 1, n^2 + 1 ):
%o A269926         partition_count += count_combinations( n, rationals, r )
%o A269926     seq.append( partition_count )
%o A269926 print(seq)
%Y A269926 Cf. A018805, A115855, A119983.
%K A269926 nonn
%O A269926 0,3
%A A269926 _Robert C. Lyons_, Mar 07 2016
%E A269926 a(0), a(7)-a(12) from _Alois P. Heinz_, Mar 14 2020
%E A269926 More terms from _Jinyuan Wang_, Dec 12 2024