Combinatorics

Combinatorics #

Counting #

In discrete mathematics, the goal is to count the number of elements in (or the cardinality of) a finite set given a description of the set.

Determining a set’s cardinality often requires exploiting some mathematical structure of the set.

A pizzeria sells 6 different varieties of pizza $\{0,1,2,3,4,5\}$.

How many ways are there to fill an order of 24 slices from the 6 varieties?

The order in which the slices are selected is unimportant; all that matters is the number of each variety in the order after they are chosen.

118755

p=set(range(6))
p

{0, 1, 2, 3, 4, 5}

Definition: Product Rule #

Definition: Product Rule

Let $A_1, A_2, \dotsc, A_n$ be finite sets.

$|\underbrace{A_1 \times A_2 \times \dotsb \times A_n}_{\text{Cartesian product}}| = \underbrace{|A_1| \times |A_2| \times \dotsb \times |A_n|}_{\text{integer multiplication}}$

The product rule provides a way to count sequences. Many sets can be expressed as sets of sequences.

Example

$ \begin{aligned} A &= \{ 0, 1 \} \\ B &= \{ 2, 3 \} \\ C &= \{ 4, 5, 6 \} \\ A \times B \times C &= \, ? \\ \end{aligned} $

$|A \times B \times C| = |A| \times |B| \times |C| = 2 \times 2 \times 3 = 12$

A={0,1}
B={2,3}
C={4,5,6}

list(product(A,B,C))

[(0, 2, 4),
 (0, 2, 5),
 (0, 2, 6),
 (0, 3, 4),
 (0, 3, 5),
 (0, 3, 6),
 (1, 2, 4),
 (1, 2, 5),
 (1, 2, 6),
 (1, 3, 4),
 (1, 3, 5),
 (1, 3, 6)]

If $\Sigma$ is a set of characters, called an alphabet, then $\Sigma^n$ is the set of all strings of length $n$ whose characters come from the set $\Sigma$.

If $\Sigma=\{0,1\}$, then $\Sigma^6$ is the set of all binary strings with $6$ bits.

The string $011101$ is an example of an element in $\Sigma^6$.

The strings $xxyzx$ and $zyyzy$ are examples of strings in the set $\{x,y,z\}^5$.

The product rule is used to determine the number of strings of a given length over a finite alphabet:

$ \begin{aligned} |\Sigma^n| = | \underbrace{\Sigma \times \Sigma \times \dotsb \times \Sigma}_{n\,\text{times}} | = \underbrace{|\Sigma| \times |\Sigma| \times \dotsb \times |\Sigma|}_{n\,\text{times}} = |\Sigma|^n \end{aligned} $

The number of binary strings of length $n$ is $2^n$ since the size of the alphabet is $2=|\{0,1\}|$.

The product rule is used to determine the number of strings in a set when one or more of the characters are restricted.

Example

Let $S$ be the set of binary strings of length $5$ that start and end with $0$.

A string is in the set $S$ if it has the form $0***0$ where each $*$ could be a $0$ or a $1$.

$ |S| =| \{0\} \times \{0,1\} \times \{0,1\} \times \{0,1\} \times \{0\} | =| \{0\} | \times | \{0,1\} | \times | \{0,1\} | \times | \{0,1\} | \times | \{0\} | =1 \times 2 \times 2 \times 2 \times 1 =2^3 =8 $

list(product({0},{0,1},{0,1},{0,1},{0}))

[(0, 0, 0, 0, 0),
 (0, 0, 0, 1, 0),
 (0, 0, 1, 0, 0),
 (0, 0, 1, 1, 0),
 (0, 1, 0, 0, 0),
 (0, 1, 0, 1, 0),
 (0, 1, 1, 0, 0),
 (0, 1, 1, 1, 0)]

Example

How many six bit strings are there?

$ |\{0,1\}^6| =|\{0,1\}|^6 =2^6 =64 $

len(list(product({0,1},repeat=6)))

Example

How many six bit strings are there that begin with $01$?

$ |S| = | \{0\} \times \{1\} \times \{0,1\} \times \{0,1\} \times \{0,1\} \times \{0,1\} | = | \{0\}| \times | \{1\} | \times | \{0,1\} | \times | \{0,1\} | \times | \{0,1\} | \times | \{0,1\} | = 1 \times 1 \times 2 \times 2 \times 2 \times 2 = 2^4 = 16 $

len(list(product({0},{1},{0,1},{0,1},{0,1},{0,1})))

Example

How many strings of length $4$ are there over the alphabet $\{a,b,c\}$?

$ |\{a,b,c\}^4| =|\{a,b,c\}|^4 =3^4 =81 $

len(list(product({'a','b','c'},repeat=4)))

Example

How many strings of length $4$ are there over the alphabet $\{a,b,c\}$ that end with the character $c$?

$ |\{a,b,c\}^3\times\{c\}| =|\{a,b,c\}|^3\times|\{c\}| =3^3 =27 $

len(list(product({'a','b','c'},
                 {'a','b','c'},
                 {'a','b','c'},
                 {'c'})))

Definition: Sum Rule #

Definition: Sum Rule

Let $A_1, A_2, \dotsc, A_n$ be sets.

If the sets are mutually disjoint

$A_i\cap A_j=\emptyset\,\text{for}\,i\ne j$

then

$|A_1 \cup A_2 \cup \dotsb \cup A_n| = |A_1| + |A_2| + \dotsb + |A_n|$

The sum rule is relevant when there are multiple choices but only one selection is made.

Example

Suppose a customer just orders a drink. The customer selects a hot drink or a cold drink. The hot drink selections are coffee, hot cocoa, or tea; and the cold drink selections are milk or orange juice. The total number of choices is $5$: $3$ hot drink choices plus $2$ cold drink choices.

$n=2$ since there are two categories of drinks.

Let $C$ be the set of cold drinks and $H$ be the set of hot drinks.

The fact that $C$ and $H$ are disjoint $C\cap H=\emptyset$ means that none of the drinks is categorized as both a hot drink and a cold drink.

The number of possible drinks is

$ |C\cup H| =|C|+|H| =3+2 =5 $

Example

Consider a system in which a password must be a string of length between $6$ and $8$.

The characters can be any lower case letter or digit.

Let $L$ be the set of all lower case letters and $D$ be the set of digits.

$|L|=26$ and $|D|=10$.

The set of all allowed characters is $C=L\cup D$.

Since $D\cap L=\emptyset$, the sum rule can be applied to find the cardinality of $C$.

$ |C| =|L\cup D| =|L|+|D| =26+10 =36 $

Let $A_j$ denote the strings of length $j$ over the alphabet $C$.

By the product rule, $A_j=36^j$.

$ |A_j| =|\underbrace{A\times A\times...\times A}_{j\,\text{times}}| =\underbrace{|A|\cdot|A|\cdot...\cdot|A|}_{j\,\text{times}} =\underbrace{36\cdot36\cdot...\cdot36}_{j\,\text{times}} =36^j $

Notice that for $j\ne k$, $A_j$ and $A_k$ are disjoint because a string cannot have length $j$ and length $k$ at the same time.

If the user must select a password of length $6$, $7$, or $8$, then the sum rule applies

$ |A_6\cup A_7\cup A_8| =|A_6|+|A_7|+|A_8| =36^6+36^7+36^8 $

L=set(string.ascii_lowercase)
D=set(string.digits)
C=D.union(L)

print(sorted(L))
print(sorted(D))
print(sorted(C))
print(f"{36**6+36**7+36**8:,}")

