A039911 - OEIS

%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