¿Cuántas cuerdas binarias de longitud 2n + 1 tienen más 1's que 0's? Usa la bijección para probar.

Question

NOTA: Esta es una pregunta de deberes, así que sólo pido pistas y sugerencias para empujarme en la dirección correcta.

Pregunta:

Deje que $n \in \mathbb {N}$ . ¿Cuántas cuerdas binarias de longitud 2n + 1 tienen más 1's que 0's? Usa la bijección para probar.

Progresos hasta ahora:

Necesitamos un conjunto de tamaño conocido, B, junto con una función bijectiva $f: A \rightarrow B$ donde A es el conjunto con cuerdas binarias de longitud $2n + 1$ y donde cada elemento de la A tiene más de 1 que de 0.

Intenté encontrar un patrón estableciendo n = 1:

$$ \begin {align*} 000 \rightarrow & \lbrace empty set \rbrace \\ 001 \rightarrow & \lbrace 1 \rbrace \\ 010 \rightarrow & \lbrace 2 \rbrace \\ 011 \rightarrow & \lbrace 1,2 \rbrace \\ 100 \rightarrow & \lbrace 3 \rbrace \\ 101 \rightarrow & \lbrace 1,3 \rbrace \\ 110 \rightarrow & \lbrace 1,2 \rbrace \\ 111 \rightarrow & \lbrace 1,2,3 \rbrace \\ \end {align*} $$

Me di cuenta de que las cadenas binarias con más de 1's que 0's se dirigen a los elementos en B donde los elementos son de tamaño $ \geq 2n$ .

Por lo tanto, el tamaño del conjunto $S$ donde $S = \lbrace x : |x| \geq 2n \rbrace $ es el número de cadenas binarias de longitud $2n+1$ con más de 1 que 0.

Aquí es donde estoy atrapado. No sé cómo encajar la bijección en esta solución. También creo que mi mapeo del conjunto A al conjunto B es incorrecto ya que el conjunto A sólo debería contener las cadenas binarias que tienen más de 1's que 0's.

Cualquier ayuda sería muy apreciada.

Answer 1

Pista: Primero, note que como su cuerda tiene longitud impar, cada cuerda binaria tiene más 1's o más 0's (sin ataduras). Supongamos que una cuerda tiene más 0's que 1's... ¿qué pasa cuando se voltean todos los bits? La nueva cadena tiene más de 1 que de 0. Así que, para tu bijección, considera emparejar una cuerda con su complemento (es decir, la cuerda con todos los 1's y 0's volteados).

Lo que se ve en esta bijección es que por cada cuerda con más de 1's que 0's hay una cuerda correspondiente con más de 0's que 1's.

Siguiendo su ejemplo, lo que se emparejarían son los siguientes:

$000 \to 111$

$001 \to 110$

$010 \to 101$

$100 \to 011$

Eso explica las 8 cuerdas binarias de longitud 3. Observe que las LHS son las cuerdas con menos 1's que 0's y las RHS son las cuerdas con más 1's que 0's.

Answer 2

Pista: Si lanzamos una moneda justa $2015$ veces, la probabilidad de que haya más cabezas que colas es, por simetría, igual a la probabilidad de que haya más colas que cabezas. No podemos tener igualdad, así que la probabilidad es $ \frac {1}{2}$ .

Answer 3

Ayudaría a considerar esta cuestión por un momento: ¿Cuántas cuerdas binarias de longitud $2n + 1$ tienen más ceros que unos? ¿Cómo puedes relacionar un problema con el otro?