['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
2,901,650,853,888

Example

A cusomter wants to purchase a laptop and has the option to select three different screen sizes, two different processor speeds, and two different storage types: HDD and SSD.

The HDD option comes in two sizes and the SSD comes in three sizes.

screen size AND processor speed AND storage(hdd OR ssd)

How many different laptop configurations are there?

$ \begin{aligned} \text{screen size}\,\,\, S&=\{14\,\text{in},15\,\text{in},16\,\text{in}\} \\ \text{processor speed}\,\,\, P&=\{2.0\,\text{GHz},2.7\,\text{GHz}\} \\ \text{HDD}\,\,\, h&=\{256\,\text{G hdd},512\,\text{G hdd}\} \\ \text{SSD}\,\,\, s&=\{128\,\text{G ssd},256\,\text{G ssd},512\,\text{G ssd}\} \\ \text{storage}\,\,\, A&=h\cup s \\ |S\times P\times A| &=|S\times P\times(h\cup s)| =|S|\cdot|P|\cdot(|h|+|s|) =3\cdot2\cdot(2+3) =30 \end{aligned} $

S={'14 in','15 in','16 in'}
P={'2.0 GHz','2.7 GHz'}
h={'128 G hdd','256 G hdd','512 G hdd'}
s={'256 G ssd','512 G ssd'}

len(list(product(S,P,h.union(s))))

Example

How many six bit strings are there that begin and end with a $1$ or begins with $00$?

Let $A$ be the set of six bit strings that begin and end with a $1$; $B$ be the set that begins with $00$; and $C$ the union of the two.

$ \begin{aligned} A &=\{1\}\times\{0,1\}^4\times\{1\} \\ |A| &=|\{1\}\times\{0,1\}^4\times\{1\}| =|\{1\}|\cdot|\{0,1\}|^4\cdot|\{1\}| =2^4 =16 \\ B &=\{0\}^2\times\{0,1\}^4 \\ |B| &=|\{0\}^2\times\{0,1\}^4| =|\{0\}|^2\cdot|\{0,1\}|^4 =2^4 =16 \\ C &=A\cup B \\ |C| &=|A\cup B| =|\{1\}\times\{0,1\}^4\times\{1\}\cup\{0\}^2\times\{0,1\}^4| =(|\{1\}|\cdot|\{0,1\}|^4\cdot|\{1\}|)+(|\{0\}|^2\cdot|\{0,1\}|^4) =16+16 =32 \end{aligned} $

A=set(product({1},{0,1},{0,1},{0,1},{0,1},{1}))
B=set(product({0},{0},{0,1},{0,1},{0,1},{0,1}))
C=len(A)+len(B)
C

Example

How many bit strings of length five or six begin with a 1?

$ \begin{aligned} b_5 &=\{1\}\times\{0,1\}^4 \\ |b_5| &=|\{1\}\times\{0,1\}^4| =|\{1\}|\cdot|\{0,1\}|^4 =2^4 =16 \\ b_6 &=\{1\}\times\{0,1\}^5 \\ |b_6| &=|\{1\}\times\{0,1\}^5| =|\{1\}|\cdot|\{0,1\}|^5 =2^5 =32 \\ |b_5\cup b_6| &=|\{1\}\times\{0,1\}^4\cup\{1\}\times\{0,1\}^5| =(|\{1\}|\cdot|\{0,1\}|^4)+(|\{1\}|\cdot|\{0,1\}|^5) =16+32 =48 \end{aligned} $

b5=set(product({1},{0,1},{0,1},{0,1},{0,1}))
b6=set(product({1},{0,1},{0,1},{0,1},{0,1},{0,1}))
len(b5)+len(b6)

Example

For length $n$, how many valid passwords are there if each character in a password is either a digit or a lowercase letter?

$ \begin{aligned} n&=9 &&|A_9| =36^9 \\ n&=10 &&|A_{10}| =36^{10} \\ n&=9\,\text{or}\,17 &&|A_9\cup A_{17}| =|A_9|+|A_{17}| =36^9+36^{17} \\ n&=10\,\text{or}\,15 &&|A_{10}\cup A_{15}| =|A_{10}|+|A_{15}| =36^{10}+36^{15} \\ n&=20\,\text{and cannot start with a digit} &&|L\times A_{19}| =|L|\cdot|A_{19}| =26\cdot36^{19} \\ n&=8\,\text{and cannot start nor end with a digit} &&|L^2\times A_6| =|L|^2\cdot|A_6| =26^2\cdot36^6 \\ n&=10\,\text{or}\,12\,\text{and must start with a digit} &&|(D\times A_{9})\cup(D\times A_{11})| =(|D|\cdot|A_{9}|)+(|D|\cdot|A_{11}|) =10\cdot36^9+10\cdot36^{11} \end{aligned} $

D=set(string.digits)
L=set(string.ascii_lowercase)
C=D.union(L)

for n in [9,10,12,15,17,20]:
  print(f"{'Passwords':<20}{len(C)}^{n:<5}= {len(C)**n:,}")

Passwords           36^9    = 101,559,956,668,416
Passwords           36^10   = 3,656,158,440,062,976
Passwords           36^12   = 4,738,381,338,321,616,896
Passwords           36^15   = 221,073,919,720,733,357,899,776
Passwords           36^17   = 286,511,799,958,070,431,838,109,696
Passwords           36^20   = 13,367,494,538,843,734,067,838,845,976,576

Example

For length $n$, how many valid passwords are there if each character in a password is either a digit, a lowercase letter, or a special character?

$ \begin{aligned} n&=6 &&|A_6| =40^6 \\ n&=7\,\text{or}\,8\,\text{or}\,9 &&|A_7\cup A_8\cup A_9| =|A_7|+|A_8|+|A_9| =40^7+40^8+40^9 \\ n&=7\,\text{or}\,8\,\text{or}\,9\,\text{and the first character cannot be a letter} &&|((D\cup S)\times A_6)\cup((D\cup S)\times A_7)\cup((D\cup S)\times A_8)| =((|D|+|S|)\cdot|A_6|)+((|D|+|S|)\cdot|A_7|)+((|D|+|S|)\cdot|A_8|) =(14\cdot40^6)+(14\cdot40^7)+(14\cdot40^8) =14\cdot(40^6+40^7+40^8) \end{aligned} $

D=set(string.digits)
L=set(string.ascii_lowercase)
S={'*','&','$','#'}
C=D.union(L).union(S)

for n in [6,7,8,9]:
  print(f"{'Passwords':<20}{len(C)}^{n:<5}= {len(C)**n:,}")

Passwords           40^6    = 4,096,000,000
Passwords           40^7    = 163,840,000,000
Passwords           40^8    = 6,553,600,000,000
Passwords           40^9    = 262,144,000,000,000

Definition: Bijection Rule #

Definition: Bijection Rule

Let $S$ and $T$ be two finite sets.

If there is a bijection from $S$ to $T$, then $|S|=|T|$.

One way to approach a difficult counting problem is to show that the cardinality of the set to be counted is equal to the cardinality of a set that is easy to count. The bijection rule says that if there is a bijection from one set to another then the two sets have the same cardinality.

A function $f:S\to T$ is called a bijection iff $f$ has a well-defined inverse. The inverse of a function $f$ that maps the set $S$ to the set $T$ is a function $g$ that maps $T$ to $S$ such that for every $s\in S$ and every $t\in T$, $f(s)=t\iff g(t)=s$. If a function has an inverse, it is denoted by $f^{-1}$.

Claim: the number of subsets of an $n$-element set is equal to the number of length-$n$ bit strings #

Claim: the number of subsets of an $n$-element set is equal to the number of length-$n$ bit strings

Let $X$ be a set of $n$ elements so that $|X|=n$.

$f:\mathcal{P}(X)\to\{0,1\}^n\implies|\mathcal{P}(X)|=|\{0,1\}^n|$

Formally

Order the elements of $X$ in some way: $x_1,x_2,...,x_n$; the order is arbitrary, but once selected, be consistent about it.

For each $Y\subseteq X,f(Y)$ is an arbitrary n-bit string $y$ whose bits are $y_1y_2...y_n$.

The string $y$ is defined by the rule $y_i=1$ if $x_i\in Y$ otherwise $y_i=0$.

The inverse of $f$ maps binary strings of length $n$ back to subsets of $X$.

$f^{-1}(y)$ is a subset $Y$ of $X$ such that $x_i\in Y$ if $y_i=1$ otherwise $x_i\not\in Y$.

For every $Y\subseteq X$ and every $y\in\{0,1\}^n$, $f(Y)=y\iff f^{-1}(y)=Y$.

Example

$ \begin{aligned} X&=\{a,b,c\} \\ |X|&=3 \\ \mathcal{P}(X) &=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\} \\ |\mathcal{P}(X)| &=|\{0,1\}^3| =|\{0,1\}|^3 =2^3=8 \end{aligned} $

