I think it should be
Here are my reasons. Suppose we want to choose of those shoes so that none match (no pairs).
Clearly . There are ways to choose pairs from the pairs
From those pairs there are ways to choose either the left or the right shoe from each pair.
Does that help?