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,893
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
22
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
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
1
vote
2
answers
775
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
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
71
votes
5
answers
30k
views
Probability for the length of the longest run in $n$ Bernoulli trials
Suppose a biased coin (probability of head being $p$) was flipped $n$ times. I would like to find the probability that the length of the longest run of heads, say $\ell_n$, exceeds a given number $m$, ...
- 70.8k
13
votes
7
answers
10k
views
Alternating sum of binomial coefficients: given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$ [duplicate]
Let $n$ be a positive integer. Prove that
\begin{align}
\sum_{k=0}^n \left(-1\right)^k \binom{n}{k} = 0 .
\end{align}
I tried to solve it using induction, but that got me nowhere. I think the ...
- 1,324
32
votes
2
answers
15k
views
6-letter permutations in MISSISSIPPI [duplicate]
How many 6-letter permutations can be formed using only the letters of the word, MISSISSIPPI? I understand the trivial case where there are no repeating letters in the word (for arranging smaller ...
- 323
31
votes
4
answers
3k
views
How can I learn about generating functions?
The intent of this question is to provide a list of learning resources for people who are new to generating functions and would like to learn about them.
I'm personally interested in combinatorics, ...
- 14.9k
21
votes
6
answers
19k
views
How to show that this binomial sum satisfies the Fibonacci relation?
The Binomial Sum
$$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$
satisfies the Fibonacci Relation.
$$
\mbox{I failed to prove that}\quad
\binom{n-k+1}{k}=...
- 966
8
votes
6
answers
8k
views
If I roll three dice at the same time, how many ways the sides can sum up to $13$? [duplicate]
If I rolled $3$ dice how many combinations are there that result in sum of dots appeared on those dice be $13$?
- 2,063
31
votes
8
answers
11k
views
Exactly half of the elements of $\mathcal{P}(A)$ are odd-sized
Let $A$ be a non-empty set and $n$ be the number of elements in $A$, i.e. $n:=|A|$.
I know that the number of elements of the power set of $A$ is $2^n$, i.e. $|\mathcal{P}(A)|=2^n$.
I came across ...
- 507
41
votes
3
answers
53k
views
Calculating the total number of surjective functions
It is quite easy to calculate the total number of functions from a set $X$ with $m$ elements to a set $Y$ with $n$ elements ($n^{m}$), and also the total number of injective functions ($n^{\underline{...
- 3,092
16
votes
4
answers
7k
views
How to find the number of $k$-permutations of $n$ objects with $x$ types, and $r_1, r_2, r_3, \cdots , r_x$ = the number of each type of object?
How can I find the number of $k$-permutations of $n$ objects, where there are $x$ types of objects, and $r_1, r_2, r_3, \cdots , r_x$ give the number of each type of object?
I'm still looking for the ...
- 1,338
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
59
votes
4
answers
61k
views
The generating function for the Fibonacci numbers
Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$
The coefficients are Fibonacci numbers, i.e., the sequence $\left\{1,1,2,3,5,8,13,21,...\right\}$.
- 825
35
votes
7
answers
27k
views
Making Change for a Dollar (and other number partitioning problems)
I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the ...
- 465
19
votes
5
answers
4k
views
Generalised inclusion-exclusion principle
In answers to combinatorial questions, I sometimes use the fact that if there are $a_k$ ways to choose $k$ out of $n$ conditions and fulfill them, then there are
$$
\sum_{k=j}^n(-1)^{k-j}\binom kja_k
...
- 239k
25
votes
1
answer
11k
views
Number of permutations of $n$ elements where no number $i$ is in position $i$
I am trying to figure out how many permutations exist in a set where none of the numbers equal their own position in the set; for example, $3,1,5,2,4$ is an acceptable permutation where $3,1,2,4,5$ is ...
Will specht
7
votes
1
answer
455
views
Why is flipping a head then a tail a different outcome than flipping a tail then a head?
In either case, one coin flip resulted in a head and the other resulted in a tail. Why is {H,T} a different outcome than {T,H}? Is this simply how we've defined an "outcome" in probability?
My main ...
- 2,331