Conteo de bijections satisfacer dada la desigualdad

Question

Dado dos conjuntos $$A=\{a_{1},a_{2},\cdots,a_{m}\},B=\{b_{1},b_{2},\cdots,b_{m}\}$ $ donde $$a_{i}<b_{i}<a_{i+1}<b_{i+1},i=1,2,\cdots,m-1$ $ y el $$ de la función g (a, b) =\begin{cases} 1&a>b\\ 0&a\le b \end{casos} $$ se espera encontrar el número de bijections $f:A\to B$ satisfacer la desigualdad $$2\sum_{i=1}^{m}g(a_{i},f(a_{i}))>m$ $

Mi intento: $$a_{i}>f(a_{i})\,\Longrightarrow g(a_{i},f(a_{i}))=1$ y $$a_{i}\le f(a_{i})\,\Longrightarrow g(a_{i},f(a_{i}))=0$ $ y que es lo que he podido conseguir.

Gracias por su ayuda.

Answer 1

Nota: La pregunta es en realidad una variante generalizada de la Tian Ji carreras de caballos problema. Un reciente artículo en Arxiv trata, precisamente, con esta pregunta (el "ganador" de los valores). El enfoque que se presenta a continuación es un poco diferente.

---

En primer lugar, vamos a simplificar los términos un poco. El bijection $f:A\to B$ puede ser sustituido por bijection $h:\{1,\ldots,m\}\to\{1,\ldots, m\}$ define mediante la relación de $f(a_i)=b_{h(i)}$. Entonces, podemos hacer la siguiente observación: $$g(a_i,f(a_i)) = 1 \Leftrightarrow a_i > f(a_i) \Leftrightarrow a_i > b_{h(i)} \Leftrightarrow i > h(i)$$

Si $\mathcal{D}(h)$ indica el número de valores de $1\leq i\leq m$ tal que $h(i)<i$, estamos buscando el número de permutaciones de satisfacciones $\mathcal{D}(h)>m/2$. Pues resulta que (la prueba se puede encontrar en el artículo mencionado anteriormente, no es demasiado difícil, aunque), el número de bijections $h$ tener $D(h)=k$ es exactamente igual al número de Euler $$E(m,k)=\sum_{j=0}^k (-1)^j\binom{m+1}{j}(k+1-j)^m$$ Since Eulerian numbers have symmetry $E(m,k)=E(m,m-1-k)$ and their sum over all values of $k$ is equal to $m!$ (the total number of bijections on $m$ elementos), podemos evaluar el deseado contar como $$\begin{eqnarray} \sum_{k>m/2} E(m,k) & = & \frac{1}{2}\left(\sum_{k>m/2} E(m,k)+\sum_{k < (m/2)-1}E(m,k)\right) \\ & = & \frac{1}{2}\left(m! - \sum_{(m/2)-1\leq k \leq (m/2)} E(m,k)\right) \\ & = & \begin{cases} \frac{1}{2}m! - E\left(m,\frac{m}{2}\right) & \mbox{for %#%#% even}\\ \frac{1}{2}m! - \frac{1}{2}E\left(m,\frac{m-1}{2}\right) & \mbox{for %#%#% odd}\\ \end{casos} \end{eqnarray}$$

Answer 2

Sólo una solución parcial, por ahora.

Una reformulación del problema es la siguiente:

Encontrar el número de $\sigma\in S_m$ tal forma que: $$ 2\cdot\left|\{i\in [1,m]: i>\sigma(i)\}\right| > m.$$

Decimos que $c(\sigma) = \left|\{i\in [1,m]: i>\sigma(i)\}\right|$ es el encargado de $\sigma$.

Claramente, si nos factor de $\sigma$ en ciclos disjuntos $\rho_1,\ldots,\rho_k$, tenemos que el precio es aditivo:

$$ \sigma = \rho_1\cdot\ldots\cdot \rho_k,\qquad c(\sigma)=\sum_{i=1}^{k}c(\rho_i).$$

Por otra parte, es trivial que la carga de un ciclo es menor que la longitud, $c(\rho_i)\leq l(\rho_i)-1,$ y que un ciclo de carga máxima iff puede escrita en una disminución de la forma: $$c\left((4,\;3,\;2,\;6,\;5)\right)=c\left((6,\;5,\;4,\;3,\;2)\right)=4.$$ Denotando como $$ N(m) = \left|\{\sigma\in S_m: c(\sigma)>\frac{m}{2}\}\right| $$ tenemos $N(1)=N(2)=0,N(3)=N(4)=1,N(5)=27$. Por otra parte, si $\sigma$ es una involución ($\sigma^2=e$) tenemos a $c(\sigma)\leq\frac{m}{2}$; por otro lado, si $\sigma$ no tiene puntos fijos, tenemos: $$ c(\sigma)+c(\sigma^{-1}) = m, $$ por lo tanto, si $m$ es impar, exactamente una permutación entre el $\sigma$ $\sigma^{-1}$ tiene un cargo superior a $m/2$.

Tris trivialmente da: $$ N(2k+1) \geq \left\lfloor\frac{(2k+1)!}{2e}\right\rfloor. $$