Contar los subconjuntos de celosía puntos

Question

Deje $n\ge 2$, y considerar el conjunto de $\binom{n}{2}$ celosía puntos en el interior del triángulo con vértices $(0,0)$, $(0,n+1)$ y $(n+1,n+1)$. Para $r\le \binom{n}{2}$, vamos a $f(n,r)$ el número de maneras en que podemos formar un subconjunto de cardinalidad $r$ de manera tal que el conjunto de $x$-coordenadas de la rejilla de puntos en el subconjunto es disjunta de la serie de $y$-coordenadas.

Por ejemplo, si $n=r=5$, uno de esos subconjunto es $\{(1,2),(1,4),(1,5),(3,4),(3,5)\}$.

¿Qué es una forma cerrada para $f(n,r)$?

Algunos de los resultados preliminares creo que puedo probar:

$$f(n,1)=\binom{n}{2}\\f(n,2)=\begin{bmatrix}n\\n-2\end{bmatrix}\\f\left(n,\left\lfloor\frac{n^2}{4}\right\rfloor\right)=\begin{cases}1&\text{if $n$ is even}\\2&\text{if $n$ is odd}\end{cases}\\f(n,r)=0\quad\text{for }r>\left\lfloor\frac{n^2}{4}\right\rfloor$$

donde los corchetes indican los números de Stirling de primera especie. No estoy tan seguro acerca de los siguientes resultados: $f(4,3)=7,\;f(5,3)=55,\;f(6,3)=240$.

Esta pregunta está motivada por abelian de la matriz de los grupos generadores de la forma $A_{ij}=I_n+E_{ij}$, $j>i$, donde $E_{ij}$ $n\times n$ matriz con un $1$ $ij$th entrada y $0$'s en otros lugares. Dichos generadores se de a pares conmutan si y sólo si sus índices de formar un subconjunto de celosía puntos como se describe en el problema anterior.

Answer 1

Esta es una prueba en la determinación de $p(n,3)$. Podemos organizar los juegos en orden no decreciente de primera coordenadas, y romper el conde en cuatro de los casos.

Si todos los primeros coordenadas son iguales, entonces tenemos conjuntos de $(a,x),(a,y),(a,z)$ y el suborden de modo que $x<y<z$, por lo que el $a<x<y<z$ dar la cuenta como el número de cuatro elemento de subconjuntos de a $\{1,...,n\}$, lo $\binom{n}{4}$ para este tipo de

Si tenemos dos primeras coordenadas entre los tres, puede ser que los más pequeños se "dobló", o la más grande. En el caso de la primera coordenadas $a,a,b$ $a<b$ el recuento de triples $(a,x),(a,y),(b,z)$ es de escoger cualquier $z$ sobre $b$ $n-b$ formas para que, y los números de $x,y$ deben ser distintos y elegido por encima de $a$, pero no permitiendo $b$ como una opción, por lo que no se $\binom{n-a-1}{2}$ maneras de hacerlo. Así que para la "aab" caso vamos a suma $$(n-b)\binom{n-a-1}{2}.$$

Un análisis similar para el caso de $(a,x),(b,y),(b,z)$ muestra deberíamos suma $$\binom{n-b}{2}(n-a-1).$$ Ambos de estas sumas están en el mismo rango de $1 \le a < b \le n-1,$ y juntos contribuite la siguiente cuenta: $$\frac{n(n-1)(n-2)(n-3)(2n-3)}{24}.$$

Por último tenemos el caso en el que todas las tres primeras coordenadas son distintos. Dicen que se $a,b,c$$a<b<c$, luego los triples $(a,x),(b,y),(c,z)$ puede ser elegido en $(n-c)(n-b-1)(n-a-2)$ formas, las sustracciones de $1$ o $2$ tomados en cuenta para el segundo coordenadas no se entre $a,b,c$. Cuando el conteo para este caso, el resultado es $$\frac{n(n-1)(n-2)^2(n-3)^2}{48}.$$

Hasta un total de todos los casos da la fórmula para $p(n,3)$ $$p(n,3)=\frac{n(n-1)(n-2)(n-3)(n^2-n+2)}{48}.$$ Esto le da, para el primer par de valores más allá de los 3, los mismos resultados $7,55,240$ señaló Jared en el post.