All Questions
Tagged with binomial-coefficients combinatorics
3,233
questions
9
votes
3
answers
339
views
How can I simplify this combinatorics expression?
I got a expression that is related to the combinatorics, and it looks like this:
$$\sum_{k=1}^n \frac{2^{2k-1}}{k}\binom{2n-2k}{n-k}\cdot \frac{1}{\binom{2n}{n}}$$
it is from a question I've been ...
- 93
6
votes
2
answers
221
views
Is this identity I found playing around with generating function with coefficients $I(n) = \int_{0}^\pi \sin^n(x) dx$ useful and or reducible?
Let $I(n) = \int_{0}^\pi \sin^n(x) dx$ , using $\sin^2(x) = 1-\cos^2(x)$ and integrating by parts we get.
$$ \begin{align} I(n) = \dfrac{n-1}{n} I(n-2) \end{align} $$
With $I(0) = \pi$ and $I(1) = 2$ ...
- 61
0
votes
0
answers
52
views
Sum of every $k$th binomial coefficients over upperindex
From the Hockey-Stick Identity, we have for $n\geq r \geq 0$:
$$\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}.$$
Now, I am wondering whether an identity exists for any fixed ( $k > 0$ ):
$$\sum_{i=...
- 113
3
votes
5
answers
218
views
Coefficient of $x^{21}$ in $(1+x+x^2+\dots+x^{10})^4$
Find the coefficient of $x^{21}$ in $(1+x+x^2+\dots+x^{10})^4$
I tried splitting the terms inside the bracket into two parts $1+x+\dots+x^9$ and $x^{10}$, and then tried binomial theorem, but that ...
- 565
2
votes
2
answers
74
views
Correctness of Solution for Forming a Committee with More Democrats than Republicans
I recently encountered a problem and derived a solution, but I am uncertain about its correctness. Here's the problem:
At a congressional hearing, there are 2n members present. Exactly
n of them are ...
- 33
0
votes
1
answer
27
views
Prove that $C(n,j)$ is periodic on $\mathbb{F}_2$? [duplicate]
Fix j and consider the sequence of binomial coefficients $[C(n,j)]_n$ on $\mathbb{F}_2$. It seems like it is periodic, but I am not sure how to prove it, or to determine its period.
- 23
0
votes
2
answers
162
views
Emma plays a game with rocks
Emma is playing a game. She has to place rocks on a $3\times3$ square board such that rocks are placed on non-adjacent squares (squares that are not directly above, below, left, or right of another ...
- 637
0
votes
3
answers
57
views
Proving $\sum_{k=m}^n\binom nk\binom km=2^{n-m}\binom nm$ [duplicate]
$$\sum_{k=m}^n{n\choose k}{k \choose m}=2^{n-m}{n\choose m}$$
I proved this by considering $2^{n-m}=(1+1)^{n-m}$ in the RHS, expanding it into binomials, and then doing some manipulations with the ...
1
vote
0
answers
89
views
The sum 4 product of binomial coefficients
I'm interested in the following sum: $\sum_{m=1}^{t}\binom{m+i-2}{i-1}\binom{t-m+n-i}{n-i}\binom{m+j-2}{j-1}\binom{t-m+n-j}{n-j}$
This sum arises when calculating the order polynomial for a type of 2-...
- 61
2
votes
1
answer
93
views
Why does the number of permutations of these sequences with non-negative partial sums have such a simple closed form (m choose n)?
I've been thinking about a problem, and I think that I have a solution, and I'm not sure why it works. Looking for an intuitive (or just any) explanation.
The problem
Choose an integer $k>1$. For ...
- 61
1
vote
2
answers
87
views
Nested sum of product of binomial numbers
I am currently working on an automata theory concerning a special case of nondeterministic automata. I am studying the state complexity of converting this automaton to a classical deterministic one (...
- 13
0
votes
0
answers
51
views
$f\left(x+1,y+1\right)=\frac{f\left(x+1,y\right)+f\left(x,y+1\right)}{2}+1$
The problem
$\forall x,y \in \mathbb{W} \\ f(x,0)=f(0,y)= 0 \\ f(1,1)=1 \\ \forall x,y \in \mathbb{N} \\
f\left(x+1,y+1\right)=\frac{f\left(x+1,y\right)+f\left(x,y+1\right)}{2}+1$
When I tried easier ...
1
vote
0
answers
59
views
Is this formula for number of binary relations correct?
I'm trying to determine the number of binary relations between sets $A$ and $B$ that are both left-unique and right-unique, which we call one-to-one. That is, relations $R$ such that every $a \in A$ ...
- 358
1
vote
1
answer
55
views
Solve the following recurrence relation: $f(N,d) = p*f(N-1,d-1) + (1-p)*f(N-1,d+1)$ subject to constraints in the body.
The constraints are $f(0,0)=1, f(0,k)=0\space \forall k \neq 0, f(N,k)=0 \space \forall k>N\space0\leq p\leq 1$ .
When working on a probability problem, I came across this recursion when working ...
- 194
0
votes
0
answers
48
views
Calculate $\displaystyle\sum_{k=0}^n \displaystyle\binom{n}{k} \dfrac{(-1)^{n-k}k^l}{l!}$ [duplicate]
I want to prove that for all $0 \leq l \leq n$, $$ \displaystyle\sum_{k=0}^n \displaystyle\binom{n}{k} \dfrac{(-1)^{n-k}k^l}{l!} = \begin{cases} 0 \text{ if } l<n \\ 1 \text{ if } l=n \end{cases}$$
...
- 21