Considere $n$ entidades $x_i$ que puede tener $m$ diferentes propiedades binarias $P_j$ . Existen $2^{n\cdot m}$ formas en que las propiedades pueden atribuirse a las entidades. En $n = m = 3$ la tabla de atribución puede tener este aspecto:
$$\begin{array}{c|c|c|c} & P_1 & P_2 & P_3 \\ \hline x_1 & 1 & 0 & 0 \\ \hline x_2 & 0 & 1 & 1 \\ \hline x_3 & 1 & 1 & 0 \end{array}$$
Si despreciamos el orden de las entidades, dos tablas de atribución son iguales cuando se obtiene una a partir de la otra mediante alguna permutación de las entidades (filas). ¿Cuántas clases de equivalencia de atribuciones existen?
Para $n = m = 2$ He descubierto que el número de atribuciones no equivalentes es
$$a(2,2) = 1 + 2 + 4 + 2 + 1 = 10$$
avec $a_0 = a_4 = 1$ siendo el número de formas no equivalentes de colocar 0 ó 4 entradas en la tabla 2x2, $a_1 = a_3 = 2$ el número de entradas de colocación 1 ó 3, y $a_2 = 4$ el número de entradas de colocación 2.
Para $n=m=3$ la suma empieza y acaba igual: $a_0 = a_9 = 1$ , $a_1 = a_8 = 3$ , pero ya estoy atascado para encontrar $a_2$ es decir, el número de formas no equivalentes de colocar 2 entradas en la tabla 3x3. Pero supongo que $9$ .
Así que uno podría tender a adivinar que $a(n,n) = 2\cdot \sum_{k=0}^{\lfloor n^2/2\rfloor} n^k$ (para impar $n$ ), pero esta cifra crece demasiado rápido.
Así que mi pregunta es cómo $a(n,n)$ o más generalmente $a(n,m)$ pueden derivarse sistemáticamente? ¿Se trata de un caso de generación de funciones?
Añadido : Esta es la tabla de $a(n,m)$ para $n,m \leq 5$ :
La diagonal puede encontrarse aquí .
Añadido : Me pregunto cuántos bits se necesitan para representar una clase de equivalencia. Considere $n=m=5$ con 376.992 clases de equivalencia para cuya representación se necesitan al menos 19 bits (porque $2^{18} =262,144$ y $2^{19} = 524,288$ ). Al ser más verboso, es necesario especificar hasta cinco filas, y para cada fila un número $\leq 5$ los números suman $5$ . Así que necesitas $5 \cdot (5 + \lceil \log_2(5)\rceil) = 40$ bits en esta representación que da la información esencial.
Añadido : El número $a(n,m)$ es también el número de clases de equivalencia de bipartitos $n \times m$ gráficos. También podría haber formulado la pregunta así, que habría sido mucho más breve.
