A000741 - OEIS

A000741

Number of compositions of n into 3 ordered relatively prime parts.
(Formerly M2531 N0999)

0, 0, 1, 3, 6, 9, 15, 18, 27, 30, 45, 42, 66, 63, 84, 84, 120, 99, 153, 132, 174, 165, 231, 180, 270, 234, 297, 270, 378, 276, 435, 360, 450, 408, 540, 414, 630, 513, 636, 552, 780, 558, 861, 690, 828, 759, 1035, 744, 1113, 870, 1104, 972, 1326, 945, 1380, 1116, 1386, 1218

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

REFERENCES

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..10000

H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.

C. Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.

N. J. A. Sloane, Transforms

FORMULA

Moebius transform of A000217(n-2).

G.f.: 1 + Sum_{n>=1} a(n)*x^n/(1 - x^n) = (1 - 3*x + 3*x^2)/(1 - x)^3. - Ilya Gutkovskiy, Apr 26 2017

EXAMPLE

From Gus Wiseman, Oct 14 2020: (Start)

The a(3) = 1 through a(8) = 18 triples:

(1,1,1) (1,1,2) (1,1,3) (1,1,4) (1,1,5) (1,1,6)

(1,2,1) (1,2,2) (1,2,3) (1,2,4) (1,2,5)

(2,1,1) (1,3,1) (1,3,2) (1,3,3) (1,3,4)

(2,1,2) (1,4,1) (1,4,2) (1,4,3)

(2,2,1) (2,1,3) (1,5,1) (1,5,2)

(3,1,1) (2,3,1) (2,1,4) (1,6,1)

(3,1,2) (2,2,3) (2,1,5)

(3,2,1) (2,3,2) (2,3,3)

(4,1,1) (2,4,1) (2,5,1)

(3,1,3) (3,1,4)

(3,2,2) (3,2,3)

(3,3,1) (3,3,2)

(4,1,2) (3,4,1)

(4,2,1) (4,1,3)

(5,1,1) (4,3,1)

(5,1,2)

(5,2,1)

(6,1,1)

(End)

MAPLE

with(numtheory):

mobtr:= proc(p)

proc(n) option remember;

add(mobius(n/d)*p(d), d=divisors(n))

end

end:

A000217:= n-> n*(n+1)/2:

a:= mobtr(n-> A000217(n-2)):

seq(a(n), n=1..58); # Alois P. Heinz, Feb 08 2011

MATHEMATICA

mobtr[p_] := Module[{f}, f[n_] := f[n] = Sum[MoebiusMu[n/d]*p[d], {d, Divisors[n]}]; f]; A000217[n_] := n*(n+1)/2; a = mobtr[A000217[#-2]&]; Table[a[n], {n, 1, 58}] (* Jean-François Alcover, Mar 12 2014, after Alois P. Heinz *)

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n, {3}], GCD@@#==1&]], {n, 0, 30}] (* Gus Wiseman, Oct 14 2020 *)

CROSSREFS

A000010 is the length-2 version.

A000217(n-2) does not require relative primality.

A000740 counts these compositions of any length.

A000742 is the length-4 version.

A000837 counts relatively prime partitions.

A023023 is the unordered version.

A101271 is the strict case.

A101391 has this as column k = 3.

A284825*6 is the pairwise non-coprime case.

A291166 intersected with A014311 ranks these compositions.