CSCI 2011 Homework 5
Chapter 8 Problems
Problem 1:
A person is standing at position (0,0) on an n by n grid. If she can only move in steps 1 unit up or 1 unit right, by
how many paths can she reach the position (n,n) for a natural number n? For example, one valid path is n steps up
followed by n steps right. In general, how many paths are there to the point (x,y) with ??, ?? ? N?
Optional Challenge Problem 1
Implement in a programming language of your choice an algorithm to determine whether a string of parentheses is
valid. As well as the string itself, the algorithm should take some representation of a set of left/right parenthesis
types. For instance, this could be a list of pairs of characters, where each pair contains a type of left parenthesis and
the corresponding right parenthesis.
For example, {(}) is poorly formed, but () is well formed. Any concatenation or nesting of well formed paranthesis
strings is well formed.
Optional Challenge Problem 2
How many valid strings of parenthesis of length 2n are there with 3 parenthesis types?
Problem 2:
You have been asked to assemble a two person task force from among your five person team.
a) How many such task forces are possible?
b) What if the task force consists of a designated leader and an assistant?
c) You have been informed that exactly 2 members of your five person team are spies. How many of the task forces
in part a include at least one spy?
d) With the above in mind, you have been given the discretion to pick as many members of your team for the task
force as you would like (instead of exactly two). How many members must the task force include to ensure that at
least one is not a spy?
e) Now consider a 9 person team of 3 hackers, 3 drivers, and 3 operations specialists. What is the smallest N such
that if a task force of N people is chosen from among this group, it includes either at least 2 hackers, or at least 3
drivers, or at least 3 operations specialists?
1
Problem 3:
Assume that ???? =

J???1
??+??
+ ???1
= ??+??+1
.
0??????
??
???1 for ??, ?? ? 1. Prove that for ??, ?? ? 0,
??
??
Problem 4:
How many length n bitstrings include k ones?
Chapter 9 Problems
Problem 5:
Five people are eating at a restaurant. There are five entrees on the menu. Everyone orders an entree. How many
combinations of entrees can be ordered this way? For this problem, it does not matter who gets each entree, only
the entire tableàorder.
Problem 6:
Answer the following, no proof required. You do not need to simplify binomial/multinomial coefficients.
a) How many rearrangements are there of the letters in the word CHANDRIAN?
b) How many rearrangements are there of the letters in the word BEELZEBUB?
c) Expand (2?? + 3??)4
Problem 7:
??+1 ??
Prove that ???, ?? ? N, if ?? ? ?? then ??+1
= ??+1???
??
?? . Give an example of values for n and k (?? < ??) where the
equation does not hold (note that the equation fails when the right hand side is not well defined).

Optional Challenge Problem 3:
The binomial coefficients appear as entries in Pascalàtriangle. Is there any analogous situation for the multinomial
coefficients? For instance, do they appear as entries in another grid of numbers generated by simple rules?
2
I don have an answer in mind for this challenge problem, but would be happy to hear your thoughts!
3

Purchase answer to see full
attachment