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

1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 4, 5, 2, 1, 2, 1, 1, 6, 11, 8, 2, 1, 4, 6, 4, 1, 1, 6, 12, 10, 3, 1, 4, 5, 2, 1, 10, 31, 42, 26, 6, 1, 4, 6, 4, 1, 1, 12, 45, 79, 72, 33, 6, 1, 6, 14, 16, 9, 2, 1, 8, 21, 25, 14, 3, 1, 8, 24, 36, 29, 12, 2, 1, 16, 79, 183, 228, 157, 56, 8, 1, 6, 15, 20, 15, 6, 1

Offset

1,5

Comments

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

Links

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

Example

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

Maple

with(numtheory):
s:= proc(m, r) option remember; mul(`if`(i<r, i, 1), i=factorset(m)) end:
a:= proc(n) option remember; `if`(n<4, n, pi(n)-nops(factorset(n))+2) end:
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) 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_] := a[n] = If[n < 4, n, PrimePi[n] - Length[FactorInteger[n]]+2]; 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]; Table[Table[t[n, k], {k, 1, a[n]}], {n, 1, 20}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

Crossrefs

Columns k=1-10 give: A000012, A000010 (for n>1), A185953, A185348, A186976, A186977, A186978, A186979, A186980, A186981.

Rightmost elements of rows give A186994.

Row sums are A186973.

Cf. A186971.

Sequence in context: A133009 A210705 A291771 * A373694 A374832 A053734

Adjacent sequences: A186969 A186970 A186971 * A186973 A186974 A186975

Keyword

nonn,tabf,look

Author

Alois P. Heinz, Mar 01 2011

Status

approved