Discrete Structures
Spring 2014
MP Johnson

Practice Exercises 2

Due: never, but you should do as many as possible! Please don't guess blindly. If you think a given generic answer might be right (i.e., one that with formulas not just numbers), do some experiments--plug in some small numbers and see if it's true in those cases.
  1. All the problems from the two midterms.

    1. Write down the definition of $n \choose k$ and $P(n,k)$.
    2. Now write down these definitions ten more times, and they call up your friends and repeat the definitions over the phone to them ten more times.
    3. What is the difference between these two quantities/concepts? How do they relate to one another?
    4. Now call your friends back and given them a simple made-up example (e.g., "there are $n$ people in the room/running the race/whatever, and for $k$ of them we're going to...") to explain what they're each counting.
    5. Oh, and also given them examples of something that's $2^n$ and something that's $n!$.

    1. Prove (just expand the formulas) that ${n \choose k} = {n \choose {n-k}}$.
    2. Explain in words why this makes sense.

  4. What do these equal?
    1. $n \choose 0$, $n \choose 1$, $n \choose 2$, $n \choose {n-1}$, $n \choose n$
    2. $n!$, ${n!} \over {(n-1)!}$
    3. $3!$, $2!$, $1!$, $0!$
    4. $\sum_{i=0}^n 2^i$, $~\sum_{i=1}^n i$

  5. Verify both of de Morgan's rules using truth tables.

  6. Prove/disprove that your favorite graphs have Hamiltonian paths/cycles, Eulerian paths/cycles, are planar, are isomorphic to one another, etc., etc.

    1. Prove the Handshake Theorem (for unweighted graphs), without induction.
    2. What's the Handshake Theorem?
    3. Given the Handshake Theorem, apply it to a given example, and check that the result's not obviously wrong. (Recall that $2 \cdot 30 \ne 30$.)

  8. Prove by induction that, for all integers n>=1 and real numbers r!=1, $$\sum_{i=0}^n r^i = {{r^{n+1} - 1} \over {r-1}}$$ That is, prove this is true for any particular real number $r!=1$. (Point being, the proof is the same for any such $r$, so the result follows for all such $r$.)

  9. How is the number or, if it can vary, the range (least possible number to largest possible number) of edges in the following graphs on $n$ nodes:
    1. directed graph
    2. an undirected graph
    3. the complete bipartite graph $K_{n}$
    4. the complete bipartite graph $K_{a,b}$
    5. a tree
    6. the path graph $P_n$
    7. the cycle graph $C_n$
    8. the star graph $S_n$ (which is the same as the bipartite graph $K_{1,n}$)

  10. How many colors are needed to color:
    1. the complete bipartite graph $K_{n}$
    2. the complete bipartite graph $K_{a,b}$
    3. a tree
    4. the path graph $P_n$
    5. the cycle graph $C_n$
    6. the star graph $S_n$ (which is the same as the bipartite graph $K_{1,n}$)
    7. the complete bipartite graph $K_{n}$
    8. the complete bipartite graph $K_{a,b}$

    1. How many binary (i.e., base 2: 0/1) strings are there of length $n$? Prove this by induction.
    2. How many ternary (i.e., base 3: 0/1/2) ones?

  12. How many different numbers can be formed by various arrangements of the five digits 1, 1, 1, 2, 3?

    1. How many length-$n$ base-10 strings are there in which it never happens that the same digit appears twice in a row?
    2. How many such length-$n$ binary strings?

    1. How many ways are there to seat 5 different men and five different women at a (non-circular) table with 10 seats?
    2. How many ways if no men may sit next to each other?

    1. How many length-$n$ binary strings are there with exactly $k$ 1s?
    2. How many such ternary strings?

    1. There are 10 red socks, 10 blue socks, and 10 green socks in the dark closet. How many do you need to pull out to be sure that you've got a matching pair?
    2. How many do you need to pull out to ensure that you've got at least one of each color?
    3. There are 10 different pairs of shoes in the dark closest. How many do you have to pull out to ensure you've got two shoes for the same foot (i.e., either at least 2 lefts or at least 2 rights)?
    4. How many do you have to pull to ensure you've got a matching pair?
    5. Thus, how many individual articles of footwear do you need to pull out to ensure you've got a matching pair of socks and a matching pair of shoes?

  17. There are again the 10 socks (so 5 pairs) of each color and 10 pairs of shoes, but now, instead of trying to ensure matches or whatever, we're thinking about how many ways we can do something, i.e., how many different kinds of outcomes can occur when we pull out a certain number.
    1. How many ways are there to pull out 2 shoes?
    2. How many ways are there to pull out 2 socks?
    3. How many ways are there to pull out 2 shoes and 2 socks?