闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

AMS 301 Finite Mathematical Structures

Exam 3

Question 1 (20 points) Elections are held for class president. There are 4 candidates A, B, C, D and 30 voters (no voter abstains). An outcome is characterized by a 4-tuple (a, b, c, d), where a denotes the number of votes candidate A received, b denotes the number of votes candidate B received, c denotes the number of votes candidate C received,

and d denotes the number of votes candidate D received.

(a) How many election outcomes are there?

(b) State part (a) as a counting problem involving the distribution of objects into boxes. A complete answer is comprised of the following: (i) Are the objects distinct or identical? (ii) Are the boxes distinct or identical? (iii) What do the boxes correspond to? and (iv) What do the balls correspond to?

(c) State part (a) as a counting problem involving the number of non-negative integral solutions to an equation. Don’t forget the constraints!

(d) How many election outcomes are there if some candidate gets a majority of votes?

Question 2 (10 points) How many arrangements of “O,” “P,” “T,” “I,” “M,” “I,” “Z,” “A,” “T,” “I,” “O,” “N” exist such that “O,” “P,” “T” appear in this order, consecutively (as in “ZIMOPTITAON”)?

Question 3 (10 points) Indicate whether each statement is “True” or “False.”

(i) (1 + x)n generates the binomial coeﬃcients (i.e. the coeﬃcients in the expanded form of (1 + x)n are ╱r(n)、. (ii) The number of non-negatve integral solutions of the equation x1 + ● ● ● + xr = n is ╱r+r(n) _ 1、= ╱、. (iii) Consider a set of n distinct objects. The number of ways to select r objects from this set is ╱r+r(n) _ 1、. (iv) The recurrence an = nan _ 1 with initial condition a1 = 1 forms a sequence (an )neN such that an is the number of ways to permute n distinct objects.

(v) All non-negative integral-soultions-of-an-equation counting problems have an equivalent form as a distribution problem in which identical objects are assigned to distinct boxes, and both of these forms have an equivalent form as a selection problem in which objects are selected with repetition from speciﬁed types.

Question 4 (15 points) Consider 5 boxes A, B, C, D, E. How many ways are there to distribute r balls into these boxes such that there are at least 5 As, at least 2 but at most 8 Bs, at most 4 Cs, at most 1 D, and at most 1 F?

(a) State an equivalent non-negative integral-solutions-of-an-equation version of this distribution problem. Don’t forget the constraints!

(b) Build the corresponding generating function. Which coeﬃcient in the generating function’s expansion contains the number of ways to distribute 17 balls subject to the constraints?

Question 5 (15 points) Build a generating function for ar in the following counting problem. Remember to state which coeﬃcient contains the answer (you do not need to calculate the coeﬃcient). How many ways are there to observe a sum of 29 when 8 distinct dice are rolled? Important: To receive full points, you must write the intermediate step in which you consider an equivalent non-negative integral-solutions-of-an-equation.

Question 6 (15 points) Consider a sequence of length n featuring red, blue, and green balls (within each color class, the balls are indistinguishable). Let an be the number of sequences with no red ball immediately to the left of a green ball (i.e. the pattern “red - green” is forbidden).

(a) Write a recurrence for an (you do not need to solve the recurrence).

(b) Write a complete set of initial conditions.

Question 7 (15 points) Suppose we draw an arrangement of n lines in R2 so that every pair of lines intersect, but such that no three lines intersect at a common point (i.e. assume general position). Let bn be the number of intersections in the arrangement.