Counting I sequence-counting problems bijection all counting problems This is precisely the strategy we'll follow. In particular, we'll get really good at count ing sequences. When we want to determine the size of some other set T, we'll find a bi jection from T to a set of sequences S. Then we'll use our super-ninja sequence-counting skills to determine ISl, which immediately gives us T We'll need to hone this idea omewhat as we go along, but that's pretty much the plan In order to pull this off, we need to clarify some issues concerning sequences and sets Recall that a set is an unordered collection of distinct elements. A set is often represented by listing its elements inside curly-braces. For example, a, b, c is a set, and ic, b, a is another way of writing the same set. On the other hand, a, b, a is not a set, because element a appears twice On the other hand, a sequence is an ordered collection of elements(called components or terms) that are not necessarily distinct. A sequence is often written by listing the terms inside parentheses. For example, (a, b, c)is a sequence, and (c, b, a) is a different sequence Furthermore(a,b, a) is a perfectly valid three-term sequence The distinction between sets and sequences is crucial for everything that follows. If you dont keep the distinction clear in your mind, you re doomed 2 Two Basic Counting rules We'll harvest our first crop of counting problems with two basic rules 2.1 The Sum rule Linus allocates his big sister Lucy a quota of 20 crabby days, 40 irritable days, and 60 generally surly days. On how many days can lucy be out-of-sorts one way or another Let set C be her crabby days I be her irritable days and s be the generally surly. In these terms, the answer to the question is CUIUS]. Now assuming that she is permitted at most one bad quality each day, the size of this union of sets is given by the Sum rule6 Counting I problems sequence−counting S T all counting problems bijection This is precisely the strategy we’ll follow. In particular, we’ll get really good at count￾ing sequences. When we want to determine the size of some other set T, we’ll find a bi￾jection from T to a set of sequences S. Then we’ll use our super­ninja sequence­counting skills to determine |S|, which immediately gives us | | T . We’ll need to hone this idea somewhat as we go along, but that’s pretty much the plan! In order to pull this off, we need to clarify some issues concerning sequences and sets. Recall that a set is an unordered collection of distinct elements. A set is often represented by listing its elements inside curly­braces. For example, {a, b, c} is a set, and {c, b, a} is another way of writing the same set. On the other hand, {a, b, a} is not a set, because element a appears twice. On the other hand, a sequence is an ordered collection of elements (called components or terms) that are not necessarily distinct. A sequence is often written by listing the terms inside parentheses. For example, (a, b, c) is a sequence, and (c, b, a) is a different sequence. Furthermore (a, b, a) is a perfectly valid three­term sequence. The distinction between sets and sequences is crucial for everything that follows. If you don’t keep the distinction clear in your mind, you’re doomed! 2 Two Basic Counting Rules We’ll harvest our first crop of counting problems with two basic rules. 2.1 The Sum Rule Linus allocates his big sister Lucy a quota of 20 crabby days, 40 irritable days, and 60 generally surly days. On how many days can Lucy be out­of­sorts one way or another? Let set C be her crabby days, I be her irritable days, and S be the generally surly. In these terms, the answer to the question is | | C ∪ I ∪ S . Now assuming that she is permitted at most one bad quality each day, the size of this union of sets is given by the Sum Rule: