- Thread starter
- #1

- Apr 14, 2013

- 4,028

Let $G$ be a graph of which the vertices are the permutations of $\{1,2,3,4,5,6,7,8,9,9,9\}$ with the property that two vertices $(\epsilon_1, \epsilon_2, \ldots, \epsilon_{11})$, $(\epsilon_1', \epsilon_2', \ldots, \epsilon_{11}')$ are connected with an edge if and only if the one is resulted from the other by exchanging the positions of two different integers.

How can we calculate the number of edges of the graph $G$ ?

We have $\frac{11!}{3!}$ (because we have 11 numbers but the number 9 is appeared three times) permutations, and so we have $\frac{11!}{3!}$ vertices, right? I haven't really understood how we can get the number of edges knowing that. Could you give me a hint?