X='abc'
P=list(powerset(X))
P

[(),
 ('a',),
 ('b',),
 ('c',),
 ('a', 'b'),
 ('a', 'c'),
 ('b', 'c'),
 ('a', 'b', 'c')]

for p in P:
  z=np.array(['0']*len(X))
  z[[X.index(i) for i in p]]=1
  print(''.join(z))

Definition: $k$-to-$1$ Correspondence #

Definition: $k$-to-$1$ Correspondence

Let $X$ and $Y$ be finite sets.

The function $f:X\to Y$ is a $k$-to-$1$ correspondence if for every $y\in Y$ there are exactly $k$ different $x\in X$ such that $f(x)=y$.

Definition: $k$-to-$1$ Rule #

Definition: $k$-to-$1$ Rule

Suppose that there is a $k$-to-$1$ correspondence from a finite set $A$ to a finite set $B$.

Then $\begin{aligned}|B|=\frac{|A|}{k}\end{aligned}$.

Another word for a bijection is a $1$-to-$1$ correspondence, so a bijection is a $k$-to-$1$ correspondence with $k=1$.

The $k$-to-$1$ rule uses a $k$-to-$1$ correspondence to count the number of elements in the range by counting the number of elements in the domain and dividing by $k$.

Example

A group of kids at a slumber party all leave their shoes in a big pile by the door. One way to count the number of kids at the party is to count the number of shoes and divide by $2$. Of course, it is important to establish that each kid has exactly one pair of shoes in the pile. Counting kids by counting shoes and dividing by $2$ is an example of the $k$-to-$1$ rule with $k=2$. Applying the $k$-to-$1$ rule requires a well-defined function from objects we can count to objects we would like to count. In this example, the function maps each shoe to the kid who owns it.

Example

Find a function from the set $X=\{1,2,...,30\}$ to $Y=\{1,2,...,10\}$ that is a $3$-to-$1$ correspondence.

$ f:X\to Y $

$ \begin{aligned} f(x)=\left\lceil\frac{x}{3}\right\rceil \end{aligned} $

$ \begin{aligned} |Y| =\frac{|X|}{3} =\frac{30}{3} =10 \end{aligned} $

for x in range(1,31):
  print(f"{'x = '}{x:<5}{'y = '}{int(np.ceil(x/3))}")

x = 1    y = 1
x = 2    y = 1
x = 3    y = 1
x = 4    y = 2
x = 5    y = 2
x = 6    y = 2
x = 7    y = 3
x = 8    y = 3
x = 9    y = 3
x = 10   y = 4
x = 11   y = 4
x = 12   y = 4
x = 13   y = 5
x = 14   y = 5
x = 15   y = 5
x = 16   y = 6
x = 17   y = 6
x = 18   y = 6
x = 19   y = 7
x = 20   y = 7
x = 21   y = 7
x = 22   y = 8
x = 23   y = 8
x = 24   y = 8
x = 25   y = 9
x = 26   y = 9
x = 27   y = 9
x = 28   y = 10
x = 29   y = 10
x = 30   y = 10

Example

If $x$ is a string then $x^R$ is the reverse of the string.

For example, if $x=1011$ then $x^R=1101$.

A string is a palindrome if the string is the same backwards and forwards; in other words, if $x=x^R$.

Let $B=\{0,1\}$.

The set $B^n$ is the set of all $n$-bit strings.

Let $P_n$ be the set of all strings in $B^n$ that are palindromes.

(i) Show a bijection between $P_6$ and $B^3$.

$ f:B^3\to P_6 $

$ f(x)=x+x^R $

(ii) What is $|P_6|$?

$ \begin{aligned} |P_6| =\frac{|B^3|}{1} =8 \end{aligned} $

(iii) Determine the cardinality of $P_7$ by showing a bijection between $P_7$ and $B^n$ for some $n$.

$ f:B^4\to P_7 $

$ f(x)=x+x^R[1:] $

$ \begin{aligned} |P_7| =\frac{|B^4|}{1} =16 \end{aligned} $

B =set('01')
n =3
Bn={''.join(c) for c in set(product(B,repeat=n))}
Pn={b+b[::-1] for b in Bn}
Pn

{'000000',
 '001100',
 '010010',
 '011110',
 '100001',
 '101101',
 '110011',
 '111111'}

B =set('01')
n =4
Bn={''.join(c) for c in set(product(B,repeat=n))}
Pn={b+b[2::-1] for b in Bn}
Pn

{'0000000',
 '0001000',
 '0010100',
 '0011100',
 '0100010',
 '0101010',
 '0110110',
 '0111110',
 '1000001',
 '1001001',
 '1010101',
 '1011101',
 '1100011',
 '1101011',
 '1110111',
 '1111111'}

Example

Let $B=\{0,1\}$.

$B^n$ is the set of binary strings with $n$ bits.

Define the set $E_n$ to be the set of binary strings with $n$ bits that have an even number of 1s.

Note that zero is an even number, so a string with zero 1s has an even number of 1s.

(i) Show a bijection between $B^9$ and $E_{10}$. Explain why your function is a bijection.

$ f:B^9\to E_{10} $

$ \begin{aligned} \mathbf{x}&=x_1x_2...x_n \\ f(\mathbf{x}) &=x_1x_2...x_nx_{n+1} \,\,\,\text{where}\,\,\, x_{n+1}=\left(\sum_{i=1}^nx_i\right)\mod2 \end{aligned} $

(ii) What is $|E_{10}|$?

$ \begin{aligned} |E_{10}| =\frac{|B^9|}{1} =512 \end{aligned} $

B =set('01')
n =9
Bn={''.join(c) for c in set(product(B,repeat=n))}
Bn_arr=np.array(list(list(codeword) for codeword in sorted(Bn)),dtype=np.int8)
En={''.join(codeword) for codeword in np.concatenate([Bn_arr,(Bn_arr.sum(axis=1)%2).reshape((Bn_arr.shape[0],1))],axis=1).astype(str)}
En

