1 Counting

Contents

1 Counting#

How many possible outcomes are there?

Examples#

Given an experiment, counting is the process of determining how many possible outcomes there are.

Example: Dice{exerc}

How many possible outcomes are there when rolling a 6-sided die?

Solution{solution}

There are 6 possible outcomes: {1, 2, 3, 4, 5, 6}.

Example: Coins{example}

How many possible outcomes are there when flipping a coin?

Solution{solution}

There are 2 possible outcomes: {heads, tails}.

Example: Two Coins{example}

How many possible outcomes are there when flipping two coins?

Solution{solution}

There are 4 possible outcomes: {heads, heads}, {heads, tails}, {tails, heads}, {tails, tails}.

Notation{notation}

We will use the following notation for counting:

Given the possible outcomes of an experiment are a set \(A\), we will denote the number of possible outcomes as \(|A|\), where \(|A|\) is the cardinality of the set \(A\).

For example, if the experiment is rolling a die, then the possible outcomes are \(A = \{1, 2, 3, 4, 5, 6\}\) and the number of possible outcomes is \(|A| = 6\).

Step Rule of Counting (aka Product Rule of Counting){rule}

If an experiment \(E\) consists of two independent steps with the outcomes \(A\) and \(B\), then the number of possible outcomes is the product of the number of possible outcomes of each step:

\(|E| = |A| \times |B|\)

Example: Number of Different Images{example}

pixels

How many different images are possible with a 2x2 pixel image, where one pixel can have 17 million different colors?

Solution{solution}

The number of possible outcomes is the product of the number of possible outcomes for each pixel \(|A|\):

\(|E| = |A| \times |A| \times |A| \times |A| = 17,000,000^{4}\)

Example: How many colors are possible for each pixel?{example}

In the above example, we assumed that each pixel can have 17 million different colors. Can you explain this number?

Hint{hint}

Each pixel is made up of 3 color channels: red, green and blue. Each channel can have 256 different values (0-255).

Solution{solution}

The number of possible colors for each pixel is the product of the number of possible values for each channel:

\(|A| = 256 \times 256 \times 256 = 16,777,216\)

Example: How many possible red-values can the red channel of a pixel have?{example}

In the above example, we assumed that each channel can have 256 different values. Can you explain this number?

Hint{hint}

Each channel is made up of 8 bits.

Solution{solution}

Each channel is made up of 8 bits. Each bit has two possible outcomes \({0, 1}\). The number of possible values for each channel is therefore \(2^8 = 256\).

Or Rule of Counting (aka Sum Rule of Counting){rule}

If the outcome of an experiment \(E\) can be either from set \(A\) or set \(B\), then the number of possible outcomes is the number \(|A| \cup |B|\).

In the case that \(A\) and \(B\) are mutually exclusive (i.e. they have no outcomes in common), then the number of possible outcomes is the sum of the number of possible outcomes for each set \(|A| + |B|\).

In general, \(|A \cup B| = |A| + |B| - |A \cap B|\).

Mutually mutually means that \(A \cap B = \emptyset\).

Example{example}

How many bit-strings of length 6 are there, that start with 01 or end with 10?

Solution{solution}

Thera are three cases to consider:

  • The bit-string starts with 01.

  • The bit-string ends with 10.

  • The bit strings starts with 01 and ends with 10.

  • The number of bit-strings that start with 01 is \(2^4 = 16\).

  • The number of bit-strings that end with 10 is \(2^4 = 16\).

  • The number of bit-strings that start with 01 and end with 10 is \(2^2 = 4\).

The number of bit-strings that start with 01 or end with 10 is therefore \(16 + 16 - 4 = 28\).

Contents