Combinatorics on divisors Consider the set $D$ of all divisors of $10000$. What is the number of subsets $H \subseteq D$ containing at least two elements such that for every $a, b \in H$, $a \mid b$ or $b \mid a$?
I tried translating the problem into one about integer grid, which makes it ask for the number of ways to choose at least two points in the square with vertices $(0, 0)$ and $(4,4)$ ordered in such a way that they can be reached sequentially by only moving up and right. But I fail to see a way to calculate it besides setting up this recurrence: let $a_{m,n}$ be the number of subsets of the square between $(0,0)$ and $(m,n)$ that satisfy the above property. We can form such a subset in a number of ways: it could be a subset already counted in $a_{m-1,n}$, or in $a_{m,n-1}$, or one of those same subsets with the addition of $(m,n)$, or be composed of $(m,n)$ and a point in the rectangle with vertices $(0,0$) and $(m, n)$ (there are $(m+1)(n+1)-1$ such points). If we simply added $a_{m-1,n}$ and $a_{m,n-1}$ we would be counting twice the subsets already counted in $a_{m-1, n-1}$.
The recurrence is thus: $\begin{cases} a_{0, 0} = 0 \\ a_{n,0} = a_{0,n} = 2a_{n-1, 0} + n \\ a_{m,n} = 2(a_{m-1,n} + a_{m,n-1} - a_{m-1,n-1}) + (m+1)(n+1)-1\end{cases}$.
And the answer we are looking for is $a_{4,4}$. Is there a more elegant way to answer this however?
 A: I'm not sure if you'll think this is elegant but here goes:-
For convenience, temporarily drop the restriction that $H$ must contain $2$ elements. We can form a variant on Pascal's triangle as follows.
Write $1$ in the top right square i.e. $(4,4)$. This represents the number of sets $H$ with $(4,4)$ as the 'least' point.
Now consider the squares in the next diagonal down i.e. $(3,4)$ and $(4,3)$. For each of these squares we calculate $1$ more than the sum of the numbers above and to the right of it i.e. a total of $2$. For $(3,4)$, the first $1$ represents the number of sets $H$ which only contain  $(3,4)$. The sum of the other numbers adds up all those sets $H$ containing  $(3,4)$ and at least one other point.
Subsequent diagonals contain the numbers
$$4,6,4$$
$$8,16,16,8$$
$$16,40,52,40,16$$
$$96,152,152,96$$
$$416,504,416$$
$$1536,1536$$
$$5136$$
So, I obtain the number $5136$ in square $(0,0)$ i.e. as the number of sets $H$ with $(0,0)$ as the 'least' point.
That means that the sum of all the numbers in the $5\times 5$ block is $ 5136+5135=10271$. We must now exclude the $5^2$ cases where we have only $1$ element in $H$ giving a total of $10246$.
A: I think that $a(5)$ in this OEIS sequence might contain the number you’re looking for, if you subtract from it the $26$ subsets containing fewer than two divisors that satisfy your condition. At least it has the right number, seems related, and seems to be correct for divisors of $2^1 5^1 = 10$ as well. (The number $a(2)$ counts the $12$ subsets of $\{1, 2, 5, 10\}$ not containing both $2$ and $5$.)
The entry for this OEIS sequence, whose terms are one-half the values of the one above, gives a generating function and other information you might find useful.