{'0000000000',
 '0000000011',
 '0000000101',
 '0000000110',
 '0000001001',
 '0000001010',
 '0000001100',
 '0000001111',
 '0000010001',
 '0000010010',
 '0000010100',
 '0000010111',
 '0000011000',
 '0000011011',
 '0000011101',
 '0000011110',
 '0000100001',
 '0000100010',
 '0000100100',
 '0000100111',
 '0000101000',
 '0000101011',
 '0000101101',
 '0000101110',
 '0000110000',
 '0000110011',
 '0000110101',
 '0000110110',
 '0000111001',
 '0000111010',
 '0000111100',
 '0000111111',
 '0001000001',
 '0001000010',
 '0001000100',
 '0001000111',
 '0001001000',
 '0001001011',
 '0001001101',
 '0001001110',
 '0001010000',
 '0001010011',
 '0001010101',
 '0001010110',
 '0001011001',
 '0001011010',
 '0001011100',
 '0001011111',
 '0001100000',
 '0001100011',
 '0001100101',
 '0001100110',
 '0001101001',
 '0001101010',
 '0001101100',
 '0001101111',
 '0001110001',
 '0001110010',
 '0001110100',
 '0001110111',
 '0001111000',
 '0001111011',
 '0001111101',
 '0001111110',
 '0010000001',
 '0010000010',
 '0010000100',
 '0010000111',
 '0010001000',
 '0010001011',
 '0010001101',
 '0010001110',
 '0010010000',
 '0010010011',
 '0010010101',
 '0010010110',
 '0010011001',
 '0010011010',
 '0010011100',
 '0010011111',
 '0010100000',
 '0010100011',
 '0010100101',
 '0010100110',
 '0010101001',
 '0010101010',
 '0010101100',
 '0010101111',
 '0010110001',
 '0010110010',
 '0010110100',
 '0010110111',
 '0010111000',
 '0010111011',
 '0010111101',
 '0010111110',
 '0011000000',
 '0011000011',
 '0011000101',
 '0011000110',
 '0011001001',
 '0011001010',
 '0011001100',
 '0011001111',
 '0011010001',
 '0011010010',
 '0011010100',
 '0011010111',
 '0011011000',
 '0011011011',
 '0011011101',
 '0011011110',
 '0011100001',
 '0011100010',
 '0011100100',
 '0011100111',
 '0011101000',
 '0011101011',
 '0011101101',
 '0011101110',
 '0011110000',
 '0011110011',
 '0011110101',
 '0011110110',
 '0011111001',
 '0011111010',
 '0011111100',
 '0011111111',
 '0100000001',
 '0100000010',
 '0100000100',
 '0100000111',
 '0100001000',
 '0100001011',
 '0100001101',
 '0100001110',
 '0100010000',
 '0100010011',
 '0100010101',
 '0100010110',
 '0100011001',
 '0100011010',
 '0100011100',
 '0100011111',
 '0100100000',
 '0100100011',
 '0100100101',
 '0100100110',
 '0100101001',
 '0100101010',
 '0100101100',
 '0100101111',
 '0100110001',
 '0100110010',
 '0100110100',
 '0100110111',
 '0100111000',
 '0100111011',
 '0100111101',
 '0100111110',
 '0101000000',
 '0101000011',
 '0101000101',
 '0101000110',
 '0101001001',
 '0101001010',
 '0101001100',
 '0101001111',
 '0101010001',
 '0101010010',
 '0101010100',
 '0101010111',
 '0101011000',
 '0101011011',
 '0101011101',
 '0101011110',
 '0101100001',
 '0101100010',
 '0101100100',
 '0101100111',
 '0101101000',
 '0101101011',
 '0101101101',
 '0101101110',
 '0101110000',
 '0101110011',
 '0101110101',
 '0101110110',
 '0101111001',
 '0101111010',
 '0101111100',
 '0101111111',
 '0110000000',
 '0110000011',
 '0110000101',
 '0110000110',
 '0110001001',
 '0110001010',
 '0110001100',
 '0110001111',
 '0110010001',
 '0110010010',
 '0110010100',
 '0110010111',
 '0110011000',
 '0110011011',
 '0110011101',
 '0110011110',
 '0110100001',
 '0110100010',
 '0110100100',
 '0110100111',
 '0110101000',
 '0110101011',
 '0110101101',
 '0110101110',
 '0110110000',
 '0110110011',
 '0110110101',
 '0110110110',
 '0110111001',
 '0110111010',
 '0110111100',
 '0110111111',
 '0111000001',
 '0111000010',
 '0111000100',
 '0111000111',
 '0111001000',
 '0111001011',
 '0111001101',
 '0111001110',
 '0111010000',
 '0111010011',
 '0111010101',
 '0111010110',
 '0111011001',
 '0111011010',
 '0111011100',
 '0111011111',
 '0111100000',
 '0111100011',
 '0111100101',
 '0111100110',
 '0111101001',
 '0111101010',
 '0111101100',
 '0111101111',
 '0111110001',
 '0111110010',
 '0111110100',
 '0111110111',
 '0111111000',
 '0111111011',
 '0111111101',
 '0111111110',
 '1000000001',
 '1000000010',
 '1000000100',
 '1000000111',
 '1000001000',
 '1000001011',
 '1000001101',
 '1000001110',
 '1000010000',
 '1000010011',
 '1000010101',
 '1000010110',
 '1000011001',
 '1000011010',
 '1000011100',
 '1000011111',
 '1000100000',
 '1000100011',
 '1000100101',
 '1000100110',
 '1000101001',
 '1000101010',
 '1000101100',
 '1000101111',
 '1000110001',
 '1000110010',
 '1000110100',
 '1000110111',
 '1000111000',
 '1000111011',
 '1000111101',
 '1000111110',
 '1001000000',
 '1001000011',
 '1001000101',
 '1001000110',
 '1001001001',
 '1001001010',
 '1001001100',
 '1001001111',
 '1001010001',
 '1001010010',
 '1001010100',
 '1001010111',
 '1001011000',
 '1001011011',
 '1001011101',
 '1001011110',
 '1001100001',
 '1001100010',
 '1001100100',
 '1001100111',
 '1001101000',
 '1001101011',
 '1001101101',
 '1001101110',
 '1001110000',
 '1001110011',
 '1001110101',
 '1001110110',
 '1001111001',
 '1001111010',
 '1001111100',
 '1001111111',
 '1010000000',
 '1010000011',
 '1010000101',
 '1010000110',
 '1010001001',
 '1010001010',
 '1010001100',
 '1010001111',
 '1010010001',
 '1010010010',
 '1010010100',
 '1010010111',
 '1010011000',
 '1010011011',
 '1010011101',
 '1010011110',
 '1010100001',
 '1010100010',
 '1010100100',
 '1010100111',
 '1010101000',
 '1010101011',
 '1010101101',
 '1010101110',
 '1010110000',
 '1010110011',
 '1010110101',
 '1010110110',
 '1010111001',
 '1010111010',
 '1010111100',
 '1010111111',
 '1011000001',
 '1011000010',
 '1011000100',
 '1011000111',
 '1011001000',
 '1011001011',
 '1011001101',
 '1011001110',
 '1011010000',
 '1011010011',
 '1011010101',
 '1011010110',
 '1011011001',
 '1011011010',
 '1011011100',
 '1011011111',
 '1011100000',
 '1011100011',
 '1011100101',
 '1011100110',
 '1011101001',
 '1011101010',
 '1011101100',
 '1011101111',
 '1011110001',
 '1011110010',
 '1011110100',
 '1011110111',
 '1011111000',
 '1011111011',
 '1011111101',
 '1011111110',
 '1100000000',
 '1100000011',
 '1100000101',
 '1100000110',
 '1100001001',
 '1100001010',
 '1100001100',
 '1100001111',
 '1100010001',
 '1100010010',
 '1100010100',
 '1100010111',
 '1100011000',
 '1100011011',
 '1100011101',
 '1100011110',
 '1100100001',
 '1100100010',
 '1100100100',
 '1100100111',
 '1100101000',
 '1100101011',
 '1100101101',
 '1100101110',
 '1100110000',
 '1100110011',
 '1100110101',
 '1100110110',
 '1100111001',
 '1100111010',
 '1100111100',
 '1100111111',
 '1101000001',
 '1101000010',
 '1101000100',
 '1101000111',
 '1101001000',
 '1101001011',
 '1101001101',
 '1101001110',
 '1101010000',
 '1101010011',
 '1101010101',
 '1101010110',
 '1101011001',
 '1101011010',
 '1101011100',
 '1101011111',
 '1101100000',
 '1101100011',
 '1101100101',
 '1101100110',
 '1101101001',
 '1101101010',
 '1101101100',
 '1101101111',
 '1101110001',
 '1101110010',
 '1101110100',
 '1101110111',
 '1101111000',
 '1101111011',
 '1101111101',
 '1101111110',
 '1110000001',
 '1110000010',
 '1110000100',
 '1110000111',
 '1110001000',
 '1110001011',
 '1110001101',
 '1110001110',
 '1110010000',
 '1110010011',
 '1110010101',
 '1110010110',
 '1110011001',
 '1110011010',
 '1110011100',
 '1110011111',
 '1110100000',
 '1110100011',
 '1110100101',
 '1110100110',
 '1110101001',
 '1110101010',
 '1110101100',
 '1110101111',
 '1110110001',
 '1110110010',
 '1110110100',
 '1110110111',
 '1110111000',
 '1110111011',
 '1110111101',
 '1110111110',
 '1111000000',
 '1111000011',
 '1111000101',
 '1111000110',
 '1111001001',
 '1111001010',
 '1111001100',
 '1111001111',
 '1111010001',
 '1111010010',
 '1111010100',
 '1111010111',
 '1111011000',
 '1111011011',
 '1111011101',
 '1111011110',
 '1111100001',
 '1111100010',
 '1111100100',
 '1111100111',
 '1111101000',
 '1111101011',
 '1111101101',
 '1111101110',
 '1111110000',
 '1111110011',
 '1111110101',
 '1111110110',
 '1111111001',
 '1111111010',
 '1111111100',
 '1111111111'}

