21
$\begingroup$

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.

$\endgroup$
8
  • 7
    $\begingroup$ I think you would be surprised with how many 'coincidences' there are in mathematics. $\endgroup$ – Fimpellizieri May 24 '17 at 5:07
  • 2
    $\begingroup$ 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. $\endgroup$ – Alon Amit May 24 '17 at 5:08
  • 6
    $\begingroup$ Another coincidence $\pmatrix{104\\39}=\pmatrix{103\\40}$ $\endgroup$ – enzotib May 24 '17 at 5:19
  • 5
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews May 24 '17 at 5:30
  • 2
    $\begingroup$ $$ \binom{14} 6 = \binom{15} 5 = \binom{78} 2 = \binom {3003} 1 $$ $\endgroup$ – Michael Hardy Aug 19 '17 at 20:22
32
$\begingroup$

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\ .$$

$\endgroup$
2
  • 4
    $\begingroup$ So all we need now is a bijective proof that $10 \cdot 9 = 15 \cdot 6$. $\endgroup$ – Sean Eberhard Aug 19 '17 at 20:57
  • $\begingroup$ 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... $\endgroup$ – Fly by Night May 23 '18 at 17:06
3
$\begingroup$

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.

enter image description here

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

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$

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – rrogers May 31 '17 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.