¿Cuántas proyecciones hay de un conjunto de tamaño n?

Question

Es bien sabido que el número de proyecciones de un conjunto de tamaño n a un conjunto de tamaño m es bastante más difícil de calcular que el número de funciones o el número de inyecciones. (Por supuesto, para las proyecciones asumo que n es al menos m y para las inyecciones que es como máximo m.) También es bien sabido que se puede obtener una fórmula para el número de proyecciones utilizando la inclusión-exclusión, aplicada a los conjuntos $X_1,...,X_m$ donde para cada $i$ el conjunto $X_i$ se define como el conjunto de funciones que nunca toman el valor $i$ . Esto da lugar a la siguiente expresión: $m^n-\binom m1(m-1)^n+\binom m2(m-2)^n-\binom m3(m-3)^n+\dots$ .

Llamemos a este número $S(n,m)$ . Me pregunto si alguien puede decirme sobre la asintótica de $S(n,m)$ . Una pregunta particular que tengo es la siguiente: para (aproximadamente) qué valor de $m$ es $S(n,m)$ ¿se maximiza? Es un pequeño ejercicio para comprobar que hay más proyecciones a un conjunto de tamaño $n-1$ que a un conjunto de tamaño $n$ . (Para ello, se calcula $S(n,n-1)$ explotando el hecho de que cada suryección debe golpear exactamente un número dos veces y todos los demás una vez). Así que el máximo no se alcanza en $m=1$ o $m=n$ .

Asumo que esto es conocido, pero una búsqueda en la web parece llevarme a la fórmula exacta. Una referencia sería genial. Una prueba, o un esquema de prueba, sería aún mejor.

Actualización. Debería haber dicho que la verdadera razón por la que me interesa el valor de m para el que se maximiza S(n,m) (para usar la notación de este post) o ¡m!S(n,m) se maximiza (para usar la notación más convencional en la que S(n,m) representa un número Stirling del segundo tipo) es que lo que me importa es el tamaño aproximado de la suma. La suma es lo suficientemente grande como para pensar que probablemente no me preocupe demasiado un factor de n, así que estaba preparado para estimar que la suma se encuentra entre el máximo y n veces el máximo.

Answer 1

Parece ser que el polinomio $P_n(x) =\sum_{m=1}^n m!S(n,m)x^m$ sólo tiene ceros reales. (Sé que es cierto que $\sum_{m=1}^n S(n,m)x^m$ sólo tiene ceros reales). Si esto es cierto, entonces el valor de $m$ maximizando $m!S(n,m)$ está dentro de 1 de $P'_n(1)/P_n(1)$ por un teorema de J. N. Darroch, Ann. Math. Stat. 35 (1964), 1317-1321. Véase también J. Pitman, J. Teoría Combinatoria, Ser. A 77 (1997), 279-303. Según la combinatoria estándar $$ \sum_{n\geq 0} P_n(x) \frac{t^n}{n!} = \frac{1}{1-x(e^t-1)}. $$ Por lo tanto, $$ \sum_{n\geq 0} P_n(1)\frac{t^n}{n!} = \frac{1}{2-e^t} $$ $$ \sum_{n\geq 0} P'_n(1)\frac{t^n}{n!} = \frac{e^t-1}{(2-e^t)^2}. $$ Dado que estas funciones son meromorfas con la menor singularidad en $t=\log 2$ , es rutinario calcular la asintótica, aunque no me he molestado en hacerlo.

Actualización. Es cierto que $P_n(x)$ tiene ceros reales. Esto se debe a que $(x-1)^nP_n(1/(x-1))=A_n(x)/x$ , donde $A_n(x)$ es un polinomio euleriano. Es se sabe que $A_n(x)$ sólo tiene ceros reales, y la operación $P_n(x) \to (x-1)^nP_n(1/(x-1))$ deja invariable la propiedad de tener real ceros reales.

Answer 2

La respuesta de Richard es corta, hábil y completa, pero quería mencionar aquí que también hay un enfoque de "variable real" que es consistente con esa respuesta; da límites más débiles al final, pero también dice un poco más sobre la estructura de la suryección "típica". Escribiré el argumento en un estilo "físico" algo informal, pero creo que se puede hacer riguroso sin un esfuerzo significativo.

Función de Tim $Sur(n,m) = m! S(n,m)$ obedece a la recurrencia fácilmente verificada $Sur(n,m) = m ( Sur(n-1,m) + Sur(n-1,m-1) )$ que al expandirse se convierte en

