0
$\begingroup$

I'm studying the combinatorics "twelvefold way", and found an identity that cannot explain myself.
The case, $ {x-1 \choose b-1} $ as far as I understand is derived the following way: $ {(x-b)+b-1 \choose x-b}={x-1 \choose x-b}={x-1 \choose b-1} $ The first identity is evident, but I don't understand the second one: $ {x-1 \choose x-b}={x-1 \choose b-1} $ Why x-b is equal to b-1?

Thanks

4 Answers 4

3

For any $n$ and $k$, $\binom{n}k=\binom{n}{n-k}\;;$ let $n=x-1$ and $k=b-1$, and you immediately get $\binom{x-1}{b-1}=\binom{x-1}{x-b}\;,$ since $(x-1)-(b-1)=x-b$. This does not mean that $b-1=x-b$; in general this is false.

There are at least two ways to see the identity $\binom{n}k=\binom{n}{n-k}\;.$ If you know that $\binom{n}k=\frac{n!}{k!(n-k)!}\;,$ it’s clear:

$\binom{n}{n-k}=\frac{n!}{(n-k)!\big(n-(n-k)\big)!}=\frac{n!}{(n-k)!k!}=\binom{n}k\;.$

Alternatively, if you know that $\binom{n}k$ is the number of $k$-element subsets of $\{1,\dots,n\}$, just observe that complementation is a bijection between $k$-element subsets and $(n-k)$-element subsets, so $\binom{n}k$ and $\binom{n}{n-k}$ must be equal.

2

It is not that $x-b$ is equal to $b-1$ but rather the following. Fix $n=x-1$ and $r=b-1$ for notation purpose.

The number of ways to choose $r$ objects from a set of $n$ is given by the binomial coefficient $ n\choose r $ However, choosing $r$ is the same as chossing which $n-r$ will be left out, so $ {n\choose r}={n\choose{n-r}}. $ Substitute your values back to get $ {{x-1}\choose{b-1}}={{x-1}\choose{x-1-(b-1)}}={{x-1}\choose{x-b}}. $

Of course, you can also prove this identity with the definition, but the combinatorial way of seeing it is, I believe, more convincing.

Edit

One has to be careful in the case $n=b=0$ The rightmost part will give the correct answer of $1$ (correct given the context of surjective maps, while the left most term will give ${-1\choose-1}$, which is not well defined.

  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6254/discussion-between-jean-sebastien-and-diego) – 2012-10-26
0

In general, ${n\choose k}={n\choose n-k}$.

  • 0
    I just saw your second message. Yes I have look at it, and I understand it and appreciate it. My comment is just directed to highlight the numerical difference between the 2 sides of the identity, that was the reason I got confused in the first place. But yeah, I got your explanation and I'm very happy with it. :) – 2012-10-26
0

I finally understood this through the "stars and bars" approach and the case $ {+βˆ’1 \choose } $ which is simpler.

Let x=10 (dots) and b=5 (subsets) (b-1= 4 bars)
$..|...|..|..|.$ So if I focus on the subsets the answer will be $ {14 \choose 4} $ But if I focus on the dots the answer will be $ {14 \choose 10} $
I had to toss a coin for choosing the accepted answer :)
Thank you very much Brian and Jean

Since somebody can find this post useful, I post the results obtained by using Pascal's triangle for the same problem, which I believe can complement the nice explanation provided by Brian and Jean. In red the results of 14 choose 4 and 14 choose 10 using Pascal's triangle