EF Addition and subtraction rules

Section 20.2 Addition and subtraction rules

As usual in mathematics, breaking a big problem into smaller parts is a useful strategy.

Theorem 20.2.1. Addition Rule.

Assume

U

is a finite set.

🔗
If $U = A_{1} ⊔ A_{2},$ then $| U | = | A_{1} | + | A_{2} | .$
🔗
If $U = A_{1} \cup A_{2},$ then $| U | = | A_{1} | + | A_{2} | - | A_{1} \cap A_{2} | .$

🔗

Proof idea.

After recalling the definition of disjoint union, Statement 1 should be obvious. To prove Statement 2, apply Statement 1 to the following disjoint unions:

\begin{aligned} U & = A_{1} ⊔ (A_{2} ∖ A_{1}), & A_{2} & = (A_{2} ∖ A_{1}) ⊔ (A_{1} \cap A_{2}) . \end{aligned}

Then combine the resulting equalities of cardinalities.

🔗

Remark 20.2.2.

🔗

Statement 1 of Theorem 20.2.1 can be extended to a disjoint union of any number of subsets.

🔗

Worked Example 20.2.3. Counting by breaking into cases.

🔗

How many words of length

3

or less are there using alphabet

Σ = {α, ω} ?

Solution.

Write

Σ_{\leq 3}^{*}

to mean the set of words in alphabet

Σ

of length

3

or less. Then

Σ_{\leq 3}^{*} = Σ_{0}^{*} ⊔ Σ_{1}^{*} ⊔ Σ_{2}^{*} ⊔ Σ_{3}^{*},

so we can break into cases based on length and then apply the Addition Rule.

Count $Σ_{0}^{*}$ .

There is only one word of length

0 :

the empty word. So

| Σ_{0}^{*} | = 1 .

Count $Σ_{1}^{*}$ .

There are only two words of length

1 :

the single-letter words

w_{α} = α

and

w_{ω} = ω .

| Σ_{1}^{*} | = 2 .

Count $Σ_{2}^{*}$ .

We can count be simply listing the elements:

Σ_{2}^{*} = {α α, α ω, ω α, ω ω} .

| Σ_{2}^{*} | = 4 .

Count $Σ_{3}^{*}$ .

This time we will just use inductive reasoning. Each word in

Σ_{2}^{*}

may be extended to a word in

Σ_{3}^{*}

by appending either an

α

or an

ω

onto the end. So there must be twice as many words in

Σ_{3}^{*}

as in

Σ_{2}^{*},

i.e.

| Σ_{3}^{*} | = 8 .

Total count.

Using the Addition Rule, we obtain the total by adding up our preliminary results:

| Σ_{\leq 3}^{*} | = 1 + 2 + 4 + 8 = 15 .

🔗

Another common strategy in mathematics is to consider the opposite.

🔗

Theorem 20.2.4. Subtraction Rule.

🔗

Assume

U

is a finite set. For every subset

A \subseteq U,

we have

| A | = | U | - | A^{c} | .

🔗

Proof idea.

Since

U = A ⊔ A^{c}

is always true, simply apply Statement 1 of Theorem 20.2.1 to this disjoint union and rearrange to isolate

| A | .

🔗

Example 20.2.5. Counting by counting the complement.

🔗

For alphabet

Σ = {a, b, c, \dots, y, z},

how many words in

Σ_{2}^{*}

do not begin with the letter

a ?

It’s much easier to count the number of words in

Σ_{2}^{*}

that do begin with

a,

as there are only

26

possibilities for the second letter.

🔗

Later in this chapter we will learn a rule that will allow us to easily calculate the total number of words in

Σ_{2}^{*}

to be

26^{2}

(see Worked Example 20.3.10). Accepting this fact for the moment, we can then use the Subtraction Rule to compute

\begin{aligned} # {2 -letter words not beginning with a} & = | Σ_{2}^{*} | - # {2 -letter words beginning with a} \\ = 26^{2} - 26 \\ = 26 (26 - 1) \\ = 26 \cdot 25 . \end{aligned}

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 20.2 Addition and subtraction rules

Theorem 20.2.1. Addition Rule.

Proof idea.

Remark 20.2.2.

Worked Example 20.2.3. Counting by breaking into cases.

Count $Σ_{0}^{*}$ .

Count $Σ_{1}^{*}$ .

Count $Σ_{2}^{*}$ .

Count $Σ_{3}^{*}$ .

Total count.

Theorem 20.2.4. Subtraction Rule.

Proof idea.

Example 20.2.5. Counting by counting the complement.

Section 20.2 Addition and subtraction rules

Theorem 20.2.1. Addition Rule.

Proof idea.

Remark 20.2.2.

Worked Example 20.2.3. Counting by breaking into cases.

Count Σ0∗.

Count Σ1∗.

Count Σ2∗.

Count Σ3∗.

Total count.

Theorem 20.2.4. Subtraction Rule.

Proof idea.

Example 20.2.5. Counting by counting the complement.

Count $Σ_{0}^{*}$ .

Count $Σ_{1}^{*}$ .

Count $Σ_{2}^{*}$ .

Count $Σ_{3}^{*}$ .