login
Triangle read by rows: T(n,k)= Sum_{c in C(n,k)}gcd(c) where C(n,k) is the set of all k-tuples of positive integers whose elements sum to n.
2

%I #20 Mar 24 2020 12:34:35

%S 1,2,1,3,2,1,4,4,3,1,5,4,6,4,1,6,9,11,10,5,1,7,6,15,20,15,6,1,8,12,24,

%T 36,35,21,7,1,9,12,30,56,70,56,28,8,1,10,17,42,88,127,126,84,36,9,1

%N Triangle read by rows: T(n,k)= Sum_{c in C(n,k)}gcd(c) where C(n,k) is the set of all k-tuples of positive integers whose elements sum to n.

%C C(n,k) counted by A007318(n-1,k-1) are also called compositions of n of size k (see A181842).

%e [1] 1

%e [2] 2 1

%e [3] 3 2 1

%e [4] 4 4 3 1

%e [5] 5 4 6 4 1

%e [6] 6 9 11 10 5 1

%e [7] 7 6 15 20 15 6 1

%p with(combstruct): # By generating the objects, very inefficient.

%p a181847_row := proc(n) local k,L,l,R,comp; R := NULL;

%p for k from 1 to n do

%p L := 0;

%p comp := iterstructs(Composition(n),size=k):

%p while not finished(comp) do

%p l := nextstruct(comp);

%p L := L + igcd(op(l));

%p od;

%p R := R,L;

%p od;

%p R end:

%p # second Maple program:

%p with(numtheory):

%p T := (n, k) -> add(phi(d)*binomial(n/d-1, k-1), d = divisors(n)):

%p seq(seq(T(n, k), k=1..n), n=1..10); # _Peter Luschny_, Aug 27 2019

%o (Sage) # uses[DivisorTriangle from A327029]

%o # DivisorTriangle Computes the (0,0)-based version.

%o DivisorTriangle(euler_phi, lambda n,k: binomial(n-1, k-1), 10) # _Peter Luschny_, Aug 27 2019

%Y Cf. A034738, A065567, A065568, A327029.

%K nonn,tabl

%O 1,2

%A _Peter Luschny_, Dec 07 2010