Example

Let $T=\{0,1,2\}$.

A string $x\in T^n$ is said to be balanced if the sum of the digits is an integer multiple of $3$.

(i) Show a bijection between the set of strings in $T^6$ that are balanced and $T^5$. Explain why your function is a bijection.

$ f:T^5\to T^6_\text{balanced} $

(ii) How many strings in $T^6$ are balanced?

$ \begin{aligned} |T^6_\text{balanced}| =\frac{|T^5|}{1} =243 \end{aligned} $

T  =set('012')
n  =6
T5 ={''.join(c) for c in set(product(T,repeat=n-1))}
T5_arr=np.array(list(list(codeword) for codeword in sorted(T5)),dtype=np.int8)
T6b={''.join(codeword) for codeword in np.concatenate([T5_arr,((3-T5_arr.sum(axis=1))%3).reshape((T5_arr.shape[0],1))],axis=1).astype(str)}
T6b

{'000000',
 '000012',
 '000021',
 '000102',
 '000111',
 '000120',
 '000201',
 '000210',
 '000222',
 '001002',
 '001011',
 '001020',
 '001101',
 '001110',
 '001122',
 '001200',
 '001212',
 '001221',
 '002001',
 '002010',
 '002022',
 '002100',
 '002112',
 '002121',
 '002202',
 '002211',
 '002220',
 '010002',
 '010011',
 '010020',
 '010101',
 '010110',
 '010122',
 '010200',
 '010212',
 '010221',
 '011001',
 '011010',
 '011022',
 '011100',
 '011112',
 '011121',
 '011202',
 '011211',
 '011220',
 '012000',
 '012012',
 '012021',
 '012102',
 '012111',
 '012120',
 '012201',
 '012210',
 '012222',
 '020001',
 '020010',
 '020022',
 '020100',
 '020112',
 '020121',
 '020202',
 '020211',
 '020220',
 '021000',
 '021012',
 '021021',
 '021102',
 '021111',
 '021120',
 '021201',
 '021210',
 '021222',
 '022002',
 '022011',
 '022020',
 '022101',
 '022110',
 '022122',
 '022200',
 '022212',
 '022221',
 '100002',
 '100011',
 '100020',
 '100101',
 '100110',
 '100122',
 '100200',
 '100212',
 '100221',
 '101001',
 '101010',
 '101022',
 '101100',
 '101112',
 '101121',
 '101202',
 '101211',
 '101220',
 '102000',
 '102012',
 '102021',
 '102102',
 '102111',
 '102120',
 '102201',
 '102210',
 '102222',
 '110001',
 '110010',
 '110022',
 '110100',
 '110112',
 '110121',
 '110202',
 '110211',
 '110220',
 '111000',
 '111012',
 '111021',
 '111102',
 '111111',
 '111120',
 '111201',
 '111210',
 '111222',
 '112002',
 '112011',
 '112020',
 '112101',
 '112110',
 '112122',
 '112200',
 '112212',
 '112221',
 '120000',
 '120012',
 '120021',
 '120102',
 '120111',
 '120120',
 '120201',
 '120210',
 '120222',
 '121002',
 '121011',
 '121020',
 '121101',
 '121110',
 '121122',
 '121200',
 '121212',
 '121221',
 '122001',
 '122010',
 '122022',
 '122100',
 '122112',
 '122121',
 '122202',
 '122211',
 '122220',
 '200001',
 '200010',
 '200022',
 '200100',
 '200112',
 '200121',
 '200202',
 '200211',
 '200220',
 '201000',
 '201012',
 '201021',
 '201102',
 '201111',
 '201120',
 '201201',
 '201210',
 '201222',
 '202002',
 '202011',
 '202020',
 '202101',
 '202110',
 '202122',
 '202200',
 '202212',
 '202221',
 '210000',
 '210012',
 '210021',
 '210102',
 '210111',
 '210120',
 '210201',
 '210210',
 '210222',
 '211002',
 '211011',
 '211020',
 '211101',
 '211110',
 '211122',
 '211200',
 '211212',
 '211221',
 '212001',
 '212010',
 '212022',
 '212100',
 '212112',
 '212121',
 '212202',
 '212211',
 '212220',
 '220002',
 '220011',
 '220020',
 '220101',
 '220110',
 '220122',
 '220200',
 '220212',
 '220221',
 '221001',
 '221010',
 '221022',
 '221100',
 '221112',
 '221121',
 '221202',
 '221211',
 '221220',
 '222000',
 '222012',
 '222021',
 '222102',
 '222111',
 '222120',
 '222201',
 '222210',
 '222222'}

Definition: Generalized Product Rule #

