Combinatorics on n-sets: Arithmetic Properties and Numerical Results

The following claim was one of the favorite “initiation question” to mathematics of Paul Erd˝os: for every non-zero natural number n, each subset of I(2n)={1,2,...,2n}, having size n + 1, contains at least two distinct elements of which the smallest divides the largest. This can be proved using the pigeonhole principle. On the other side, it is easy to see that there are subsets of I(2n)of sizen without divisor-multiple pairs;we call themn-sets, and we study some of their combinatorial properties giving also some numerical results. In particular, we give a precise description of the elements that, for a fixed n,donotbelongto every n-set, as well as the elements that do belong to all the n-sets. Furthermore, we give an algorithm to count the n-sets for a given n and, in this way, we can see the behavior of the sequence a(n)of thenumber of n-sets. We will present some different versions of the algorithm, along with their performances, and we finally show our numerical results, that is, the first 200 values of the sequence a(n) and of the sequence q(n):=a(n +1)/a(n).