All Questions
Tagged with formal-proof co.combinatorics
4 questions
4
votes
1
answer
119
views
Proving Equal Set Sizes in Sequential Point Selection on a Real Interval with Variable-Length Intervals
I'm here as an engineer working on a point sampling algorithm and I've noticed that when I perform the algorithm on an ordered set of points in one direction it selects the exact same number of points ...
- 151
20
votes
1
answer
4k
views
Where can I find Gonthier's Coq code proving the four color theorem?
In a 2008 article in the Notices, Georges Gonthier announced a computer-checked proof of the four color theorem using Coq:
Gonthier, Georges. Formal proof—the four-color theorem.
Notices Amer. ...
- 29.7k
5
votes
4
answers
1k
views
Binomial ID $\sum_{k=m}^p(-1)^{k+m}\binom{k}{m}\binom{n+p+1}{n+k+1}=\binom{n+p-m}{n}$
Could I get some help with proving this identity?
$$\sum_{k=m}^p(-1)^{k+m}\binom{k}{m}\binom{n+p+1}{n+k+1}=\binom{n+p-m}{n}.$$
It has been checked in Matlab for various small $n,m$ and $p$. I have a ...
- 573
8
votes
1
answer
455
views
Proving that a combinatorial sequence has no compact formula
Suppose we have a sequence $a_n$ given by some combinatorial formula, e.g. involving a sum of n terms (like ${n \choose k}^{10}3^{-k}$ etc.). Sometimes it is plausible that there is no compact ...
- 3,323