login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 20
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

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

FORMULA

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

EXAMPLE

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;

MAPLE

with(numtheory):

s:= proc(m, r) option remember; mul(`if`(i<r, i, 1), i=factorset(m)) end:

a:= n-> 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 *)

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.

Sequence in context: A183110 A117895 A188002 * A286312 A278492 A128139

Adjacent sequences:  A186971 A186972 A186973 * A186975 A186976 A186977

KEYWORD

nonn,tabf

AUTHOR

Alois P. Heinz, Mar 02 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 18:56 EDT 2021. Contains 347694 sequences. (Running on oeis4.)