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

1, 1, 4, 33, 385, 11483, 305684, 24306812, 1472403740, 247008653639, 34519470848749, 12828108172960015, 1928570926371392597, 1431184075250830915405, 670210514199929067110226, 1159071708111028412649897690, 702243565303276226975262410876, 1815785932270337215073101716635095

Offset: 0

Author

Robert C. Lyons, Mar 07 2016

Keywords

• nonn

Comments

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

Examples

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

Crossrefs

Cf. A018805, A115855, A119983.

Programs

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

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)

Extensions

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

More terms from Jinyuan Wang, Dec 12 2024