Consider a race with $20$ runners. There is a first place, a second place, and a third place trophy. An outcome of the race is defined to be who wins each of the three trophies. How many outcomes are possible? All $20$ of the runners are eligible to win the first place trophy. Once the first place runner is determined, there are $19$ possibilities left for the second place trophy (since no one can place both first and second). Once the top two runners are determined, there are $18$ possibilities for the third place trophy. The number of possibilities for the outcome of the race is $20\cdot19\cdot18=6840$. This example illustrates that a useful way to think about counting is to imagine selecting an element from the set to be counted. The selection process is carried out in a sequence of steps. In each step, one more decision is made about the item that will be selected. At the end of the process the item to be selected is fully specified. The generalized product rule says that in selecting an item from a set, if the number of choices at each step does not depend on previous choices made, then the number of items in the set is the product of the number of choices in each step.

Definition: Generalized Product Rule

Consider a set $S$ of sequences of $k$ items.

Suppose that there are $n_1$ choices for the first item. For every possible choice for the first item, there are $n_2$ choices for the second item. For every possible choice for the first and second items, there are $n_3$ choices for the third item. For every possible choice for the first $k-1$ items, there are $n_k$ choices for the $k$-th item. Then

$|S| = n_1 \times n_2 \times \dotsb \times n_k$

Example

A family of four (two parents, two kids) goes on a hiking trip.

The trail is narrow and they must walk single file.

How many ways can they walk with a parent in the front and a parent in the back?

The desired sequence is (parent, child, child, parent).

The first person in the sequence can be one or the other parent: two choices.

$2$

For each choice for the first person, there are two choices for the second person, one or the other kid.

$2\cdot2$

If the second person is the first kid, then the third person must be the second kid, and vice versa. Only one choice exists for the third person.

$2\cdot2\cdot1$

The last person must be the parent who was not chosen to be the first person. Only one choice exists for the fourth person.

$2\cdot2\cdot1\cdot1=4$

Example

Suppose that there are three people in a startup.

They rent an office space with eight offices and four desks, anticipating growth.

Each person can select an office and a desk.

The selection is done in the order that the participants joined the company with the founder going first.

How many ways are there for the selection to be done?

First, the founder has a choice of eight different offices and four different desks $8\cdot4$ (via the product rule).

Next, the first employee has a choice of seven different offices and three different desks $7\cdot3$.

Finally, the second employee has a choice of six different offices and two different desks $6\cdot2$.

The number of possible selections is

$(8\cdot4)\cdot(7\cdot3)\cdot(6\cdot2)=8064$

Example

A club with $10$ students elects a president, vice president, secretary, and treasurer, and no student can hold more than one position.

(i) How many ways are there to select the class officers?

$ 10\cdot9\cdot8\cdot7=5040 $

(ii) Suppose that there are five girls and five boys in the club. How many ways are there to elect the officers if the president is a girl?

$ 5\cdot9\cdot8\cdot7=2520 $

(iii) Suppose that there are five girls and five boys in the club. How many ways are there to elect the officers if the president is a girl and the vice president is a boy?

$ 5\cdot5\cdot8\cdot7=1400 $

Example

$ \begin{aligned} D&=\{0,1,2,3,4,5,6,7,8,9\} \\ L&=\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z\} \\ S&=\{*,\&,\$,\#\} \end{aligned} $

How many passwords of length $6$ are there given the following constraints?

(i) no repeated characters

$40\cdot39\cdot38\cdot37\cdot36\cdot35=2,763,633,600$

(ii) no repeated characters and the first character cannot be a special character

$36\cdot39\cdot38\cdot37\cdot36\cdot35=2,487,270,240$

Example

How many strings are there over the set $\{a,b,c\}$ that have length $10$ in which no two consecutive characters are the same?

For example, the string $abcbcbabcb$ would count and the strings $abbbcbabcb$ and $aacbcbabcb$ would not count.

$ 3\cdot2^9=1536 $

Example

License plate numbers in a certain state consists of seven characters; the first character is a digit; the next four characters are capital letters; and the last two characters are digits.

(i) How many different license plate numbers are possible?

$ 10^3\cdot26^4=456,976,000 $

(ii) How many different license plate numbers are possible if no digit can appear more than once?

$ 10\cdot26^4\cdot9\cdot8=329,022,720 $

(iii) How many different license plate numbers are possible if no digit or letter can appear more than once?

$ 10\cdot26\cdot25\cdot24\cdot23\cdot9\cdot8=258,336,000 $

Example

A manager must select three coders from their group of seven junior and three senior coders to write three different software projects.

The first project can be written by any of the coders; the second project must be written by a senior coder; and the third project must be written by a junior coder.

How many ways are there for them to assign three coders to the projects if no coder can be assigned to more than one project?

$ 10\cdot2\cdot6=120 $

Definition: r-Permutation #

One of the most common applications of the generalized product rule is in counting permutations.

Definition: $r$-Permutation

An $r$-permutation is a sequence of $r$ items with no repetitions taken from the same set.

Example

Consider the set $X=\{\text{John},\text{Paul},\text{George},\text{Ringo}\}$.

The sequences $(\text{Paul},\text{Ringo},\text{John})$ and $(\text{John},\text{George},\text{Paul})$ are both examples of $3$-permutations over $X$.

In a sequence, order matters, so the sequence $(\text{Paul},\text{Ringo},\text{John})$ is different from $(\text{Ringo},\text{Paul},\text{John})$.

X={'John','Paul','George','Ringo'}
list(permutations(X,r=3))

[('John', 'Paul', 'Ringo'),
 ('John', 'Paul', 'George'),
 ('John', 'Ringo', 'Paul'),
 ('John', 'Ringo', 'George'),
 ('John', 'George', 'Paul'),
 ('John', 'George', 'Ringo'),
 ('Paul', 'John', 'Ringo'),
 ('Paul', 'John', 'George'),
 ('Paul', 'Ringo', 'John'),
 ('Paul', 'Ringo', 'George'),
 ('Paul', 'George', 'John'),
 ('Paul', 'George', 'Ringo'),
 ('Ringo', 'John', 'Paul'),
 ('Ringo', 'John', 'George'),
 ('Ringo', 'Paul', 'John'),
 ('Ringo', 'Paul', 'George'),
 ('Ringo', 'George', 'John'),
 ('Ringo', 'George', 'Paul'),
 ('George', 'John', 'Paul'),
 ('George', 'John', 'Ringo'),
 ('George', 'Paul', 'John'),
 ('George', 'Paul', 'Ringo'),
 ('George', 'Ringo', 'John'),
 ('George', 'Ringo', 'Paul')]

Example

Select a $5$-permutation from a set with $8$ elements $\{A,B,C,D,E,F,G,H\}$.

$8$ choices exist for the first item. If $F$ is selected, the remaining choices are $\{A,B,C,D,E,G,H\}$.

There are $7$ choices for the second item, $6$ for the third, $5$ for the fourth, and $4$ for the fifth.

There are

$8\cdot7\cdot6\cdot5\cdot4=6720$

$5$-permutations from a set of $8$.

Claim: about the number of $r$-permutations from a set with $n$ elements #

Claim

Let $r$ and $n$ be positive integers with $r\le n$.

The number of $r$-permutations from a set with $n$ elements is

$ \begin{aligned} P(n,r) &=\frac{n!}{(n-r)!} =\frac{n(n-1)...(n-r+1)\cancel{(n-r)(n-r-1)...1}}{\cancel{(n-r)(n-r-1)...1}} =n(n-1)...(n-r+1) \end{aligned} $

The closed form for $P(n,r)$ is a consequence of the generalized product rule.

There are $n$ choices for the first item in the sequence because the set from which the items are drawn has $n$ elements.

Once the choice for the first item in the sequence is made, there are $n-1$ choices for the next item.

In general, once the first $i$ items in the sequence have been chosen, there are $n-i$ remaining elements from which the next one can be chosen.

The selection process continues until $r$ items have been chosen for the sequence.

Just before the last ($r$-th) item is chosen, $r-1$ items have already been chosen and there are $n-(r-1)=n-r+1$ items from which to select the last item.

Example

A manager has eight employees whom they can assign to five different jobs that need to get done on a given day.

A job only requires one person, and no person can be assigned to more than one job.

How many possible ways can they do the assignment?

Order the jobs arbitrarily so that one job is first, one is second, etc.

An assignment is a $5$-permutation from the set of $8$ employees.

The first person gets the first job, the second person gets the second job,…,and the fifth person gets the fifth job.

The number of $5$-permutations from a set of $8$ people is

$ P(8,5)=8\cdot7\cdot6\cdot5\cdot4=6720 $

E={'Sue','Dave','Chuck','Rajiv','Candace','Jeremy','Nelson','Maureen'}
len(list(permutations(E,r=5)))

Example

A red, blue, and green die are thrown each of which has six possible outcomes.

How many outcomes are possible in which the three dice all show different numbers?

$ P(6,3)=6\cdot5\cdot4=120 $

Example

There are $5$ computers and $3$ students.

How many ways are there for the students to sit at the computers if no computer has more than one student and each student is seated at a computer?

$ P(5,3)=5\cdot4\cdot3=60 $

Example

A class has ten students and the teacher will give out three prizes, but no student can receive more than one prize.

How many ways can the teacher distribute the prizes?

$ P(10,3)=10\cdot9\cdot8=720 $

Definition: Permutation #

Definition: Permutation

A permutation is a sequence that contains each element of a finite set exactly once.

The number of permutations of a finite set with $n$ elements is

$ P(n,n)=n\times(n-1)\times...\times2\times1=n! $

Example

$ \begin{aligned} S&=\{a,b,c\} \\ P(3,3)&=3!=6 \end{aligned} $

S=set('abc')
list(permutations(S))

[('c', 'a', 'b'),
 ('c', 'b', 'a'),
 ('a', 'c', 'b'),
 ('a', 'b', 'c'),
 ('b', 'c', 'a'),
 ('b', 'a', 'c')]

Example

A wedding party consisting of a bride, a groom, two bridesmaids, and two groomsmen line up for a photo.

How many ways are there for the wedding party to line up?

$ P(6,6)=6!=720 $

S=set(range(6))
len(list(permutations(S)))

Example

John, Paul, George, and Ringo would like to sit on a bench together, but Paul and John would like to sit next to each other.

How many possible seatings are there?

In order to apply the generalized product rule, view the set of possibilities as a process in which a seating is specified.

The first step is to determine whether Paul sits to the left or right of John.

There are two possible choices: Paul is to the left of John or Paul is to the right of John.

Then glue Paul and John together in the chosen order to satisfy the constraint that they sit together.

Now there are three items to order: two of them are people (George and Ringo) and the other is a pair that is bound together (John and Paul).

The next step is to select a permutation of the three items.

There are three factorial permutations of the three items; and for each permutation, there are two ways to order John and Paul.

$ P(3,3)\cdot2=3!\cdot2=12 $

S=set(range(3))
len(list(permutations(S)))*2

Example

A wedding party consisting of a bride, a groom, two bridesmaids, and two groomsmen line up for a photo.

How many ways are there for the wedding party to line up so that the bride is next to the groom?

$ P(5,5)\cdot2=5!\cdot2=240 $

S=set(range(5))
len(list(permutations(S)))*2

Example

$ \begin{aligned} D&=\{0,1,2,3,4,5,6,7,8,9\} \\ L&=\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z\} \end{aligned} $

