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.

Filter by
Sorted by
Tagged with
62
votes
6answers
48k views

Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$

I was hoping to find a more "mathematical" proof, instead of proving logically $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$. I already know the logical Proof: $${n \choose k}^2 = {...
11
votes
4answers
2k views

Prove $\sum\limits_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity) [duplicate]

Let $n$ be a nonnegative integer, and $k$ a positive integer. Could someone explain to me why the identity $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ holds?
25
votes
12answers
21k views

Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$

I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$. I suppose I could use the counting rules in probability, perhaps combination= ${{n}...
71
votes
4answers
7k views

Identity for convolution of central binomial coefficients: $\sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$

It's not difficult to show that $$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$ On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...
18
votes
3answers
13k views

I have a problem understanding the proof of Rencontres numbers (Derangements)

I understand the whole concept of Rencontres numbers but I can't understand how to prove this equation $$D_{n,0}=\left[\frac{n!}{e}\right]$$ where $[\cdot]$ denotes the rounding function (i.e., $[x]$...
119
votes
14answers
65k views

Taking Seats on a Plane

This is a neat little problem that I was discussing today with my lab group out at lunch. Not particularly difficult but interesting implications nonetheless Imagine there are a 100 people in line to ...
8
votes
2answers
4k views

extended stars-and-bars problem(where the upper limit of the variable is bounded)

The problem of counting the solutions $(a_1,a_2,\ldots,a_n)$ with integer $a_i\geq0$ for $i\in\{1,2,\ldots,n\}$ such that $$a_1+a_2+a_3+....a_n=N$$ can be solved with a stars-and-bars argument. What ...
4
votes
6answers
2k views

If I roll three dice at the same time, how many ways the sides can sum up to $13$?

If I rolled $3$ dice how many combinations are there that result in sum of dots appeared on those dice be $13$?
9
votes
7answers
6k views

Alternating sum of binomial coefficients: given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

Let $n$ be a positive integer. Prove that \begin{align} \sum_{k=0}^n \left(-1\right)^k \binom{n}{k} = 0 . \end{align} I tried to solve it using induction, but that got me nowhere. I think the ...
56
votes
5answers
18k views

Probability for the length of the longest run in $n$ Bernoulli trials

Suppose a biased coin (probability of head being $p$) was flipped $n$ times. I would like to find the probability that the length of the longest run of heads, say $\ell_n$, exceeds a given number $m$, ...
11
votes
5answers
912 views

What does $\binom{-n}{k}$ mean?

For positive integers $n$ and $k$, what is the meaning of $\binom{-n}{k}$? Specifically, are there any combinatorial interpretations for it? Edit: I just came across Daniel Loeb, Sets with a ...
6
votes
3answers
7k views

Demonstrate another way to solve the Inclusion–exclusion principle?

I'm attempting to solving the Inclusion–exclusion principle, which is generally described as follows... $$\begin{align} \left| \bigcup\limits_{i=1}^n A_i \right| = + \left( \sum\limits_{i=0}^n | ...
20
votes
5answers
5k views

Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$

I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a ...
25
votes
3answers
40k views

How to use stars and bars?

How to use the stars and bars method? Say I want to find number of combinations I can get with $x_1+x_2+x_3+x_4=22$, where $x_i\in\mathbb{N}$. Is this the correct time to apply the method? This is ...
41
votes
4answers
34k views

The generating function for the Fibonacci numbers

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers, i.e., the sequence $\left\{1,1,2,3,5,8,13,21,...\right\}$.
27
votes
7answers
21k views

Making Change for a Dollar (and other number partitioning problems)

I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted ...
17
votes
1answer
7k views

Probability distribution in the coupon collector's problem

I'm trying to solve the well known Coupon Collector's Problem by explicitly finding the probability distribution (so far all the methods I read involve using some sort of trick). However, I'm not ...
26
votes
1answer
9k views

6-letter permutations in MISSISSIPPI

How many 6-letter permutations can be formed using only the letters of the word, MISSISSIPPI? I understand the trivial case where there are no repeating letters in the word (for arranging smaller ...
20
votes
3answers
6k views

Number of permutations of $n$ where no number $i$ is in position $i$

I am trying to figure out how many permutations exist in a set where none of the numbers equal their own position in the set; for example, $3,1,5,2,4$ is an acceptable permutation where $3,1,2,4,5$ is ...
7
votes
5answers
10k views

How to prove Vandermonde's Identity: $\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$?

How can we prove that $$\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}?$$ (Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Probability, 8th ed by Sheldon Ross.
40
votes
8answers
5k views

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$? I know this is well-known. But how to prove it rigorously? Even mathematical induction does not seem so straight-forward. ...
33
votes
3answers
34k views

Calculating the total number of surjective functions

It is quite easy to calculate the total number of functions from a set $X$ with $m$ elements to a set $Y$ with $n$ elements ($n^{m}$), and also the total number of injective functions ($n^{\underline{...
11
votes
5answers
10k views

How to show that this binomial sum satisfies the Fibonacci relation?

The binomial sum $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$ satisfies the Fibonacci relation. I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any hints ...
10
votes
4answers
7k views

Enumerating number of solutions to an equation

How do you find the number of solutions like this? $$x_1 + x_2 + x_3 + x_4 = 32$$ where $0 \le x_i \le 10$. What's the generalized approach for it?
58
votes
5answers
96k views

Number of ways to write n as a sum of k nonnegative integers

How many ways can I write a positive integer $n$ as a sum of $k$ nonnegative integers up to commutativity? For example, I can write $4$ as $0+0+4$, $0+1+3$, $0+2+2$, and $1+1+2$. I know how to find ...
10
votes
4answers
3k views

Combinatorial proof

Using notion of derivative of functions from Taylor formula follow that $$e^x=\sum_{k=0}^{\infty}\frac{x^k}{k!}$$ Is there any elementary combinatorial proof of this formula here is my proof for $x$...
12
votes
2answers
9k views

Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$

I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$ I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
40
votes
1answer
17k views

How to count number of bases and subspaces of a given dimension in a vector space over a finite field? [duplicate]

Let $V_{n}(F)$ be a vector space over the field $F=\mathbb Z_{p}$ with $\dim V_{n} = n$, i.e., the cardinality of $V_{n}(\mathbb Z_{p}) = p^{n}$. What is a general criterion to find the number of ...
39
votes
3answers
7k views

How do I count the subsets of a set whose number of elements is divisible by 3? 4?

Let $S$ be a set of size $n$. There is an easy way to count the number of subsets with an even number of elements. Algebraically, it comes from the fact that $\displaystyle \sum_{k=0}^{n} {n \...
41
votes
4answers
91k views

Number of onto functions

What are the number of onto functions from a set $\Bbb A $ containing m elements to a set $\Bbb B$ containing n elements. I ...
4
votes
6answers
2k views

Number of occurrences of k consecutive 1's in a binary string of length n (containing only 1's and 0's)

Say a sequence $\{X_1, X_2,\ldots ,X_n\}$ is given, where $X_p$ is either one or zero ($0 < p < n$). How can I determine the number of strings, which do contain at least one occurrence of ...
36
votes
7answers
51k views

In how many ways can a number be expressed as a sum of consecutive numbers?

All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example $9$ can be expressed in three such ways, $2+3+4$, $4+5$ or simply $9$. In how many ...
14
votes
5answers
8k views

How do you prove ${n \choose k}$ is maximum when $k$ is $ \lceil \tfrac n2 \rceil$ or $ \lfloor \tfrac n2\rfloor $?

How do you prove $n \choose k$ is maximum when $k$ is $\lceil n/2 \rceil$ or $\lfloor n/2 \rfloor$? This link provides a proof of sorts but it is not satisfying. From what I understand, it focuses on ...
9
votes
5answers
3k views

How many ways can $b$ balls be distributed in $c$ containers with no more than $n$ balls in any given container?

I think there are $\binom{b+ c - 1}{c-1}$ ways to distribute $b$ balls in $c$ containers. (Please correct me if that's a mistake.) How does this change if I am not allowed to place more than $n$ balls ...
12
votes
2answers
3k views

Number of monomials of certain degree

Wikipedia says that the number of different monomials of degree $M$ in $N$ variables is $$\frac{(M+N-1)!}{M!(N-1)!}\; .$$ Can anyone explain why this is true?
11
votes
3answers
3k views

Proof of a combinatorial identity: $\sum\limits_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$ [duplicate]

Possible Duplicate: Identity involving binomial coefficients This was part of a homework assignment that I had, and I couldn't figure it out. Now it is bugging me. Can anyone help me? Although a ...
6
votes
2answers
525 views

Sum of Stirling numbers of both kinds

Let $a_k$ be the number of ways to partition a set of $n$ elements $orderly$,which means that order of subsets matters, but order of elements in each subset does not. My task: Prove, that$$\sum_{k=...
5
votes
2answers
3k views

What is the number of invertible $n\times n$ matrices in $\operatorname{GL}_n(F)$?

$F$ is a finite field of order $q$. What is the size of $\operatorname{GL}_n(F)$ ? I am reading Dummit and Foote "Abstract Algebra". The following formula is given: $(q^n - 1)(q^n - q)\cdots(q^n - ...
19
votes
1answer
2k views

Find the number of arrangements of $k \mbox{ }1'$s, $k \mbox{ }2'$s, $\cdots, k \mbox{ }n'$s - total $kn$ cards.

Find the number of arrangements of $k \mbox{ }1'$s, $k \mbox{ }2'$s, $\cdots, k \mbox{ }n'$s - total $kn$ cards - so that no same numbers appear consecutively. For $k=2$ we can compute it by using ...
9
votes
2answers
6k views

Counting number of moves on a grid

Imagine a two-dimensional grid consisting of 20 points along the x-axis and 10 points along the y-axis. Suppose the origin (0,0) is in the bottom-left corner and the point (20,10) is the top-right ...
3
votes
1answer
1k 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 ...
13
votes
6answers
1k views

Book on combinatorial identities

Do you know any good book that deals extensively with identities obtained using combinatorial and/or probabilistic arguments (e.g., by solving the same combinatorial or probability problem in two ...
13
votes
4answers
27k views

Sum of $k {n \choose k}$ is $n2^{n-1}$

Proof that $\suṃ̣_{k=1}^{n}k {n \choose k}$ for $n \in \mathbb N$ is equal to $n2^{n-1}$. As a hint I got that $k {n \choose k} = n {n-1\choose k-1} $. I tried solving this by induction but, in the ...
16
votes
6answers
10k views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$ I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
1
vote
3answers
639 views

Give a combinatorial proof: $ n(n+1)2^{n-2} = \sum_{k=1}^{n}k^2\binom{n}{k} $

Find a Combinatorial argument for the following binomial identity: $$n(n+1)2^{n-2} = \sum_{k=1}^{n}k^2\binom{n}{k} $$
16
votes
1answer
16k 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 ...
47
votes
2answers
7k 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 ...
8
votes
4answers
589 views

Prove $\binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a}$

I want to prove this equation, $$ \binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a} $$ I thought of proving this equation by prove that you are using different ways to count the same set of ...
5
votes
2answers
3k 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. ...
24
votes
5answers
108k views

Number of ways of distributing n identical objects among r groups

I came across this formula in a list: The number of ways of distributing $n$ identical objects among $r$ groups such that each group can have $0$ or more $(\le n)$ objects I know that standard way ...