Número de árboles con un lado fijo

Question

Considerar que un vértice situado $[n]$. Por el teorema de Cayley allí hay árboles de $n^{(n-2)}$ $[n]$, pero cómo puede uno cuenta a continuación ligeramente modificado versión:

¿Cuál es el número de árboles en los vértices de $[n]$ donde el % de borde $\{1,2\}$definitivamente está contenido en los árboles?

Answer 1

Realmente podemos hacerlo directamente del teorema de Cauchy, sin hacer uso de una prueba de este resultado.

Por cada $e=\{k,\ell\}\in[n]$ $k\ne\ell$ $S_n(e)$ es el número de árboles en $[n]$ que contienen el borde $e$, que $e_0=\{1,2\}$ y que $S_n=S_n(e_0)$; claramente $S_n(e)=S_n$ % todo $e\in E$, donde $E$ es el conjunto de posibles aristas. Entonces

$$\sum_{e\in E}S_n(e)=\binom{n}2S_n$$

cuenta cada árbol en $[n]$ $n-1$ veces, una vez para cada uno de sus bordes. Hay árboles de $n^{n-2}$ $[n]$, así

$$\binom{n}2S_n=(n-1)n^{n-2}\;,$$

y

$$S_n=2n^{n-3}\;.$$

Answer 2

Parece que usted puede ajustar esta prueba.

En primer lugar, denotamos por a $S_n$ el número de árboles con uno de sus bordes fijos, y luego seguimos, como contar el número de maneras en la orientación de los bordes puede ser añadido a la forma de árboles de raíces donde su borde se agrega por primera vez. Como en la prueba original, se puede recoger la raíz en $n$ formas, y añadir los bordes en $(n-2)!$ permutaciones (la diferencia es que añadimos el borde de la primera). Llegamos a $S_n n(n-2)!$ secuencias.

En segundo lugar, vamos a añadir bordes, uno por uno, pero vamos a empezar con su borde (que ya está seleccionado). La única cosa que tenemos que elegir es su dirección. Entonces, vamos a continuar normalmente con el resto, es decir, si hay $k$ bosques, podemos elegir el punto de partida en $n$ formas (cualquier vértice y el punto final en $(k-1)$ (sólo las raíces). Cuando se multiplica juntos podemos conseguir (de manera similar a la prueba original)

$$ 2\prod_{k=2}^{n-1}n(k-1) = 2n^{n-2}(n-2)!$$

Comparando los dos tenemos

$$S_n n (n-2)! = 2n^{n-3}n(n-2)!$$

por lo tanto

$$S_n = 2n^{n-3}.$$

Espero que esta ayuda ;-)

Answer 3

Lema de 6 en este trabajo da un resultado más fuerte: el número de marcado que abarca árboles en $n$ vértices que contiene cualquier bosque fijo. En el caso de un solo borde de bosque, la fórmula se simplifica a $2n^{n-3}$.