1
$\begingroup$

I was dealing with this problem:

Consider the set $S=\{1,2,3,\dots,100\}$. We construct two subsets $A$ and $B$ with $10$ elements each, such that the elements of $A$ are all smaller than the ones of $B$. How many ways are there to construct two such sets?

The answer is straightforward: $\binom{100}{20}$ But then, this following question came to my mind and I struggled to find an approach.

Consider the set $S=\{1,2,3,\dots,100\}$. We construct two subsets $A$ and $B$ with $10$ elements each, such that; when their elements are arranged in ascending order, each $i$th element of $A$ is smaller than the $i$th element of $B$. How many ways are there to construct two such sets?

I'm not interested in a computational solution; other than that, is there a nice way to solve this?

$\endgroup$
  • $\begingroup$ Do $A$ and $B$ have to be disjoint or can they overlap? $\endgroup$ – bof Jan 26 at 6:32
1
$\begingroup$

The below assumes that $A$ and $B$ must be disjoint. It is not clear if that was required or not in the problem statement.

First choose $A \cup B$, which is $100 \choose 20$. Then you need to find the number of ways to partition $[1,20]$ into two $10$ element subsets subject to the corresponding element condition. These are the Catalan numbers. Look at the monotonic paths staying below the diagonal. Think of $n=10$ (the number of elements in $A$). If there is a right arrow, the next number goes in $A$, if there is an up arrow, the next number goes in $B$ As long as we don't get above the diagonal, we meet the corresponding element condition. So there are ${100 \choose 20}C_{10}={100 \choose 20}\frac 1{11}{20 \choose 10}$ ways

$\endgroup$
  • $\begingroup$ @bof: you are correct I assumed A and B are disjoint in my answer. I don't immediately see a way to fix it. I thought about adding $1$ to all the elements in B, but that doesn't seem to work out. I added a note. $\endgroup$ – Ross Millikan Jan 26 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.