MathFun4Kids

Proof: For $n=1$, we have $2$ possible binary strings, as $0$, and $1$. We have $f(1)=2$ as none of the $2$ possible binary strings containing $010$ or $101$.

For $n=2$, we have $4$ possible binary strings, as $00$, $01$, $10$, and $11$. We have $f(2)=4$ as none of the $4$ possible binary strings containing $010$ or $101$.

When $n=3$, there are $8$ possible binary strings, as $000$, $001$, $010$, $011$, $100$, $101$, $110$, and $111$. Excluding $010$ and $101$, we have $f(3)=6$.

Therefore, $f(n)=f(n-1)+f(n-2)$ when $n=3$.

For a binary string of length $n$ that does not contain a sub-string as $010$ nor $101$, the string can end up with a suffix as $00$, $01$, $10$, or $11$. Let $a(n)$, $b(n)$, $c(n)$, and $d(n)$ be the number of strings with length as $n$ that end up with a suffix as $00$, $01$, $10$, and $11$ respectively. Therefore $$f(n)=a(n)+b(n)+c(n)+d(n)$$ Additionally, we have the following relationships:

$$ \begin{array}{rcl} a(n)&=&a(n-1)+c(n-1)\\ b(n)&=&a(n-1)\\ c(n)&=&d(n-1)\\ d(n)&=&b(n-1)+d(n-1)\\ \end{array} $$

Therefore

$$ \begin{array}{rcl} f(n)&=&a(n)+b(n)+c(n)+d(n)\\ \ &=&(a(n-1)+c(n-1))+a(n-1)+d(n-1)+(b(n-1)+d(n-1))\\ \ &=&(a(n-1)+b(n-1)+c(n-1)+d(n-1))+(a(n-1)+d(n-1))\\ \ &=&f(n-1)+((a(n-2)+c(n-2))+(b(n-2)+d(n-2)))\\ \ &=&f(n-1)+(a(n-2)+b(n-2)+c(n-2)+d(n-2))\\ \ &=&f(n-1)+f(n-2)\\ \end{array} $$

Combining with the case when $n=3$, it is proved that $\boxed{f(n)=f(n-1)+f(n-2)}$.

Solution 1: The problem is equivalent to write $8$ as the sum of at least three positive integers.

Case 1: There are $8$ $1$s in the sum, i.e. $1+1+1+1+1+1+1+1$. There is only $1$ way.

Case 2: There are $6$ $1$s in the sum, i.e. $1+1+1+1+1+1+2$. There are $7$ ways.

Case 3: There are $5$ $1$s in the sum, i.e. $1+1+1+1+1+3$. There are $6$ ways.

Case 4: There are $4$ $1$ in the sum, with the following sub-cases:

Case 4.1: For sum as $1+1+1+1+4$, there are $5$ ways.

Case 4.2: For sum as $1+1+1+1+2+2$, there are $\dfrac{6!}{4!\cdot 2!}=15$ ways.

Case 5: There are $3$ $1$s in the sum, with the following sub-cases:

Case 5.1: For sum as $1+1+1+5$, there are $4$ ways.

Case 5.2: For sum as $1+1+1+3+2$, there are $\dfrac{5!}{3!\cdot 1!\cdot 1!}=20$ ways.

Case 6: There are $2$ $1$s in the sum, with the following sub-cases:

Case 6.1: For sum as $1+1+6$, there are $3$ ways.

Case 6.2: For sum as $1+1+4+2$, there are $\dfrac{4!}{2!\cdot 1!\cdot 1}=12$ ways.

Case 6.3: For sum as $1+1+3+3$, there are $\dfrac{4!}{2!\cdot 2!}=6$ ways.

Case 6.4: For sum as $1+1+2+2+2$, there are $\dfrac{5!}{2!\cdot 3!}=10$ ways.

Case 7: There are $1$ $1$s in the sum, with the following sub-cases:

Case 7.1: For sum as $1+5+2$, there are $6$ ways.

Case 7.2: For sum as $1+4+3$, there are $6$ ways.

Case 7.3: For sum as $1+3+2+2$, there are $\dfrac{4!}{1!\cdot 1!\cdot 2!}=12$ ways.

Case 8: There is no $1$s in the sum, with the following sub-cases:

Case 8.1: For sum $2+2+2+2$, there is only $1$ way.

Case 8.2: For sum $2+2+4$, there are $3$ ways.

Case 8.3: For sum $2+3+3$, there are $3$ ways.

Combining all the above cases, the answer to the question is:

$$1+7+6+5+15+4+20+3+12+6+10+6+6+12+1+3+3=\boxed{120}$$

Solution 2: The problem is equivalent to write $8$ as the sum of at least three positive integers, which is the same as placing $8$ identical balls into $n$ unique boxes, where $n=3,4,5,6,7,8$.

Case 1: Place 8 $1$s into $8$ different boxes, with each box contains at least $1$s. There is only ${{8-1}\choose{8-1}}=1$ way.

Case 2: Place 8 $1$s into $7$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{7-1}}=7$ ways.

Case 3: Place 8 $1$s into $6$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{6-1}}=21$ ways.

Case 4: Place 8 $1$s into $5$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{5-1}}=35$ ways.

Case 4: Place 8 $1$s into $4$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{4-1}}=35$ ways.

Case 5: Place 8 $1$s into $3$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{3-1}}=21$ ways.

Combining all the above cases, the answer to the question is:

$$1+7+21+35+35+21=\boxed{120}$$

Solution 3: The problem is equivalent to write $8$ as the sum of at least three positive integers. The total ways of writing $8$ as the sum of any positive integers, without any restrictions, including singleton, is $2^{8-1}=128$, as there are at most $8-1=7$ plus signs $(+)$ that can be used in a sum.

There is $1$ way to write $8$ as the sum of only one positive integers (singleton). And there are $7$ ways to write $8$ as the sum of only two positive integers.

Therefore, by complementary principle, the answer to the question is: $$128-1-7=\boxed{120}$$

Solution: Since $2$ players do not want to be benched, they must be included in the starting lineup. Therefore, the other $4$ players in the starting line-up must be selected from the remaining $6$ players, including those $2$ players who do not want to be captain, vice-captain, or goalie.

Case 1: If none of the two players who do not want to be captain, vice-captain, or goalie is selected.

The total number of ways to form the starting lineup would be $$6!=720$$ as no restrictions will be applied to the positions.

Case 2:If we select one of two players who do not want to be captain, vice-captain, or goalie to be in the starting lineup.

There are $2$ ways to select one of the above two to be one of the $3$ unique field players.

Additionally, $3$ additional players will be selected from the remaining 4 players who do not have any restrictions. These $3$ players plus the other $2$ players who do not want to be on the bench will have $5!$ permutations for the starting lineup.

Therefore, the total number of ways is $$ {{2}\choose{1}}\cdot {{3}\choose{1}}\cdot{{4}\choose{3}}\cdot 5!=2\cdot 3\cdot 4\cdot 120=2880$$

Case 3: If we select both two players who do not want to be captain, vice-captain, or goalie to be in the starting lineup.

There are $3$ ways to select $2$ positions from the $3$ unique field players for the above two players with $2!$ permutations.

The remaining $2$ players will be selected from the $4$ players without restriction. These $2$ players plus the $2$ players who do not want to be on the bench will have $4!$ permutations for the starting lineup.

Therefore the total number of ways is: $${{3}\choose{2}}\cdot 2! \cdot {{4}\choose{2}}\cdot 4!=3\cdot 2\cdot 6\cdot 24=864$$

Combining the above $3$ cases, the answer to the question is $$720+2880+864=\boxed{4464}$$