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

Author

N. J. A. Sloane

Keywords

• nonn
• tabl
• easy

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)

Examples

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

Links

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

Crossrefs

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

Row sums give A000740.

Programs

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);
# second Maple program:
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

Extensions

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

Edited by Alois P. Heinz, May 06 2025