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,901
questions
76
votes
7
answers
132k
views
Proof a graph is bipartite if and only if it contains no odd cycles
How can we prove that a graph is bipartite if and only if all of its cycles have even order? Also, does this theorem have a common name? I found it in a maths Olympiad toolbox.
- 106k
19
votes
4
answers
18k
views
Combinations of selecting $n$ objects with $k$ different types
Suppose that I am buying cakes for a party. There are $k$ different types and I intend to buy a total of $n$ cakes. How many different combinations of cakes could I possibly bring to the party?
- 9,317
19
votes
2
answers
7k
views
Root of unity filter
Can some one help me understand the technique called "Root of unity filter" . I just know how to use it. It's as follow:
For series $f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n$ we need to find the ...
- 325
18
votes
3
answers
21k
views
Choosing numbers without consecutive numbers.
In how many ways can we choose $r$ numbers from $\{1,2,3,...,n\}$,
In a way where we have no consecutive numbers in the set? (like $1,2$)
- 1,572
13
votes
2
answers
3k
views
In how many ways can we colour $n$ baskets with $r$ colours?
In how many ways can we colour $n$ baskets using up to $r$ colours such that no two consecutive baskets have the same colour and the first and the last baskets also have different colours?
For ...
- 165
6
votes
5
answers
4k
views
Number of solution for $xy +yz + zx = N$
Is there a way to find number of "different" solutions to the equation $xy +yz + zx = N$, given the value of $N$.
Note: $x,y,z$ can have only non-negative values.
- 279
27
votes
4
answers
27k
views
Finding the n-th lexicographic permutation of a string
I have an ordered set of symbols S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. I want to find the 1,000,000-th permutation in lexicographic order of S. It is a programming puzzle, but I wanted to figure out a ...
- 431
21
votes
2
answers
44k
views
Number of ways of choosing $m$ objects with replacement from $n$ objects
There is a set of $n$ distinct objects. How many possible multisets can we get when choosing $m$ objects with replacement? Note that the elements in a set are unordered and distinct, and the elements ...
- 47.7k
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
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
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
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
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
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
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
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
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
9
votes
1
answer
3k
views
Number of $(0,1)$ $m\times n$ matrices with no empty rows or columns
I am looking to calculate the number of $m\times n$ matrices which have no empty rows or columns (at least one $1$ in each row and column).
I have looked at the answers to a few similar questions ...
- 93
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