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

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?

• In general, the number of ways of selecting $k$ objects out of $n$ objects total will be $\binom{n}{k}=\dfrac{n!}{k!(n-k)!}$. In your case, you just use $k=\frac{n}{2}$, giving the central binomial coefficients. In general it is a terrible idea to list them all out and brute force the count. In the case of $n=6$ that is $\binom{6}{3}=\frac{6!}{3!3!}=20$. Had you brute forced and listed them all out you should have also gotten $20$, so you must have missed some if you only counted $16$, the problem with trying to manually count Nov 15 '19 at 16:46
• hello @JMoravitz thank you! would you know if the method I use to get the combinations with shifting the index doesn't get you all the combinations? Nov 15 '19 at 16:51
• As for coding this... that gets a bit off topic, but you can use three nested for loops, each index corresponding to which position in your string should be the usual letter versus an x. Pseudo code being: basestr = "xxxxxx"; for i in [1..6] { for j in [(i+1)..6] { for k in [(j+1)..6] { result = basestr; result[i]=i; result[j]=j; result[k]=k; print(result) } } }. Adjust the code for your prefered language. All combinations will be generated, none missed. Note that $\sum\limits_{i=1}^6\sum\limits_{j=i+1}^6\sum\limits_{k=j+1}^6 1 = \binom{6}{3}=20$. Nov 15 '19 at 16:54
• thanks @JMoravitz this is exactly how I coded this, three nested loops. but because I calculated 20 combinations I'm thinking something is wrong. I wrote it out by hand and got 16 and by code as well. I've been looking at these 16 for 45 minutes haha. I cannot find the missing 4. So I figured my math is wrong. Nov 15 '19 at 16:57
• If you share the list and/or the code, we might be able to point out what went wrong, but in terms of the mathematics of your question, again, there will be $\binom{6}{3}=20$ combinations. As a guess, perhaps you hardcoded a limit on the highest that $i$ could go too low. There are exactly four outcomes where $i$ occurs in the third position or later. That would have had you miss xxcdex, xxcdxf, xxcxef, xxxdef Nov 15 '19 at 17:00

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)}}}