21.1.9. Claims About Bad Sequence

Try these first

1. 1.

   What is the total number of valid sequences of 1's and -1's?

   Hint

   Think about how many places you can choose for the 1's.

2. 2.

   Define a bad sequence in your own words.

   Hint

   Consider sequences with parentheses or ladder-like paths.

3. 3.

   What is the formula for Catalan numbers?

   • C(2n
   • n)/(n+1)
   • C(2n
   • n+1)
   • C(n
   • 2n)

   Hint

   Recall the conclusion at the end of our session.

4. 4.

   True or False: Set A is defined to include all legitimate sequences with no restrictions.

   • True
   • False

   Hint

   Think about the restrictions we talked about.

5. 5.

   Given n = 4, find all valid sequences of 1's and -1's, and verify using the Catalan number formula.

   Hint

   Write out the sequences; account for each by ensuring partial sums are valid.

6. 6.

   If the first two positive indices yield a negative sum, demonstrate the reflection method with an example.

   Hint

   Ask yourself how you can visualize the switch in numbers.