Contando el bit voltea

Question

Para $n, m \geq 1$, vamos a $\Lambda^{n,m}$ ser el conjunto de todos los $(n+m)$-cadenas de bits con exactamente $n$ ceros y $m$.

Por ejemplo, $\Lambda^{2,3} = \{00111, 11100, 10011, 11001, 01110, 01011, 01101, 11010, 10110, 10101 \}$.

Deje $b=b_1\ldots b_{n+m} \in \Lambda^{n,m}, b_i \in \{0, 1\} \forall i$. Definir $T(b)$ como el número de bits que se voltea ocurring en la cadena de $b$. (lo que quiero decir matemáticamente por "el número de bits-flips" es $T(b) = \sum_{i=1}^{n+m-1} b_i\oplus b_{i+1}$ ). Ahora, para $k\geq 0$, vamos a ${\mathcal{T}^{n,m}_k}$ ser el conjunto de todos los $b\in \Lambda^{n,m}$ tal que $T(b)=k$.

Mi pregunta: ¿existe un cerrado fórmula para el número de elementos en ${\mathcal{T}^{n,m}_k}$?

Por ejemplo: tomar de nuevo $\Lambda^{2,3}$ desde arriba, tengo por cierto ordenó que los dos primeros elementos, $00111$$11100$, tienen exactamente un bit-flip, por lo tanto ${\mathcal{T}^{2,3}_1} = 2$%. En una manera similar, la tercera a la quinta elementos tienen exactamente dos bits-flips, por lo tanto ${\mathcal{T}^{2,3}_2} = 3$%. Por la misma moneda, ${\mathcal{T}^{2,3}_3} = 4$% y por último ${\mathcal{T}^{2,3}_4} = 1$%.

Nota 1: he sido capaz de hacer funcionar el más simple de los casos ( $k=2, 3$ ), pero conseguir intimidados con mayor $k$.

Nota 2: este problema es de mi intento de reformular el Problema de 2-6 de R. Feynman, el libro de las integrales de camino "La ruta de abordaje integral QM". En ese contexto de lo que estamos contando es el número de caminos posibles con un determinado número de esquinas en un discreto ((1+1)-dimensional) el espacio-tiempo de la celosía.

Answer 1

Uno tiene que distinguir los casos $k=2j-1$ $k=2j$ donde $j\geq1$. En el siguiente voy a tratar el caso de $k=2j-1$ y dejar el caso $k=2j$.

Cuando hay $2j-1$ volteretas tenemos $j$ no vacío paquetes de ceros consecutivos alternando con $j$ no vacío paquetes consecutivos.

Con el fin de hacer la $j$ no vacío paquetes de ceros tenemos que poner a la separación de las barras de $|$ a $j-1$ de la $n-1$ espacios en una cadena de $n$ ceros. Esto se puede hacer en ${n-1\choose j-1}$ maneras. Del mismo modo y de forma independiente, se puede hacer $j$ no vacío paquetes de en ${m-1\choose j-1}$ maneras.

Todavía podemos decidir si vamos a empezar nuestras final de la cadena con $0$ o con $1$.

De ello se sigue que $$\left|{\cal T}_{2j-1}^{n,m}\right|=2{n-1\choose j-1}{m-1\choose j-1}\ .$$