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,922
questions
4
votes
2
answers
3k
views
Number of solutions of $x_1+x_2+\dots+x_k=n$ with $x_i\le r$
Let $n,k,r$ be positive integers. The number of all nonnegative solutions of the Diophantine Equation $x_1+x_2+\dots+x_k=n$ is $\binom{n+k-1}{n}$. Is there a general formula for the number of ...
- 1,542
3
votes
1
answer
453
views
Combinatorics That Looks Similar to Vandermonde's Identity
How do I simplify:
$$\sum_{r = 0}^{\lfloor \frac{k}{2} \rfloor} \dbinom{k}{2r} \cdot \dbinom{n-k}{k-2r}?$$
Basically, the sum is: $\dbinom{k}{0} \cdot \dbinom{n-k}{k} + \dbinom{k}{2} \cdot \dbinom{n-k}...
- 539
79
votes
9
answers
85k
views
What is the math behind the game Spot It?
I just purchased the game Spot It. As per this site, the structure of the game is as follows:
Game has 55 round playing cards. Each card has eight randomly placed symbols. There are a total of 50 ...
- 894
40
votes
4
answers
6k
views
Combinatorial interpretation of Binomial Inversion
It is known that if $f_n = \sum\limits_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is ...
- 6,265
31
votes
3
answers
4k
views
How to prove that the number $1!+2!+3!+...+n!$ is never square?
How to prove that the number $1!+2!+3!+...+n! \ \forall n \geq 4$ is never square?
I was told to count permutations but I cannot figure out what we are permuting.... Thanks!
- 569
25
votes
4
answers
7k
views
The locker problem - why squares?
There are 1000 lockers in a high school with 1000 students. The
problem begins with the first student opening all 1000 lockers; next
the second student closes lockers 2,4,6,8,10 and so on to ...
- 645
25
votes
4
answers
11k
views
Combinatorial interpretation of sum of squares, cubes
Consider the sum of the first $n$ integers:
$$\sum_{i=1}^n\,i=\frac{n(n+1)}{2}=\binom{n+1}{2}$$
This makes the following bit of combinatorial sense. Imagine the set $\{*,1,2,\ldots,n\}$. We can ...
- 55.1k
25
votes
3
answers
8k
views
Circular permutations with indistinguishable objects
Given n distinct objects, there are $n!$ permutations of the objects and $n!/n$ "circular permutations" of the objects (orientation of the circle matters, but there is no starting point, so $1234$ and ...
- 36.6k
18
votes
3
answers
10k
views
Number of ways to put $n$ unlabeled balls in $k$ bins with a max of $m$ balls in each bin
The number of ways to put $n$ unlabeled balls in $k$ distinct bins is
$$\binom{n+k-1}{k-1} .$$
Which makes sense to me, but what I can't figure out is how to modify this formula if each bucket has a ...
- 587
17
votes
8
answers
2k
views
Proving a binomial sum identity $\sum _{k=0}^n \binom nk \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}$
Mathematica tells me that
$$\sum _{k=0}^n { n \choose k} \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}.$$
Although I have not been able to come up with a proof.
Proofs, hints, or references are all ...
user899
15
votes
4
answers
6k
views
Number of equivalence classes of $w \times h$ matrices under switching rows and columns
If I have a $w \times h$ matrix where each value is an integer $0 \lt n \lt 20$,
how can I count the number of distinct configurations, where $2$ configurations are "distinct" if there is no way to ...
- 323
13
votes
4
answers
9k
views
Number of Derangements of the word BOTTLE
I am wondering how to calculate the number of derangements for the word BOTTLE. I understand how to actually do the formula for derangements already. My issue is what do you do with repeated letters. ...
12
votes
2
answers
6k
views
What is the minimum number of locks on the cabinet that would satisfy these conditions?
Eleven scientists want to have a cabinet built where they will keep some top secret work. They want multiple locks installed, with keys distributed in such a way that if any six scientists are present ...
- 4,996
11
votes
3
answers
25k
views
Probability question about married couples
If four married couples are arranged in a row, what is the probability
that no husband sits next to his wife?
Would it be
$1- \frac{2(4!)}{8!}$?
- 1,958
10
votes
4
answers
2k
views
Counting $k$-ary ordered trees
The (full) binary counting tree problems give the number of binary trees that can be formed using $N$ nodes $T(n)= C_n$, where $C_i$ are the Catalan numbers. The recursion form is $T_n = \sum_{i=0}...
- 225
10
votes
7
answers
6k
views
Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]
I need to prove that there is the following equality:
$$
\sum\limits_{k=0}^n {n-k \choose k} = F_{n}
$$
where $F_{n}$ is a n-th Fibonacci number.
The problem seems easy but I can't find the way to ...
- 1,013
9
votes
3
answers
2k
views
Showing probability no husband next to wife converges to $e^{-1}$
Inspired by these questions:
Probability of Couples sitting next to each other (Sitting in a Row)
Probability question about married couples
Four married couples, eight seats. Probability that ...
- 159k
8
votes
0
answers
673
views
Proving $\sum\limits_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$ [closed]
Prove that $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$
I ...
- 3,224
7
votes
2
answers
260
views
Exploring $ \sum_{n=0}^\infty \frac{n^p}{n!} = B_pe$, particularly $p = 2$.
I was exploring the fact that $$ \sum_{n=0}^\infty \frac{n^p}{n!} = B_pe,$$
where $B_n$ is the $n$th Bell number.
I found this result by exploring the series on wolframalpha and looking up the ...
user109879
5
votes
4
answers
5k
views
Probability that random walk will reach state $k$ for the first time on step $n$
We have a random walk which starts in state $0$. At each step, a coin is tossed with probability of heads: $P(H)=p$. If we get a heads, we go to the next higher integer state and on tails, we go to ...
- 6,943
5
votes
2
answers
1k
views
$\sum_{k=-m}^{n} \binom{m+k}{r} \binom{n-k}{s} =\binom{m+n+1}{r+s+1}$ using Counting argument
I saw this question here:- Combinatorial sum identity for a choose function
This looks so much like a vandermonde identity, I know we can give a counting argument for Vandermonde. However much I try ...
- 860
4
votes
2
answers
7k
views
N circles in the plane
You are given a family of n pairwise intersecting circles in the plane. No three intersect(share a common point). Find a simple formula for counting the number of regions determined by these circles.
...
- 602
4
votes
1
answer
780
views
If $|A| > \frac{|G|}{2} $ then $AA = G $ [closed]
I'v found this proposition.
If $G$ is a finite group , $ A \subset G $ a subset and $|A| > \frac{|G|}{2} $ then $AA = G $.
Why this is true ?
- 11.5k
2
votes
3
answers
11k
views
In how many ways can $3$ red, $3$ blue, and $3$ green balls be arranged so that no two balls of the same colour are consecutive (up to symmetry)?
Make sequence of $9$ balls from 3 red, 3 blue, 3 green, in such a way that no two balls of the same colour are next to each other. In how many different ways can you do this? (symmetric arrangements ...
- 395
221
votes
4
answers
85k
views
Why can a Venn diagram for $4+$ sets not be constructed using circles?
This page gives a few examples of Venn diagrams for $4$ sets. Some examples:
Thinking about it for a little, it is impossible to partition the plane into the $16$ segments required for a complete $...
- 9,583
48
votes
2
answers
2k
views
Guessing a subset of $\{1,...,N\}$
I pick a random subset $S$ of $\{1,\ldots,N\}$, and you have to guess what it is. After each guess $G$, I tell you the number of elements in $G \cap S$. How many guesses do you need?
- 3,373
33
votes
3
answers
11k
views
The $5n+1$ Problem
The Collatz Conjecture is a famous conjecture in mathematics that has lasted for over 70 years. It goes as follows:
Define $f(n)$ to be as a function on the natural numbers by:
$f(n) = n/2$ if $n$ ...
- 5,134
22
votes
2
answers
31k
views
Painting the faces of a cube with distinct colours
I don't think this is solved by Burnside's Lemma since there is a condition that each side is painted a different colour. The question is as follows.
If I had a cube and six colours, and painted ...
- 3,857
20
votes
3
answers
16k
views
Combinatorial argument to prove the recurrence relation for number of derangements
Give a combinatorial argument to prove that the number of derangements satisfies the following relation:
$$d_n = (n − 1)(d_{n−1} + d_{n−2})$$
for $n \geq 2$.
I am able to prove this algebraically but ...
- 201
19
votes
5
answers
2k
views
Showing that $Q_n=D_n+D_{n-1}$
Let $T_n$ be the set of permutations of $\{1,2,\ldots,n\}$ which do not have $i$ immediately followed by $i+1$ for $1\le i\le n-1$; in other words, let
\begin{align}
T_n=\{\sigma \in S_n: \sigma(i)+1\...
- 27.3k