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

%I #33 Sep 05 2023 20:46:27

%S 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,

%T 36,38,60,71,56,28,8,1,45,50,90,127,126,84,36,9,1,55,67,132,215,253,

%U 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

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

%C First differences of row sums equals A034738.

%H Alois P. Heinz, <a href="/A065567/b065567.txt">Rows n = 1..200</a> (first 31 rows from Sean A. Irvine)

%F Sum_{k=1..n} (-1)^(k+1) * T(n,k) = A002088(n). - _Alois P. Heinz_, Sep 05 2023

%e Triangle begins:

%e 1;

%e 3, 1;

%e 6, 3, 1;

%e 10, 7, 4, 1;

%e 15, 11, 10, 5, 1;

%e ...

%e T(4,2) = 7 = gcd(1,2) + gcd(1,3) + gcd(1,4) + gcd(2,3) + gcd(2,4) + gcd(3,4).

%p with(combstruct):

%p a065567_row := proc(n) local k,L,l,R,comb;

%p R := NULL;

%p for k from 1 to n do

%p L := 0;

%p comb := iterstructs(Combination(n),size=k):

%p while not finished(comb) do

%p l := nextstruct(comb);

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

%p od;

%p R := R,L;

%p od;

%p R end: # _Peter Luschny_, Dec 07 2010

%p # second Maple program:

%p b:= proc(n, g, t) option remember; `if`(n=0, g*x^t,

%p b(n-1, igcd(g, n), t+1)+b(n-1, g, t))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0$2)):

%p seq(T(n), n=1..12); # _Alois P. Heinz_, Sep 05 2023

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

%Y Row sums give A065568.

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

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

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

%Y Cf. A002088, A034738.

%K nonn,tabl

%O 1,2

%A _Wouter Meeussen_, Nov 30 2001