Ways to choose $k$ items out $n$ without overlap in the chosen sets This is part of a much larger and harder problem I am solving. I feel like it's a somewhat easy combinatorics problem, but that is not my field, and I can't find a solution online.
So I have a set of $n$ distinct items. Say, $\{0,1,2,3\}$ (so $n=4$), or the positions of characters on this string: "$1111$". We know $n$ to be a power of two, and $k$ to be even.
I want to know how many ways there are to choose $k$ items from the set, without any overlap.
With $\{0,1,2,3\}$ and $k=2$, if I choose $0,1,$ then I can only choose $2,3$. If I choose $0,2,$ then I can only choose $1,3.$ Etc. With those parameters, we can see there are $3$ ways to choose sets of two without overlap (aabb, abab, abba; or their complements (with a the chosen items and b the non-chosen)).
With $\{0,1,2,3,4,5,6,7\}$ and $k=2$, if I choose $0,1,$ then I can choose any two out of $\{2,3,...,7\}$.
I tried to puzzle this out. I thought I had $\binom42$ ways of choosing the first two items, and then I had the remaining $\binom{4-2}{2}$ choices, but I'm not sure how to combine those facts, since $\binom{4-2}{2}$ is 1, and multiplying, subtracting, or dividing it with $\binom42$ doesn't give the right answer.
And clearly $\binom{4-2}{2}/2 = 3$ seems to be right, but I don't know how to explain the "$/2$", and if it generalizes to other values of $k$ or $n$.
Thanks for any help you can provide.
 A: I'm going to interpret your problem as "how many ways can I choose $k$ things from $n$, and then choose $k$ more things from the remaining $n-k$ things?" In that case, let's think of the $n$ objects as being mapped to three different letters, $a,b,c$. Then $a$ will denote the objects in the first set, $b$ will denote the objects in the second set, and $c$ will denote objects not chosen. In the final answer, which set was chosen first/second will not matter, but we introduce this notion to make things easier to count.
This is the same as counting the number of "words" with $n$ letters that have $k$ $a$'s, $k$ $b$'s and $n-2k$ $c$'s, where the position of the letter gives the value of the entry corresponding to that letter. For example, $n=8$ and $k=2$:
$aacbccbc$ corresponds to $\{0,1\}$ for the first set, $\{4,7\}$ for the second, and the rest not chosen.
Standard combinatorics tells us that there are $${n}\choose{k, k, n-2k}$$ ways to do this. However, because you don't care which set was chosen first and which set was chosen second, the words $aacbccbc$ and $bbcaccac$ are indistinguishable to us. Since there's exactly $2$ ways for this to happen each time, you divide by $2$ again to get $$\frac{1}{2}\binom{n}{k, k, n-2k}$$ different ways. Hope this helps!
A: Indeed, to choose $k$ elements without repetition and without regard to order from a set of size $n$, there are $ \binom{k}{n} $ ways to do this. However this considers choosing, for example, $\{0,1\}$ from the set $\{0,1,2,3\}$, and thereby automatically ‘not choosing’ $\{2,3\}$, as not being equivalent to choosing $\{2,3\}$ and thereby automatically ‘not choosing’ $\{0,1\}$, counting as two different ways to choose 2 items from a list of 4, since a different selection was made.
This is then why the value from $ \binom{k}{n}$ disagrees with your test examples by a factor of 2: you considered choosing a set and not choosing the same set as being equivalent. If in your application this is not appropriate, then you are free to divide by 2 to account for this difference of perspectives.
