A039911 Triangle read by rows: number of compositions of n into relatively prime summands.

1, 1, 0, 1, 2, 0, 1, 3, 2, 0, 1, 4, 6, 4, 0, 1, 5, 10, 9, 2, 0, 1, 6, 15, 20, 15, 6, 0, 1, 7, 21, 35, 34, 18, 4, 0, 1, 8, 28, 56, 70, 56, 27, 6, 0, 1, 9, 36, 84, 126, 125, 80, 30, 4, 0, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 0, 1, 11, 55, 165, 330, 462, 461, 325, 154, 42, 4, 0, 1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 0

Offset

1,5

Comments

From C. Ronaldo: (Start)

Let R_k(n) be the number of compositions (ordered partitions) of n with k relatively prime parts. We have the following expressions for R:

Formula: R_k(n) = Sum_{d|n} C(d-1,k-1)*mobius(n/d).

Recurrence: C(n,k) = Sum_{j=k..n} floor(n/j)*R_k(j) for k > 1 and R_1(j) = delta_j1 (the Kronecker delta).

G.f.: Sum_{j>=1} R_k(j)(x^j/(1-x^j)) = (x/(1-x))^k. (End)

Links

Table of n, a(n) for n=1..91.

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

Example

Triangle begins:
  1;
  1,  0;
  1,  2,  0;
  1,  3,  2,  0;
  1,  4,  6,  4,  0;
  1,  5, 10,  9,  2,  0;
  1,  6, 15, 20, 15,  6,  0;
  ...

Maple

with(numtheory):
R:=proc(n, k) local s, d: s:=0: for d from 1 to n do if irem(n, d)=0 then s:=s+binomial(d-1, k-1)*mobius(n/d) fi od: RETURN(s) : end:
seq(seq(R(n, n-k+1), k=1..n), n=1..15);
# Alternative:
R:=proc(n, k) options remember: local j: if k=1 then RETURN(piecewise(n=1, 1)) else RETURN(binomial(n, k)-add(floor(n/j)*R(j, k), j=k..n-1)) fi: end:
seq(seq(R(n, n-k+1), k=1..n), n=1..15); # C. Ronaldo

Crossrefs

Emeric Deutsch points out that the mirror-image, A101391, is a better version of this triangle.

Row sums give A000740.

Sequence in context: A216235 A306914 A317023 * A319284 A338526 A182703

Adjacent sequences: A039908 A039909 A039910 * A039912 A039913 A039914

Keyword

nonn,tabl,easy

Author

N. J. A. Sloane

Extensions

More terms from C. Ronaldo (aga_new_ac(AT)hotmail.com), Dec 28 2004

Edited by Alois P. Heinz, May 06 2025

Status

approved