Finding a formula is not the way to look at the problem. That’s the lazy approach! If we had to have a formula for every problem we would have so many formulae we would need a formula to find the one we’re looking for! It’s all about logical thinking. Sometimes a formula will arise when we think through a problem logically. But the big clue is to look for a pattern. Formulae often arise when we spot a pattern.

Let’s see if a pattern comes out of this problem.

Let’s go through each day. On Day 1, we have a choice of 3 pairs of shoes. Label the pairs A, B, C.

On Day 2 we can have AB, AC, BA, BC, CA, CB. That’s 6 combinations, twice as many as Day 1.

On Day 3 we can have ABA, ABC, ACA, ACB, BAB, BAC, BCA, BCB, CAB, CAC, CBA, CBC—12 combinations.

On Day 4 we have twice as many again—24.

Now we can see at least one simple pattern in the number of combinations for the number of days: 3, 6, 12, 24, 48, ..., because each combination “spawns” 2 for the next day. We can write this as a formula: 2ⁿ⁻¹×3 where n is the number of days. So when n=10 there are 2⁹×3=512×3=1536 combinations—but not all will be valid.

I note that you edited the question. I found a formula based on observation which seems to fit the facts and enables us to predict the result for any number of days: 2ⁿ+2(-1)ⁿ. So when n=10, this comes to 1026. I think I can show the logic leading to the formula, if you need it.