¿Cuáles son las fórmulas matemáticas de permutación y combinación?
La definición de disposición: a partir de n elementos diferentes, cualquier m (m≤n, myn son números naturales, lo mismo a continuación) se organizan en una columna en un orden determinado, que se llama desde n Una permutación de m elementos de diferentes elementos; el número de todas las permutaciones de m (m≤n) elementos de n elementos diferentes se denomina número de permutaciones de m elementos de n elementos diferentes, utilizando el símbolo A (n, m) para representar. .
Fórmula de cálculo:
Además, se estipula que 0!=1(n! significa n(n-1)(n-2)...1, que es 6!=6x5x4x3x2x1[ 1]?
La definición de combinación: de n elementos diferentes, cualquier m (m≤n) elementos se toma y se combina en un grupo, lo que se denomina combinación de m elementos tomados. de n elementos diferentes El número de todas las combinaciones de m (m ≤ n) elementos de n elementos diferentes se denomina número de combinaciones de m elementos de n elementos diferentes. Se representa con el símbolo C (n, m)
Fórmula de cálculo:
;C(n,m)=C(n,n-m) (n≥m)
Otras fórmulas de permutación y combinación se basan en n elementos. El número de permutaciones cíclicas de m elementos extraídos de =A(n,m)/m=n!/m(n-m)!. Los n elementos se dividen en k categorías, y los números en cada categoría son n1. , n2,... El número total de disposiciones de n elementos nk es n!/(n1! m k-1, m
Símbolo
Una pregunta común
p>¿C-Combinación? ¿Número de combinaciones [2]?
A-Arreglo? (P-Permutación en el libro de texto antiguo)
N-El total número de elementos
M-El número de elementos que participan en la selección
! - Factorial
Principio básico de conteo
⑴Principio de suma y Método de conteo de clasificación
⒈Principio de suma: para hacer una cosa, puede haber n veces para completarla Métodos de clase, en
Identidades combinadas (2 fotos) Hay m1 métodos diferentes en el primera clase de métodos, m2 métodos diferentes en la segunda clase de métodos,..., en la enésima clase de métodos Hay mn formas diferentes de , entonces hay N=m1 m2 m3 ... mn formas diferentes de lograr esto.
⒉El primer tipo de método pertenece al conjunto A1, y el segundo tipo de método El método pertenece al conjunto A2,..., el método de la enésima categoría pertenece al conjunto An, entonces. el método para completar esto pertenece al conjunto A1UA2U...UAn
⒊Requisitos de clasificación: cada categoría en cada categoría puede completar esta tarea de forma independiente, los métodos específicos en los dos tipos diferentes de métodos son; diferentes entre sí (es decir, la clasificación no se superpone); cualquier método para completar esta tarea pertenece a una determinada categoría (es decir, la clasificación no se pierde)
⑵ Principio de multiplicación y pasos. método de conteo paso a paso
⒈? Principio de multiplicación: para hacer una cosa, es necesario dividirla en n pasos. Hay m1 formas diferentes de realizar el primer paso. haz el segundo paso,..., hay mn formas diferentes de hacer el enésimo paso, luego hay N=m1×m2×m3×…×mn formas diferentes de completar esto Método
⒉Razonable. requisitos paso a paso
Esta tarea no se puede completar en ningún paso. La tarea debe completarse y solo estos n pasos deben completarse continuamente en cada paso. Los recuentos son independientes entre sí; Como el método seguido en un paso es diferente, el método correspondiente para completar el asunto también es diferente.
3. También está estrechamente relacionado con las variables aleatorias discretas posteriores.
La paridad y uniformidad del número de combinación
La definición de paridad: para el número de combinación C (n, k) (ngt; = k): convierta n y k a binario respectivamente, si un determinado dígito binario Si el n correspondiente es 0 y k es 1, entonces C (n, k) es un número par, de lo contrario, es un número impar.
El siguiente es el método de determinación:
Conclusión:
Para C(n, k), si n&k == k entonces c(n, k) es un número impar, en caso contrario es un número par.
Prueba:
Para C(n, k), si n&k == k, entonces c(n, k) es un número impar; de lo contrario, es un número par.
Prueba:
Usa la inducción matemática:
De C(n, k) = C(n-1, k) C(n-1, k -1);
corresponde al triángulo Yang Hui:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
………………
Se puede comprobar que las capas anteriores y k = 0 satisfacen la conclusión. Lo siguiente demuestra que cuando C(n-1, k) y C(n-1, k-1) (k gt; 0) satisfacen la conclusión,
C(n, k) satisface la conclusión.
1). Supongamos que C(n-1, k) y C(n-1, k-1) son números impares:
Entonces: (n-1) amp. ; k == k;
(n-1) & (k-1) == k-1
Desde k y el último bit de k-1 (aquí The; bit se refiere al bit binario, lo mismo a continuación) debe ser diferente, por lo que el último bit de n-1 debe ser 1
Ahora suponga n&k == k.
De manera similar, debido a que los últimos dígitos de n-1 y n son diferentes, se puede concluir que el último dígito de k es 1.
Debido a que el último dígito de n-1 es 1, el último dígito de n es 0, por lo que n&k != k, lo cual es contrario a la suposición.
Así que namp;k != k.
2). Supongamos que C(n-1, k) y C(n-1, k-1) son números pares:
Entonces: (n-1) amp. ; k != k;
(n-1)amp;(k-1) != k-1;
Ahora supongamos que namp;k == k.
Entonces, para el caso en el que el último dígito de k es 1:
En este momento, el último dígito de n también es 1, por lo que hay (n-1)amp (k; -1) == k-1 , contradiciendo la hipótesis.
Para el caso en el que el último dígito de k es 0:
Entonces debe haber una parte al final de k que se vea así: 10 que represente cualquier número de ceros.
En consecuencia, la parte correspondiente de n es: 1{*}*; * representa 0 o 1.
Y si solo uno de los {*}* correspondientes a n es 1, entonces se establece (n-1)amp;k == k, por lo que la parte correspondiente de n también debería ser 10.
En consecuencia, las partes finales de k-1 y n-1 son ambas 01, por lo que se establece (n-1)amp; (k-1) == k-1, lo cual es contrario a la suposición.
Así que namp;k != k.
De 1) y 2), cuando C(n, k) es un número par, n&k != k.
3). Supongamos que C(n-1, k) es un número impar y C(n-1, k-1) es un número par:
Entonces existe : (n-1) amp;k == k;
(n-1)amp;(k-1) != k-1;
Obviamente, el último bit de k solo puede ser 0, de lo contrario se puede deducir de (n-1)amp;k == k que (n-1)amp (k-1) == k-1.
Entonces debe haber una parte al final de k que se vea así: 10;
En consecuencia, la parte correspondiente de n-1 es: 1{*}*;
En consecuencia, la parte correspondiente de k-1 es: 01;
Si desea hacer (n-1) amp (k-1) != k-1, necesita; el {* correspondiente a n-1 Al menos uno de }* es 0.
Entonces la parte correspondiente de n es: 1{*}* (no cambiará de 1 a 0 debido al acarreo)
Entonces namp ; k = k.
4). Supongamos que C(n-1, k) es un número par y C(n-1, k-1) es un número impar:
Entonces: ( n-1) amp; k != k;
(n-1) amp; (k-1) == k-1
Hay dos situaciones:
Cuando el último dígito de k-1 es 0:
Entonces debe haber una parte al final de k-1 que se vea así: 10;
En consecuencia , la parte correspondiente de k es: 11;
En consecuencia, la parte correspondiente de n-1 es: 1{*}0 (Si es 1{*}1, entonces (n-1) amp;k == k)
En consecuencia, la parte correspondiente de n es: 1{*}1;
Entonces n&k = k.
Cuando el último dígito de k-1 es 1:
Entonces debe haber una parte al final de k-1 que se vea así: 01 (el 0 anterior puede ser; adjunto)
En consecuencia, la parte correspondiente de k es: 10;
En consecuencia, la parte correspondiente de n-1 es: 01 (Si es 11, entonces (n-; 1) amp ;k == k)
En consecuencia, la parte correspondiente de n es: 10;
Entonces n&k = k.
De 3) y 4), cuando C(n, k) es un número impar, n&k = k.
En resumen, la conclusión está demostrada.