Solution Total Distributions

I Basic Counting Problems
(a) How many distributions of 100( identical) objects into 12 distinct boxes so each box holds 50 objects?
(
)
Solution Total distributions: 100+121
Number of ways to distribute, with 51 in one of the boxes: 12 49+121
. Hence,
11
12
the final solution:
(
)
(
)
100 + 12 1
49 + 11 1
12
(1)
11
11
(b) How many arrangements of the letters in WWWBARRACKOBAMACOM in which no A is followed immediately by a
W?
Solution Place the non-Ws first. There are 17 letters, 3 of which are W, 4 of which are A.
14!
St. 1 Arr. 14 non-W: 4!(2!)
4
(11+31)
St. 2 Dist. 3 Ws:
3
And since we used staging, we multiply to get:

(
)
14!
11 + 3 1
4!(2!)4
3
(2)
( )
(c) Card-counting. Total number of n-card hands is 52
n
(13)(4)(12)(4)
i. 4-of-a-kind. 1 4 1 1 = 13 1 12 4 = 624
( )(4)5
ii. 0-pairs, i.e. 5 diff values. 13
= 1287 1024 = 1317888
5
1
(d) Counting arrangements of a multiset with a certain property.
i. n items, k types, q1 qk of each type 1 k s.t. n = q1 + qk . Total number of permutations of all n items is
n!
q1 !q2 !qk ! .
ii. Prepeated (n, r) = nr
(
)
iii. Crepeated (n, r) = n+r1
(Recall: this is the placement of Xs and /s)
r
iv. Example Forming repeated 10-combinations with multiset R, B, W s.t.
(
)
A. 5Rs; St.1 pick 5Rs: 5 ways. St.2 select repeated 5-comb from R, B, W = 3+51
= 21 ways
5
B. 5Rs; use 1 stage per number of Rs. St.1 for 1R, St.2 for 2R and so forth.
(e) Counting distributions with a certain property
i. The number of unrestricted dist. of r distinct objects into n distinct boxes is nr .
ii. Number of restricted dist. of r distinct obj. into n dist. boxes, with qi objects in box i for 1 i n, is
r!
q1 !...1n !
II Pidgeonhole Principle
(a) If we distribute r pidgeons into n pidgeon-holes and r > n, then some hole has 2 pidgeons.
(b) Suppose 7 points are placed inside or on the boundary of a 4x3 rectangle. Show some pair of the points are at most 5
apart.
Solution Partition the box into six 1x2 rectangles. Clearly, the diagonal is 5. By the
pidgeonhole principle, we must
have two of the points in the same rectangle, and the pair of points is distance at most 5 apart.
III Summation Problems
n
(1 + x) =
n ( )
n
k=0
xk
( )
n
n!
=
k!(n k)!
k
( ) (
)
n
n
=
k
nk
( )
(
)
n
n n1
=
k
k k1
( ) (
) (
)
n
n1
n1
=
+
k
k
k1
( )( ) ( )(
)
n k
n nl
=
k
l
l
kl
(
)(
)
(
)
r
m
n
m+n
=
k
rk
r
for n, k 0 (factorial representation)

for n k 0 (symmetry)
for n k > 0 (factoring property)
for n > k > 0 (addition formula)
for n k l 0 (product identity)
for m, n, r 0 (vandermonde)
k=0
(a) Determine
Solution
( )( nk )
1 n
k=0 2k k
mk
in closed form
( )(
)
m
nk
1 n
2k k
mk
k=0
(
)(
)
m
m
1 n
=
2k m
k
k=0
( )
(
)
m
n
m 1 k
=
( )
m
k 2
k=0
( )
( )
n
n 1 m
1 m
=
(1 + ) =
( )
2
m
m 2
(3)
product identity
(5)
binomial theorem
IV Basic Generating Function Problems

