I have already gone over the recursive solution. It was simple, maybe even elegant. However, its complexity was horrendous, factorial growth. The solution I’m about to lay out is complex in comparison. So we should do a simple example first.
The Problem (general)
How many ways can one climb a set of stairs of any length by taking step options from any number of options?
Simple Example Again
I want to go over the example again, but not using trees. We will use combinations.
How many ways can one climb a set of stairs with five steps by either taking one or two steps at a time?
I first want to just consider the larger categories of different ways one could climb these stairs.
- 5 steps of one
- 3 steps of one and 1 step of two
- 1 step of one and 2 steps of two
Note that for the second category (3 steps of one and 1 step of two) there are a number of different ways this can be done.
Three larger categories. Now we need to see how many ways each of these categories yields. To find this we will use combinations.
I will pause here to note that I like using multinomial combination notation to describe combinations.
\(
\begin{matrix}
n=n_{1}+n_{2}+n_{3} \\
\begin{pmatrix}
n \\
n_{1},n_{2},n_{3}
\end{pmatrix}
=\frac{n!}{n_{1}!n_{2}!n_{3}!}
\end{matrix}
\)
So a normal combination can be expressed in this fashion.
\(
\begin{pmatrix}
n \\
k
\end{pmatrix}
=
\begin{pmatrix}
n \\
k,n-k
\end{pmatrix}
=\frac{n!}{k!(n-k)!}
\)
Applying combinations to our three categories
-
5 steps
\(
\begin{pmatrix}
5 \\
5
\end{pmatrix}=1
\)
1 way when we can just take one step at a time -
3 steps plus 1 step is 4
\(
\begin{pmatrix}
4 \\
3,1
\end{pmatrix}=4
\)
4 ways when we take 3 steps of one and 1 step of two -
1 step plus 2 steps is 3
\(
\begin{pmatrix}
3 \\
1,2
\end{pmatrix}=3
\)
3 ways when we take 1 step of one and 2 steps of two
\(1+4+3=8\)
Which is what we got last time using trees.
Let’s take a closer look at these larger categories.
-
1 way when we can just take one step at a time
\(11111\) -
4 ways when we take 3 steps of one and 1 step of two
\(2111\)
\(1211\)
\(1121\)
\(1112\) -
3 ways when we take 1 step of one and 2 steps of two
\(122\)
\(212\)
\(221\)
This concludes the simple example. If you are not seeing how the number of ways for each category is linked to combinations, please read on. Otherwise, at this point, it will be ok to move on to Part 2.
Dinstringuishable Permutations
Is another name for what we are doing above.
Examples Examples Examples
let’s consider we have a 10 step staircase and we can take one, two, or three steps at a time.
Now we are going to look at the specific case where we take 2 steps of three, 2 steps of one, and 1 step of two.
So one outcome would look like
\(33112\)
And let’s calculate the multinomial combination
\(
\begin{pmatrix}
5 \\
2,2,1
\end{pmatrix}
=\frac{5!}{2!2!1!}
=\frac{120}{2\cdot2}
=30
\)
See if you can figure out how I came up with the 5, two 2s, and the 1.
Before I explain what is going on there. Let’s try to list out the 30 examples.
First, let’s do a replacement to make it easier to look at and describe (3-> A, 1->B, and 2->C). It is really complicated saying things like “2 steps of three, 2 steps of one, and 1 step of two”. Unfortunately, this problem forces us to use some sort of description like that. It would be less confusing to say something like “2 steps of A, 2 steps of B, and 1 step of C”
So
\(33112\)
Would now be
\(AABBC\)
First I will consider just A’s and B’s
\(AABB\)
\(ABAB\)
\(ABBA\)
\(BAAB\)
\(BABA\)
\(BBAA\)
6 ways
Now I will iterate the C through each of the above 6 ways.
\(CAABB\)
\(ACABB\)
\(AACBB\)
\(AABCB\)
\(AABBC\)
\(CABAB\)
\(ACBAB\)
\(ABCAB\)
\(ABACB\)
\(ABABC\)
\(CABBA\)
\(ACBBA\)
\(ABCBA\)
\(ABBCA\)
\(ABBAC\)
\(CBAAB\)
\(BCAAB\)
\(BACAB\)
\(BAACB\)
\(BAABC\)
\(CBABA\)
\(BCABA\)
\(BACBA\)
\(BABCA\)
\(BABAC\)
\(CBBAA\)
\(BCBAA\)
\(BBCAA\)
\(BBACA\)
\(BBAAC\)
And there are our 30 examples. Let’s now try to understand the link to combinations.
\(
\begin{pmatrix}
5 \\
2,2,1
\end{pmatrix}
=\frac{5!}{2!2!1!}
\)
There are \(5!=120\) ways that 5 distinct objects can be ordered. However, some of our objects are indistinguishable from each other
For a second, let’s consider that we can distinguish between the A’s.
If we can do this, each of the examples could be broken down into two different ways.
\(AABBC\)
Would be able to be distinguished to
\(A_1A_2BBC\)
\(A_2A_1BBC\)
And we could do the same for the B’s giving
\(A_1A_2B_1B_2C\)
\(A_1A_2B_2B_1C\)
\(A_2A_1B_1B_2C\)
\(A_2A_1B_1B_2C\)
So our one way now becomes 4 ways.
If we did this to each of our above 30 examples, that would be \(30\cdot4=120\) or our \(5!\) ways to order 5 distinguishable objects.
Ok, we can go back to not being able to distinguish between the A’s and B’s. We have 2 A’s and 2 B’s. The number of ways to order two objects is \(2!\). So we divide it out.
\(
\begin{pmatrix}
5 \\
2,2,1
\end{pmatrix}
=\frac{5!}{2!2!1!}
=120
\)
We are now ready to break this method down and talk about how we are going to get a computer to do this for us.
Recent Comments