A065568 -id:A065568 - cp's OEIS frontend

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

Wouter Meeussen, Nov 30 2001

First differences of row sums equals A034738.

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

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

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.

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

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

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

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.

Original entry on oeis.org

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

Peter Luschny, Dec 07 2010

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

			[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

Cf. A034738, A065567, A065568, A327029.

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

# 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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula