#Practice Final for Math 454(2), Fall 2020, Dr. Z.

Each bunch of problems is with increasing difficulty. Full answers to all parts (a) would be needed to pass the class with a C
(provided that all the homework, attendance quizzes and projects have been submitted).  Parts (b),(c), (d), ... are more challenging.
Some of the (harder) problems may require coding.


YOU CAN USE Maple, of course, the Lectures, Maple code, posted solutions, and more generally the internet, EXCEPT 
you have to do it by yourself, and  EXPLAIN EVERYTHING!

1. (a) In how many ways can you walk from [0,0] to [30,25] where the allowed steps are [1,0] or [0,1]

   (b) In how many ways can you walk from [0,0] to [30,25] where the allowed steps are [1,0] or [0,1]
    and you MUST stay in the region x>=y

   (c) In how many ways can you walk from [0,0] to [30,25] where the allowed steps are [1,0] or [0,1], [1,1], or [2,1]
    and you MUST stay in the region x>=y

   (d) In how many ways can you walk from [0,0] to [30,25] where the allowed steps are [1,0] or [0,1], [1,1], or [2,1]
    and you MUST never visit a vertex [i,j] where BOTH i and j are primes


2. (a) How many words in the alphabet {0,1,3} are there of length 20?

   (b) How many words in the alphabet {1,3,7} are there that add-up to 100?

   (c) How many words are there in the alphabet {1,2,3,....} (all positive integers) that add-up to n? For general n

   (d) How many words are there in the alphabet {1,3,5,7,....} (all ODD positive integers) that add-up to n? For general n

   (e) How many words are there in the alphabet {0,1} of length 67 such that you never have three consecutive ones.

3. (a) Let pi be the permutation of {1,2,..., 100} such that pi[i]=i+1 for i=1.., 99, and pi[100]=1. What is pi^47?

   (b) Define a permutation of {0,1,..., 19} by pi[i]:=i^4 +5*i+1 mod 20. (i) Is it a permutation?
      If it is, how many cycles does it have? What are they?

   (c) How many permutations of {1,2,..., 100} are such that  you NEVER have three places i1, i2, i3, i1<i2<i3 such that
      pi[i1]<pi[i2]<pi[i3]

4. What is the egf (in the variable x) enumerating

   (a) All permutations
  
   (b) Permutations where the only allowed cycle lengths are 2,3,5?

   (c) Permutations where all the cycles-lengths are allowed EXCEPT are 2,3,5?

   (d) Permutations where all the cycles-lengths are allowed EXCEPT are 2,3,5? AND the number of cycles is even.


5. What is the egf (in the variable x) enumerating

 (a) All set-partitions. How many are there of the set {1,2,...,51}?

 (b) All set partitions with an odd number of participants. How many are there of the set {1,2,...,51}?

 (c) All set partitions with any number of participants but each participating set must be of odd size. How many are there of the set {1,2,...,51}?

 (d) All set partitions with and even number of participants and each participant must be of odd size. How many are there of the set {1,2,...,51}?


6. (a) How many labeled graphs are there with 43 vertices?

   (b) How many labeled CONNECTED graphs are there with 43 vertices?

   (c) How many labeled graphs are there with EXACTLY 3 components with 43 vertices?

   (d) How many labeled CONNECTED graphs are there with 76 vertices and 100 edges?

   (e) How many labeled trees are there with 1000 vertices and 1000 edges?


7. (a) How many integer partitions are there of 100?

   (b) How many integer partitions of 100 are there where all the parts are odd?

   (c) How many integer partitions of 100 are there where all the parts are different than each other?

   (d) How many integer partitions of 100 are there where all the parts are different than each other and all the parts are odd.

   (e) How many integer partitions of [p[1],..., p[k]] of 300 are there where you can never have an i between 1 and k-2 such that
       p[i]-p[i-1]=1 and p[i-1]-p[i-2]=2