Note that given is Complete graph ===> there is a edge between every pair of vertices.
we have n vertices, let name them as V1,V2,...Vn.
We want the paths between V1 and Vn.
there are remaining, n-2 elements, i.e., V2,V3,....Vn-1 . ===> let the Set S = { remaining elements } ===> |S| = n-2.
what is the Power Set of this elements ===> size of power Set of S = 2n-2.
in the power set, each set is lead to unique path ( labels are in the path are strictly increasing order ) between V1 and Vn.
∴ No.of Simple paths between V1 and Vn Such that the labels in the path are strictly increasing order = 2n-2.
ex:-
let take K5..... name the labels as V1,V2,V3,V4,V5.
We want the simple paths between V1 and V5.
remaining vertices are {V2,V3,V4}, then the power set is contains the following set
1) ∅ ====> the path which we required is V1 --- V5.
2) { V2 } ====> the path which we required is V1 --- V2 --- V5.
3) { V3 } ====> the path which we required is V1 --- V3 --- V5.
4) { V4 } ====> the path which we required is V1 --- V4 --- V5.
5) { V2,V3 } ====> the path which we required is V1 --- V2 --- V3 --- V5.
6) { V2,V4 } ====> the path which we required is V1 --- V2 --- V4 --- V5.
7) { V3,V4 } ====> the path which we required is V1 --- V3 --- V4 --- V5.
8) { V2,V3,V4 } ====> the path which we required is V1 --- V2 --- V3 --- V4 --- V5.
Now i am interested in that,what the formula if in the question the restriction " labels are in the path are strictly increasing order " removed ?
the power set contains = 2n-2. sets
we can partition them as
$\binom{n-2}{0} + \binom{n-2}{1} + \binom{n-2}{2} + ...+ \binom{n-2}{n-2}$ = 2n-2.
$\binom{n-2}{0}$ ===> lead to 1 permutation paths
$\binom{n-2}{1}$ ===> lead to 1 permutation paths
$\binom{n-2}{2}$ ===> lead to 2 permutation paths
............
$\binom{n-2}{n-2}$ ===> lead to (n-2)! permutation paths
∴ No.of Simple paths between V1 and Vn = $\binom{n-2}{0} * 1! + \binom{n-2}{1} * 1! + \binom{n-2}{2} * 2! + ...+ \binom{n-2}{n-2} * (n-2)! $.