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
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