A320435 Regular triangle read by rows where T(n,k) is the number of relatively prime k-subsets of {1,...,n}, 1 <= k <= n.

1, 1, 1, 1, 3, 1, 1, 5, 4, 1, 1, 9, 10, 5, 1, 1, 11, 19, 15, 6, 1, 1, 17, 34, 35, 21, 7, 1, 1, 21, 52, 69, 56, 28, 8, 1, 1, 27, 79, 125, 126, 84, 36, 9, 1, 1, 31, 109, 205, 251, 210, 120, 45, 10, 1, 1, 41, 154, 325, 461, 462, 330, 165, 55, 11, 1, 1, 45, 196

Offset

1,5

Comments

Two or more numbers are relatively prime if they have no common divisor > 1. A single number is not considered to be relatively prime unless it is equal to 1.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Formula

T(n,k) = Sum_{d=1..floor(n/k)} mu(d)*binomial(floor(n/d), k). - Andrew Howroyd, Jan 19 2023

Example

Triangle begins:
    1
    1    1
    1    3    1
    1    5    4    1
    1    9   10    5    1
    1   11   19   15    6    1
    1   17   34   35   21    7    1
    1   21   52   69   56   28    8    1
    1   27   79  125  126   84   36    9    1
    1   31  109  205  251  210  120   45   10    1
    1   41  154  325  461  462  330  165   55   11    1
    1   45  196  479  786  923  792  495  220   66   12    1
    1   57  262  699 1281 1715 1716 1287  715  286   78   13    1
The T(6,2) = 11 sets are: {1,2}, {1,3}, {1,4}, {1,5}, {1,6}, {2,3}, {2,5}, {3,4}, {3,5}, {4,5}, {5,6}. Missing from this list are: {2,4}, {2,6}, {3,6}, {4,6}.

Mathematica

Table[Length[Select[Subsets[Range[n], {k}], GCD@@#==1&]], {n, 10}, {k, n}]

Prog

(PARI) T(n, k) = sum(d=1, n\k, moebius(d)*binomial(n\d, k)) \\ Andrew Howroyd, Jan 19 2023

Crossrefs

Row sums are A085945.

Second column is A015614.

Cf. A000837, A186974, A187106, A289508, A289509, A300486, A303139, A320424, A320436.

Sequence in context: A131767 A026780 A209421 * A275421 A243576 A211314

Adjacent sequences: A320432 A320433 A320434 * A320436 A320437 A320438

Keyword

nonn,tabl

Author

Gus Wiseman, Jan 08 2019

Status

approved