$Sur(n,m) = \sum m_1 ... m_n = \sum \exp( \sum_{j=1}^n \log m_j )$

donde la suma es sobre todos los caminos $1=m_1 \leq m_2 \leq \ldots \leq m_n = m$ en el que cada $m_{i+1}$ es igual a $m_i$ o $m_i+1$ ; se puede interpretar $m_i$ como el tamaño de la imagen del primer $i$ elementos de $\{1,\ldots,n\}$ . Si hacemos el ansatz $m_j \approx n f(j/n)$ para alguna función agradable $f: [0,1] \to {\bf R}^+$ con $f(0)=0$ y $0 \leq f'(t) \leq 1$ para todos $t$ y utilizar los cálculos estándar de entropía (fórmula de Stirling y sumas de Riemann, en realidad), obtenemos una contribución a $Sur(n,m)$ de la forma

$\exp( n \int_0^1 \log(n f(t))\ dt + n \int_0^1 h(f'(t))\ dt + o(n) )$ (*)

où $h$ es la función de entropía $h(\theta) := -\theta \log \theta - (1-\theta) \log (1-\theta)$ . Por lo tanto, al menos heurísticamente, el perfil óptimo proviene de la maximización de la función

$\int_0^1 \log(f(t)) + h(f'(t))\ dt$

sujeta a la condición de contorno $f(0)=0$ . (El hecho de que $h$ es cóncavo hará que este problema de maximización sea bonito y elíptico, lo que hace muy probable que estos argumentos heurísticos puedan hacerse rigurosos). La ecuación de Euler-Lagrange para este problema es

$-\frac{f''}{f'(1-f')} = \frac{1}{f}$

mientras que el límite libre en $t=1$ nos da la condición de contorno adicional de Neumann $f'(1)=1/2$ . La invariancia de traslación de la lagrangiana da lugar a una cantidad conservada; en efecto, multiplicando la ecuación de Euler-Lagrange por $f'$ e integrando se obtiene

$\log(1-f') = \log f + C$

que se resuelve fácilmente como

$f = \frac{1}{A} (1 - B e^{-At} )$

para algunas constantes A, B. La condición de contorno de Dirichlet $f(0)=0$ da $B=1$ la condición de contorno de Neumann $f'(1)=1/2$ da $A=\log 2$ Por lo tanto

$f(t) = (1 - 2^{-t}) / \log 2$ .

En particular $f(1)=1/(2 \log 2)$ que coincide con la respuesta de Richard de que el máximo se produce cuando $m/n \approx 1/(2 \log 2)$ . Para que coincida con la asintótica para $Sur(n,m)$ en la respuesta de Richard (hasta un error de $\exp(o(n))$ Necesito tener

$\int_0^1 \log f(t) + h(f'(t))\ dt = - 1 - \log \log 2.$

Y, afortunadamente, resulta ser así (tras un cálculo ligeramente tedioso).

Este cálculo revela más sobre la estructura de una suryección "típica" de n elementos a m elementos para m libre, aparte de que $m/n \approx 1/(2 \log 2)$ muestra que para cualquier $0 < t < 1$ la imagen de la primera $tn$ tiene una cardinalidad de aproximadamente $f(t) n$ . Si se fija $m$ en lugar de dejarlo libre, entonces se tiene una descripción similar de la suryección pero hay que ajustar el parámetro A (tiene que resolver la ecuación trascendental $(1-e^{-A})/A = m/n$ ).

Con un poco más de esfuerzo, este tipo de cálculo también debería revelar la distribución típica de las preimágenes de la suryección, y sugerir un proceso aleatorio que genere algo que esté dentro de o(n) ediciones de una suryección aleatoria.

También es interesante observar que la respuesta $m/n \approx 1/(2\log 2) = 0.72134\ldots$ encaja muy bien con el cálculo numérico de Kevin $f(1000)=722$ Así que ahora tenemos varias confirmaciones independientes de que esta es la respuesta correcta...

Answer 3

Esto se parece a los números Stirling del segundo tipo (hasta el $m!$ factor).

Este y este Los artículos se dedican específicamente a los números máximos de Striling. Parece que para grandes $n$ la expansión asintótica relevante es $$k! S(n,k)= (e^r-1)^k \frac{n!}{r^n}(2\pi k B)^{-1/2}\left(1-\frac{6r^2\theta^2 +6r\theta+1}{12re^r}+O(n^{-2})\right),$$ où $$e^r-1=k+\theta,\quad \theta=O(1),$$ $$B=\frac{re^{2r}-(r^2+r)e^r}{(e^r-1)^2}.$$

Answer 4

He encontrado este documento de Temme (disponible aquí ) que da una asintótica explícita pero algo complicada para el número de Stirling S(n,m) del segundo tipo, por los métodos aludidos en respuestas anteriores (funciones generadoras -> integral de contorno -> descenso más pronunciado)

Aquí está la asintótica (copiada de ese documento). Primero se establece

$t_0 := \frac{n-m}{m}$

y encuentra el número real positivo $x_0$ resolver la ecuación trascendental

$\frac{1-e^{-x_0}}{x_0} = \frac{m}{n}$

(se tiene la asintótica $x_0 \approx 2(1-m/n)$ cuando $m/n$ se acerca a 1, y $x_0 \approx n/m$ cuando $m/n$ es cercano a cero). Se define entonces

$A := \phi(x_0) - m t_0 + (n-m) t_0$

où

$\phi(x) := - n \ln x + m \ln(e^x - 1).$

(Nota: $x_0$ es el punto estacionario de $\phi(x)$ .) Se tiene una representación integral

$S(n,m) = \frac{n!}{m!} \frac{1}{2\pi i} \int e^{\phi(x)} \frac{dx}{x}$

donde la integral es un pequeño contorno alrededor del origen. El método del punto de equilibrio da entonces

$S(n,m) = (1+o(1)) e^A m^{n-m} f(t_0) \binom{n}{m}$

où

$f(t_0) := \sqrt{\frac{t_0}{(1+t_0)(x_0-t_0)}}$

y o(1) va a cero como $n \to \infty$ (uniformemente en m, creo).

En principio, ahora se puede aproximar $m! S(n,m)$ con una precisión de o(1) y calcular su máximo en tiempo finito, pero esto parece algo tedioso. Sin embargo, parece que el máximo se alcanza cuando $m/n = c+o(1)$ para alguna constante explícita $0 < c < 1$ .

EDIT: En realidad, está claro que el máximo se va a obtener en el rango $n/e \leq m \leq n$ asintóticamente, porque $m! S(n,m)$ es igual a $n! \approx (n/e)^n$ cuando $m=n$ y por otro lado tenemos el límite superior trivial $m! S(n,m) \leq m^n$ . Entre otras cosas, esto hace que $x_0$ y $t_0$ acotado, por lo que el término f(t_0) también está acotado y no tiene mayor importancia para la asintótica. Sin embargo, los otros términos siguen siendo exponenciales en n...

EDIT: También está la identidad

$\sum_{k=1}^n (k-1)! S(n,k) = (-1)^n Li_{1-n}(2)$

où $Li_s$ es el polilogaritmo función. Así que, hasta un factor de n, la cuestión es la misma que la de obtener una asintótica para $Li_{1-n}(2)$ como $n \to -\infty$ . Esto parece bastante factible (presumiblemente a partir de otro método de integración de contornos y de descenso más pronunciado), pero una búsqueda rápida de las asintóticas existentes no dio esto inmediatamente.

Answer 5

Si f es una suryección arbitraria de N sobre M, entonces podemos pensar que f particiona N en m grupos diferentes, cada grupo de entradas representando el mismo punto de salida en M. Los números Stirling del segundo tipo cuentan cuántas maneras de particionar un conjunto de elementos N en m grupos. Pero esto lo subestima, porque cualquier permutación de esos m grupos define una suryección diferente pero se cuenta igual. Hay m! permutaciones de este tipo, por lo que nuestro número total de proyecciones es

¡m! S(n,m)

Para ver los valores máximos, defina una secuencia S_n = n - M_n donde M_n es el m que alcanza el valor máximo para un n dado - en otras palabras, S_n es la "distancia del borde derecho" para el valor máximo. Las tablas generadas por ordenador sugieren que esta función es constante para 3-4 valores de n antes de aumentar en 1. Si esto es cierto, entonces la coordenada m que maximiza m S(n,m) está limitada por n - ceil(n/3) - 1 y n - floor(n/4) + 1.

No tengo pruebas de lo anterior, pero te da una conjetura con la que trabajar mientras tanto.