# Partition a set into 2 subsets

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?

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

## 1 Answer

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

• @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. – Ross Millikan Jan 26 at 15:24