(Escriba $\langle S\rangle$ para el submonoid generado por $S$.)
Deje $A$ denotar un conjunto y $S$ denotar un subconjunto de a $A^*$ equipada con un distinguido bien el pedido. Deje $M$ denotar un monoid y $f : S \rightarrow M$ denotar una función. A continuación, obtenemos una función correspondiente $f' : \langle S\rangle \rightarrow M,$ define recursivamente como sigue. En primer lugar, $f'(1) = 1$. En segundo lugar, para todos los $x \in S$$y \in \langle S \rangle$, si para todas las $x' \in S$ $y' \in \langle S \rangle$ satisfacción $x'y' = xy$ tenemos $x \leq x'$, $f'(xy) = f(x) f'(y).$ Que tal vez un poco difícil de entender, así que permítanme darles un ejemplo.
Deje $A = \{b,c\}$$S = \{bc \leq b \leq c\}$. Deje $M = \{a,b,c\}^*$ y definir ese $f:S \rightarrow M$ ser dada por $$bc \mapsto a, b \mapsto b, c \mapsto c.$$ Then the corresponding function $$f' : \langle bc,b,c\rangle \rightarrow M$$ just has the effect of replacing each subword of the form $bc$ with the symbol $un$. For example: $$f'(bbcc) = f(b)f'(bcc) = f(b)f(bc)f'(c) = f(b)f(bc)f(c)f'(1) = f(b)f(bc)f(c) = bac$$
(La motivación inicial para esta pregunta es que la función de $f'$ que reemplaza $bc$'s $a$' surgió en forma natural, mientras que la resolución de un problema sobre el binomio de caminos en la última combinatoria de asignación.)
Ahora, al pasar de $f : S \rightarrow M$ $f' : \langle S \rangle \rightarrow M$tipo de looks, como la contigüidad, en el sentido de la categoría de teoría. No he sido capaz de formalizar este. Así:
Pregunta. Es esta una contigüidad? Si es así, ¿cuáles son las categorías relevantes y functors?
(Menor duda: en monoid teoría, ¿ qué estoy denotando $f'$ tiene un nombre?)
Adenda. La motivación detrás de $f'$ fue solicitados, así que aquí está.
Deje $A_k$ denota el conjunto de todos los $k$-longitud de las palabras $x$ en el alfabeto $\{U,D\}$ tal que para cada prefijo $p$ $x,$ tenemos $|p|_U \geq |p|_D$. Por ejemplo, $UUDD \in A_4$ tiene esta propiedad, debido a que los prefijos de esta palabra son $$\{1,U,UU,UUD,UUDD\}$$ and it can be seen that there's always at least as many $U$'s as $D$'s. (This can be visualized as a zig-zag pattern ($U$ = up and one step to the right, $D$ = down and one step to the right) in $\mathbb{R}^2$ that starts at the origin and never goes below the $$x-eje).
Bien. He aquí algunas cifras: $$|A_1| = |\{U\}| = 1$$
$$|A_3| = |\{UUU;UUD,UDU\}| = 3$$
$$|A_5| = |\{UUUUU;UDUUU,UUDUU,UUUDU,UUUUD;UDUDU,UUDDU,UDUUD,UUDUD,UUUDD\}| = 10$$
El problema es demostrar que:
Teorema. Si $k$ es impar, entonces $|A_k| = \frac{1}{2}\binom{k+1}{(k+1)/2}.$
Nuestra solución fue la siguiente.
Deje $B_k$ denota el conjunto de todos los $k$-longitud de las palabras $x$ en el alfabeto $\{U,D\}$ tal que $|x|_U = |x|_D$$x_0 = D$. (Esto puede ser visualizado como una longitud de $2k$ patrón de zigzag que se inicia en el origen, cuyo primer paso es $D$ y que termina en algún lugar de la $x$-eje).
Para $k$ impar, $B_k$ está vacía.
Pero si $k$ es incluso, tenemos:
$$|B_k| = \frac{1}{2}\binom{k}{k/2}$$
Ahora vamos a $k$ denotar un fijo, pero arbitraria número impar. Vamos a definir una función $$\varphi:A_k \rightarrow B_{k+1}.$$ If this function $f$ puede ser demostrado ser un bijection, entonces podemos argumentar de la siguiente manera:
$$|A_k| = |B_{k+1}| = \frac{1}{2}\binom{k+1}{(k+1)/2}$$
lo que demuestra el resultado.
De manera informal, nuestra propuesta de $\varphi$ fue de la siguiente manera:
- Considere la posibilidad de $x \in A_k$.
- Cambio $x$ por que se adhiere a la $D$ símbolo a la izquierda. Tenga en cuenta que el resultado es necesariamente un elemento de $A_{k+1}$, debido a la rareza de $k$.
- Ahora ir a través y empezar a cambiar las $U$'s en $D$'s de izquierda a derecha, pero con la condición de que los patrones de la forma $UD$ se omiten; de no ser tocado. Pare cuando el número de $D$s'es lo suficientemente grande que es igual al número de $U$'s, que es ahora menor.
- Llame al resultado $\varphi(x)$.
Aquí tenemos una ilustración de $\varphi$$k=5$, por ejemplo. La primera flecha indica que se adhiere a la $D$ al inicio de la palabra, y la segunda flecha indica el resto del proceso.
$$UUUUU \mapsto DUUUUU \mapsto DDDUUU$$
$$UUUUU \mapsto DUDUUU \mapsto DUDDUU$$
$$UUUUU \mapsto DUUDUU \mapsto DDUDUU$$
$$UUUUU \mapsto DUUUDU \mapsto DDUUDU$$
$$UUUUU \mapsto DUUUUD \mapsto DDUUUD$$
$$UUUUU \mapsto DUDUDU \mapsto DUDUDU$$
$$UUUUU \mapsto DUUDDU \mapsto DUUDDU$$
$$UUUUU \mapsto DUDUUD \mapsto DUDUUD$$
$$UUUUU \mapsto DUUDUD \mapsto DUUDUD$$
La pregunta entonces es: ¿cómo podemos definir formalmente $\varphi$?
Deje $A$ denota el conjunto $\{U,D\}$ $S$ denotar el poset $\{UD\leq U\leq D\}$. Definir $f : S \rightarrow \{A,U,D\}^*$ como sigue: $$f(UD) = A,f(U)=U,f(D)=D$$
A continuación, obtenemos una función correspondiente $$f' : \{U,D\}^* \rightarrow \{A,U,D\}^*$$ by applying the construction under question. It follows that $f'$ has the effect of removing $UD$ patterns and replacing them with $UN$'s. For example: $$f'(DUDUUU) = Df'(UDUUU) = DAf'(UUU) = \cdots = DAUUUf'(1) = DAUUU.$$ Once we've got the word in this form, it becomes easy to define the function that replaces $U$'s with $D$'s without touching $UD$'s, because we've replaced all the $UD$'s with $$'s. Omitting certain details that the reader can easily work out for themselves, the full chain for $UDUUU \en A_5$ termina buscando algo como esto:
$$UDUUU \mapsto DUDUUU \mapsto DAUUU \mapsto DADUU \mapsto DUDDUU$$
