A186974 Irregular triangle T(n,k), n>=1, 1<=k<=A036234(n), read by rows: T(n,k) is the number of k-element subsets of {1, 2, ..., n} having pairwise coprime elements.

1, 2, 1, 3, 3, 1, 4, 5, 2, 5, 9, 7, 2, 6, 11, 8, 2, 7, 17, 19, 10, 2, 8, 21, 25, 14, 3, 9, 27, 37, 24, 6, 10, 31, 42, 26, 6, 11, 41, 73, 68, 32, 6, 12, 45, 79, 72, 33, 6, 13, 57, 124, 151, 105, 39, 6, 14, 63, 138, 167, 114, 41, 6, 15, 71, 159, 192, 128, 44, 6

Offset: 1

Author

Alois P. Heinz, Mar 02 2011

Keywords

• nonn
• tabf

Comments

T(n,k) = 0 for k > A036234(n). The triangle contains all positive values of T.

Examples

			T(5,3) = 7 because there are 7 3-element subsets of {1,2,3,4,5} having pairwise coprime elements: {1,2,3}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,5}, {3,4,5}.
Irregular Triangle T(n,k) begins:
  1;
  2,  1;
  3,  3,  1;
  4,  5,  2;
  5,  9,  7,  2;
  6, 11,  8,  2;
  7, 17, 19, 10, 2;
		

Links

• Alois P. Heinz, Rows n = 1..220, flattened

Crossrefs

Columns k=1-10 give: A000027, A015614, A015617, A015623, A015698, A186982, A186983, A186984, A186985, A186986.

Row sums give A187106.

Rightmost terms of rows give A319187.

Cf. A036234, A186972.

Programs

Maple

with(numtheory):
s:= proc(m, r) option remember; mul(`if`(i pi(n) +1:
b:= proc(t, n, k) option remember; local c, d, h;
      if k=0 or k>n then 0
    elif k=1 then 1
    elif k=2 and t=n then `if`(n<2, 0, phi(n))
    else c:= 0;
         d:= 2-irem(t, 2);
         for h from 1 to n-1 by d do
           if igcd(t, h)=1 then c:= c +b(s(t*h, h), h, k-1) fi
         od; c
      fi
    end:
T:= proc(n, k) option remember;
       b(s(n, n), n, k) +`if`(n<2, 0, T(n-1, k))
    end:
seq(seq(T(n, k), k=1..a(n)), n=1..20);

Mathematica

s[m_, r_] := s[m, r] = Product[If[i < r, i, 1], {i, FactorInteger[m][[All, 1]]}]; a[n_] := PrimePi[n]+1; b[t_, n_, k_] := b[t, n, k] = Module[{c, d, h}, Which[k == 0 || k > n, 0, k == 1, 1, k == 2 && t == n, If[n < 2, 0, EulerPhi[n]], True, c = 0; d = 2-Mod[t, 2]; For[h = 1, h <= n-1, h = h+d, If[ GCD[t, h] == 1, c = c + b[s[t*h, h], h, k-1]]]; c]]; t[n_, k_] := t[n, k] = b[s[n, n], n, k] + If[n < 2, 0, t[n-1, k]]; Table[Table[t[n, k], { k, 1, a[n]}], {n, 1, 20}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

Formula

T(n,k) = Sum_{i=1..n} A186972(i,k).