A181847 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.

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, 36, 35, 21, 7, 1, 9, 12, 30, 56, 70, 56, 28, 8, 1, 10, 17, 42, 88, 127, 126, 84, 36, 9, 1

Offset: 1

Author

Peter Luschny, Dec 07 2010

Keywords

• nonn
• tabl

Comments

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

Examples

			[1]   1
[2]   2   1
[3]   3   2    1
[4]   4   4    3    1
[5]   5   4    6    4    1
[6]   6   9   11   10    5   1
[7]   7   6   15   20   15   6   1
		

Crossrefs

Cf. A034738, A065567, A065568, A327029.

Programs

Maple

with(combstruct): # By generating the objects, very inefficient.
a181847_row := proc(n) local k,L,l,R,comp; R := NULL;
for k from 1 to n do
   L := 0;
   comp := iterstructs(Composition(n),size=k):
   while not finished(comp) do
      l := nextstruct(comp);
      L := L + igcd(op(l));
   od;
   R := R,L;
od;
R end:
# second Maple program:
with(numtheory):
T := (n, k) -> add(phi(d)*binomial(n/d-1, k-1), d = divisors(n)):
seq(seq(T(n, k), k=1..n), n=1..10); # Peter Luschny, Aug 27 2019

Sage

# uses[DivisorTriangle from A327029]
# DivisorTriangle Computes the (0,0)-based version.
DivisorTriangle(euler_phi, lambda n,k: binomial(n-1, k-1), 10) # Peter Luschny, Aug 27 2019