All Questions
40
questions
0
votes
0
answers
125
views
Counting argument for an alternating sum identity $\sum_{b=0}^{\binom{a}{c}}(-1)^{b+1}f(a,b,c)=(-1)^{a+c}\binom{a-1}{c-1}$
Let $f(a,b,c)$ be the number of ways of writing a set of size $a$ as a union of $b$ distinct subsets of size $c$. I've noticed that
$$\sum_{b=0}^{\binom{a}{c}}(-1)^{b+1}f(a,b,c)=(-1)^{a+c}\binom{a-1}{...
- 2,407
0
votes
0
answers
82
views
Number of ways to select subsets to cover the original set
Suppose $S$ is a set with $n$ elements. Let $U=\{T|T\subseteq S\text{ and }|T|=k\}$, i.e., $U$ is the set of all possible subsets of $S$ with cardinality $k$. Clearly $|U|=\binom{n}{k}$. Then how many ...
- 185
2
votes
2
answers
107
views
Inclusion-exclusion conundrum: $\sum_{k=1}^{\lfloor n/2\rfloor} (-1)^{k-1}k\binom{n-k}{k}2^{n-2k} = \binom{n+1}{3}$
I want a proof (preferably combinatorial) of the identity
$$
\sum_{k=1}^{\lfloor n/2\rfloor} (-1)^{k-1}k\binom{n-k}{k}2^{n-2k} = \binom{n+1}{3}.
$$
I suspect that there is an inclusion-exclusion proof ...
- 451
3
votes
2
answers
119
views
To prove: $\sum_{r=0}^{n}{{(-1)^r}{n\choose r}(n-r)^k}=\begin{cases}0&;& k\lt n\\n!&;& k=n\end{cases}$ [duplicate]
To prove: $$\sum_{r=0}^{n}{{(-1)^r}{n\choose r}(n-r)^k}=\begin{cases}0&;& k\lt n\\n!&;& k=n\end{cases}$$
My Attempt:
LHS$={n\choose0}n^k-{n\choose1}(n-1)^k+{n\choose2}(n-2)^k-...+(-1)...
- 8,338
0
votes
3
answers
71
views
How to find the number of committees which contain Aaron, Beatrice, or both Aaron and Beatrice
A committee of $5$ members is to be chosen seven men and five women. Find the number of ways this committee can be formed if the man Aaron or the woman Beatrice or both of them must be in the ...
- 805
6
votes
1
answer
377
views
Is there a combinatorial interpretation for a sum that includes $(-1)^k$?
There are a lot of combinatorial sums that one can prove with a combinatorial interpretation like double counting. For example
\begin{align*}
\begin{array}{c}
\displaystyle{\sum_{k = 0}^n \binom{n}{k} ...
- 1,131
4
votes
2
answers
80
views
Two inequalities with inclusion-exclusion
Let $S$ be a base set of size $n$.
Also denote $k$ of $S$'s subsets by $A_1,...,A_k\in 2^S$ such that $\bigcup_i A_i=S$.
Furthermore, let $n_\alpha=\lvert\bigcap_{i\in\alpha}A_i\rvert$ be the size of ...
- 75
0
votes
0
answers
272
views
Why is $\sum_{i=0}^k (-1)^{k-i} {n \choose i} {n-i-1 \choose k-i}=1$
Prove $\sum_{i=0}^k (-1)^{k-i} {n \choose i} {n-i-1 \choose k-i}=1$. I was recently working through the proof of a question using inclusion exclusion and was stuck on this part. I verified this ...
- 141
4
votes
1
answer
198
views
binomial coefficient in the inclusion-exclusion principle
Suppose n people leave their coats at the cloakroom, but on leaving the cloakroom the supervisor randomly gives any coat back to each person. Now to determine the number of permutations in which s ...
user672626
6
votes
1
answer
156
views
Combinatorial interpretation of a sum
I would like to know if there exists a way to interpret this sum by a combinatorial argument
$$\sum _ { k = 0 } ^ { n } \frac { ( - 4 ) ^ { k } k ! } { ( 2 k + 1 ) ! ( n - k ) ! } = \frac { 1 } { ( 2 ...
- 113
2
votes
0
answers
104
views
Alternative way to deduce combinatorial identity?
By considering the partial fraction decomposition of a certain family of expressions, I have managed to deduce the identity:
$$\sum_{k=0}^{n} (-1)^k {2n\choose k} (n-k)^{2m} \equiv 0 $$
where $n > ...
- 2,466
1
vote
0
answers
120
views
Proving this equation involving derivative of a rook polynomial.
So, there is an exercise in Section 8.3 in Alan Tucker's Applied Combinatorics regarding rook polynomials. The problem is as follow.
Let $R_{n, m}(x)$ be the rook polynomial for an $n \times m$ ...
- 11
3
votes
2
answers
298
views
How to prove that $\sum_{k=0}^m(-1)^k\binom{m}{k}\binom{n-k}{r}=\binom{n-m}{r-m} \qquad (n\ge r\ge m\ge 0)$
How to prove that
$$\sum_{k=0}^m(-1)^k\binom{m}{k}\binom{n-k}{r}=\binom{n-m}{r-m} \qquad (n\ge r\ge m\ge 0)$$
by using inclusion-exclusion principle?
With inclusion–exclusion principle, it's not hard ...
- 133
1
vote
2
answers
127
views
Evaluating $\sum_{i=0}^{30}(-1)^i {{30} \choose {i}}(30-i)^{31}$
As the title says, I've been asked to evaluate this sum: $$\sum_{i=0}^{30}(-1)^i {{30} \choose {i}}(30-i)^{31}$$ and have been unable to do so. The possible answers are $$\frac {30\cdot31!} 2, \frac {...
- 367
-2
votes
1
answer
88
views
Number of strings containing each vowel at least once?
Consider the English alphabet {$a,b,c,...,z$}. How many strings of length $n$ can be formed in which each vowel {$a,e,i,o,u$} appears at least once?
user843514