Questions tagged [combinatorics]
For questions about the study of finite or countable discrete structures, especially how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.
6,913
questions
33
votes
5
answers
57k
views
Counting bounded integer solutions to $\sum_ia_ix_i\leqq n$
I want to find the number of nonnegative integer solutions to
$$x_1+x_2+x_3+x_4=22$$
which is also the number of combinations with replacement of $22$ items in $4$ types.
How do I apply stars and bars ...
77
votes
20
answers
24k
views
Proof of the hockey stick/Zhu Shijie identity $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$
After reading this question, the most popular answer use the identity
$$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1},$$
or, what is equivalent,
$$\sum_{t=k}^n \binom{t}{k} = \binom{n+1}{k+1}.$$
What's ...
- 1,620
30
votes
3
answers
12k
views
Extended stars-and-bars problem(where the upper limit of the variable is bounded)
The problem of counting the solutions $(a_1,a_2,\ldots,a_n)$ with integer $a_i\geq0$ for $i\in\{1,2,\ldots,n\}$ such that
$$a_1+a_2+a_3+\ldots+a_n=N$$
can be solved with a stars-and-bars argument.
...
35
votes
3
answers
21k
views
I have a problem understanding the proof of Rencontres numbers (Derangements)
I understand the whole concept of Rencontres numbers but I can't understand how to prove this equation
$$D_{n,0}=\left[\frac{n!}{e}\right]$$
where $[\cdot]$ denotes the rounding function (i.e., $[x]$...
- 453
91
votes
9
answers
106k
views
Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$
I was hoping to find a more "mathematical" proof, instead of proving logically $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$.
I already know the logical Proof:
$${n \choose k}^2 = {...
- 911
99
votes
4
answers
12k
views
Identity for convolution of central binomial coefficients: $\sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$
It's not difficult to show that
$$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$
On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...
- 1,520
198
votes
21
answers
124k
views
Taking Seats on a Plane
This is a neat little problem that I was discussing today with my lab group out at lunch. Not particularly difficult but interesting implications nonetheless
Imagine there are a 100 people in line to ...
- 4,929
32
votes
1
answer
19k
views
Probability distribution in the coupon collector's problem
I'm trying to solve the well known Coupon Collector's Problem by explicitly finding the probability distribution (so far all the methods I read involve using some sort of trick). However, I'm not ...
- 4,800
14
votes
5
answers
3k
views
What does $\binom{-n}{k}$ mean?
For positive integers $n$ and $k$, what is the meaning of $\binom{-n}{k}$?
Specifically, are there any combinatorial interpretations for it?
Edit: I just came across Daniel Loeb, Sets with a ...
- 3,078
16
votes
3
answers
13k
views
Demonstrate another way to implement the Inclusion–exclusion principle?
I'm attempting to implement the Inclusion–exclusion principle, which is generally described as follows...
$$\begin{align}
\left| \bigcup\limits_{i=1}^n A_i \right| =
+ \left( \sum\limits_{i=1}^n | ...
- 317
1
vote
2
answers
773
views
Inclusion–exclusion principle; what is $(-1)^{n+1}$
could somebody kindly confirm that my understanding of inclusion-exclusion matches it's formula.
for a 3 sets example; we add 3 unions, subtract the total of all 3 pairwise intersections and add the ...
- 261
34
votes
12
answers
39k
views
Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$
I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$.
I suppose I could use the counting rules in probability, perhaps combination= ${{n}...
user6639
10
votes
7
answers
24k
views
How to prove Vandermonde's Identity: $\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$?
How can we prove that
$$\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}?$$
(Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Probability, 8th ed by Sheldon Ross.
- 3,909
2
votes
1
answer
850
views
Number of solutions to equation of varying size, with varying upper-bound range restrictions [duplicate]
Given:
$x_1 + x_2 + ... + x_n = k$
where each $x_i$ can have some value between $0$ and $10$ (we might have $0\leq x_1\leq 7$ and we might have $0\leq x_2\leq 9$ and so on...)
How many nonnegative ...
15
votes
4
answers
6k
views
Prove $\sum\limits_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity) [duplicate]
Let $n$ be a nonnegative integer, and $k$ a positive integer. Could someone explain to me why the identity
$$
\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}
$$
holds?
- 1,919