Varios

cuentan solamente cuando satisfac Swipe to View nexr page satisfacen la condición de ci y también cuando satisfacen cj y otras condiciones cj, para j * i) Para cualesquiera i,] {1 tales que i , N(ci cj) denotará el número de elementos de S que satisfacen ambas condlciones ci,cj y tal vez otras más. N (ci cj) no cuenta los elementos de S que sólo satisfacen ci,cj. ] Continuando de esta forma, si Is i, j, k t son tres enteros distintos, entonces N (ci cj ck) denota el número de elementos de S que satisfacen, tal vez entre otras, cada una de las condiciones ci cj y ck. Para cada 1 si t, = N – N(ci) denota el número de elementos de S que no satisfacen la condición cia Si 1 si, j s t, con denota el número de elementos de S que no satisfacen alguna de las condiciones cicj [Esto no es lo mismo que . Del diagrama de Venn de la figura 8. 1, vemos que si N(ci) denota el número de elementos del círculo del lado izquierdo y N (cj)denota el número de elementos del circulo del lado derecho, entonces N (cicj) es el número de elementos en el solapamiento, mientras que N cuenta los elementos que quedan fuera de la unión de estos c[rculos. 2- 2 En consecuencia, de la figura8. , N – [N(ci) +N(cj)] +N(cicj), donde se suma el último término debido a que fue eliminado dos veces en el termino [N(ci + N(cj)]. De manera análoga, de la figura 8. obtenemos que: A partir del patrón sugerido en estos dos caso 2 OF de la figura 8. 2 obtenemos que: A partir del patrón sugerido en estos dos casos, establecemos el siguiente teorema. TEOREMA 8. 1 El principio de inclusión y exclusión. Consideremos un conjunto S tal que S = N y las condiciones ci, 1 si satisfechas por algunos de los elementos de S. Él número de elementos de S que no satisfacen ninguna de las condiciones ci , 1 i s t, se denota con donde Demostración: Aunque este resultado puede establecerse mediante inducción en r, daremos aquí un argumento combinatorio.

Para cada x e S, mostramos que x contribuye con el mismo número, 00 1, a cada lado de la ecuación (2). fig 8. 1 y fig 8. 2 Si x no satisface ninguna de las condiciones, entonces x se cuenta una vez en Ñ y una vez en N, pero no se cuenta en los demás términos de la ecuación (2). En consecuencia, x contribuye con 1 a cada lado de la ecuación. La otra posibilidad es que x satisfaga exactamente r de las condiciones, donde . En este caso, x no contribuye a . Pero, en el lado derecho de la ecuación (2), x se cuenta ) una vez en N 2) r veces en (Una vez por cada una de las r condiciones. 3) veces en (una vez por cada par de condiciones elegidas de las r que satisface. ) 4) veces en (¿Por qué? vez en donde las r que satisface. ) 4) veces en (¿Por qué? ) -1 vez en donde la suma se toma sobre todas las selecciones de tamaño r de las t condiciones. En consecuencia, en el lado derecho de la ecuación (2), x se cuenta por el teorema del binomio. Por lo tanto, los dos lados de la ecuación (2) cuentan los mismos elementos de S y se verifica la igualdad Un corolario inmediato de este principio es el siguiente: COROLARIO 8. Según las hipótesis del teorema 8. , el número de elementos de S que satisfacen al menos una de las condiciones ci, donde 1 gi t, está dado por N (cl c2 ct)— Antes de resolver algunos ejemplos, analizaremos una notación adicional para simplificar el enunciado del teorema 8. 1 . Escribimos Sl- [MCI) + N (c2)+….. N (ct)], MCI c2) N (CIC3)+. . (cl ct) N (c2c3)+. Y en general .. +N(ct-1 ct)], donde la suma se toma sobre todas las selecciones de tamaño k de la colección de I condiciones. Por lo tanto, Sk tiene sumandos en ella. Ahora veremos cómo se aplica este principio para resolver algunos problemas de conteo.

Ejemplo 8. 1 Determinaremos el número de enteros positivos n tales que y n no es divisible entre 2, 30 5. En este caso, S = {1, 2, satisface a) la condición cl, si ne 100. para n € S, n re 2, a) b) c) 100) y N — 100. Para n € S, n satisface la condición cl, si n es divisible entre 2, la condición c2 si n es divisible entre 3 y la condición c3 si n es divisible entre 5. Entonces, la respuesta de este problema es Como ya conocemos la función PISO, usamos la notación para denotar el máximo entero menor o igual que r, para cualquier número real r.

