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

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

Offset

2,3

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=2..75.

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,  2;
  1,  3,  2;
  1,  4,  6,  4;
  1,  5, 10,  9,  2;
  1,  6, 15, 20, 15,  6;
  ...

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-1), n=1..15); 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-1), n=1..15); # C. Ronaldo

Crossrefs

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

Sequence in context: A136451 A361894 A066121 * A208945 A209073 A332077

Adjacent sequences: A039908 A039909 A039910 * A039912 A039913 A039914

Keyword

tabl,nonn,easy

Author

N. J. A. Sloane

Extensions

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

Status

approved