Número de elementos en el poder cartesiano con una restricción mayoritaria.

Question

Problema: me gustaría saber el número de elementos en el sistema de alimentación de $X^n$ (producto cartesiano de un conjunto $X$ por sí mismo, $n$), con una mayoría de restricción: ¿cuántos elementos en $X^n$ tienen una (relativa) de la mayoría de uno de los elementos del conjunto (es decir $x\in X$)?

En la parte superior de eso, me gustaría corregir un elemento en el sistema de potencia a un valor determinado (es decir, el segundo), y contar el número de posibilidades con este valor fijo.

Ejemplo sencillo: con $X=\{A, B, C\}$$n=4$. La pregunta es: ¿cuántas palabras de cuatro letras con un $A$ en la segunda posición (relativa) de la mayoría de $A$'s? Y ¿cuántos tienen un (relativo) de la mayoría de $B$'s?

Solución para el ejemplo simple: se puede iterar sobre el número total $k$ del elemento que queremos como un (relativo) de la mayoría (es decir $A$).

• Con $k=4$ elementos $A$, existe 1 opción ($A$ es la mayoría, y $A$ está en la segunda posición)

$AAAA$

• Con $k=3$ elementos $A$, hay tres posibilidades para la localización de $A$'s. El segundo elemento es $A$ por restricción. Los dos extra $A$'s puede estar en la posición $(1,3), (1,4)$ o $(3,4)$. Y no es una posición libre, donde se puede ser de todo, pero $A$: 2 posibilidades. En total: $3\times 2=6$ posibilidades.

$AAAB, AAAC, AABA, AACA, BAAA, CAAA$

• Con $k=2$ elementos $A$'s, hay un extra-reto: los dos puestos restantes no debe ser el mismo, de lo contrario $A$'s no son una mayoría más. Acerca de la localización de la $A$'s, uno se fija en la segunda posición y el otro $A$ puede estar en posición de $(1)$, $(3)$ o $(4)$: 3 posibilidades. En los dos puestos restantes, hay 2 posibilidades para el primero ($B$ o $C$ pero no $A$) y 1 posibilidad para la segunda (no $A$ y no el mismo que el primero). Total: 6 posibilidades.

$AABC, AACB, BAAC, CAAB, BACA, CABA$

• Con $k=1$ elemento $A$, hay cero posibilidades de $A$ a a ser una mayoría (tres restantes posibilidades, con sólo dos cartas, $B$$C$, por lo que necesariamente una mayoría de $B$ o $C$).

Así que con $n=4$ y 3 elementos en la serie original, hay 13 posibilidades.

Solución General? Hay una forma cerrada de la fórmula para calcular este número?

Mismo problema, expresado en una red de formulación: En una red con 3 filas ($\{A, B, C\}$) y $n=4$ columnas, asumiendo las rutas de izquierda a derecha (por ejemplo, usando el nodo $A_1$,$B_2$, $A_3$ y, finalmente,$C_3$), la pregunta es: ¿cuántos caminos se va a través del nodo $A_2$ (relativo) de la mayoría de $A$ los nodos?

Mismo problema, expresada en un voto contexto: Calcular la ganancia de los resultados de la pluralidad de voto

Answer 1

Deje $|X|=m$ (el número de candidatos) y $n$ el número de votantes. Para la primera pregunta, por la teoría básica de la exponencial de las funciones de generación, el número de maneras para ser candidato a $A$ para obtener una pluralidad de votos es el coeficiente de $\frac{x^n}{n!}$ en la suma $$\sum_{k\ge0} \frac{x^k}{k!}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{m-1}.$$ Para ver esto, suma de todos los números posibles $k$ de los votos que $A$ recibe; el otro $m-1$ candidatos pueden llegar a $k-1$ de los votos cada uno. (Algunos de los términos de esta suma es cero, pero eso está bien.)

Para la segunda pregunta, si a solucionar uno de los votos, hay dos posibilidades, dependiendo de si se trata de la fijación de un voto por $A$ o por otro candidato. En el primer caso, la respuesta será $$\left[\frac{x^{n-1}}{(n-1)!}\a la derecha] \sum_{k\ge0} \frac{x^{k-1}}{(k-1)!}\izquierda(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{m-1} $$

(la notación $[z^n]f(z)$ denotar la operación de extraer el coeficiente de $z^n$ en el poder formal de la serie de $f(z)=\sum f_n z^n$ en el análisis de la combinatoria. Véase Philippe Flajolet y Robert Sedgewick, Analítica de la Combinatoria, Cambridge University Press (2009), pág.19))

(el coeficiente de $A_n$ en un aumento exponencial de generación de función es recuperado por $A_n=n!\cdot [z^n]A(z)$, ya que el $[z^n]A(z) = A_n/n!$ (ibid., p.98))

