MHB How many edges does the graph have?

[mathmari]

Hey!

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? (Wondering)

 

[Opalg]

Hey!

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? (Wondering)

I would start by fixing a vertex $(\epsilon_1, \epsilon_2, \ldots, \epsilon_{11})$ and counting the number of edges connected to that vertex. There will be one such edge for each transposition of the form $(\epsilon_i, \epsilon_j)$, where $i\ne j$ and $\epsilon_i$, $\epsilon_j$ are not both equal to $9$.

If there are $N$ such transpositions then $N$ will be the same for each vertex, so the total number of endpoints of edges will be $\dfrac{11!N}{3!}$. Since each edge has two endpoints, the total number of edges is then $\dfrac{11!N}{2\cdot3!}$.

 

[mathmari]

I would start by fixing a vertex $(\epsilon_1, \epsilon_2, \ldots, \epsilon_{11})$ and counting the number of edges connected to that vertex. There will be one such edge for each transposition of the form $(\epsilon_i, \epsilon_j)$, where $i\ne j$ and $\epsilon_i$, $\epsilon_j$ are not both equal to $9$.

If there are $N$ such transpositions then $N$ will be the same for each vertex, so the total number of endpoints of edges will be $\dfrac{11!N}{3!}$. Since each edge has two endpoints, the total number of edges is then $\dfrac{11!N}{2\cdot3!}$.

Ah ok! And is N the number of transpositions of 9 numbers, i.e $\binom{9}{2}$ ? (Wondering)

 

[Opalg]

Ah ok! And is N the number of transpositions of 9 numbers, i.e $\binom{9}{2}$ ? (Wondering)

There are $11$ coordinates, and you can transpose any two of them provided that they are not both $9$s. So that gives you ${11\choose2} - {3\choose2}$ possibilities.

 

[mathmari]

There are $11$ coordinates, and you can transpose any two of them provided that they are not both $9$s. So that gives you ${11\choose2} - {3\choose2}$ possibilities.

I understand! Thank you! (Smile)