A119983 -id:A119983 - cp's OEIS frontend

A154886 Number of ways to partition n into reduced fractions i/j with j <= n.

1, 5, 51, 655, 20980, 578779, 46097340, 2889706132, 485416306983, 68334145684271, 24330218582223815, 3847311627258606534, 2716890193805515507433, 1270766589764097820833691, 2188031110546839992589840986, 1331298554328475793875243619997

Offset: 1

Reinhard Zumkeller, Jan 17 2009

nonn

			a(2) = #{2, 3/2+1/2, 1+1, 1+1/2+1/2, 1/2+1/2+1/2+1/2} = 5.

Robert Gerbicz, Table of n, a(n) for n = 1..43

Cf. A154887, A119983, A143270.

modifiedFarey[n_] := Union@ Flatten@ Table[a/b, {b, n}, {a, b*n}]; t[n_, k_] := Length@ IntegerPartitions[n, {k}, modifiedFarey@ n]; Plus @@@ Table[t[n, k], {n, 7, 7}, {k, n*(Plus @@ EulerPhi@ Range@n)}] (* Robert G. Wilson v, Aug 30 2010 *)

a(7) from Robert G. Wilson v, Aug 30 2010

a(8)-a(16) from Robert Gerbicz, Nov 19 2010

A154888 Number of ways to partition 1 into distinct reduced fractions i/j with j <= n.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 16, 24, 37, 48, 71, 88, 133, 284, 435, 472, 773, 826, 1835, 4369, 5546, 5649, 9924, 16465, 19944, 32324, 75913, 76168, 140802, 141141, 238514, 537697, 598296, 2556065, 4674085, 4674844, 4985386, 9716587, 23983712, 23984971, 48523606, 48525215

Offset: 1

Reinhard Zumkeller, Jan 18 2009

nonn

a(n) = A116084(n) + 1 for all n because the decompositions are the same except for the additional fraction 1/1 allowed here but excluded in A116084. - M. F. Hasler, Jul 14 2016

			a(6) = #[1, 5/6+1/6, 4/5+1/5, 3/4+1/4, 2/3+1/3, 3/5+2/5, 1/2+1/3+1/6] = 7.

Cf. A116085, A119983, A154887.

Equals A116084(n) + 1.

Farey[n_] := Union@ Flatten@ Table[ a/b, {b, n}, {a, b}]; t[n_, k_] := t[n, k] = Block[{c = j = 0, ip = IntegerPartitions[1, {k}, Farey@ n]}, len = 1 + Length@ ip; While[j < len, If[Plus @@ Union@ ip[[j]] == 1, c++ ]; j++ ]; c]; f[n_] := Plus @@ Table[ t[n, k], {k, Ceiling[n/2]}]; Array[f, 24] (* Robert G. Wilson v, Aug 30 2010 *)

a(22)-a(26) from Robert G. Wilson v, Aug 30 2010
a(27)-a(34) from Don Reble, Jul 13 2016
a(35)-a(41) from Giovanni Resta, Jul 15 2016
a(42)-a(43) from Jinyuan Wang, Dec 12 2024

A115856 First differences of A115855.

Original entry on oeis.org

1, 2, 3, 6, 9, 14, 23, 48, 82, 55, 250, 100, 469, 2213, 2232, 296, 6623, 489, 29495, 89362, 35815, 1254, 259171, 411355, 176134, 952660, 3819125, 4564, 9371908, 6841, 13668113, 47144847, 6769988, 403602715, 672086464, 21636, 53588139, 1454972415, 6300092899, 44582

Offset: 1

Reinhard Zumkeller, Feb 01 2006

nonn

By definition of A115855, a(n+1) is the number of ways 1 can be written as sum of distinct positive fractions having no denominator larger than n, and at least one equal to n (in its reduced form). - M. F. Hasler, Jul 14 2016

Cf. A116085, A119983.

Table[Length@ Select[Flatten[Map[IntegerPartitions[1, {#}, Rest@ Union[Flatten@ TensorProduct[#, 1/#] &@ Range@ n /. {Integer -> 0, k /; k > 1 -> 0}]] &, Range@ n], 1], Total@ # == 1 && MemberQ[Union@ Denominator@ #, n] &], {n, 2, 25}] (* Michael De Vlieger, Jul 15 2016 *)

a(n) = A115855(n+1) - A115855(n).

a(A000040(n)-1) = A000041(A000040(n)) - 1.

a(20)-a(27) from Michael De Vlieger, Jul 15 2016

More terms from Jinyuan Wang, Dec 12 2024

A180360 Table t(n,k) is the number of ways to partition 1 into k fractions using the Farey fractions of order n, read row by row.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 1, 5, 4, 2, 1, 1, 6, 6, 5, 3, 1, 1, 9, 10, 8, 5, 2, 1, 1, 11, 14, 13, 10, 6, 3, 1, 1, 14, 20, 22, 21, 15, 9, 4, 1, 1, 16, 26, 36, 39, 33, 22, 11, 4, 1, 1, 21, 36, 47, 49, 40, 27, 14, 6, 2, 1, 1, 23, 44, 70, 87, 89, 76, 53, 31, 14, 5, 1, 1, 29, 58, 88, 105, 103, 87

Offset: 1

Robert G. Wilson v, Aug 30 2010

...
..1
..1...1
..1...2...1
..1...3...2...1
..1...5...4...2...1
..1...6...6...5...3...1
..1...9..10...8...5...2...1
..1..11..14..13..10...6...3...1
..1..14..20..22..21..15...9...4...1
..1..16..26..36..39..33..22..11...4...1
..1..21..36..47..49..40..27..14...6...2...1
..1..23..44..70..87..89..76..53..31..14...5...1
..1..29..58..88.105.103..87..60..36..17...7...2...1
...

			t(6,3) = 6 because 1 = 2/3+1/6+1/6 = 3/5+1/5+1/5 = 1/2+1/3+1/6 = 1/2+1/4+1/4 = 2/5+2/5+1/5 = 1/3+1/3+1/3.

Robert G. Wilson v, Table of n, a(n) for n = 1..389.

Row sum A119983, first column and main diagonal A000012, second column A046657.

Farey[n_] := Union@ Flatten@ Table[a/b, {b, n}, {a, b}]; t[n_, k_] := Length@ IntegerPartitions[1, {k}, Farey@ n]; Table[ t[n, k], {n, 13}, {k, n}] // Flatten

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

Original entry on oeis.org

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

Offset: 0

Robert C. Lyons, Mar 07 2016

nonn

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

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

Cf. A018805, A115855, A119983.

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

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

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)

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

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

More terms from Jinyuan Wang, Dec 12 2024

cp's OEIS Frontend

A154886 Number of ways to partition n into reduced fractions i/j with j <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A154888 Number of ways to partition 1 into distinct reduced fractions i/j with j <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A115856 First differences of A115855.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions

A180360 Table t(n,k) is the number of ways to partition 1 into k fractions using the Farey fractions of order n, read row by row.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Sage

Sage

Extensions