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

1, 1, 4, 33, 385, 11483, 305684, 24306812, 1472403740, 247008653639, 34519470848749, 12828108172960015, 1928570926371392597

Offset

0,3

Comments

A018805 is the number of rational parts a/b, such that 1<=a,b<=n and gcd(a,b)=1.

Links

Table of n, a(n) for n=0..12.

Example

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 }.

Maple

a:= proc(n) option remember; local l, b; l, b:=
      sort([{seq(seq(x/y, y=1..n), x=1..n)}[]]),
      proc(r, i) option remember; `if`(r=0, 1,
        `if`(i<1, 0, add(b(r-l[i]*j, i-1), j=
        `if`(i=1, r/l[i], 0..r/l[i]))))
      end; b(n, nops(l))
    end:
seq(a(n), n=0..7);  # Alois P. Heinz, Mar 14 2020

Mathematica

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]]];
a /@ Range[0, 7] (* Jean-François Alcover, Nov 29 2020, after Alois P. Heinz *)

Prog

(Sage)
from itertools import combinations_with_replacement
seq = []
for n in range( 1, 5 ):
    rationals = set()
    for a in range( 1, n+1 ):
        for b in range( 1, n+1 ):
            rational = Rational( (a, b) )
            rationals.add( rational )
    partition_count = 0
    for r in range( 1, n^2 + 1 ):
        for partition in combinations_with_replacement( rationals, r ):
            if sum( partition ) == n:
                partition_count += 1
    seq.append( partition_count )
print(seq)
(Sage)# Faster version
def count_combinations( n, values, r ):
    combo = [ None ] * r
    level = 0
    min_index = 0
    count = 0
    return get_count( n, values, r, combo, level, min_index, count )
def get_count( n, values, r, combo, level, min_index, count ):
    if level < r:
        for i in range( min_index, len( values ) ):
            combo[level] = values[i]
            if sum( combo[0:level] ) < n:
                count = get_count( n, values, r, combo, level+1, i, count )
    else:
        if sum( combo ) == n:
            count += 1
    return count
seq = []
for n in range( 1, 5 ):
    rational_set = set()
    for a in range( 1, n+1 ):
        for b in range( 1, n+1 ):
            rational = Rational( (a, b) )
            rational_set.add( rational )
    rationals = sorted( list( rational_set ) )
    partition_count = 0
    for r in range( 1, n^2 + 1 ):
        partition_count += count_combinations( n, rationals, r )
    seq.append( partition_count )
print(seq)

Crossrefs

Cf. A018805, A119983, A209489.

Sequence in context: A293020 A293193 A295256 * A331794 A156132 A215364

Adjacent sequences: A269923 A269924 A269925 * A269927 A269928 A269929

Keyword

nonn,more

Author

Robert C. Lyons, Mar 07 2016

Extensions

a(0), a(7)-a(12) from Alois P. Heinz, Mar 14 2020

Status

approved