number of combinations by choosing $\frac{n}{2}$ elements out of n elements

Question

Edit: The mistake was in me counting (enumerating by hand) which @JMoravitz kindly taught me to do right in the chat. Apologies!

I'm trying to code a problem I have, and I would like to use a combination approach. But I seem to make the wrong assumptions, or I cannot calculate right (which is reasonably plausible).

If I have, n elements and I pick $\frac n2$ elements, I thought the number of combinations I get should be n choose $\frac n2$ ?

For example 4 elements gives 6 combinations. And 6 elements give 20 combinations.

So if I have elements a b c d I can have:

a b x x or

a x c x or

a x x d or

x b c x or

x b x d

total of 6.

If I do this for 6 elements a b c d e f

a b c x x x

a b x d x x

....

x b c d x x

x b c x e x

.....

x x x d e f

And count them I am getting a total of 16 combinations? Am I missing some with this method? If not (though possible, I went over it numerous times already), how do I calculate the right number of combinations?

Thank you for your help.

Answer 1

Summarizing the chat and comments above, there are in general $\binom{n}{k}=\dfrac{n!}{k!(n-k)!}$ ways to choose $k$ elements out of $n$. For the special case of $k=n/2$ these are the Central Binomial Coefficients.

Following the pattern begun in the list above and taking it all the way, we arrive at a pseudocode for generating the list as simply looping over three indices (or $n/2$ indices in general), at each nested loop starting the index at one higher than the current index of the loop it is in.

Some dirty javascript code accomplishing this for the case of $n=6$: for (i=0; i<6; i++){ for (j=i+1; j<6; j++){ for (k=j+1; k<6; k++){ resultstr = ""; for(l=0; l<6; l++){resultstr+=l==i||l==j||l==k?l:"x"}console.log(resultstr)}}}

This particular order in which we listed the combinations is of particular interest and is what we call the lexicographic order of the combinations. Had we listed them without the X's, your list is abc, abd, abe, abf, acd, ace, acf, ..., def. The lexicographic order of these is then simply the "dictionary order", just as you would have expected to see these arranged in the dictionary.

As for what went wrong with your earlier code, perhaps some gremlins played a trick on you, but when going to verify the code it was correct and got the expected result.