Probability you end dice rolling sequence with 1-2-3 and odd total number of rolls Here's a question from the AIME competition:

Misha rolls a standard, fair six-sided die until she rolls 1-2-3 in that order on three consecutive rolls. The probability that she will roll the die an odd number of times is ${m\over{n}}$ where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

This is what I did. Let's add up the following cases with an odd number of rolls, where in each sequence of XXX... there is no subsequence of 123:

*

*Probability of 123: $({1/6})^3$

*Probability of XX123: $({1/6})^3$

*Probability of XXXX123: $(1/6)^3(1 - 2(1/6)^3)$

*Probability of XXXXXX123: $(1/6)^3(1 - 4(1/6)^3 + (1/6)^6)$

*Probability of XXXXXXXX123: $(1/6)^3 (1 - 6(1/6)^3 + \binom{4}{2} (1/6)^6) = (1/6)^3 (1 - 6(1/6)^3 + 6(1/6)^6)$

*Probability of XXXXXXXXXX123: $(1/6)^3 (1 - 8(1/6)^3 + \binom{6}{2} (1/6)^6 - 4(1/6)^9) = (1/6)^3 (1 - 8(1/6)^3 + 15(1/6)^6 - 4(1/6)^9)$

*Probability of XXXXXXXXXXXX123: $(1/6)^3 (1 - 10(1/6)^3 + \binom{8}{2} (1/6)^6 - \binom{6}{3}(1/6)^9 + (1/6)^{12}) = (1/6)^3 (1 - 10(1/6)^3 + 28 (1/6)^6 - 20(1/6)^9 + (1/6)^{12})$

*$\ldots$and so forth.

I notice some obvious patterns, but nonetheless I'm stuck with proceeding further. Any hints towards finding a way to add this all up would be well-appreciated. Please, no complete solutions.
Edit: For the record, the correct probability after you add this all up should be ${{216}\over{431}}$.
Edit 2: There are a number of solutions to this problem here: https://artofproblemsolving.com/wiki/index.php/2018_AIME_II_Problems/Problem_13
However, all the solutions at the link are extremely clever, whereas my approach is a naive brute force. I would like some hints/suggestions on how to make my brute force approach work.

Consider an easier problem: What if she only needs to get 1-2? Or even simpler case: just one particular number. Can you relate these problems somehow?

I'll just store this here:
A = matrix([[0,0,0,0,5,1,0,0],
            [0,0,0,0,4,1,1,0],
            [0,0,0,0,4,1,0,1],
            [0,0,0,6,0,0,0,0],
            [5,1,0,0,0,0,0,0],
            [4,1,1,0,0,0,0,0],
            [4,1,0,1,0,0,0,0],
            [0,0,0,0,0,0,0,6],
           ])/6

QInds = [0,1,2,4,5,6]
RInds = [3, 7]
Q = A[QInds, QInds]
R = A[QInds, RInds]
#show(A)
show((matrix.identity(6)-Q)^(-1)*R)

g = DiGraph(A, loops=True, format='weighted_adjacency_matrix')
g.relabel(lambda v: (v%4, 'even' if v<4 else 'odd'))
show(g.plot( figsize=10, edge_labels=True, vertex_size=100, edge_thickness=0.2, edge_color='gray'))

