cp's OEIS Frontend

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

%I A039911 #19 May 06 2025 16:45:52
%S A039911 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,
%T A039911 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,
%U A039911 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
%N A039911 Triangle read by rows: number of compositions of n into relatively prime summands.
%C A039911 From C. Ronaldo: (Start)
%C A039911 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 A039911 Formula: R_k(n) = Sum_{d|n} C(d-1,k-1)*mobius(n/d).
%C A039911 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 A039911 G.f.: Sum_{j>=1} R_k(j)(x^j/(1-x^j)) = (x/(1-x))^k. (End)
%H A039911 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 A039911 Triangle begins:
%e A039911   1;
%e A039911   1,  0;
%e A039911   1,  2,  0;
%e A039911   1,  3,  2,  0;
%e A039911   1,  4,  6,  4,  0;
%e A039911   1,  5, 10,  9,  2,  0;
%e A039911   1,  6, 15, 20, 15,  6,  0;
%e A039911   ...
%p A039911 with(numtheory):
%p A039911 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:
%p A039911 seq(seq(R(n,n-k+1),k=1..n),n=1..15);
%p A039911 # second Maple program:
%p A039911 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:
%p A039911 seq(seq(R(n,n-k+1),k=1..n),n=1..15); # C. Ronaldo
%Y A039911 _Emeric Deutsch_ points out that the mirror-image, A101391, is a better version of this triangle.
%Y A039911 Row sums give A000740.
%K A039911 nonn,tabl,easy
%O A039911 1,5
%A A039911 _N. J. A. Sloane_
%E A039911 More terms from C. Ronaldo (aga_new_ac(AT)hotmail.com), Dec 28 2004
%E A039911 Edited by _Alois P. Heinz_, May 06 2025