Linked Questions
11 questions linked to/from Lower bound for sum of binomial coefficients?
0
votes
0
answers
108
views
Lower bound on sum of binomial coefficients [duplicate]
Is there a good lower bound for the tail of sums of binomial coefficients, so a lower bound for $\sum_{i=1}^k {n \choose 2i-1}$?
7
votes
3
answers
790
views
Expected cardinality of a randomly chosen element of the family of subsets of $\{1,\ldots,n\}$ with at most $k$-elements
Assume that $1\le k \le n$ and let $\mathscr{Z}$ be the family of all subsets of $\{1,\ldots,n\}$ with at most $k$ elements. Pick a random element $X$ of $\mathscr{Z}$ (we consider the probablity ...
- 1,658
4
votes
2
answers
7k
views
Partial Sum of the Binomial Theorem [duplicate]
The binomial theorem states $\sum_{k=0}^nC_n^kr^k=(1+r)^n$. I am interested in the function \begin{equation}
\sum_{k=0}^mC_n^kr^k, \quad m<n
\end{equation}
for fixed $n$ and $r$, and both $m$ and $...
- 41
3
votes
3
answers
698
views
Lower/Upper bounds for $ \sum\limits_{i=0}^k \binom ni x^i $
Are there good lower/upper bounds for
$ \sum\limits_{i = 0}^k {\left( \begin{array}{l} n \\ i \\ \end{array} \right)x^i } $ where $0<x<1$, $k \ll n$?
- 31
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
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
9
votes
2
answers
420
views
Maximum of the weighted binomial sum $2^{-r}\sum_{i=0}^r\binom{m}{i}$
Let $m$ be a positive integer and let $f_m(r)=2^{-r}\sum_{i=0}^r\binom{m}{i}$. Clearly $f_m(0)=f_m(m)=1$ and $f_{2r+1}(r)=2^{2r}$.
Conjecture: If $m>12$, then the maximum value of $f_m(r)$ for $r\...
- 1,991
2
votes
1
answer
909
views
Upper bound of sum of binomial coefficients
I am looking for an upper bound - up to constant factor - for:
$\sum_{k=t}^{t+l} {n \choose k} \cdot 2^{-n}$ where:
The values of $t$ are between: $\frac{n}2+\sqrt{n} \leq t \leq \frac{9n}{10}$. (...
- 23
0
votes
1
answer
704
views
Asymptotic behaviour of Binomial Sum
I am interested in the behaviour of:
$\gamma_k=\sum_{i=0}^{k} {n \choose i}$
as n becomes large and where $k$ could potentially be a function of $n$ rather than a constant. One line of attack I can ...
- 103
0
votes
2
answers
208
views
Interpolating asymptotic expression for logarithm of middle binomial sums
Define $S(k,2n)=\sum_{i=-k}^k\binom{2n}{n+i}$ at every $k\in\{0,\dots,n\}$.
We know $$\ln(S(\gamma\mbox{ } n^\gamma,2n))\asymp(2n\ln2-\frac12\ln\pi-\frac12\ln n)$$ at $\gamma\rightarrow0$ and $$\ln(S(...
- 1,826
2
votes
0
answers
62
views
A combinatorial question about encoding the subsets of logarithmic-bounded cardinality
Let $k \in \mathbb N - \{0\}$ and $f(n) = \binom n 0 + \binom n 1 + \dotsc + \binom n {\log^k n}$.
Our question is:
$f(n) = o(2^{\log^{k+1} \ (n)})$ or $f(n) = \Theta(2^{\log^{k+1} \ (n)})$, which ...
- 193