 Solution

Multiplying transition probabilities along a path gives a denominator $n!$. The numerator factors into one product depending only on the final number of labels and, for each label, a productIt is therefore unchanged when the final label frequencies are permuted. This proves the claimed equality.