Problem set 1: Basics of Combinatorics
1 Problems for Seminar
The following numbers of flights are available:
- Moscow–New Delhi: 4 flights;
- Moscow–Dubai: 5 flights;
- New Delhi–Sydney: 3 flights;
- Dubai–Sydney: 6 flights.
How many ways are there to get from Moscow to Sydney?
There are 13 people on a pirate ship.
How many ways are there to choose a captain and an assistant?
There are 10 mice in a laboratory. We need to select 5 of them to carry out an experiment.
How many ways are there to choose them?
There are 8 different types of train cars, one of which is a restaurant car.
How many different ways are there to build a train consisting of 6 cars if the restaurant car must be present?
Prove the following identities:
(a)
\[ \binom{n}{k}=\binom{n}{n-k}. \]
(b)
\[ \binom{n}{k}=\binom{n+k-1}{k}. \]
(c)
\[ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}. \]
(d)
\[ \binom{n}{0} + \binom{n}{1} +\cdots+ \binom{n}{n} = 2^n. \]
Suppose there are 1112 cities in Russia.
Aleksey and Andrey each visited half of them, independently of one another.
We know that 14 cities were visited by both Aleksey and Andrey.
How many cities were visited by neither of them?
100 passengers are boarding a plane with 100 seats.
Each passenger has a ticket with a unique seat number.
How many ways are there to seat the passengers so that none of them sits in their assigned seat?
Suppose we have 3 violets, 4 roses, and 5 tulips.
How many ways are there to make a bouquet such that:
(a) All flowers are of the same kind.
(b) The number of flowers of each kind is odd.
(c) There are at least two flowers of different kinds.
Two bouquets are considered identical if and only if they contain the same number of flowers of each kind.
Empty bouquets are not allowed.
How many distinct solutions does the equation
\[ x_1+x_2+\cdots+x_m=n, \]
where \(m\geq 1\) and \(n\in\mathbb{N}\), have:
(a) In nonnegative integers?
(b) In positive integers?
How many six-digit numbers have digits whose sum equals 29?
2 Homework
Prove the following identities:
(a)
\[ \binom{n}{1} + 2\binom{n}{2} +\cdots+ n\binom{n}{n} = n2^{n-1}. \]
(b)
\[ \binom{n}{0}^{2} + \binom{n}{1}^{2} +\cdots+ \binom{n}{n}^{2} = \binom{2n}{n}. \]
(c)
\[ \binom{n+m-1}{n-1} + \binom{n+m-2}{n-1} +\cdots+ \binom{n-1}{n-1} = \binom{n+m}{n}. \]
Use identity (c) to prove that
\[ \sum_{i=1}^{n}i = \frac{n(n+1)}{2} \]
and
\[ \sum_{i=1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6}. \]
How many ways are there to distribute 15 different balls into 5 boxes such that each box contains exactly 3 balls?
Suppose we want to create a password using letters of the English alphabet and digits.
(a) How many passwords of length 8 are possible?
(b) How many passwords of length 8 are possible if at least one digit must be included?
(c) How many passwords of length 8 are possible if at least two characters are identical?
Suppose an alphabet consists exclusively of the following three symbols:
\[ \diamond,\quad \square,\quad \circ. \]
(a) How many words of length 5 can be formed?
(b) How many words of length at most 5 can be formed?
Two friends have collections of distinct coins.
One friend owns 9 coins, while the other owns 7 coins.
How many ways can the two friends exchange two coins?
A store sells roses in 3 different colors.
How many ways are there to arrange a bouquet consisting of 7 roses?
Each of five people independently chooses a number from 1 to 100.
How many possible outcomes are there in which at least two people choose the same number?
Let \(n,k\in\mathbb{N}\) satisfy
\[ 0<k<n-1. \]
Consider all two-element subsets of
\[ [n]=\{1,2,\ldots,n\}. \]
How many of these subsets contain both:
- an element greater than \(k\);
- an element less than \(k\)?
Find the answer using two different counting approaches.
Suppose there are \(n\) black balls and \(n\) white balls, all pairwise distinct.
Count the number of ways to choose a collection of balls such that the number of selected white balls equals the number of selected black balls.
A closed-form expression is required.
In a class of 30 students:
- 20 students speak English;
- 5 students speak Spanish;
- 5 students speak Russian;
- 2 students speak both English and Russian;
- 2 students speak both English and Spanish;
- 1 student speaks both Spanish and Russian;
- 1 student speaks all three languages.
How many students do not speak any of these three languages?
How many ways are there to choose 6 cards from a standard deck of 52 cards such that all four suits are represented among the selected cards?