Número de coincidencias en n nodos

Question

Estoy tratando de encontrar el número de coincidencias que son posibles en los gráficos $G=(V,E)$ con $V = [n] = \{0, ..., n-1\}$

Dejemos que $a_n$ sea el número de coincidencias en $[n]$ . Entonces pienso calcular $a_n = \Sigma^{n}_{k = 0} b_k$ con $b_k$ siendo el número de coincidencias en $[n]$ con n nodos.

Entonces $b_k$ es $0$ para todo lo que no sea k, ya que el número de nodos en un emparejamiento tiene que ser par.

Para k. pares: De los n nodos quiero seleccionar k nodos para la coincidencia. Para que haya $\frac{n!}{(n-k!)}$ formas de ordenar en los k nodos seleccionados. (n elementos en la primera posición, n-1 en la segunda, ..., n-k+1 en la k-ésima posición)

Los 2 primeros elementos forman una arista, los 2 siguientes también y así sucesivamente. Estos forman el emparejamiento. Pero no importa si es {a,b} o {b,a} , por lo que dividiría por $2^{k/2}$

Además, no importa si el borde se produce en la primera posición o en la última, por lo que volvería a dividir por $(k/2)!$ para que como hay las opciones de ordenar los bordes.

Sin embargo, esto no supone una expresión compacta y agradable para utilizarla en una función generadora. El tipo de coeficiente binomial me hace pensar, si utilizar el teorema del binomio, pero no coincide con esto.

Answer 1

Llego a la misma conclusión, utilizando el hecho de que el número de coincidencias perfectas en el gráfico completo $K_{2n}$ es $$\frac{(2n)!}{n!\ 2^n}$$

Esto se puede demostrar por inducción. Si $a_n$ es el número de coincidencias perfectas en $K_{2n}$ entonces, puedes elegir un vértice $u$ y lo empareja con (2n-1) vértices, y luego encuentra un emparejamiento perfecto en $K_{2n-2}$ . Por lo tanto, $a_n=(2n-1)a_{n-1}$ y $$a_n=(2n-1)(2n-3)\ldots 1 = \frac{(2n)!}{(2n)(2n-2)\ldots 2}= \frac{(2n)!}{2^n \ n!}$$

Entonces el $T_n$ número total de coincidencias en $G$ es (con $\#K_{2k}$ el número de subgrafos completos en $2k$ vértices entre $n$ ) \begin {align*} T_n &= \sum_ {k=1}^{ \lfloor n/2 \rfloor K_{2k} \cdot \frac {(2k)!}{k! \ 2^k} \\ &= \sum_ {k=1}^{ \lfloor n/2 \rfloor } \binom {n}{2k} \cdot \frac {(2k)!}{k! \ 2^k} \\ &= \sum_ {k=1}^{ \lfloor n/2 \rfloor } \frac {n!}{2^k\ k! \ ¡(n-2k)! \\ \end {align*}

Y llego a la conclusión de que entonces tú. Sin embargo, no creo que podamos hacerlo mucho mejor. Sigo buscando