# Is there an elegant bijective proof of $\binom{15}{5}=\binom{14}{6}$?

I mean, there have to be two combinatorial structures with some transparent set-theoretic bijection between them, with one of them obviously having $\binom{15}{5}$ elements and the other $\binom{14}{6}$. Right? It can't be a mere coincidence.

• I think you would be surprised with how many 'coincidences' there are in mathematics. – Fimpellizieri May 24 '17 at 5:07
• I wouldn't really be surprised. I was hoping it's obvious this was phrased somewhat tongue-in-cheek. But still, I wonder if there's a nice combinatorial proof. – Alon Amit May 24 '17 at 5:08
• Another coincidence $\pmatrix{104\\39}=\pmatrix{103\\40}$ – enzotib May 24 '17 at 5:19
• If $\binom{b}{a}=\binom{b-1}{a+1}$ then $b!(a+1)!(b-a-2)!=(b-1)!a!(b-a)!$ or $b(a+1)=(b-a)(b-a-1)$. This gives us a diophantine equation: $$0=b^2-2ab+a^2-b+a-ab=b^2-3ab+a^2+(a-b)$$ It's not impossible to find a combinatoric meaning to this, but it seems unlikely to be edifying. – Thomas Andrews May 24 '17 at 5:30
• $$\binom{14} 6 = \binom{15} 5 = \binom{78} 2 = \binom {3003} 1$$ – Michael Hardy Aug 19 '17 at 20:22

Assume that we have to choose from $15$ people a committee of $5$ plus a president and a secretary.

(a) We can first choose the ordinary members in ${15\choose 5}$ ways, then the president in $10$ ways and the secretary in $9$ ways.

(b) We can first choose the president in $15$ ways, then $6$ members in ${14\choose 6}$ ways, and name one of these to secretary in $6$ ways.

It follows that $${15\choose5}\cdot 10\cdot 9=15\cdot{14\choose 6}\cdot 6\ .$$

• So all we need now is a bijective proof that $10 \cdot 9 = 15 \cdot 6$. – Sean Eberhard Aug 19 '17 at 20:57
• This is an excellently crafted example; I tried to think of one and couldn't. It doesn't answer the OP's question though. It's an example that shows the two numbers are equal. I think the OP wants two different examples where 15C5 appears in one, 14C6 in the other, and then we're able to match choices in example 1 bijectively with choices in example 2. I have no idea how to do this... – Fly by Night May 23 '18 at 17:06

As I recall, line 14 has the only occurrence of consecutive entries $a,2a,3a,$ these being 1001, 2002, 3003. These are forced to be divisible by $7 \cdot 11 \cdot 13$ by number theory properties.

I think there may be other cases of consecutive entries in the same row with $a+b = c.$ Seems to me there was a question, and someone worked it all out.

• Wow, are the squares on the paper bigger or did you just write really small? – Ovi Sep 15 '17 at 15:51

Welp, let's do it

$${15\choose 5} = \frac {15!}{10!5!}$$

$${14\choose 6}=\frac {14!}{8!6!}$$

$${15\choose 5} = \frac {15!}{10!5!}= \frac {14!}{8!6!}\cdot\left[\frac {15}{(9\cdot10)\cdot\frac 1 {6}}\right]$$

So ${15\choose 5}={14\choose 6}$ solely "because" $6\cdot15=\prod_{n=(14-6)+2}^{15-5} n$.

And that is .... a "coincidence". It really is. It's an easy coincidence to force but it isn't anything intrinsic.

If conditions:

$$n <m$$

and $a,b,c,d,\ldots, k$ are $v$ consecutive numbers,

and $a-n=m-k$

and $nm=abcd\cdots k$

then we will have ${m\choose n}={m-v\choose n+v}$

I think, someone might want to check that.

[actually that is surely incorrect, but what is below is probably correct]

Hmmmph, I'm probably off by an indexing factor but...

$${n\choose m}={n-v\choose m+v}\cdot\frac {[(n-v+1)\cdots n]}{[(m+1)\cdots(m+v)]}\cdot[(n-m+v)\cdots(n-v+1)]$$

So these are equal whenever $\frac {[(n-v+1)\cdots n]}{[(m+1) \cdots (m+v)]} \cdot [(n-m+v)\cdots(n-v+1)]=1$

If we let $b-a=k$, then:

$b(b-k)=k(k+1)$

and

$k^2+k(1+b)-b^2=0$

so we need $(1+b)^2+4b^2=5b^2+2b+1=m^2$.

For example, $b=15$ gives $5\cdot225+30+1=1156=34^2$, and $k=\frac{-16+34}{2}=9$.

Given that $\binom{15}{5}=\binom{14}{4}+\binom{14}{5}$, it derives from the fact that $\binom{14}{4}+\binom{14}{5}=\binom{14}{6}$

These are in the ratio of $1:2:3$ because the denominators of $4!10!,5!9!,6!8!$ are in the ratio $1:2:3$

There's a combinatorial reason which follows from the prime factors of the factorials in the denominators, and the fact that from $4!10!$ to $5!9!$ we lose $5\times2$ but gain $5$ and when we step from $5!9!$ to $6!8!$ we gain $3\times2$ but lose $3^2$. So at the very least it's the close incidence of the prime factors of $k$ and $n-k$, in which the same factor is gained and lost two steps in a row.

• When you write out Pascal's matrix in matrix form you can build an obvious "filter" matrix such that when the above relation is satisfied you get a zero entry in the result of the matrix multiplication. I would say, you are looking for Fibonacci subsequences in the binomial/Pascal matrix. It seems that this might lead to an analytic criterion for the above. – rrogers May 31 '17 at 14:40