Binomial formula for number of combinations - Maximum of N!/((N-x)!x!) found at x = N/2?

81 Views Asked by At

I am looking to show that the maximum of the binomial formula: $W = \frac{N!}{(N-x)!x!}$ is found at $x = \frac{N}{2}$

W being the number of ways to take a group of size x from a pool of N

I think the easiest way is to find the minimum of the denominator: $(N-x)!x!$

This makes sense to me intuitively as if you try to take x from N that you will have the most "options" if you split N directly in half, but I am stuck on how to show it.

Thanks

1

There are 1 best solutions below

1
On BEST ANSWER

You can look at what is happening to the denominator incrementally. Imagine you are increasing $0\leq x < N$ to $x+1$, then you would have $$ (N-(x+1))!(x+1)! = \frac{x+1}{N-x} (N-x)!x! $$ so you would diminish the denominator by doing so if and only if $(x+1)/(N-x) < 1$ ie. $x < (N-1)/2$. Similarly, you can check that by replacing $0 < x \leq N$ by $x-1$, then you would diminish the denominator if and only if $x > (N+1)/2$.

By combining these two idea you get that the value $x$ minimizing $(N-x)!x!$ should be between $(N-1)/2$ and $(N+1)/2$.

For $N$ even, we get your expected idea $x = N/2$, but note that when $N$ is odd, both $(N-1)/2$ and $(N+1)/2$ are correct.