Linked Questions
13 questions linked to/from Sum of 'the first k' binomial coefficients for fixed $N$
55
votes
4
answers
5k
views
When do binomial coefficients sum to a power of 2?
Define the function $$S(N, n) = \sum_{k=0}^n \binom{N}{k}.$$
For what values of $N$ and $n$ does this function equal a power of 2?
There are three classes of solutions:
$n = 0$ or $n = N$,
$N$ is odd ...
- 5,217
17
votes
5
answers
7k
views
General bound for the number of subgroups of a finite group
I am interested in the following:
Let $G$ be a finite group of order $n$. Is there an explicit function $f$ such that
$|s(G)| \leq f(n)$ for all $G$ and for all natural numbers $n$, where $s(G)$ ...
user13040
11
votes
2
answers
4k
views
Approximation of sum of the first binomial coefficients for fixed N
I'd like to compute $\sum_{i=0}^k {{N}\choose{i}}$. Is there a computable approximation for that?
- 111
5
votes
3
answers
473
views
Maximize a weighed combinatorial sum
I am trying to maximize the function $$f_s(k)=\frac{1}{2k+s}\sum_{i=0}^k {2k+s\choose i}2^{-(2k+s)}$$ for both $\{s,k\}\in\mathbf N$, that is, for fixed $s$ what is the value of $k$ that maximizes $...
- 153
4
votes
2
answers
465
views
Asymptotics of an alternating sum involving the prefix sum of binomial coefficients
Let $c>1$.
Question.
What is the asymptotic behaviour of the sum
\begin{align}
S_n = \sum_{k=0}^{n} \left(-\frac{1}{2} \right)^k \binom{n}{k} \sum_{j=0}^{k} \binom{cn+k}{j}
\end{align}
as $n$ ...
- 233
4
votes
1
answer
1k
views
Estimating the distribution of minimal hamming distances within a set of strings?
Is their an efficient mathematical way to estimate the distribution of minimal hamming distances for a set of random strings of length 8 over a 4-letter alphabet? E.g. given a set of 100-10,000 ...
- 85
4
votes
1
answer
674
views
Complete graph coloring with cycle restriction
The following question is probably open (It was posted on AoPS a long time ago, but no one has a solution)
We have a complete graph with $n$ vertices. Each edge is colored in one of $c$ colors such ...
3
votes
2
answers
754
views
Counting Regions in Hyperplane Arranglements
Consider the following:
1) How many connected regions can $n$ hyperplanes form in $\mathbb R^d$?
2) What if the set of hyperplanes are homogeneous?
3) Given a set of $n$ pairs of ...
- 197
7
votes
1
answer
626
views
Upper bound on the number of convex connected components of the complement of the zero set of a polynomial
The classic Milnor-Thom upper bound on the sum of the Betti numbers of real algebraic sets (for a nice exposition and references, see e.g. N.R. Wallach, On a Theorem of Milnor and Thom, in S. Gindikin ...
- 7,817
1
vote
3
answers
349
views
how to proof this Stirling related equation
here is what I need to proof, have no idea were to start. I know there is some connection with the Stirling theorem.
$$
\sum_{i=0}^{d}\binom{m}{i} \leq \left ( \frac{em}{d} \right )^{d}
$$
I tried ...
- 11
0
votes
0
answers
1k
views
Partial sum of binomial coefficients
For some integer $z \ge 2$ and large integer $n$ and $ t=\lceil \log n\rceil $, what is an approximate value for the following partial binomial sum?
$$ \sum_{i=0}^{n-t} \binom{n}{i}z^i .$$
Another ...
- 1
1
vote
1
answer
336
views
sum of binomial coefficient approximation by geometric series
I follow a subject almost like this link:
Sum of 'the first k' binomial coefficients for fixed $N$
$$
f(N,k) = \sum^{k}_{i=0} \binom{N}{i} .
$$
Michael Lugo suggest a way with geometric series ...
- 21
1
vote
0
answers
399
views
Bounding a sum of binomial coefficients in terms of 'the next one'
I need to bound a sum of a portion of binomial coefficients in terms of "the next one", and understand what is the best which can be said in this sense.
Given a real number $t \geq 2$, call $P(t)$ ...
- 731