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,923
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
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,715
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
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
6
votes
2
answers
743
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
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
15k
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
151k
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,875
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
9
votes
4
answers
1k
views
Prove $\binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a}$
I want to prove this equation,
$$
\binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a}
$$
I thought of proving this equation by prove that you are using different ways to count the same set of ...
- 221
53
votes
2
answers
11k
views
How to reverse the $n$ choose $k$ formula?
If I want to find how many possible ways there are to choose k out of n elements I know you can use the simple formula below:
$$ \binom{n}{k} = \frac{n! }{ k!(n-k)! } .$$
What if I want to go the ...
- 831
30
votes
5
answers
30k
views
Using Pigeonhole Principle to prove two numbers in a subset of $[2n]$ divide each other
Let $n$ be greater or equal to $1$, and let $S$ be an $(n+1)$-subset of $[2n]$. Prove that there exist two numbers in $S$ such that one divides the other.
- 357
29
votes
3
answers
5k
views
Alternating sum of squares of binomial coefficients
I know that the sum of squares of binomial coefficients is just ${2n}\choose{n}$ but what is the closed expression for the sum ${n\choose 0}^2 - {n\choose 1}^2 + {n\choose 2}^2 + \cdots + (-1)^n {n\...
- 291
27
votes
1
answer
34k
views
The number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts
This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give ...
- 497
25
votes
5
answers
4k
views
Evaluate $\sum\limits_{k=1}^n k^2$ and $\sum\limits_{k=1}^n k(k+1)$ combinatorially
$$\text{Evaluate } \sum_{k=1}^n k^2 \text{ and } \sum_{k=1}^{n}k(k+1) \text{ combinatorially.}$$
For the first one, I was able to express $k^2$ in terms of the binomial coefficients by considering a ...
- 6,799
22
votes
2
answers
3k
views
What's the General Expression For Probability of a Failed Gift Exchange Draw
My family does a gift exchange every year at Christmas. There are five couples and we draw names from a hat. If a person draws their own name, or the name of their spouse, all the names go back in a ...
- 295
17
votes
2
answers
26k
views
Arrangements of a,a,a,b,b,b,c,c,c in which no three consecutive letters are the same
Q: How many arrangements of a,a,a,b,b,b,c,c,c are there such that
$\hspace{5mm}$ (i). no three consecutive letters are the same?
$\hspace{5mm}$ (ii). no two consecutive letters are the same?
A:(i). ...
- 1,216
15
votes
3
answers
416
views
Proving that $\frac{(k!)!}{k!^{(k-1)!}}$ is an integer
I have to prove that:
$$\frac{(k!)!}{k!^{(k-1)!}} \in \Bbb Z$$
for any $k \geq 1, k \in \Bbb N$
Tried doing $t = k!$ which would give $$\frac{t!}{t^{t/k}}$$
But I think I just made it harder, and ...
- 4,861
12
votes
2
answers
928
views
The pebble sequence (Bulgarian solitaire)
Let we have $n\cdot(n+1)/2$ stones grouped by piles. We can pick up 1 stone from each pile and put them as a new pile. Show that after doing it some times we will get the following piles: $1, 2, \...
- 4,793
9
votes
5
answers
8k
views
Fibonacci sequence divisible by 7? [closed]
Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$.
I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.
- 149
6
votes
2
answers
4k
views
How many $N$ digits binary numbers can be formed where $0$ is not repeated
How many $N$ digits binary numbers can be formed where $0$ is not repeated.
Note - first digit can be $0$.
I am more interested on the thought process to solve such problems, and not just the answer.
...
- 233
6
votes
1
answer
1k
views
$x+y+z=n$. Finding the number of solutions.
I have found two formulas. I want to connect them!
The number of ways in which a given positive integer $n≥3$ can be expressed as a sum of three positive integers $x,y,z$ (i.e. $x+y+z=n$) , subject ...
- 3,789
5
votes
1
answer
1k
views
Find a generating function for the number of strings
The string $AAABBAAABB$ is a string of ten letters, each of which is $A$ or $B$, that does include the consecutive letters $ABBA$. Determine, with justification, the total number of strings of ten ...
- 11.2k
3
votes
1
answer
2k
views
How can I determine the number of unique hands of size H for a given deck of cards?
I'm working on a card game, which uses a non-standard deck of cards. Since I'm still tweaking the layout of the deck, I've been using variables as follows:
Hand size: $H$
Number of suits: $S$
Number ...
- 123