( )
( )
( )
( )
n
n 2
n r
n n
n
(1 + x) = 1 +
x+
x + +
x +
x
1
2
r
n
( )
n
n mk
(1 xm )n =
(1)k
x
k
k=0
( ) ( )
( )
( )
n
n m
n 2
n mn
=
x +
x m + + (1)n
x
0
1
2
n
1 xn+1
= 1 + x + x2 + + xn
1x
1
= 1 + x + x2 +
1x
)
(
1
n+k1 k
=
x
(1 x)n
k
ex =
enx =
k=0
k=0
k=0
x
(4)
(6)
(7)
(8)
(9)
(finite geomtric series)
(10)
(infinite geomtric series)
(11)
(12)
x0
x1
xk
=
+
+ ...
k!
0!
1!
(13)
xk
(nx)k
=
nk
k!
k!
(14)
k=0
0
e + ex
x
x2
x4
=
+
+
+ ...
2
0!
2!
4!
ex ex
x1
x3
x5
sinhx =
=
+
+
+ ...
2
1!
3!
5!
coshx =
(15)
(16)
(a) Determine the coefficient of x17 in g(x) = (x2 + x3 x4 + x5 )3 (x + x2 + x3 + . . . )

Solution
g(x) = (x2 (1 + x + x2 + x3 ))3 (x(1 + x + x2 . . . ))
7
3 3
(17)
= x (1 + x + x + x ) (1 + x + x . . . )
( 1 x4 )3 1
= x7
1x
1x
= x7 (1 x4 )3 (1 x)4
(18)
finite geometric series
We need the coefficient of x10 in (1 x4 )3 (1 x)4 . This is:

)
( )
( )
(
4+k1 k
3 4
3 8
x
(1 +
x +
x ...)
k
1
2
k=0
(
) ( )(
) ( )(
)
4 + 10 1
3 4+61
3 4+21
+
= 64
10
1
6
2
2
(b) How many r-digit ternary sequences in which the total number of 0s and 1s is even?
Solution. Use cases to count 0s and 1s. (Both even and both odd case.)
ex + ex
2
ex ex
Both odd :
2
2 : ex
Both even :
(19)
(20)
(21)
(22)
2
So, g(x) = ex ( e +e
ex ( e
2r ) +
3 +(1)r
And hence, ar =
.
2
ex 2
)
2
= ex ( e
2x
+2+e2x
)
4
+ ex ( e
2x
2+e2x
)
4
e3x
2
ex
2
r=0 (
3r +(1)r xr
) r! .
2
(c) You roll a fair die 2n times, where n 0 is an integer. What is the probability you roll an even number of 1s?
Solution The number of total outcomes is 62n . Since we want an even number of 1s, assign the indicator polynomial
ex +ex
to the number of 1s, and indicator polynomial ex to each of 2 6. The generating function g(x) is then
2
ex + ex
1
1
= e6x + e4x
2
2
2
1 k xk
1 k xk
=
6
4
+
2
k!
2
k!
g(x) = e5x
k=0
(23)
(24)
k=0
We want the coefficient of k = 2n in g(x). This is:

1 2n
(6 + 42n )
2
(25)
The final probability is then:

1 2n
(6 + 42n )
2
62n
(26)
V Partitions of Integers
(a) List of Theorems
i. (This one is not formally a theorem) It is worth noting that the conjugate of a partition is unique, and that the
conjugate of a conjugate is the original partition.
ii. The number of partitions of n into exactly k parts equals the number of partitions of n with largest part exactly k.
iii. The number of partitions of n into at most k parts equals the number of partitions of n with largest part exactly k.
iv. The number of self-conjugate paritions of n equals the number of partitions of n into distinct, odd parts.
v. The number of partitions of n into distinct parts equals the number of partitions of n into odd parts.
vi. The number of partitions of n into distinct powers of 2 is 1.
(b) Example The generating function for ar , the number of ways to express r as a sum of distinct integers is g(x) =
(1 + x)(1 + x2 )(1 + x3 ) . . . (1 + xk ) . . .
(c) Recall that by the geomtric series
1
1: 1 + x1 + x2 =
1x
1
2: 1 + x2 + x4 =
1 x2
1
3: 1 + x3 + x6 =
1 x3
(d) i. Find the OGF of the number of partitions of n into parts not divisible by 3. The indicator polynomials:
1
1:
1x
1
2:
1 x2
3: 1 (no 3s)
1
4:
1 x4
1
5:
1 x5
6: 1 (no 6s)
The generating function for p(n) is therefore:
1
(1 x)(1
x4 )(1 x5 )
3
6
(1 x )(1 x )(1 x9 )
=
(1 x)(1 x2 )(1 x3 )
( 1 x3k )
=
1 xk
g1 (x) =
(multiply all terms)
x2 )(1
(multiply by all indicator polynomials for multiples of 3)
k=1
ii. Find the OGF for the number of partitions of n in which each part occurs 2 times.
1: 1 + x + x2
3
2: 1 + x2 + x4
3: 1 + x3 + x6
g2 (x) =
1 + xk + x2k
)
(27)
k=1
VI Setting Up Recurrence Relations

(a) Find a recurrence with initial conditions for cn , the number of ways to climb n stairs, if the climber can take 1, 2, or 3
stairs at a time. c3 = 4
Solution The final recurrence relation is:
cn = cn1 + cn2 + cn3
(28)
Where
for n 0 (0 ways to climb 0 or fewer steps)
cn = 0
c1 = 1
c2 = 2
(29)
(30)
(31)
VII Solving Recurrence Relations

