Supongamos que en un $n \times n$ cuadrado de la cuadrícula, ponemos bordes, como se nos haría normalmente para formar la unidad de plazas (horizontal, vertical de los bordes de cada vértice.) La pregunta es: si quitamos $k$ puntos, ¿cuántas maneras hay de hacer esto de modo que la gráfica está conectado? (Vamos a estar de acuerdo para llamar a la gráfica resultante después de la eliminación de $k$ vértices de un extremo del gráfico.)
Para facilitar la discusión, deja que los vértices ser dada por Cartesiano de coordenadas, a partir de con $(0,0)$ y van hasta $n-1$ $x-y$ eje (primer cuadrante.)
Para dejar en claro cuál es el problema:
Si un vértice es eliminado, por lo que es en cada extremo conectado a ella.
no importa qué tipo de gráfico es el de la izquierda después de que el vértice de la mudanza. Tal vez para aclarar este punto: decir que nos están quitando $n^2-1$ vértices. Luego hay $n^2$ maneras de hacer esto [los vértices están marcados.]
El orden en el que los vértices son eliminados no importa.
Debe quitar, precisamente, $k$ vértices, por lo que no le estoy pidiendo a contar la eliminación de $j \leq k$ vértices.
¿Se conocen los métodos conocidos para este tipo de conteo?
el siguiente es parte del trabajo que he hecho hasta ahora:
Si $k=2$$n>2$, razoné que el número de maneras es $\binom{n^2}{2}-4$, ya que siempre se puede "cortar una esquina."
el siguiente es incorrecto: sin Embargo, la situación cambia para $k=3$, ya que hay diferentes maneras de tomar una esquina que sale de un vértice aislado (o, incluso, $3$ vértices.) En particular, me di cuenta de que $3$ formas de cortar una esquina, así que podemos aprovechar $\binom{n^2}{3}-4\cdot 4$ como el posible número de maneras.
Es razonable anticipar explícita o fórmula recursiva, en general?
Actualización parece como si sólo he estado considerando los casos donde los vértices son removidos podría ser "estirado", o que cada una de las opciones de vértice se encontraba junto a uno de los ya elegidos (vertical, horizontal o diagonal.) De lo contrario, parece molesto que podría sección "off" en una esquina, por ejemplo por la eliminación de $(1,0)$$(0,1)$, pero luego la elección de un cualquier otra colección de vértices, con el fin de formar una desconectado final gráfico. En consecuencia, a pesar de que yo estoy pidiendo que precisamente los vértices de ser eliminado, se debe considerar $k=2$ en este caso, ya que para cada forma de desconectar el gráfico también ha $n^2-3$ opciones, así que por $k=3$, también se debe restar off $(\binom{n^2}{2}-4)\cdot (n^2-3)$ así, para obtener: $\binom{n^2}{3}-4\cdot 4-(\binom{n^2}{2}-4)\cdot (n^2-3)$ maneras sin necesidad de desconectar el gráfico. ¿Esto parece correcto? suspiro.
siéntase libre de editar las etiquetas, no tengo un buen sentido de lo que podría ser apropiado para este problema.
