A bar of chocolate is made of 10 distinguishable triangles as shown below. How many ways are there to divide the bar, along the edges of the triangles, into two or more contiguous pieces?
Solution
Every way to divide the bar can be described as a nonempty set of edges to break, with the condition that every endpoint of a broken edge is either on the boundary of the bar or connects to another broken edge. Let the center edge have endpoints and . We do casework on whether the center edge is broken. If the center edge is broken, then we just need some other edge connecting to to be broken, and some other edge connecting to to be broken. We have choices for the edges connecting to , of which 1 fails. Similarly, we have valid choices for the edges connecting to . This yields possibilities. If the center edge is not broken, then the only forbidden arrangements are those with exactly one broken edge at or those with exactly one broken edge at . Looking at just the edges connecting to , we have 5 cases with exactly one broken edge. Thus, there are ways to break the edges connecting to . Similarly there are 27 valid choices for the edges connecting to . This yields cases, once we subtract the situation where no edges are broken. The final answer is .