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,912
questions
48
votes
6
answers
222k
views
How many distinct functions can be defined from set A to B?
In my discrete mathematics class our notes say that between set $A$ (having $6$ elements) and set $B$ (having $8$ elements), there are $8^6$ distinct functions that can be formed, in other words: $|B|^...
- 749
29
votes
3
answers
32k
views
Simplifying Catalan number recurrence relation
While solving a problem, I reduced it in the form of the following recurrence relation.
$ C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1} $
However https://en.wikipedia.org/...
- 395
24
votes
4
answers
28k
views
Count number of increasing functions, nondecreasing functions $f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$, with $m \geq n$.
I stumbled upon a question given like:
Let $m$ and $n$ be two integers such that $m \geq n \geq 1$.
Count the number of functions $$f: \{1, 2, · · · , n\} \to \{1, 2, · · · , m\}$$ of the following ...
- 491
18
votes
6
answers
3k
views
Book on combinatorial identities
Do you know any good book that deals extensively with identities obtained using combinatorial and/or probabilistic arguments (e.g., by solving the same combinatorial or probability problem in two ...
- 1,896
13
votes
6
answers
2k
views
Proof of $\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1}$?
How do I prove that
$$\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1} \>?$$
I saw this in a book discussing generating functions.
- 1,977
9
votes
4
answers
3k
views
No closed form for the partial sum of ${n\choose k}$ for $k \le K$?
In Concrete Mathematics, the authors state that there is no closed form for
$$\sum_{k\le K}{n\choose k}.$$
This is stated shortly after the statement of (5.17) in section 5.1 (2nd edition of the book)....
- 763
8
votes
3
answers
9k
views
Number of surjections from $\{1,...,m\}$ to $\{1,...,n\}$
Let $m,n$ be two integers such that, $m\ge n$. Compute the number of surjections from $\{1,...,m\}$ to $\{1,...,n\}$
There are $n^m$ functions (total).
we subtract from $n^m$ the number of non-...
- 1,705
6
votes
2
answers
741
views
Sum of Stirling numbers of both kinds
Let $a_k$ be the number of ways to partition a set of $n$ elements $orderly$,which means that order of subsets matters, but order of elements in each subset does not.
My task:
Prove, that$$\sum_{k=...
- 207
6
votes
3
answers
14k
views
How can I find the number of the shortest paths between two points on a 2D lattice grid?
How do you find the number of the shortest distances between two points on a grid where you can only move one unit up, down, left, or right? Is there a formula for this?
Eg. The shortest path between ...
- 459
5
votes
2
answers
2k
views
Double Factorial: Number of possibilities to partition a set of $2n$ items into $n$ pairs
I know that the partition of $2n$ items into $n$ pairs has something to do with double factorial, but I am not sure how many possibilities we exactly have.
We can choose such a partition into pairs ...
- 2,600
36
votes
1
answer
14k
views
Undergrad-level combinatorics texts easier than Stanley's Enumerative Combinatorics?
I am an undergrad, math major, and I had basic combinatorics class using Combinatorics and Graph Theory by Harris et al before (undergrad level). Currently reading Stanley's Enumerative Combinatorics ...
- 517
34
votes
5
answers
150k
views
Number of ways of distributing $n$ identical objects among $r$ groups
I came across this formula in a list:
The number of ways of distributing $n$ identical objects among $r$ groups such that each group can have $0$ or more $(\le n)$ objects
I know that standard way ...
- 585
23
votes
6
answers
27k
views
Counting the number of surjections.
How many functions from set $\{1,2,3,\ldots,n\}$ to $\{A,B,C\}$ are surjections? $n \geq 3$
Attempt
I was hoping to count the number of surjections by treating $A,B,C$ like bins, and counting the ...
- 2,865
15
votes
9
answers
21k
views
Combinatorial proof of $\sum_{k=1}^n k k!=(n+1)!-1$
Prove: $\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$ (preferably combinatorially)
It's pretty easy to think of a story for the RHS: arrange $n+1$ people in a row and remove the the option of everyone ...
- 4,011
9
votes
1
answer
5k
views
Partial sum of rows of Pascal's triangle
I'm interested in finding
$$\sum_{k=0}^m \binom{n}{k}, \quad m<n$$
which form rows of Pascal's triangle. Surely $\sum\limits_{k=0}^n \binom{k}{m}$ using addition formula, but the one above ...
- 1,727