2
votes
Accepted
Helly's theorem for $n\geq d+3$
I'm sure there's a neater way to do this, but:
Take any collection of $d+2$ of the $n$ convex set. By your proof they have a common intersection. Now if we multiply all $n$ sets by $\mathbb{R}$ to ...
- 5,633
2
votes
Accepted
Show that $\sum_{k=1}^n{2^{2k-1}\binom{2n+1}{2k}B_{2k}(0)}=n$
I'm giving credits to @darijgrinberg because I was using the Bernoulli polynomials to approach the proof and I finally figured it out thanks to his comment.
Bernoulli polynomials are defined through ...
- 2,648
1
vote
Finding a new MST for $G(V,E)$ after connecting a new vertex
This is exactly one step of Prim's algorithm. There we already have a minimum spanning tree of some subset of vertices $V'$ then we consider new vertex $v$ and it's incident edges along with the ...
- 21
1
vote
Closed formula for probability of n-digit numbers containing three consecutive sixes
We use a generating function approach to derive a formula for the wanted sequence of probabilities. In order to do so we reformulate the problem a bit. We consider an alphabet $\mathcal{V}=\{0,1,2,3,4,...
- 109k
1
vote
Simple paths in a graph
There are two paths from a to b, two paths from b to d, and one path from a to d.
Therefore, 2 x 2 + 1 = 5.
- 2,592
1
vote
Accepted
Does any permutation "cover" a permutation with less inversions?
It's enough to do the case $k=|E(\pi)|-1$ by induction. Any nonidentity permutation $\pi$ must have an inversion of the form $\langle i, j\rangle$ where $\pi(i)= \pi(j)+1$ (I'm going to use $\langle i,...
- 11k
1
vote
Closed form for the recurrence $S_n = 1 + S_{n-1} + \frac{2}{n} S_{n-2}$, where $S_1=1$ and $S_2=2$?
Too long for a comment.
After reading the more than elegant solution provided by @M.E.W., consider
$$S_n(a)=-\frac{1}{4} \sum_{k=0}^{n-1} \frac{a^{n-k}}{(n-k)!} (k+2)(k+1)$$ the summation is given in ...
- 268k
1
vote
Accepted
Confused about a counting problem
The $10!$ comes up when trying to figure out how many pairings there are when only offense-offense and defense-defense pairings are allowed. Then there are still $20$ pairings, but they partition into ...
- 15k
1
vote
Accepted
Regarding the question of translating the verbal descriptions of definitions and theorems into propositional logic
To fully formalize your definition of $P$ in predicate logic, you might consider something like:
$~~~~~\forall f: \forall d: \forall c: [\forall a:[a\in d \implies f(a)\in c]\\ ~~~~~\implies [P(f,d,c) ...
- 14.8k
Only top scored, non community-wiki answers of a minimum length are eligible