How many passwords of length $k$ are there given the following constraints?

(i) $k=19$; no repeated characters

$ \begin{aligned} P(36,19) =\frac{36!}{(36-19)!} =\frac{36!}{17!} \end{aligned} $

(ii) $k=9$; no repeated characters; starts with $k$

$ \begin{aligned} P(35,8) =\frac{35!}{(35-8)!} =\frac{35!}{27!} =948,964,262,400 \end{aligned} $

(iii) $k=10$; no repeated characters; starts with $d$

$ \begin{aligned} P(35,9) =\frac{35!}{(35-9)!} =\frac{35!}{26!} =25,622,035,084,800 \end{aligned} $

(iv) $k=20$; no repeated characters; starts with $w0$

$ \begin{aligned} P(34,18) =\frac{34!}{(34-18)!} =\frac{34!}{16!} =14,110,584,707,870,682,697,957,376 \end{aligned} $

(v) $k=9$; no repeated characters; must contain $l$

$ \begin{aligned} P(9,1)\cdot P(35,8) =\frac{9!}{(9-1)!}\cdot\frac{35!}{(35-8)!} =\frac{9!}{8!}\cdot\frac{35!}{27!} =9\cdot948,964,262,400 =8,540,678,361,600 \end{aligned} $

(vi) $k=18$; no repeated characters; must contain $k$

$ \begin{aligned} P(18,1)\cdot P(35,17) =\frac{18!}{(18-1)!}\cdot\frac{35!}{(35-17)!} =\frac{18!}{17!}\cdot\frac{35!}{18!} =18\cdot1,613,955,767,240,110,567,849,984 =29,051,203,810,321,990,221,299,712 \end{aligned} $

(vii) $k=12$; no repeated characters; must contain $h,8,0,2$

$ \begin{aligned} P(12,4)\cdot P(32,8) =\frac{12!}{(12-4)!}\cdot\frac{32!}{(32-8)!} =\frac{12!}{8!}\cdot\frac{32!}{24!} =11,880\cdot424,097,856,000 =5,038,282,529,280,000 \end{aligned} $

Example

Count the number of different functions with the given domain, target, and additional properties.

(i) $f:\{0,1\}^7\to\{0,1\}^7$

$2^7$ choices for $f(x_1)$, $2^7$ choices for $f(x_2)$, …, $2^7$ choices for $f(x_{2^7})$.

$ |\underbrace{\{0,1\}^7\times\{0,1\}^7\times...\times\{0,1\}^7}_{2^7\,\text{times}}| =\underbrace{|\{0,1\}|^7\cdot|\{0,1\}|^7\cdot...\cdot|\{0,1\}|^7}_{2^7\,\text{times}} =(2^7)^{2^7} =128^{128} $

(ii) $f:\{0,1\}^7\to\{0,1\}^7$ and $f$ is one-to-one

$2^7$ choices for $f(x_1)$, $2^7-1$ choices for $f(x_2)$, …, $1$ choice for $f(x_{2^7})$.

$ P(2^7,2^7)=2^7!=128! $

(iii) $f:\{0,1\}^5\to\{0,1\}^7$

$2^7$ choices for $f(x_1)$, $2^7$ choices for $f(x_2)$, …, $2^7$ choices for $f(x_{2^5})$.

$ |\underbrace{\{0,1\}^7\times\{0,1\}^7\times...\times\{0,1\}^7}_{2^5\,\text{times}}| =\underbrace{|\{0,1\}|^7\cdot|\{0,1\}|^7\cdot...\cdot|\{0,1\}|^7}_{2^5\,\text{times}} =(2^7)^{2^5} =128^{32} $

(iv) $f:\{0,1\}^5\to\{0,1\}^7$ and $f$ is one-to-one

$2^7$ choices for $f(x_1)$, $2^7-1$ choices for $f(x_2)$, …, $2^7-2^5+1$ choices for $f(x_{2^5})$.