desde ahora tenemos que colocar $k-1$ votos $A$. (Esto le da el mismo $13$ como en el ejemplo). Del mismo modo, si usted está arreglando un voto para uno de los otros candidatos, la expresión se convierte en $$\left[\frac{x^{n-1}}{(n-1)!}\a la derecha] \sum_{k\ge0} \frac{x^{k}}{k!}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{m-2}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-2}}{(k-2)!}\right). $$

Answer 2

• Si $k>n/2$:

Para los no-elementos fijos de la mayoría ($k-1$), hay $\binom{n-1}{k-1}$ de posibilidades (funciona en el sencillo ejemplo con $k=4$: $\binom{3}{3}=1$; y $k=3$: $\binom{3}{2}=3$).

El número de "libre" posiciones (para los otros elementos de la mayoría) es $n-k$. Para cada posición, hay $|X|-1$ posibilidades (todos los elementos en $X$, pero la mayoría). Por eso, $(|X|-1)^{n-k}$ posibilidades.

En total: $(|X|-1)^{n-k} \cdot \binom{n-1}{k-1}$ posibilidades

• Si $k<n/2$:

Mismo razonamiento para el posicionamiento de la "mayoría" de los elementos: $\binom{n-1}{k-1}$ posibilidades.

El número de posiciones libres para otros elementos también es $n-k$. Pero ningún elemento en estas combinaciones deben aparecer más de $k$ veces. Una manera de calcular esto es (1) el recuento de todas las posibilidades: $(|X|-1)^{n-k}$ y (2) eliminar todas las posibilidades con $k, k+1, k+2, ..., n-k$ de uno de los elementos, por cada elemento.

El paso (2) como un subquestion aquí: Número de elementos en coordenadas cartesianas de la alimentación con un máximo de restricción

• El paso (2) de uno dado otro elemento

  • Para otros elementos, con $k$ de este elemento: arreglar $k$ veces el otro elemento: $n-k$ espacios libres, $k$ elementos, $\binom{n-k}{k}$ posibilidades. Para cada posibilidad, se nos ponen los demás (no de la mayoría, no otra): $n-k-k$ espacios libres, $|X|-2$ elementos, $(|X|-2)^{n-k-k}$ posibilidades. En total: $(|X|-2)^{n-k-k}\cdot \binom{n-k}{k}$ posibilidades para un determinado elemento con $k$ de las apariencias.

  • Para $k+1$ apariciones: $(|X|-2)^{n-k-k-1}\cdot \binom{n-k}{k+1}$ posibilidades

  • ...

  • Para $n-k$ apariciones: $(|X|-2)^{n-k-k-n}\cdot \binom{n-k}{n-k}= 1$ posibilidad, intuitiva.

Así, para un determinado elemento: $\sum_{j=k}^{n-k} (|X|-2)^{n-k-j}\cdot \binom{n-k}{j}$ posibilidades. PERO la doble contabilización (véase el Número de elementos en coordenadas cartesianas de la alimentación con un máximo de restricción), por lo $j$ en la suma tiene un punto de partida diferente: $j=k + \lfloor \frac{n-k-k}{2} \rfloor=k + \lfloor \frac{n-2k}{2} \rfloor = k + \lfloor \frac{n}{2} - k \rfloor = \lfloor \frac{n}{2} \rfloor$, por lo que para un elemento específico: $\sum_{j=\lfloor \frac{n}{2}\rfloor}^{n-k} (|X|-2)^{n-k-j}\cdot \binom{n-k}{j}$

• El paso (2) para todos los demás elementos:

Hay $|X|-1$ otros elementos, por lo que el número de posibilidades con más de $k$ los tiempos de cualquier otro elemento de es $(|X|-1)\sum_{j=k}^{n-k} (|X|-2)^{n-k-j}\cdot \binom{n-k}{j}$

Respuesta Final: $\sum_{k=1, k>n/2}^n (|X|-1)^{n-k} \cdot \binom{n-1}{k-1} + \sum_{k, k\leq n/2} \Bigg((|X|-1)^{n-k}-(|X|-1)\sum_{j=\lfloor \frac{n}{2}\rfloor}^{n-k} (|X|-2)^{n-k-j}\cdot \binom{n-k}{j}\Bigg)\cdot \binom{n-1}{k-1}$

Con el ejemplo sencillo y $k=2$, la ecuación nos da $(|X|-1)^{n-k}-(|X|-1)\sum_{j=\lfloor \frac{n}{2}\rfloor}^{n-k} (|X|-2)^{n-k-j}\cdot \binom{n-k}{j} = (2^2-2)\cdot 3=6$, lo cual es correcto.