Counting I For example, let's return to two sets mentioned earlier A=all ways to select a dozen doughnuts when five varieties are available B=all 16-bit sequences with exactly 4 ones Lets consider a particular element of set a: 00000000.00 chocolate lemon-filled sugar Weve depicted each doughnut with a 0 and left a gap between the different varieties Thus, the selection above contains two chocolate doughnuts, no lemon-filled, six sugar, two glazed and two plain. Now let's put a 1 into each of the four gaps 001 1000000100.100 sugar glazed Weve just formed a 16-bit number with exactly 4 ones--an element of B i,. This example suggests a bijection from set A to set B: map a dozen doughnuts consist- of: c chocolate, l lemon-filled, s sugar, g glazed, and p plain to the sequence 010:0 01010 The resulting sequence always has 16 bits and exactly 4 ones, and thus is an element of B. Moreover, the mapping is a bijection; every such bit sequence is mapped to by exactly one order of a dozen doughnuts. Therefore, A=B by the Bijection Rule! This demonstrates the magnifying power of the bijection rule. We managed to prove that two very different sets are actually the same size- even though we dont know exactly how big either one is. But as soon as we figure out the size of one set, we'll immediately know the size of the other. This particular bijection might seem frighteningly ingenious if you,ve not seen it be- fore. But you'll use essentially this same argument over and over and over, and soon you'll consider it boringly routine 1.4 Sequence The Bijection Rule lets us count one thing by counting another. This suggests a general t really good at counting just a few things and then use bijections to count PythonCounting I 5 For example, let’s return to two sets mentioned earlier: A = all ways to select a dozen doughnuts when five varieties are available B = all 16­bit sequences with exactly 4 ones Let’s consider a particular element of set A: 0 0 0 0 0 0 0 0 � 0 0 0 0 ���� ���� � �� ���� ���� chocolate lemon­filled sugar glazed plain We’ve depicted each doughnut with a 0 and left a gap between the different varieties. Thus, the selection above contains two chocolate doughnuts, no lemon­filled, six sugar, two glazed, and two plain. Now let’s put a 1 into each of the four gaps: ���� 1 0 0 0 0 0 0 � 0 0 1 1 0 0 1 0 0 ���� � �� ���� ���� chocolate lemon­filled sugar glazed plain We’ve just formed a 16­bit number with exactly 4 ones— an element of B! This example suggests a bijection from set A to set B: map a dozen doughnuts consist￾ing of: c chocolate, l lemon­filled, s sugar, g glazed, and p plain to the sequence: � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 �� � �� � �� � �� � �� � c l s g p The resulting sequence always has 16 bits and exactly 4 ones, and thus is an element of B. Moreover, the mapping is a bijection; every such bit sequence is mapped to by exactly one order of a dozen doughnuts. Therefore, |A| = | | B by the Bijection Rule! This demonstrates the magnifying power of the bijection rule. We managed to prove that two very different sets are actually the same size— even though we don’t know exactly how big either one is. But as soon as we figure out the size of one set, we’ll immediately know the size of the other. This particular bijection might seem frighteningly ingenious if you’ve not seen it be￾fore. But you’ll use essentially this same argument over and over and over, and soon you’ll consider it boringly routine. 1.4 Sequences The Bijection Rule lets us count one thing by counting another. This suggests a general strategy: get really good at counting just a few things and then use bijections to count everything else: