Sun and Moon Bracelets
Combinatorics · 2025 Mathematch, Final Round | proposed by @lumiere
Krabby is creating celestial pendants for a fund-raising activity to go to space. She forms each pendant by letting her bead maker randomly create either a moon bead (M) or a sun bead (S), with equal probability once in a while. Then, she attaches each newly made bead to the right of the other beads that were already created.
Suppose Krabby stops creating the pendant once the bead maker produces the string of three beads M, S, and M in that order. How many ways can Krabby have a celestial pendant containing exactly 9 beads?