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
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
87
votes
9
answers
133k
views
What is the proof that the total number of subsets of a set is $2^n$? [closed]
What is the proof that given a set of $n$ elements there are $2^n$ possible subsets (including the empty-set and the original set).
- 2,783