%I #13 Jan 05 2025 19:51:35
%S 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,
%T 28,56,70,56,27,6,1,9,36,84,126,125,80,30,4,1,10,45,120,210,252,210,
%U 120,45,10,1,11,55,165,330,462,461,325,154,42,4,1,12,66,220,495,792,924,792
%N Triangle read by rows: number of compositions of n into relatively prime summands.
%C From C. Ronaldo: (Start)
%C 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:
%C Formula: R_k(n) = Sum_{d|n} C(d-1,k-1)*mobius(n/d).
%C 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).
%C G.f.: Sum_{j>=1} R_k(j)(x^j/(1-x^j)) = (x/(1-x))^k. (End)
%H H. W. Gould, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/2-4/gould.pdf">Binomial coefficients, the bracket function and compositions with relatively prime summands</a>, Fib. Quart. 2(4) (1964), 241-260.
%e Triangle begins:
%e 1;
%e 1, 2;
%e 1, 3, 2;
%e 1, 4, 6, 4;
%e 1, 5, 10, 9, 2;
%e 1, 6, 15, 20, 15, 6;
%e ...
%p 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
%Y _Emeric Deutsch_ points out that the mirror-image, A101391, is a better version of this triangle.
%K tabl,nonn,easy
%O 2,3
%A _N. J. A. Sloane_
%E More terms from C. Ronaldo (aga_new_ac(AT)hotmail.com), Dec 28 2004