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
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
KEYWORD
AUTHOR
EXTENSIONS
More terms from C. Ronaldo (aga_new_ac(AT)hotmail.com), Dec 28 2004
STATUS
approved