¿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 tomados 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

¿C-Combinación? ¿Número de combinaciones [2]?

¿A-Arreglo? (P-Permutación en el libro de texto antiguo)

N-El número total 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: hacer una cosa y completarla con n tipos de métodos, en

Identidades combinadas (2 fotos) Hay m1 métodos diferentes en el primer tipo de métodos , m2 métodos diferentes en el segundo tipo de métodos,..., en el enésimo tipo Hay mn métodos diferentes en el método, luego hay N=m1+m2+m3+…+mn métodos diferentes para completar esto

⒉El primer tipo de método pertenece al conjunto A1. El método del segundo tipo de método pertenece al conjunto A2,..., y el método del enésimo tipo de método pertenece al conjunto An. el método para completar esto pertenece al conjunto A1UA2U...UAn.

⒊Requisitos de clasificación: cada método de la clase puede completar esta tarea de forma independiente, los métodos específicos en los dos tipos diferentes son; diferentes entre sí (es decir, la clasificación no se superpone); cualquier método que complete esta tarea pertenece a una determinada clase (es decir, no se pierde la clasificación

⑵ Principio de multiplicación y paso a paso). -método de conteo de pasos

⒈? Principio de multiplicación: para hacer algo, es necesario dividirlo en n pasos. El primer paso es Hay m1 formas diferentes, hay m2 formas diferentes de realizar el segundo paso. ..., hay mn formas diferentes de realizar el enésimo paso, luego, para completar esto, hay N=m1×m2×m3×…× mn métodos diferentes

⒉Paso a paso razonable. requisitos

Esta tarea no se puede completar en ningún paso. Solo se deben completar n pasos continuamente para completar esta tarea, siempre que el método se adopte 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)(n>=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);

Correspondiente 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 satisface la conclusión, lo siguiente demuestra que cuando C(n-1,k) y C(n-1,k-1) (k > 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)&k. = = k;

(n-1)&(k-1) == k-1;

Desde el último bit de k y k-1 (el bit aquí se refiere (para que sean bits binarios, lo mismo a continuación) deben ser diferentes, por lo que el último dígito de n-1 debe ser 1

Ahora suponga que 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.

Entonces n&k != k.

2). Supongamos que C(n-1,k) y C(n-1,k-1) son números pares:

Entonces: (n-1)&k. ! = k;

(n-1)&(k-1) != k-1;

Ahora supongamos que n&k == k.

Entonces, para cuando el último dígito de k es 1:

En este momento, el último dígito de n también es 1, entonces (n-1)&(k-1) == k-1, que es contrario al supuesto.

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)&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)&(k-1) == k-1, lo cual es contrario a la suposición .

Entonces n&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: ( n-1) &k == k;

(n-1)&(k-1) != k-1;

Obviamente, el último bit de k solo puede ser 0, de lo contrario (n-1)&k == k se puede deducir (n-1)&(k-1) == k-1.

Entonces el final de k debe tener una parte en la forma de: 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)&(k-1) != k-1, el {*} correspondiente a n-1 se requiere Al menos uno de * es 0.

Entonces la parte correspondiente de n es: 1{*}* (no cambiará de 1 a 0 debido al acarreo)

Entonces n&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) &k != k;

(n-1)&(k-1) == k-1;

Hay dos situaciones:

Cuando k Cuando el último dígito de -1 es 0:

Entonces debe haber una parte al final de k-1 que se vea así: 10;

En consecuencia, el 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)&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 el final de k-1 debe tener una parte en la forma: 01 (se puede agregar el 0 anterior)

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) &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.