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
13
votes
2
answers
14k
views
Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$
I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$
I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
- 6,305
33
votes
6
answers
19k
views
How do you prove ${n \choose k}$ is maximum when $k$ is $ \lceil \tfrac n2 \rceil$ or $ \lfloor \tfrac n2\rfloor $?
How do you prove $n \choose k$ is maximum when $k$ is $\lceil n/2 \rceil$ or $\lfloor n/2 \rfloor$?
This link provides a proof of sorts but it is not satisfying. From what I understand, it focuses on ...
- 1,183
13
votes
4
answers
5k
views
Combinatorial proof: $e^x=\sum\limits_{k=0}^{\infty}\frac{x^k}{k!}$
Using notion of derivative of functions from Taylor formula follow that
$$e^x=\sum_{k=0}^{\infty}\frac{x^k}{k!}$$
Is there any elementary combinatorial proof of this formula
here is my proof for $x$...
- 17k
138
votes
22
answers
79k
views
Good Book On Combinatorics
What is your recommendation for an in-depth introductory combinatoric book? A book that doesn't just tell you about the multiplication principle, but rather shows the whole logic behind the questions ...
89
votes
7
answers
164k
views
Number of ways to write n as a sum of k nonnegative integers
How many ways can I write a positive integer $n$ as a sum of $k$ nonnegative integers up to commutativity?
For example, I can write $4$ as $0+0+4$, $0+1+3$, $0+2+2$, and $1+1+2$.
I know how to find ...
- 901
22
votes
10
answers
5k
views
Truncated alternating binomial sum
It is easily checked that
$\displaystyle\sum_{i\ =\ 0}^{n}\left(\, -1\,\right)^{i} \binom{n}{i} = 0$, for example by appealing to the binomial theorem.
I'm trying to figure out what happens with the ...
- 693
13
votes
4
answers
14k
views
Enumerating number of solutions to an equation [duplicate]
How do you find the number of solutions like this?
$$x_1 + x_2 + x_3 + x_4 = 32$$
where $0 \le x_i \le 10$.
What's the generalized approach for it?
- 303
45
votes
8
answers
8k
views
why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$
why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$?
I know this is well-known. But how to prove it rigorously? Even mathematical induction does not seem so straight-forward.
...
- 4,157
12
votes
3
answers
5k
views
Proof of a combinatorial identity: $\sum\limits_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$ [duplicate]
Possible Duplicate:
Identity involving binomial coefficients
This was part of a homework assignment that I had, and I couldn't figure it out. Now it is bugging me. Can anyone help me? Although a ...
- 307
65
votes
5
answers
159k
views
Number of onto functions
What are the number of onto functions from a set $\Bbb A $ containing m elements to a set $\Bbb B$ containing n elements.
I ...
- 905
5
votes
2
answers
2k
views
Combinatorial interpretation for Vandermonde's identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?
A known identity of binomial coefficients is that
$$
\sum_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}.
$$
Is there a combinatorial proof/explanation of why it holds? Thanks.
- 51
48
votes
1
answer
30k
views
How to count number of bases and subspaces of a given dimension in a vector space over a finite field? [duplicate]
Let $V_{n}(F)$ be a vector space over the field $F=\mathbb Z_{p}$ with $\dim V_{n} = n$, i.e., the cardinality of $V_{n}(\mathbb Z_{p}) = p^{n}$. What is a general criterion to find the number of ...
- 12.6k
21
votes
3
answers
13k
views
What is the number of invertible $n\times n$ matrices in $\operatorname{GL}_n(F)$?
$F$ is a finite field of order $q$. What is the size of $\operatorname{GL}_n(F)$ ?
I am reading Dummit and Foote "Abstract Algebra". The following formula is given: $(q^n - 1)(q^n - q)\cdots(q^n - ...
- 3,711
44
votes
3
answers
10k
views
How do I count the subsets of a set whose number of elements is divisible by 3? 4?
Let $S$ be a set of size $n$. There is an easy way to count the number of subsets with an even number of elements. Algebraically, it comes from the fact that
$\displaystyle \sum_{k=0}^{n} {n \...
- 429k
17
votes
4
answers
72k
views
Sum of $k {n \choose k}$ is $n2^{n-1}$
Proof that $\suṃ̣_{k=1}^{n}k {n \choose k}$ for $n \in \mathbb N$ is equal to $n2^{n-1}$.
As a hint I got that $k {n \choose k} = n {n-1\choose k-1} $.
I tried solving this by induction but, in the ...
- 1,324
47
votes
6
answers
78k
views
Expected Value of a Binomial distribution?
If $\mathrm P(X=k)=\binom nkp^k(1-p)^{n-k}$ for a binomial distribution, then from the definition of the expected value
$$\mathrm E(X) = \sum^n_{k=0}k\mathrm P(X=k)=\sum^n_{k=0}k\binom nkp^k(1-p)^{n-k}...
user31280
39
votes
7
answers
67k
views
In how many ways can a number be expressed as a sum of consecutive numbers? [duplicate]
All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example $9$ can be expressed in three such ways, $2+3+4$, $4+5$ or simply $9$. In how many ...
- 581
22
votes
16
answers
4k
views
How to show $\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$
How does one show that $$\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$$ for each nonnegative integer $n$?
I tried using the Snake oil technique but I guess I am applying it incorrectly. With the ...
- 5,528
22
votes
1
answer
3k
views
Find the number of arrangements of $k \mbox{ }1'$s, $k \mbox{ }2'$s, $\cdots, k \mbox{ }n'$s - total $kn$ cards.
Find the number of arrangements of $k \mbox{ }1'$s, $k \mbox{ }2'$s, $\cdots, k \mbox{ }n'$s - total $kn$ cards - so that
no same numbers appear consecutively. For $k=2$ we can compute it by using ...
- 1,041
18
votes
2
answers
14k
views
Inductive Proof for Vandermonde's Identity?
I am reading up on Vandermonde's Identity, and so far I have found proofs for the identity using combinatorics, sets, and other methods. However, I am trying to find a proof that utilizes mathematical ...
user41419