Contar número de especiales en funciones

Question

Definimos una función en $[n] \times [n]$ $[n-2] \cup \{0\}$ siguiente, donde $[n] = \{1,2,3,\ldots ,n\}$,

$$f : [n] \times [n] \rightarrow [n-2] \cup \{0\}.$$

1) $f(x,x) = 0$.

2) $f(x,y) = f(y,x) > 0$, for $y ≠ x$.

3) $f(x,y) \leq \max(f(x,z),f(z,y))$ de todos $x,y,z$ pertenecer a $[n]$.

¿Cuántas funciones son posibles para un determinado $n$? He intentado mi mejor pero no soy capaz de conseguir cualquier cerca de la solución! Incluso se puede ver como un gráfico sin señas simple con números vértices, f que representan los pesos del borde. ¡Cualquier ayuda se agradece!

Answer 1

En primer lugar observamos que la condición 3) es trivialmente satisfecho dejando $z=x$ o $z=y$, como usuario de Marc van Leeuwen se indicó en los comentarios.

A continuación, se nos tenga en cuenta que para que el mapa sobre cada elemento de a $[n-2]\cup \{0\}$ debe tener un vacío preimagen en $[n]\times[n]$.

Por la condición 1), $0$ tiene un vacío preimagen que consta de todos los elementos en el formulario de $(x,x)$.

Condición 2) los estados $f(x,y)=f(y,x)\ne0$$x\ne y$, de modo que podamos identificar los elementos $(x,y)$$(y,x)$, ya que ambos deben estar en o ambos no estar en la preimagen de cualquier elemento en particular.

Ya tenemos $n\choose2$ elementos $(x,y)$ $[n]\times[n]$ tal que $x\ne y$, podemos reducir nuestro problema de contar el número de en las asignaciones a partir de un conjunto de $n\choose 2$ elementos de un conjunto de $n-2$ elementos.

Como se explica aquí: Calcular el número total de surjective funciones, este número está dado por $S({n\choose2},n-2)(n-2)!$ donde $S(x,y)$ son los números de Stirling del segundo tipo.