Es la Relación Asociativa Operaciones Binarias para Todas las Operaciones Binarias en un Conjunto de $n$ Elementos, en General, Pequeña?

Question

Empecé a pensar en el número de asociativa (binario) operaciones en un conjunto con $n$ elementos de hoy en día. Buscando en internet he encontrado este documento que indica que sólo la $113$ de los posibles $19,683$ operaciones en un período de tres elementos conjunto de satisfacer la asociación. Por eso, $50\%$ de las operaciones binarias en un elemento del conjunto de satisfacer la asociación, y a menos de $0.6\%$ de todas las operaciones binarias en un conjunto de tres elementos satisfacer asociación. Para un $n$-element set, donde $n$ denota un número natural, es la relación de $R_{n}=A_{n}/B_{n}$, el número asociativo de las operaciones binarias $A_{n}$ en el número de todas las operaciones binarias $B_{n}$, en general de pequeño? No me refiero a las siguientes preguntas de forma equivalente, pero ya que parecen más concretamente responsable, en principio, no

$$ \lim_{n \to +\infty} \frac{A_{n}}{B_{n}} = 0 ? $$

También, se $F : n \to R_{n}$ un monótonamente decreciente de la función?

Algunos Antecedentes de la Pregunta: En su Álgebra Lineal Problema de la Libreta de 1995 en la p. 6 Paul Halmos escribe "La comúnmente aceptada de las actitudes hacia la ley conmutativa y la asociativa de la ley son diferentes. Muchos en la vida real de las operaciones no conmutan; la comunidad matemática ha aprendido a vivir con ese hecho e incluso para disfrutar de ella. Las violaciones de la ley asociativa, por otro lado, suelen ser considerados por los especialistas". Para todos los que me conocen, Halmos podría haber escrito que para motivar el estudio de Álgebra Lineal y no literalmente significa lo que parece decir. Pero, si él quiere decir lo que parece decir, y si $F : n \to R_{n}$ es monótonamente decreciente, o $R_{n}$ es generalmente pequeño, creo que hay algo mal con lo que Halmos dice, puesto que no asociativo operaciones parecen tan comunes que uno puede así disfrutar de ellos.

Answer 1

Después de obtener un Doctorado en Har-cago, Allie consiguió un trabajo de la configuración de la diaria Operación Binaria Mesa en el set $\{1,2,\dots, n\}$.

Cada día Allie iniciado por la elección de $1 \circ 1$ al azar, con todas las opciones igualmente probables. Lo $1 \circ 1$ resultó ser, es decir $x$, Allie entonces eligió al azar el valor de $x \circ 1$ entre las opciones legales. (Por supuesto, si por suerte resultó que $x=1$, $x \circ 1$ ya estaba determinado.)

Sería inútil tratar de describir el resto de Allie del procedimiento, ya que tendían a cambiar de día a día. Pero los dos primeros pasos fueron siempre como se describe.

Después de los dos primeros pasos, Allie siempre se comprueba si la operación fue (hasta ahora) asociativa. Si la primera opción era la $1\circ 1=1$ (probabilidad: $1/n$) hemos automático de asociatividad, es decir, la asociatividad con una probabilidad de $1$.

De lo contrario (probabilidad: $1-1/n$), si $1\circ 1=x \ne 1$, la operación es asociativa precisamente si $x \circ 1=1\circ x$. Para cualquier $x \ne 1$, esta probabilidad es $1/n$. Así que la probabilidad de que $(1\circ 1)\circ 1=1\circ(1\circ 1)$ es $$\left(\frac{1}{n}\right)(1) +\left(1-\frac{1}{n}\right)\left(\frac{1}{n}\right)$$ Esto se simplifica a $(2n-1)/n^2$.

Pero esta probabilidad es $\ge A_n/B_n$ donde $A_n$ $B_n$ se definen como en la posterior. Así $$\frac{A_n}{B_n} \le \frac{2n-1}{n^2}$$

En particular, $A_n/B_n$ enfoques $0$ $n$ se hace grande.

La desigualdad que hemos obtenido es apretado en la $n=1$, pero absurdamente más débil que la verdad para un gran $n$. Uno podría producir mucho mejores estimaciones, y sin duda hay incluso una modesta de la literatura sobre el tema.

Answer 2

El número asociativo de las operaciones binarias en un $n$-elemento del conjunto es dado en el http://oeis.org/A023814

Tal vez usted podría seguir los enlaces en esa página y el informe de nuevo a nosotros.