|
%I #46 Nov 29 2020 02:11:08
%S 1,1,4,33,385,11483,305684,24306812,1472403740,247008653639,
%T 34519470848749,12828108172960015,1928570926371392597
%N Number of partitions of n into rational parts a/b such that 1<=a,b<=n and gcd(a,b)=1.
%C A018805 is the number of rational parts a/b, such that 1<=a,b<=n and gcd(a,b)=1.
%e For n=2, the rational parts a/b, such that 1<=a,b<= n and gcd(a,b)=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 a:= proc(n) option remember; local l, b; l, b:=
%p sort([{seq(seq(x/y, y=1..n), x=1..n)}[]]),
%p proc(r, i) option remember; `if`(r=0, 1,
%p `if`(i<1, 0, add(b(r-l[i]*j, i-1), j=
%p `if`(i=1, r/l[i], 0..r/l[i]))))
%p end; b(n, nops(l))
%p end:
%p seq(a(n), n=0..7); # _Alois P. Heinz_, Mar 14 2020
%t 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 a /@ Range[0, 7] (* _Jean-François Alcover_, Nov 29 2020, after _Alois P. Heinz_ *)
%o (Sage)
%o from itertools import combinations_with_replacement
%o seq = []
%o for n in range( 1, 5 ):
%o rationals = set()
%o for a in range( 1, n+1 ):
%o for b in range( 1, n+1 ):
%o rational = Rational( (a, b) )
%o rationals.add( rational )
%o partition_count = 0
%o for r in range( 1, n^2 + 1 ):
%o for partition in combinations_with_replacement( rationals, r ):
%o if sum( partition ) == n:
%o partition_count += 1
%o seq.append( partition_count )
%o print(seq)
%o (Sage)# Faster version
%o def count_combinations( n, values, r ):
%o combo = [ None ] * r
%o level = 0
%o min_index = 0
%o count = 0
%o return get_count( n, values, r, combo, level, min_index, count )
%o def get_count( n, values, r, combo, level, min_index, count ):
%o if level < r:
%o for i in range( min_index, len( values ) ):
%o combo[level] = values[i]
%o if sum( combo[0:level] ) < n:
%o count = get_count( n, values, r, combo, level+1, i, count )
%o else:
%o if sum( combo ) == n:
%o count += 1
%o return count
%o seq = []
%o for n in range( 1, 5 ):
%o rational_set = set()
%o for a in range( 1, n+1 ):
%o for b in range( 1, n+1 ):
%o rational = Rational( (a, b) )
%o rational_set.add( rational )
%o rationals = sorted( list( rational_set ) )
%o partition_count = 0
%o for r in range( 1, n^2 + 1 ):
%o partition_count += count_combinations( n, rationals, r )
%o seq.append( partition_count )
%o print(seq)
%Y Cf. A018805, A119983, A209489.
%K nonn,more
%O 0,3
%A _Robert C. Lyons_, Mar 07 2016
%E a(0), a(7)-a(12) from _Alois P. Heinz_, Mar 14 2020
|