$ \begin{aligned} P(2^7,2^5) =\frac{2^7!}{(2^7-2^5)!} =\frac{128!}{96!} \end{aligned} $

Example

At a certain university in the U.S., all phone numbers are $7$-digits long and start with either $824$ or $825$.

(i) How many different phone numbers are possible?

$ |\{8\}\times\{2\}\times\{4,5\}\times D^4| =|\{8\}|\cdot|\{2\}|\cdot|\{4,5\}|\cdot|D|^4 =2\cdot10^4 =20,000 $

(ii) How many different phone numbers are there in which the last four digits are all different?

$ \begin{aligned} 2\cdot P(10,4) =2\cdot\frac{10!}{6!} =10,080 \end{aligned} $

len(sorted(product({'8'},{'2'},{'4','5'},set(string.digits),set(string.digits),set(string.digits),set(string.digits))))

2*len(list(permutations(set(string.digits),r=4)))

Example

Ten members of a wedding party are lining up in a row for a photograph.

(i) How many ways are there to line up the ten people?

$ P(10,10)=10!=3,628,800 $

(ii) How many ways are there to line up the ten people if the groom must be beside the bride in the photo?

$ 2\cdot P(9,9)=2\cdot9!=725,760 $

(iii) How many ways are there to line up the ten people if the bride must be next to the maid of honor and the groom must be next to the best man?

$ 2^2\cdot P(8,8)=4\cdot8!=161,280 $

Example

A girl scout troop with $10$ girl scouts and $2$ leaders goes on a hike.

When the path narrows, they must walk in a single file with a leader at the front and a leader at the back.

How many ways are there for the entire troop to line up?

$ 2\cdot P(10,10)=2\cdot10!=7,257,600 $

Definition: $r$-Combination #

Consider a class with $20$ students who must elect three representatives to the student council; the teacher conducts a vote and reveals the names of the three students who received the most votes but they do not reveal how many votes each student received or which one received more votes than the other two.

How many ways are there to select the three representatives?

The outcome of the election is a set of three students, not a sequence, because there is no particular order imposed on the three representatives: the outcome {Joshua, Karen, Ingrid} is the same outcome as {Karen, Ingrid, Joshua}.

Definition: Permutation

A subset of size $r$ is called an $r$-subset.

An $r$-subset may be called an $r$-combination.

The counting rules for sequences and subsets are commonly referred to as “permutations and combinations”.

The term “combination” in the context of counting is another word for “subset”.

In counting the number of ways to elect the three representatives, we are counting the number of different $3$-subsets of students from a class of size $20$.

Example

Let $S=\{a,b,c\}$.

(i) Is $(b,a)$ a $2$-permutation or a $2$-combination from $S$?

(ii) Is $\{b,a\}$ a $2$-permutation or a $2$-combination from $S$?

(iii) How many different $2$-permutations from $S$ are there?

$ \begin{aligned} P(3,2)=\frac{3!}{(3-2)!}=6 \end{aligned} $

(iv) How many different $2$-combinations from $S$ are there?

$3$

S=set('abc')
print(list(permutations(S,r=2)))
print(list(combinations(S,r=2)))

[('c', 'a'), ('c', 'b'), ('a', 'c'), ('a', 'b'), ('b', 'c'), ('b', 'a')]
[('c', 'a'), ('c', 'b'), ('a', 'b')]

Example

Consider the case in which a subset of three colors is selected from the set $\{\text{blue},\text{green},\text{orange},\text{pink},\text{red}\}$.

The number of $3$-permutations from the set of five colors is

$ \begin{aligned} P(5,3)=\frac{5!}{(5-3)!}=60 \end{aligned} $

Now define a function mapping $3$-permutations to $3$-combinations.

The function is defined by just removing the ordering so that $(\text{orange},\text{pink},\text{blue})$ and $(\text{blue},\text{orange},\text{pink})$ both map to the set $\{\text{orange},\text{blue},\text{pink}\}$.

The function is $3!$-to-$1$, so by the $k$-to-$1$ rule the number of $3$-combinations of colors is

$ \begin{aligned} \frac{P(5,3)}{3!} =\frac{5!}{(5-3)!3!} =\frac{5!}{3!2!} =10 \end{aligned} $

Definition: General Rule for Counting $r$-Permutations #

Definition: General Rule for Counting $r$-Permutations

To derive the general rule for counting $r$-combinations, define a mapping between $r$-permutations from a set of size $n$ and $r$-combinations.

The $k$-to-$1$ rule will be applied with $k=r!$.

$S=\{1,2,...,n\}$

There are $P(n,r)$ $r$-permutations from $S$:

$ \text{\# r-permutations from S} \begin{cases} (1,2,...,r) \\ \vdots \\ (r,r-1,...,2,1) \\ \vdots \\ (n-r+1,...,n) \\ \vdots \\ (n,n-1,...,n-r+1) \end{cases} $

$r!$ $r$-permutations map to each $r$-subset from $S$

$ \text{\# r-subsets from S} \begin{cases} \{1,2,...,r\}\leftarrow \begin{cases} (1,2,...,r) \\ \vdots \\ (r,r-1,...,2,1) \end{cases} \\ \vdots \\ \{n-r+1,...,n\}\leftarrow \begin{cases} (n-r+1,...,n) \\ \vdots \\ (n,n-1,...,n-r+1) \end{cases} \end{cases} $

Each $r$-subset from $S$ has $r!$ $r$-permutations that map onto it.

$ \begin{aligned} \text{\# r-subsets from S} =\frac{\text{\# r-permutations from S}}{r!} =\frac{P(n,r)}{r!} =\frac{n!}{r!(n-r)!} \end{aligned} $

Example

Consider a function that maps $5$-permutations from a set $S=\{1,2,...,20\}$ to $5$-combinations from $S$.

The function takes a $5$-permutation and removes the ordering on the elements.

How many $5$-permutations map on to the subset $\{2,5,13,14,19\}$?

$5!=120$

Figures #

[ w ] 1848-1911 Schubert, Hermann
[ w ] 1249-1314 Shijie, Zhu
[ w ] 1735-1796 Vandermonde, Alexandre-Théophile
[ w ] 1873-1940 Young, Alfred

Terms #

[ w ] Cardinality
[ w ] Combination
[ w ] Combinatorics
[ w ] Countability
[ w ] Counting
[ w ] Double Counting
[ w ] Enumerative Combinatorics
[ w ] Falling Factorial
[ w ] Partition
[ w ] Pascal’s Rule
[ w ] Pascal’s Triangle
[ w ] Permutation
[ w ] Permutation Parity
[ w ] q-Analog
[ w ] q-Vandermonde Identity
[ w ] Schubert Calculus
[ w ] Uncountability
[ w ] Vandermonde’s Identity
[ w ] Young Tableau

Combinatorics

Contents

Combinatorics #

Programming Environment #

Counting #

Definition: Product Rule #

Definition: Sum Rule #

Definition: Bijection Rule #

Claim: the number of subsets of an \(n\)-element set is equal to the number of length-\(n\) bit strings #

Definition: \(k\)-to-\(1\) Correspondence #

Definition: \(k\)-to-\(1\) Rule #

Definition: Generalized Product Rule #

Definition: r-Permutation #

Claim: about the number of \(r\)-permutations from a set with \(n\) elements #

Definition: Permutation #

Definition: \(r\)-Combination #

Definition: General Rule for Counting \(r\)-Permutations #

Figures #

Terms #