El trato con la cardinalidad de las clases de equivalencia de forma natural encaja en otra respuesta, que estoy tratando aquí.
Comenzamos con el binario caso. El primer paso en esta dirección, es notar que la matriz de adyacencia de un generalizado binario de Bruijn gráfica tiene una estructura muy simple:
$A_{ij}(\alpha) = \alpha_{2i} \delta_{2i \mod (B/q),j} + \alpha_{2i+1} \delta_{(2i+1) \mod (B/q),j}$
La matriz correspondiente/combinatoria Laplaciano es preparado a partir de receta
$\mathcal{L}(A) := \Delta(A1) - A$
donde $\Delta$ se refiere a cualquiera de los diversos diagonal operaciones (contexto, debería ser suficiente para determinar qué). La matriz de árbol teorema da que el número de árboles de expansión es cualquier director de menor importancia (todos son iguales):
$t(A) = \hat{\mathcal{L}}_{i,i}(A), \quad \forall i$.
No parece ser la pena de trabajo de una fórmula explícita para un determinante de la $k$ genéricos, incluso con $q = 2$. Un argumento clave el apoyo a este pesimismo es que cualquier finito Euleriano (por lo tanto, fuertemente conectado) dimgraph puede ser incrustado en algunos generalizada de Bruijn gráfica (que se acaba de tomar un camino de Euler para ver esto). En el ejemplo $q = 2$, $k = 4$ tenemos
$\hat{\mathcal{L}}_{B,B}(\alpha) = \alpha_1 \alpha_7 (\alpha_8 + \alpha_9)(\alpha_{12} + \alpha_{13})(\alpha_2 \alpha_5 \alpha_{11} + \alpha_3 \alpha_4 \alpha_{10} + \alpha_3 \alpha_4 \alpha_{11} + \alpha_3 \alpha_5 \alpha_{11})$
y esto toma varias páginas para derivar a mano con la expansión de los menores. No es difícil ver que no hay ninguna manera de llevar a cabo la fila o columna de permutaciones para convertir la matriz en bloque diagonal de la forma (excepto en los casos degenerados), y, en el menor expansión suficiente términos probablemente de los cultivos para producir (en el mejor), una victoria Pírrica. Para casos especiales en los que un gran conjunto de términos que poseen las simetrías se puede establecer a cero, la búsqueda de una fórmula podría ser fructífero: sin embargo, no vamos a perseguir cualquier línea aquí.
La MEJOR teorema establece que el número de etiqueta de Euler en circuitos de Bruijn clase de equivalencia está dada por la MEJOR función
$f_{BEST}(\alpha) := t(\alpha) \cdot \prod_{i=0}^{B/q-1} (\deg_i(\alpha) - 1)!$
donde el vértice o grados (que son lo mismo) son los indicados. La evaluación de esta función rápidamente se vuelve muy exigente, como el número de evaluaciones y $k$ de aumento. El factorial términos sólo puede añadir a cualquier demandas computacionales esta función hace.
En realidad, las cosas se ponen aún peor: la etiqueta de Euler circuitos enumerados por el MEJOR función en una correspondencia uno a uno con los collares. La correspondencia es trivial para el periódico collares, por lo que la división de la MEJOR función por la obvia producto de factoriales no acaba de funcionar. La fórmula adecuada para el collar de la función es (como J. Jonsson señalado en el sci.de matemáticas.de investigación)
$f_{neck}(\alpha) := \sum_{d|\gcd \alpha}\frac{\phi(d) f_{BEST}(\alpha/d)}{d\cdot(\alpha/d)!}$
donde el phi de Euler de la función se indica y las funciones de las tuplas son definidos en el obvio (de las componentes). En lugar de una detallada de la prueba nos limitamos a ofrecer una breve explicación: para cada término de la suma, la $f_{BEST}(\alpha/d)$ contribución da el número de la etiqueta "divisor-Euler" circuitos con la correspondiente longitud; el factorial términos de la cuenta para eliminar las etiquetas. El $d$ término en el denominador representa la concatenación de estos "divisor-Euler" circuitos en un circuito de Euler. Finalmente, el phi de la función de cuentas por no equivalentes turnos entre estos diversos "divisor-Euler" circuitos.
Podemos pasar de aquí a obtener el p-ary MEJOR y collar de funciones. La matriz de adyacencia de un generalizada q-ario de Bruijn gráfica no es muy diferente que en el binario caso:
$A_{ij} = \sum_{\ell=0}^{q-1} \alpha_{qi+\ell} \delta_{(qi+\ell) \mod (B/q), j}$.
Es un ejercicio en la notación para mostrar que el Laplaciano es
$\hat{\mathcal{L}}_{ij}(\alpha) = \sum_{\ell = 0}^{q-1} \alpha_{qi+\ell}\left(\delta_{ij} - \delta_{(qi+\ell) \mod (B/q),j} \right)$
y el $q$-ary forma de collar de la función tiene el mismo formato que la versión binaria.
Como un ejemplo, considere el caso de $q = 2$: no es fácil conseguir que
$f_{BEST}(\alpha) = \frac{\alpha_1(\alpha_0 + \alpha_1)!(\alpha_1 + \alpha_3)!}{(\alpha_0 + \alpha_1)(\alpha_1 + \alpha_3)}$
y a partir de esto que
$f_{neck}(\alpha) = \frac{\alpha_1}{(\alpha_0 + \alpha_1)(\alpha_1 + \alpha_3)} \sum_{d|\gcd(\alpha_0, \alpha_1, \alpha_3)} \phi(d) \binom{\frac{\alpha_0 + \alpha_1}{d}}{\frac{\alpha_1}{d}}\binom{\frac{\alpha_1 + \alpha_3}{d}}{\frac{\alpha_1}{d}}$.
Para tomar el ejemplo más, volvamos a fijar la longitud de la palabra a los 16 años y calcular la distancia. Calculamos no trivial de valores de el collar de la función sobre la $\alpha_0$-$\alpha_1$ plano de $0 \le \alpha_0 \le 14$$1 \le \alpha_1 \le 7$:
4 7 4
22 56 75 56 22
42 126 210 245 210 126 42
43 120 212 280 309 280 212 120 43
22 55 90 120 140 147 140 120 90 55 22
7 12 17 20 23 24 25 24 23 20 17 12 7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Observe también que el collar de la función es igual a la unidad para $(\alpha_0, \alpha_1) = (0, 0)$, $(0, 8)$, y $(16, 0)$.
