Prove the following combinatorial identities by formula.
C(n+1, k+1) = C(n, k+1)
+ C(n, k).
C(r, r) + C(r+1, r) +
C(r+2, r) + … + C(n, r) = C(n+1,
r+1). Hint: Use (a), and notice that
C(r, r) + C(r+1, r) = C(r+2,
r+1). The series telescopes.
Using the identity in 4b above, derive a formula for the sum
(1)(2)(3) + (2)(3)(4) + … + (n-2)(n-1)(n).
Hint: Set r = 3.
If you have 2n socks in a drawer, n white and
n black, and you reach in to choose 2 socks at random,
How many ways are there to choose?
How many of these ways result in getting a pair of the same
color?
Write a simple closed form formula in terms of n for
the chance choosing a matching pair of socks from a drawer
with n white and n black socks.
A few short problems:
How many ways are there to choose a president, vice
president, secretary and treasurer from 9 people?
How many ways can 13 identical balls be distributed into 3
distinct boxes?
How many numbers greater than 3,000,000 can be formed from
permutations of 1,2,2,4,6,6,6?
How many nine-digit numbers with twice as many odd digits as
even digits? (leading zeros are allowed, and zeros are
considered even)
How many passwords can be created in the form [A-Z][a-z]^{9}[0,1]^{6}?
(That is, a capital letter followed by 9 lowercase letters
followed by 6 bits).
How many different 7-card Poker hands are there?
How many 7-card poker hands are a flush (all one suit)?
Let A and B be n-bit numbers, each
representing a subset of n elements. For example, if the
elements are {X, Y, Z}, then 000 is the empty set, 111 is the
entire set, and 011, is the subset {Y, Z}. What are the
chances, given two randomly chosen n-bit numbers, that
the first is a subset of the second? Hints: Count
the total pairs of n-bit numbers, one from A and one
from B. Count how many of these pairs have the first set a
subset of the second. You might get a sum involving combinations
and powers of two but the answer can be reduced to something
very simple using the binomial theorem.
How many ways are there to distribute eight balls into six
distinct boxes with at least one ball in each box if:
The balls are identical?
The balls are distinct? Hint: Separate into
disjoint cases and add.
How many ways are there to distribute eight balls into
six distinct boxes with at most four balls combined in the
first two boxes if:
The balls are identical? Hint: Separate into
disjoint cases and add.
The balls are distinct? Hint: Separate into
disjoint cases and add.
Fibonacci in Pascal’s Triangle.
Prove by induction that the nth Fibonacci number F_{n}
equals C(n, 0) + C(n-1, 1) + C(n-2,
2) + … + C(ceiling(n/2), floor (n/2)).
You should assume that F_{0} = F_{1} =
1.
There’s a new screen saver that displays a random rectangular
piece of an n by n checkerboard.
How many rectangles are there in a checkerboard of size 1?
2? 3? 4?
How many squares are there in a checkerboard of size 1? 2?
3? 4?
Guess a general formula for the number of squares and
rectangles. Put each in closed form in terms of n.
Prove your formulas are true.
What’s the chance that the rectangle displayed is a square?
Give a simplified closed form in terms of n.
Although the number of squares and rectangles increase
without bound as n increases, what happens to the
ratio of squares to rectangles?
A password is created with eight characters each of which is
between the letters a and z inclusive. How many different
passwords are possible?
If no duplicate letters are allowed, then how many passwords
are possible?
In each case, if 2,000,000 random attempts are made by a
hacker to guess the password, what’s the chance that he cracks
it?
If it is known that the password is one of the 3,300,000
entries in a list of words and proper names, and again the
hacker tries 2,000,000 random attempts to crack it. What’s the
chance of his success?
Assume one person out of 10,000 is infected with HIV, and
there is a test in which 2.5% of all people test positive for
the virus although they do not really have it. If you test
negative on this test, then you definitely do not have HIV.
What is the chance of having HIV, assuming you test positive
for it?
A round-robin tournament is one where each player plays each
of the other players exactly once. Prove that if no person loses
all his games, then there must be two players with the same
number of wins. (Use pigeonhole principle).
Each of two disks has one megabyte of bits around its
perimeter, half of which are ones and half of which are zeros.
Prove that no matter how the bits are arranged, the disks can be
placed on top of each other, so that half a megabyte of bits
match up. (Hint: Count the total matches as you rotate the top
disk around the bottom, and make a pigeonhole argument).
How many different collections of four integers are there
(duplicates allowed), where each integer is between 2 and 5,
inclusive, and the sum equals 25? (Use
Inclusion/Exclusion).
Three computer tasks A, B, C each with 5 ordered parts:
A1 through A5, B1 through B5, and C1 through C5, are being
multi-tasked by my PC. Each task must execute its parts in order
one through five. Thus A1 B1 B2 C1 C2 C3 C4 B3
A2 etc. is an acceptable order. Assume, that the
choice of which task to work on next is chosen randomly, and
that the next part of that task is then executed. What is
the probability that after all 15 parts are complete, five parts
of at least one task were executed consecutively? (Use
Inclusion/Exclusion).
A password requires that you use a sequence of upper-case
characters, lower-case characters and digits. A valid password
must be at least 10 characters long, and it must contain at
least one character from each of the three sets of characters.
If you generate 10 random characters from the union of the three
sets of characters, what is the probability that you will get a
valid password? (Use Inclusion/Exclusion).
What are the chances that a randomly dealt 13-card hand has at
least one of every suit? (Use Inclusion/Exclusion).