A065567 T(n,m) is the sum over all m-subsets of {1,...,n} of the gcd of the subset.

1, 3, 1, 6, 3, 1, 10, 7, 4, 1, 15, 11, 10, 5, 1, 21, 20, 21, 15, 6, 1, 28, 26, 36, 35, 21, 7, 1, 36, 38, 60, 71, 56, 28, 8, 1, 45, 50, 90, 127, 126, 84, 36, 9, 1, 55, 67, 132, 215, 253, 210, 120, 45, 10, 1, 66, 77, 177, 335, 463, 462, 330, 165, 55, 11, 1, 78, 105, 250, 512, 798, 925, 792, 495, 220, 66, 12, 1

Offset: 1

Author

Wouter Meeussen, Nov 30 2001

Keywords

• nonn
• tabl

Comments

First differences of row sums equals A034738.

Examples

			Triangle begins:
   1;
   3,  1;
   6,  3,  1;
  10,  7,  4, 1;
  15, 11, 10, 5, 1;
  ...
T(4,2) = 7 = gcd(1,2) + gcd(1,3) + gcd(1,4) + gcd(2,3) + gcd(2,4) + gcd(3,4).
		

Links

• Alois P. Heinz, Rows n = 1..200 (first 31 rows from Sean A. Irvine)

Crossrefs

Row sums give A065568.

T(2n,n) gives A244174 for n>=1.

T(2n,n+1) gives A001791 for n>=1.

T(2n+1,n+1) gives A001700 for n>=0.

Cf. A002088, A034738.

Programs

Maple

with(combstruct):
a065567_row := proc(n) local k,L,l,R,comb;
R := NULL;
for k from 1 to n do
   L := 0;
   comb := iterstructs(Combination(n),size=k):
   while not finished(comb) do
      l := nextstruct(comb);
      L := L + igcd(op(l));
   od;
   R := R,L;
od;
R end: # Peter Luschny, Dec 07 2010
# second Maple program:
b:= proc(n, g, t) option remember; `if`(n=0, g*x^t,
      b(n-1, igcd(g, n), t+1)+b(n-1, g, t))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0$2)):
seq(T(n), n=1..12);  # Alois P. Heinz, Sep 05 2023

Mathematica

Table[Plus@@(GCD@@@KSubsets[Range[n], m]), {n, 16}, {m, n}]

Formula

Sum_{k=1..n} (-1)^(k+1) * T(n,k) = A002088(n). - Alois P. Heinz, Sep 05 2023