(a) Solve
an = 5an1 6an2
a1 = 1, a2 = 5
for n 3
Solution Let g(x) = a1 x + a2 x2 + . . . . Multiply the recurrence through by xn and apply
an xn = 5x
n=3
g(x) a1 x
an1 xn1 6x2
n=3
a2 x2
(32)
(33)
n=3
to get
an2 xn2
(34)
(
)
= 5x g(x) a1 x) 6x2 g(x)
(35)
n=3
(1 5x + 6x )g(x) = x + 5x 5x
x
x
1
1
g(x) =
=
=
2
1 5x + 6x
(1 3x)(1 2x)
1 3x 1 2x
=
(3k 2k )xk
2
(36)
(37)
(38)
k=0
So the coefficient of xn in g(x) = 3n 2n

VIII Fibonacci Identity
IX Inclusion-Exclusion
(a) Let A1 , A2 . . . An U , a finite set. Then the number of elements in U occur in exactly 0 of the subsets is
N (A1 An ) = N (U )
N (Ai ) +
N (Ai Aj )
N (Ai Aj Ak ) + + (1)n N (A1 A2 An ) (39)
i
i,j
i,j,k
(b) How many 5-card hands from a standard deck contain at least one card of each suit?
Solution Let
( )
52
U =all 5-card hands, N (U ) =
5
(40)
A1 =all 5-card hands with no spades

A2 =all 5-card hands with no hearts
(41)
(42)
A3 =all 5-card hands with no diamonds

A4 =all 5-card hands with no clubs
(43)
(44)
We want
N1234 = N
Ni +
Ni,j
i,j
Ni,j,k + Ni,j,k,l
(45)
i,j,k
( )( ) ( )( ) ( )( ) ( )( ) ( )( )
4 52
4 39
4 26
4 13
4 0
=
+
0
5
1
5
2
5
3
5
4 5
(46)
X Snake-oil summation
n ( )
k=0
xk = (1 + x)n
(47)
( )
k k
xn
x =
n
(1 x)n + 1
(48)
k=n
)
(
n+k1 k
1
x =
k
(1 x)n
(49)
k=0
)
(
n+k
k=0
(a)
m ( )(
m
k=0
n
r+k
xk =
1
(1 x)n+1
(50)
(n is the key parameter)
Solution Let f (n) =
m ( )(
m
k=0
n
r+k
, and F (x) =
f (n)xn
n=0
)

m ( )(
m
n
F (x) =
xn
k
r
+
k
n=0 k=0
)
m ( )
(
m
n
F (x) =
xn
k n=0 r + k
k=0
m ( )
m
xr+k
F (x) =
k (1 x)r+k+1
k=0
)k
m ( )(
xr
m
x
F (x) =
(1 x)r+1
k
1x
k=0
(
)
m
x
xr
1
xr
1
+
=
F (x) =
r+1
r+1
(1 x)
1x
(1 x)
(1 x)m
(
(m + r + 1) + k 1)
xr
r
F (x) =
=x
xk
(1 x)m+r+1
k
(51)
trivial summation switch
(52)
by the other theorem
(53)
(54)
this is just the binomial theorem
(55)
(56)
k=0
(57)
The closed form of f (n) is the coefficient of xn in F (x), where n = r + k. So solve for k, then substitute into the
coefficient of xk
(
) (
) (
)
(m + r + 1) + k 1
(m + r + 1) + (n r) 1
m+n
=
=
k
nr
nr

Solution Total Distributions

Uploaded by

Copyright:

Available Formats

Solution Total Distributions

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Solution Total Distributions

Uploaded by

Copyright:

Available Formats

I Basic Counting Problems

And since we used staging, we multiply to get:

for n, k 0 (factorial representation)

IV Basic Generating Function Problems

(infinite geomtric series)

(a) Determine the coefficient of x17 in g(x) = (x2 + x3 x4 + x5 )3 (x + x2 + x3 + . . . )

We need the coefficient of x10 in (1 x4 )3 (1 x)4 . This is:

We want the coefficient of k = 2n in g(x). This is:

The final probability is then:

(multiply all terms)

(multiply by all indicator polynomials for multiples of 3)

VI Setting Up Recurrence Relations

VII Solving Recurrence Relations

Solution Let g(x) = a1 x + a2 x2 + . . . . Multiply the recurrence through by xn and apply

an1 xn1 6x2

So the coefficient of xn in g(x) = 3n 2n

A1 =all 5-card hands with no spades

A3 =all 5-card hands with no diamonds

(n is the key parameter)

Solution Let f (n) =

by the other theorem

You might also like