All Questions
Tagged with binomial-coefficients combinatorics
3,233
questions
2
votes
2
answers
125
views
what is some polynomial bound of the following expression?
I have the expression (for some $k$ and $r$ natural numbers):
$\sum_{l=0}^r {l \choose k}$.
Is there a way to bound this expression using a polynomial of degree which is linear in $k$ (or polynomial ...
- 713
24
votes
5
answers
10k
views
Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$
I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a ...
- 15.5k
5
votes
1
answer
389
views
Is there a combinatorial proof of this congruence identity?
Prove that
$$\binom{2p}{p} \equiv 2\pmod{p^3},$$
where $p\ge 5$ is a prime number.
- 119
4
votes
2
answers
3k
views
5
votes
3
answers
394
views
Prove that $\sum_{i=0}^n2^{3i} \binom {2n+1}{2i+1}$ is never divisible by 5
Question : Prove that the number is never divisible by 5.
- 329
5
votes
2
answers
11k
views
Number of even and odd subsets [duplicate]
Suppose we have the following two identities:
$\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$
$\displaystyle \sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$
The first says that the number of subsets of ...
- 14k
2
votes
2
answers
420
views
Combinatorial Identity and Counting
Show that $\binom{2n}{2} = 2 \binom{n}{2}+n^2$.
LHS: This is the number of pairs of $2n$ distinct elements.
RHS: We can rewrite this as $2 \binom{n}{2}+ \binom{n}{1} \binom{n}{1}$. So you can ...
- 14k
14
votes
1
answer
692
views
Combinatorial Proof of $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$ for $n \geq 4$
For $n \geq 4$, show that $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$.
LHS: So we have a set of $\binom{n}{2}$ elements, and we are choosing a $2$ element subset.
RHS: We are ...
- 14k
8
votes
2
answers
3k
views
Combinatorial Identity $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$
Show that $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$.
In the LHS $\binom{n+r-1}{r}$ counts the number of ways of selecting $r$ objects from a set of size $n$ where ...
- 14k
10
votes
3
answers
1k
views
Simplify $\sum \limits_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}}$
Can this sum be simplified: $\sum \limits_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}}$
Or at least is there a simple fairly tight upperbound?
EDIT
So I think this sum is more easily bounded than I ...
- 1,129
17
votes
6
answers
3k
views
Combinatorial proof of a binomial coefficient summation: $\sum_{k=1}^n \binom nk \binom n{k-1} = \frac12\binom{2n+2}{n+1} - \binom{2n}n$
Let $n$ and $k$ be integers with $1 \leq k \leq n$. Show that:
$$\sum_{k=1}^n {n \choose k}{n \choose k-1} = \frac12{2n+2 \choose n+1} - {2n \choose n}$$
I was told this is supposed to use a ...
- 449
10
votes
3
answers
460
views
Non-probabilistic proofs of a binomial coefficient identity from a probability question
Combining the answers given by me and Ralth to the probability question at Probability of getting three zeros when sampling a set, we get the following identity:
$$
\sum\limits_{k = m}^n {{n \choose k}...
- 24.2k
24
votes
6
answers
2k
views
Exercise from Comtet's Advanced Combinatorics: prove $27\sum_{n=1}^{\infty }1/\binom{2n}{n}=9+2\pi \sqrt{3}$
In exercise 36 Miscellaneous Taylor Coefficients using Bernoulli
numbers on pages 88-89 of Louis Comtet's Advanced Combinatorics, 1974,
one is asked to obtain the following explicit formula for the ...
- 38.8k
14
votes
4
answers
2k
views
How this operation is called?
This operation is similar to discrete convolution and cross-correlation, but has binomial coefficients:
$$f(n)\star g(n)=\sum_{k=0}^n \binom{n}{k}f(n-k)g(k) $$
Particularly,
$$a^n\star b^n=(a+b)^n$$...
- 9,261
4
votes
1
answer
253
views
Limit involving the totient function and combination
Do you think the following limits are correct?
$\displaystyle\lim_{d\to\infty}\frac{\sum\limits_{k=1}^{d} {\varphi(N) \choose k} {d-1 \choose k-1}}{\varphi(N)^d}=0$
$\displaystyle\lim_{N\to\infty}\...
- 41