MATH/CSCI 2113
Assigment 2
Due Wednesday, January 23, at the beginning of class.

For each of the following problems, show your work.

1. Find the successors of the following permutations in a lexicographic ordering: (a) 15432 (b) 54312 (c) 35421.

2. (a) Generate all rearrangements of the word BOOST, in lexicographic order (where letters that come earlier in the alphabet are smallest). (b) Check that the number of rearrangements you found coincides with the formula for the number of rearrangements as learned last week.

3. (a)

   Determine the number of nonnegative integer solutions to the pair of equations:

   
   

   $$\begin{array}{ll} x_1+x_2+x_3 &=6\\ x_1+x_2+x_3+x_4+x_5&=15 \end{array}$$

   
   

   (b)

   How many of these solutions have $x_3\not= 3$? ( Hint: count by complement.)

4. Describe an algorithm which, on input of two integers $k$ and $n$, where $1\leq k\leq n$, generates all subsets of size $k$ of the set $\{ 1,2,3,\dots,n\}$. Give a precise, step-by-step description of your algorithm. You may also use pseudocode.

5. Determine how many integer solutions there are to the equation
   
   $$x_1+x_2+x_3+x_4=19,$$
   
   
   if

   (a)

   $0\leq x_i<8$ for $1\leq i\leq 4$,

   (b)

   $0\leq x_1\leq 5$, $0\leq x_2\leq 6$, $3\leq x_3\leq 7$, $3\leq x_4\leq 8$.

   Hint: use inclusion/exclusion