Esta función es útil en este problema, ya que vemos que 50 [puesto que los ) enteros positivos 2, 4, 6, 98 2 * 49), 2 * 50) son diViSibles entre 2]; 1_100/3 _I – — I _ 33 1/3 _ I = 33 [puesto que los 33(- _lOO/3 _ l) enteros positivos 96 (z 3 • 32), 3* 33) son divisibles entre 3]; N (cic2)- 1_100/6 _I — 16 [puesto que hay 16 elementos en S que son divisibles entre 2 y 3, y por tanto divisibles entre mcm (2, 3) 2 * 3 6]; N (Cl,C3) 1_100/10 = 10; (divisible entre 2 y 5) N(c2c3) 1_100/15_ = 6; (divisible entre 3 y 5) Y, N(CIC2C3) = = 3. divisible entre 2, 3Y 5) Si aplicamos el principio de inclusión y exclusión, tenemos que = SO – SI + S2-S3 = N – N(C2) + N(C3)] [N(cl, c2) + N(cl, c3) + N(c2 c3)] – MCI, c2 d) = 100-[50 + 33+ 20]+ [16 +10+6]-3 = 25 (Estos 26 números son s OF 20]+ [16 +10+ 6]-3 – 26 73, 77, 79, 83, 89, 91 y 97. ) EJEMPLO 8. 2. En el capitulo 1 encontraremos el número de soluciones no negativas de la Ecuación XI + x2 + x3 + x4- 18. Responderemos ahora la misma pregunta con la restricción adicional XIS 7, para todo i 4.

