Combinatorics • Topic 8

Powers of 2

Powers of 2 ( $2^{n}$ ) appear frequently in combinatorics due to their connection with binary choices and subsets.

Subset Counting

Theorem

The number of subsets of a set with

n

elements is

2^{n}

This allows us to identify counting problems with binary strings of length $n$ .

k = 0 \sum n (k n) = (0 n) + (1 n) + \dots + (n n) = 2^{n}

This states that the total number of subsets is the sum of subsets of size 0, size 1, ..., size

n

i = 0 \sum n - 1 2^{i} = 1 + 2 + 4 + \dots + 2^{n - 1} = 2^{n} - 1

In binary:

n 11 \dots 1 = 100 \dots 0 - 1

Exercise (Problem 1)

A "composition" of an integer

n

is a way of writing

n

as a sum of positive integers where order matters. (e.g.,

3 = 2 + 1 = 1 + 2 = 1 + 1 + 1

). Prove there are

2^{n - 1}

compositions of

n

Exercise (Problem 2)

Find the remainder when

2^{100}

is divided by 3.

Exercise (Problem 3)

Determine the number of subsets of

{1, 2, \dots, 10}

that contain at least one odd number.