+399 We can use case work counting with this. We have three cases, if we start with \(1\) step, \(2\) steps, or \(3\) steps. You then can add a subcase of \(1\) step, \(2\) steps, or \(3\) steps to the beginning cases. You can keep doing this until all your cases add up to \(9\). This is a hassle, but it works. I don't reccommend this method, but I do not know any other methods, sorry. The end answer is \(149\). Haha I hope this helped! Hopefully you can find a better solution!
- Daisy
+118687
|
| steps (in any order) | number of steps | Permutations | |
| all ones | 1,1,1,1,1,1,1,1,1 | 9 | 1 | 1 |
| ones and 2s | 1,1,1,1,1,1,1,2 | 8 | 8 | 8 |
| 1,1,1,1,1,2,2 | 7 | 7C2 | 21 | |
| 1,1,1,2,2,2 | 6 | 6C3 | 20 | |
| 1,2,2,2,2 | 5 | 5 | 5 | |
| ones and threes | 1,1,1,1,1,1,3 | 7 | 7 | 7 |
| 1,1,1,3,3 | 5 | 5C2 | 10 | |
| all threes | 3,3,3 | 3 | 1 | 1 |
| twos and threes | 2,2,2,3 | 4 | 4 | 4 |
| ones, twos and threes | 3,2,1,1,2 | 5 | 5*4C2 | 30 |
| 3,2,1,3 | 4 | 4*3 | 12 | |
| 3,2,1,1,1,1 | 6 | 6*5 | 30 | |
| TOTAL | 149 |
+26393 When I run up a staircase, my stride can carry me up 1, 2, or 3 steps at a time. In how many ways can I run up a 9-step staircase (given that my last stride lands me on the 9th step)?
Let \(T_n\) be the number of ways to climb n stairs taking only 1 or 2 or 3 steps:
\(\begin{array}{|rcll|} \hline T_n &=& \mathcal{T}_{n+2} \qquad \mathcal{T} \text{ is the Tribonacci number } \\\\ && \text{case of n=9 steps}: \\\\ T_{9} &=& \mathcal{T}_{11} \qquad \\ && \mathcal{T}_0 = 0 \\ && \mathcal{T}_1 = 0 \\ && \mathcal{T}_2 = 1 \\ && \mathcal{T}_3 = 1 \\ && \mathcal{T}_4 = 2 \\ && \mathcal{T}_5 = 4 \\ && \mathcal{T}_6 = 7 \\ && \mathcal{T}_7 = 13\\ && \mathcal{T}_8 = 24\\ && \mathcal{T}_9 = 44\\ && \mathcal{T}_{10} = 81\\ && \mathcal{T}_{11} = 149\\ && \mathcal{T}_{12} = 274\\ && \ldots \\ T_{9} &=& 149 \\ \hline \end{array}\)
Source: http://oeis.org/search?q=1%2C2%2C4%2C7%2C13%2C24%2C&sort=&language=english&go=Search
"Tribonacci numbers: \(a(n) = a(n-1) + a(n-2) + a(n-3) \text{ with } a(0)=a(1)=0, a(2)=1\)."
"a(n) = number of compositions of n-2 with no part greater than 3.
Example: a(5)=4 because we have \(1+1+1 = 1+2 = 2+1 = 3\).
\(\ldots\)
\(a(n+1) = \dfrac{3*c*\left((1/3)*(a+b+1)\right)^n}{c^2-2*c+4}\) where
\(a=(19+3*\sqrt{33})^{1/3}\),
\(b=(19-3*\sqrt{33})^{1/3}\),
\(c=(586+102*\sqrt{33})^{1/3}\).
Round off to the nearest integer."
Example:
\(\begin{array}{|rcll|} \hline T_{9} = a(11)& =& \dfrac{3*c*\left((1/3)*(a+b+1)\right)^{10}}{c^2-2*c+4} \\ a=(19+3*\sqrt{33})^{1/3}& =& 3.30905647997\ldots \\ b=(19-3*\sqrt{33})^{1/3}& =& 1.20880378568\ldots \\ c=(586+102*\sqrt{33})^{1/3}& =& 10.5431194025\ldots \\ T_{9} & =& \frac{3*10.5431194025*\left((1/3)*(3.30905647997+1.20880378568+1)\right)^{10}}{10.5431194025^2-2*10.5431194025+4} \\ & =& \frac{14,014.7325577}{94.0711279297} \\ & =& 148.980169220 \\ \mathbf{T_{9}} & \mathbf{=}& \mathbf{149} \\ \hline \end{array} \)