S es el conjunto de soluciones de XI + x2 +x3 + x4 18, con O sx, para todo Así, Decimos que una solución XI, x2, x3, x4, satisface la condición ci donde 1 i si xi >7 0 (xi 8). La respuesta al problema es entonces Por simetría, N(cl) = N(c2) = N(c3) = N(c4). Para calcular N(cl), consideramos las soluciones enteras de XI + x2 + x3 + x4- 10, donde cada xi para toda 1 si 4. Entonces sumamos 8 al valor de XI, y obtenemos las soluciones de XI + x2 +x3 + x4 10 que satlsfacen la condición cl. or lo tanto, N(ci) =para todo 1 s Del mismo modo, N(cl c2) es el número de soluciones enteras de XI + x2 + x3 4×4 = 2, donde xi 0, para todo 1 Así, N(cl c2) Como N(ci cj ck O para cualquier selección de las tres condiciones y N(cl c2 c3 c4) = 0, tenemos que =N-S1+S2-S3+S4-. Así, de las 1330 soluciones enteras no negativas de XI + x2 +x3 + x4= 18, sólo 246 de ellas satisfacen xi 7 para todo li < 4. Nuestro siguiente ejemplo establece la fórmu 6 OF sólo 246 de ellas satisfacen xi 7 para todo li 4.

Nuestro siguiente ejemplo establece la fórmula que conjeturamos antenormente para contar las funciones sobreyectlvas. Ejemplo 8. 3 Para conjuntos finitos A B, tales que A —m 2 n — IBI, sean A – { al …. arm .. bn} y S el conjunto de todas las funciones f: A a- {51, 52.. B. Entonces N = S = nm. Para todo 1 < i n, sea ci la condición sobre S tal que una función f: A B satisface Cl si bi no está en la imagen de f. (Observe la diferencia entre ci en este caso y ci en los ejemplos 8. 1 y 8. 2.

Entonces es el número de funciones en S que tienen bi en su imagen y cuenta el número de funciones sobre f: A 3. Para cualquier 1 g i n, N(ci) (n – l)m, ya que cualquier elemento de B, excepto bi, puede usarse como segunda componente de un par ordenado para una función f: A B, cuya imagen no incluye bi. De la misma forma, para cualquier 1 si < J n, existen (n – 2)m funciones f: A B cuya imagen no contiene bi ni bj. De estas observaciones obtenemos que [MCI) + N(c2) + N(cn)] = n(n – l)m = (n – l)m yS2 = [N(cl c2) + N(cl c3) + + N(cl c3) +….. +N (c2 cn)+…… = En general, para todo 1 n,

El principio de inclusión y exclusión implica que el número de funciones sobre de Aa B es =N-SI -S3+ +( exclusión implica que el número de funciones sobre de Aa B N -SI + S2 -S3+ Sn = nm – (n-l)m + (n-2)m – (n-3)m +… + Antes de terminar de analizar este ejemplo, notemos que También puede evaluarse en el caso m < n. Además, para m< n, la expresión Sigue contando el número de funciones f: A B, tales que IAI m ,181 n y cada elemento de B está en la imagen de f. Pero ahora este número es O. Por ejemplo, supongamos que m = 3 < 7 = n. Entonces cuenta el número de funciones sobre f: AB para IA = 3 y IBI -7.

Sabemos que este número es O, y también encontramos que 343 – 1512 + 2625 – 2240 + 945 – 168+ o. Por lo tanto, para cualquier m, n e Z si m < n, entonces Resolveremos ahora un problema similar a los del capitulo 3, relacionado con los diagramas de Venn. EJEMPLO 8. 4 ¿De cuántas formas pueden permutarse las 26 letras del alfabeto de tal manera que ninguno de los patrones sea car, dog, pun, o byte? Sea S el conjunto de todas las permutaciones de 26 letras. Entonces ISI =26!. Para todo 1 < í < 4, una permutación de S satisface la condición ci si la permutación contiene car, dog, pun o byte, respectivamente. ra calcular N(ci), por ejemplo, contamos el número de formas en que pueden permutarse los 24 símbolos car, b, d, e, f,... , p, q, s, , x,y, número de formas en que pueden permutarse los 24 símbolos car, b, d, e, f,. „ p, q, s, x,y, z. Así, N(cl)= 24! y de una manera similar obtenemos N(C2) = N(C3) = 241, 23! mientras que N(c4) = Para N(cl c2), trabajamos con los 22 símbolos car, dog, b, e, x, y, z, que pueden permutarse de 22! formas. De aquí obtenemos que N(cl c2) — 22! y con otros cálculos semejantes obtenemos N(CI 0) = N(C2 0) = 22! , N(ci c4) = 21! , i Además, N(cl c3 17!

N(CiCjC4) = 19! Así, el número de permutaciones de 5 que no contienen ninguno de los patrones dados es = 26! — [3(24! ) + 23! ] + [3(22! ) + 3(21)! ] – [20! ) 3(19)! ] 171. Nuestro siguiente ejemplo trata un problema de teoría de números. EJEMPLO 8. 5 Para n C Z+. n > 2, sea el número de enteros positivos m, tales que 1 s m < ny mcd (m , n) = 1. esto es m, n son primos relativos. Esta función es la función phi de Euler y surge en varias situaciones del álgebra abstracta relacionadas con la enumeración. Encontramos que 1, – -2, -2, -2. Para cualquier primo p, .

Queremos obtener u Encontramos que – 1 —2, —2, —4 y —2. Para cualquier primo p, . Queremos obtener una fórmula para cp(n) relacionada con n para no tener que hacer una comparación caso por caso para todo m, 1 Sm < n, con el entero n. La deducción de nuestra fórmula usará el principio de inclusión y exclusión, como en el ejemplo 8. 1. Procedemos como sigue: para n 22, usamos el teorema fundamental de la aritmética y escribimos pel 1, pe22. pett, donde pl „p2,…. pt son primos distintos y ei 1, para todo 1 si t. Consideremos el caso en que t 4. Esto será suficiente para demostrar la idea general.

Si S ={1, ), tenemos N= ISI y para todo Is decimos ue k € S satisface la condición ci si k es divisible entre pi . para 1 k < n, mcd(k, n) = 1 si k no es divisible entre cualquiera de los primos pi, donde 1 s 4. por lo tanto cp(n) = Para todo 1 s i 4, tenemos N(ci) = n/pi ; N(cl cj)= n/(pi p]), para todo 1 i 4. También, N(ci cj cl) = pi pj pl) , para todos 1 i< j < I s 4, y N(cl c2 c3 c4) —n / (pl p2 p3 p4) Así – Sl+ S2 – S3+S4 Program EulerPhiFunction (input,output); Va i,j,k,n,phi,originalvalue: integer; Begin Write ( ‘ El valor de n es Read (n); phi : n; originalvalue n; If n Mod 0 then h phi Div 2; While n Mod 2 — 0 do