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
17
votes
2
answers
82k
views
Distinct ways to keep N balls into K Boxes?
How many different ways I can keep $N$ balls into $K$ boxes, where each box should at least contain $1$ ball, $N >>K$, and the total number of balls in the boxes should be $N$? For example: for ...
- 315
15
votes
8
answers
1k
views
Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$
I just found this identity but without any proof, could you just give me an hint how I could prove it?
$$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$
I know that $$2^n = \sum\limits_{k=0}^...
- 153
10
votes
6
answers
2k
views
Proving that ${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k} $
How can I prove that $${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k} $$
I tried the following:
We use the falling factorial power:
$$y^{\underline k}=\underbrace{y(y-1)(...
- 3,919
7
votes
4
answers
6k
views
How many ways can $r$ nonconsecutive integers be chosen from the first $n$ integers?
During self-study, I ran across the question of how many ways six numbers can be chosen from the numbers 1 - 49 without replacement, stipulating that no two of the numbers be consecutive.
I can ...
- 6,773
7
votes
3
answers
5k
views
Restricted Compositions
Number Composition studies the number ways of compositing a number.
I wanna know the number of compositions of $m$ with $n$ parts with the size of the max part equal to or less than $k$.
Is there a ...
- 1,977
6
votes
3
answers
1k
views
Polynomials and partitions
There is a question I have based on the fact:
If you take a quadratic polynomial with integer coefficients, take the set $\{1,2,3,4,5,6,7,8\}$, make a partition $A=\{1,4,6,7\}$, $B=\{2,3,5,8\}$, and ...
- 1,640
50
votes
7
answers
79k
views
How many triangles
I saw this question today, it asks how many triangles are in this picture.
I don't know how to solve this (without counting directly), though I guess it has something to do with some recurrence.
How ...
- 23.2k
38
votes
9
answers
87k
views
Combination with repetitions.
The formula for computing a k-combination with repetitions from n elements is:
$$\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}$$
I would like if someone can give me a simple basic proof that a ...
user31280
34
votes
3
answers
4k
views
Exercise 1.6.3 from Alon & Spencer's *The Probabilistic Method*: prove that $Pr[|X-Y| \leq 2] \leq 3 Pr[|X-Y| \leq 1]$ for i.i.d. real RVs $X$ and $Y$
Doing a little reading over the break (The Probabilistic Method by Alon and Spencer); can't come up with the solution for this seemingly simple (and perhaps even a little surprising?) result:
(A-S ...
- 498
33
votes
9
answers
8k
views
Prove that $(mn)!$ is divisible by $(n!)\cdot(m!)^n$
Let $m$ be a positive integer and $n$ a nonnegative integer. Prove that
$$(n!)\cdot(m!)^n|(mn)!$$
I can prove it using Legendre's Formula, but I have to use the lemma that
$$ \dfrac{\displaystyle\...
- 5,719
28
votes
2
answers
6k
views
Expected number of rolling a pair of dice to generate all possible sums
A pair of dice is rolled repeatedly until each outcome (2 through 12) has occurred at least once. What is the expected number of rolls necessary for this to occur?
Notes: This is not very deep ...
- 281
20
votes
6
answers
46k
views
Number of relations that are both symmetric and reflexive
Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive?
The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...
- 2,684
20
votes
5
answers
47k
views
The Number Of Integer Solutions Of Equations
The Number Of Integer Solutions Of Equations
An approach is to find the number of distinct non-negative integer-valued vectors $(x_1,x_2,...,x_r)$ such that $$x_1 + x_2 + ... + x_r = n$$
Firstly, ...
- 1,587
17
votes
3
answers
46k
views
Explanation circular permutation
Well if one looks at the formula of circular permutations $Pc = (n-1)!$
But as we come to that formula, I need a concrete example and an explanation.
Another thing, I have seen that when working ...
- 323
16
votes
4
answers
59k
views
Expected number of cards you should turn before finding an ace
NOTE: I want to check my solution only
Same question here
The question is this:
Shuffle an ordinary deck of 52 playing cards containing four aces. Then turn up the cards
from the top until the first ...
- 3,914
12
votes
4
answers
41k
views
In how many different ways can we place $8$ identical rooks on a chess board so that no two of them attack each other?
In how many different ways can we place $8$ identical rooks on a chess board so that no two of them attack each other?
I tried to draw diagrams onto a $8\times8$ square but I'm only getting $16$ ways....
- 125
10
votes
4
answers
410
views
Express $1 + \frac {1}{2} \binom{n}{1} + \frac {1}{3} \binom{n}{2} + \dotsb + \frac{1}{n + 1}\binom{n}{n}$ in a simplifed form
I need to express $$1 + \frac {1}{2} \binom{n}{1} + \frac {1}{3} \binom{n}{2} + \dotsb + \frac{1}{n + 1}\binom{n}{n}$$ in a simplified form.
So I used the identity $$(1+x)^n=1 + \binom{n}{1}x + \...
user220382
10
votes
7
answers
5k
views
The number of subsets of a set of cardinality $n$
Please help with this question. Show that for a finite set $A$ of cardinality $n$, the cardinality of $P(A)$ is $2^n$, where $P(A)$ is the power set of $A$. Thank you in advance for any help that is ...
- 419
9
votes
2
answers
16k
views
How many ways can N elements be partitioned into subsets of size K?
Let's have $2$ numbers, $N$ and $K$, where $K$ divides $N$. The number of $K$-combinations from a given set $S$ of $N$ elements is a well-known formula. Let's concatenate $N/K$ groups (resulting in $N$...
- 143
5
votes
4
answers
2k
views
How many ways can the sum of $n$ dice be $s$?
For example, if $n = 2$, and $s=7$ one could have $(1,6), (2,5), (3,3), (4,3), (5, 2), (6,1)$, for six ways.
If $n = 10$ and $s = 30$, one possible combination could be $(1, 2, 3, 4, 3, 2, 1, 5, 6, 3)$...
- 163
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
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
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
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
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