·

Cursos Gerais ·

Matemática Discreta

Send your question to AI and receive an answer instantly

Ask Question

Preview text

Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 CC0279 - Elementos de Análise Combinatória Teoria do Cap 4- Seções 4.2 e 4.3 do Morgado - 20/07/2020 Prof. Mauricio Mota 1. ( Teorema -pg 104) Se x e a são números reais e n é um inteiro positivo (x + a)^n = \sum_{k=0}^{n} \binom{n}{k} a^k x^{n-k}. Note que: (x + a)^n = (x + a)(x + a) \ldots (x + a) = P_1 P_2 \ldots P_n. Quantas vezes aparece a^k x^{n-k}? Para isto devemos escolher um a de k produtos entre os produtos P_1 P_2 \ldots P_n dos restantes (n - k) a gente escolhe o fator x. Assim há \binom{n}{k} de escolher os k produtos. A expansão geral é a soma destes fatores. vamos expandir o somatório: (x + a)^n = \binom{n}{0} x^n + \binom{n}{1} a^1 x^{n-1} + \binom{n}{2} a^2 x^{n-2} + \ldots + \binom{n}{n} a^n x^0. Na realidade temos um polinômio de grau n na variável x: P(x) = (x + a)^n = A_0 + A_1 x + A_2 x^2 + \ldots + A_n x^n, em que A_k = \binom{n}{k} a^k, k = 0, 1, 2, \ldots, n. Note que: P(1) = A_0 + A_1 + A_2 + \ldots + A_n = \sum_{k=0}^{n} A_k, isto é, a soma dos coeficientes do desenvolvimento P(x) = (x + a)^n é o valor numérico do polinômio calculado no ponto x = 1, isto é, S = P(1) = (1 + a)^n = \sum_{k=0}^{n} \binom{n}{k} a^k. i. O desenvolvimento de (x + a)^n possui (n+1) termos. ii. Os coeficientes do desenvolvimento de (x + a)^n são os elementos da linha n do triângulo de Pascal. Note que: A linha 0 é dada por: (x + a)^0 = 1 = \binom{0}{0} A linha 1 é dada por: (x + a)^1 = x + a = \binom{1}{0} x + \binom{1}{1} a A linha 2 é dada por: (x + a)^2 = x^2 + 2ax + a^2 = \binom{2}{0} x^2 + \binom{2}{1} ax + \binom{2}{2} a^2 A linha 3 é dada por: (x + a)^3 = x^3 + 3ax^2 + 3a^2 x + a^3 = \binom{3}{0} x^3 + \binom{3}{1} a x^2 + \binom{3}{2} a^2 x + \binom{3}{3} a^3 A linha 4 é dada por: (x + a)^4 = x^4 + 4ax^3 + 6a^2 x^2 + 3a^3 x + a^4 = \binom{4}{0} x^4 + \binom{4}{1} ax^3 + \binom{4}{2} a^2 x^2 + \binom{4}{3} a^3 x + \binom{4}{4} a^4, e assim por diante. iii. Escrevendo os termos do desenvolvimento na ordem decrescente das potências de x, o termo de ordem (k + 1) é dado por: T_{k+1} = \binom{n}{k} a^k x^{n-k}, k = 0, 1, 2, \ldots, n. Geralmente o binômio de Newton pode aparecer como: (a + b)^n = \sum_{k=0}^{n} \binom{n}{k} b^k a^{n-k}. As vezes aparece na forma: P(x) = (a(x) + b(x) )^n = \sum_{k=0}^{n} \binom{n}{k} [b(x) ]^k [a(x) ]^{n-k} . Neste caso a soma dos coeficientes de é dada por: ) ^n. Outras vezes aparece como: (a - b)^n = (a + (- Vamos resolver alguns exemplos: Exemplo 1. Determine o coeficiente de no desenvolvimento de — Solução: Vemos que n = 9 e a(x) = x^3 e b(x) = -\frac{1}{x^2}=-x^{-2}. O termo genérico do desenvolvimento é dado por: T_{k+1} = \binom{n}{k} a^k x^{n-k} = \binom{n}{k} (-x^{-2} )^k (x^3 )^{9-k} = \binom{n}{k} (-1)^k x^{-2k} (x^3 )^{9-k} = \binom{n}{k} (-1)^k x^{-2k} x^{27-3k} = \binom{n}{k} (-1)^k x^{27-5k}. O problema pede o termo em x^2. logo 27 - 5k = 2, o que acarreta k = 5. Assim k + 1 = 6. O termo de posição 6 é dado por: T_6 = \binom{9}{5} (-1)^5 x^{27-25} = -126x^2, e o coeficiente vale -126. Exemplo 2. Determine o termo máximo do desenvolvimento de (1 + 1/3)^65. Solução: Vemos que n = 65 e a = 1 e b = \frac{1}{3}. O termo genérico do desenvolvimento é dado por: T_{k+1} = \binom{65}{k} (\frac{1}{3} )^k 1^{65-k} = \binom{65}{k} (\frac{1}{3} )^k = \binom{65}{k} \frac{1}{3^k} = \frac{65!}{k!(65-k)!3^k}. Para que valores de k temos Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 T_{k+1} > T_k? Note que T_k = T_{k-1+1} = \binom{65}{k-1} \frac{1}{3^{k-1}} = \frac{65!}{k!(66-k)!}3^{k-1}. \frac{65!}{k!(65-k)!}3^k > \frac{65!}{(k-1)!(66-k)!}3^{k-1}. Vamos arrumar de modo conveniente e cancelando 65! \frac{(66-k)!}{(65-k)!\hspace{1mm}} > \frac{k!}{(k-1)!}\frac{3^k}{3^{k-1}} Simplificando \frac{(66-k)(65-k)!}{(65-k)!\hspace{1mm}} > \frac{k(k-1)!}{(k-1)!}3^k > \frac{k}{1} 3^k ou 66 - k > 3k, e k < \frac{66}{4} = 16,5. Logo T_{k+1} > T_k para k \in \{0,1,2,\ldots,16\} e analogamente T_{k+1} < T_k para k \in \{17,18,\ldots,65\}. Vamos juntar tudo: T_1 < T_2 < T_3 < \ldots < T_{16} > T_{17} > T_{18} > \ldots > T_{66}. Assim o termo máximo é \binom{65}{16}T_{17} Vamos ver a solução pelo > n=65 > > k=0:n;k [1] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 [26] 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 [51] 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 > > > ####a_k=T_{k+1} > ak=choose(n,k)*(3^(-k)) > max(ak) [1] 15054479 > which.max(ak) ####assim k=16, e o máximo é T_17. [1] 17 > > Exemplo 3. Determine o termo máximo do desenvolvimento de P(x) = (1+x)^9=\sum_{k=0}^{9}\binom{9}{k} x^k. Solução: Assim T_{k+1} = \binom{9}{k}, \hspace{1mm} k = 0,1,2,\ldots,10. Logo T_1 = T_{10} = \binom{9}{0} = \binom{9}{9} = 1, T_2 = T_9 = \binom{9}{1} = \binom{9}{8} = 9, T_3 = T_8 = \binom{9}{2} = \binom{9}{7} = 36, T_4 = T_7 = \binom{9}{3} = \binom{9}{6} = 84, T_5 = T_6 = \binom{9}{4} = \binom{9}{5} = 126. Usando o software R temos: > n=9 > k=0:n;k [1] 0 1 2 3 4 5 6 7 8 9 > T_k=choose(n,k);T_k [1] 1 9 36 84 126 126 84 36 9 1 > O valor máximo é 126. Os termos são T_5 e T_6. Perceba que neste caso são dois valores de k que atingem o valor máximo. Vamos formalizar? Quando há duas modas temos que procurar valores de k tais que: T_{k+1}= T_k? Sabemos que Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 T_{k+1} = \binom{9}{k}, \hspace{1mm} k = 0,1,2,\ldots,10, e T_{k=k-1+1} = \binom{9}{k-1}, \hspace{1mm} k = 1,2,\ldots,10. Assim, T_{k+1} = T_k, \binom{9}{k} = \binom{9}{k-1}, Logo como k \neq k-1 e usando as propriedades de combinações complementares temos: k + k - 1 = 9, 2k = 10, k = 5. Logo T_5 = T_6. Quando T_{k+1} < T_k? \frac{9!}{k!(9-k)!} < \frac{9!}{(k-1)!(10-k)!}, simplificando 9! e manipulando os termos: \frac{(k-1)!}{k!}<\frac{(9-k)!}{(10-k)!}, vamos brincar um pouco mais: \frac{(k-1)!}{k(k-1)!}<\frac{(9-k)!}{(10-k)(9-k)!}, simplificando \frac{1}{k} < \frac{1}{(10-k)}, logo 10-k < k, 10 < 2k, Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 P(x) = \sum_{i=0}^{m} A_i x^i = A_0 + A_1 x + A_2 x^2 + \ldots + A_m x^m. O valor numérico de P(x) para x = 1 nos dará a soma pretendida. P(1) = \sum_{i=0}^{m} A_i 1^i = A_0 + A_1 + A_2 + \ldots + A_m = \sum_{i=0}^{m} A_i. Assim \sum_{i=0}^{m} A_i = P(1) = \left(1^3 - 2 \times 1^2\right)^{15} = (-1)^{15} = -1. Vamos fazer de outra maneira usando O software R: Note que o termo geral é dado por: T_{k+1} = \binom{15}{k} \left(-2x^2\right)^k \left(x^3\right)^{15-k} = \binom{15}{k} (-1)^k x^{45-k}. Para k = 0 temos o expoente m = 45 que é o grau de nosso polinômio. Logo \sum_{k=0}^{15} A_k = \sum_{k=0}^{15} \binom{15}{k} (-2)^k = \sum_{k=0}^{15} \binom{15}{k} (-2)^k 1^{15-k} = (-2 + 1)^{15} = -1, note que 1^{15-k} = 1, belo truque não? multiplicar por 1 não altera. Seja T_k o k-ésimo coeficiente termo. assim, T_k = \binom{15}{k-1} (-2)^{k-1}. > n=15 > k=1:(n+1);k [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 > T_k=(-2)^{k-1}*choose(15,k-1);T_k [1] 1 -30 420 -3640 21840 -96096 320320 -823680 [9] 1647360 -2562560 3075072 -2795520 1863680 -860160 245760 -32768 > > sum(T_k) [1] -1 > Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 > > n=9 > > > k=0:n;k [1] 0 1 2 3 4 5 6 7 8 9 > > C_k=choose(n,k);C_k [1] 1 9 36 84 126 126 84 36 9 1 > > ###o valor máximo 126 ocorre nas posições 5 e 6. > > max(C_k) [1] 126 > > which.max(C_k) #####Cuidado ele fornece a posição da primeira posição. [1] 5 > > > Exemplo 4. Qual é a soma dos coeficientes do desenvolvimento de P(x) = (x^3 - 2x^2)^{15}. Solução: O desenvolvimento do binômio tem 16 termos. Poderíamos calcular cada termo e depois somá-los. Esta técnica é muito trabalhosa. Vamos pensar em outra. Se tivermos um polinômio de grau m , isto é, Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 Os próximos exemplos são somatórios que precisam ser transformados em Binômio de Newton. Vamos aprender? Exemplo 5. Calcule S = \sum_{k=0}^{n} \binom{n}{k} x^{k}. Solução: Note que: S = \sum_{k=0}^{n} \binom{n}{k} x^{k} \times 1 = \sum_{k=0}^{n} \binom{n}{k} x^{k} \times 1^{n-k} = . Temos a fórmula do Binômio de Newton. Logo S = (1 + x)^{n} = (x + 1)^{n}. Exemplo 6. Calcule S = \sum_{k=0}^{n} k \binom{n}{k} x^{k}. Solução: Note que para k = 0 o coeficiente é nulo e assim não altera a soma. Vamos começar o somatório com k = 1. S = \sum_{k=0}^{n} k \binom{n}{k} x^{k} = \sum_{k=1}^{n} k \binom{n}{k} x^{k}. Vamos simplificar usando o fato que k não é zero.: k \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!} = n \frac{(n-1)!}{(k-1)!(n-k)!} = n \binom{n-1}{k-1}. Logo, S = \sum_{k=1}^{n} k \binom{n}{k} x^{k} = n \sum_{k=1}^{n} \binom{n-1}{k-1} x^{k}. Fazendo a mudança de variável i = k-1 no somatório temos que para k = 1 temos i = 1 - 1 = 0 e para k = n temos i = n - 1. Note que k = i + 1. Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 Dessa maneira S = n \sum_{k=1}^{n} \binom{n-1}{k-1} x^k = n \sum_{i=0}^{n-1} \binom{n-1}{i} x^{i+1} = nx \sum_{i=0}^{n-1} \binom{n-1}{i} x^i. S = nx \sum_{i=0}^{n-1} \binom{n-1}{i} x^i = nx \sum_{i=0}^{n-1} \binom{n-1}{i} x^i 1^{n-1-i} = nx(1+x)^{n-1}. Uma outra solução envolve derivada. Considere a função real de variável real f(x) = (1+x)^n, cujaderivadaemrelaçãoxédadapor: f'(x) = n(1+x)^{n-1}. Usando Binômio de Newton podemos pensar também: f(x) = (1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k, cujaderivadaemrelaçãoxédadapor: f'(x) = \sum_{k=0}^{n} k \binom{n}{k} x^{k-1}. Igualandoasduastemos: \sum_{k=0}^{n} k \binom{n}{k} x^{k-1} = n(1+x)^{n-1}, multiplicandoambososladosporxtemos \sum_{k=0}^{n} k \binom{n}{k} x^k = nx(1+x)^{n-1}. Exemplo7.Usandooexemplo6mostreque: \sum_{k=0}^{n} k \binom{n}{k} = n2^{n-1}. Solução: Note que: f(1) = \sum_{k=0}^{n} k \binom{n}{k} 1^k = n \times 1 \times ( Exemplo7.Mostreque Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 \sum_{k=0}^{n} \binom{n}{k} = 2^n. Solução: Vamos usar a fórmula do binômio de Newton: (x+a)^n = \sum_{k=0}^{n} \binom{n}{k} a^k x^{n-k}, fazendo a = x = 1 temos: (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^k 1^{n-k} = \sum_{k=0}^{n} \binom{n}{k} = 2^n. Exemplo8.Mostreque \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0^n = 0. Solução: Vamos usar a fórmula do binômio de Newton: (x+a)^n = \sum_{k=0}^{n} \binom{n}{k} a^k x^{n-k}, fazendo a = -1 e x = 1 temos: (1-1)^n = \sum_{k=0}^{n} \binom{n}{k} (-1)^k 1^{n-k} = \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0^n = 0. Exemplo9.O próximo exemplo tratará de obter a soma dos termos de ordem par de um Binômio de Newton (x+a)^n ordenado segundo as potências decrescentes de x.Seja S_p esta soma e C_p a soma dos coeficientes dos termos de ordem par. Mostre que: S_p = \frac{(x+a)^n - (x-a)^n}{2}, C_p = \frac{(1+a)^n - (1-a)^n}{2}, Solução: Vamos expandir (x+a)^n (x+a)^n = T_1 + T_2 + T_3 + T_4 + \cdots e (x-a)^n = T_1 - T_2 + T_3 - T_4 - Subtraindo as duas expressões temos: -a)^n = 2 [T_2 + T_4 + \cdots ] Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 (x+a)^n = \sum_{k=0}^{n} \binom{n}{k} a^k x^{n-k} = \sum_{j=1}^{n+1} T_j. (x-a)^n = \sum_{k=0}^{n} \binom{n}{k} (-1)^k a^k x^{n-k} = \sum_{j=1}^{n+1} (-1)^{j-1}T_j. Subtraindo temos: (x+a)^n - (x-a)^n = \sum_{j=1}^{n+1} T_j - \sum_{j=1}^{n+1} (-1)^{j-1}T_j. Vamos colocar o - do segundo somatório para o interior do mesmo. (x+a)^n - (x-a)^n = \sum_{j=1}^{n+1} T_j + \sum_{j=1}^{n+1} (-1)^{j}T_j, e (x+a)^n - (x-a)^n = \sum_{j=1}^{n+1} (1+(-1)^j)T_j, Vamos deixar um único somatório (x+a)^n - (x-a)^n = \sum_{j=1}^{n+1} (1+(-1)^j)T_j (x+a)^n - (x-a)^n = \sum_{j=1}^{n+1} \big (1+(-1)\big ) mas se \ j \ é \ ímpar se \ j \ é \ par . Assim, para todos os valores de \, tais que . Assim, _______________ Para calcular a soma dos coeficientes de ordem par basta fazer . + a)^n - (1-a)^n. 2 Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 Vamos considerar um exemplo para ilustrar: Considere (x + 2)⁴ = x⁴ + 8x³ + 24x² + 32x + 16 = T₁x⁴ + T₂x³ + T₃x² + T₄x + T₅ e Considere (x - 2)⁴ = x⁴ - 8x³ + 24x² - 32x + 16 = T₁x⁴ - T₂x³ + T₃x² - T₄x + T₅ Assim, Sₚ = T₂ + T₄ = 16x³ + 64x = 2[T₂ + T₄]. Se vc quiser saber a soma dos coeficientes de ordem par 8 + 32 = 40 é só fazer: Cₚ = P(1) = (1 + a)ⁿ - (1 - a)ⁿ 2 = (1 + 2)⁴ - (1 - 2)⁴ 2 = 34 - (-1)⁴ 2 = 81 - 1 2 = 40. 2. Polinômio de Leibniz. Vamos generalizar a fórmula do binômio de Newton. O que seria por exemplo (a + b + c)²? (a + b + c)² = (a + b + c)(a + b + c) = a² + b² + c² + 2ab + 2ac + 2bc. O que seria por exemplo (a + b + c)³? (a + b + c)³ = (a + b + c)(a + b + c)² = a³ + b³ + c³ + 3a²b + 3a²c + 3b²c + 3ab² + 3ac² + 3bc² + Temos 10 termos. Como explicar isso a priori? Note que cada termo é da forma com não negativos. Se tem . Se tem . Se k = 1 tem abc. Logo teremos tantos termos quantas são as soluções não negativas da equação: i + j + Sabemos que (Morgado páginas 48 a 52) que o número de soluções inteiras não negativas da equação é dada por No nosso caso temos e . Logo ( 3 - 1 3) = ( Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 O termo geral de (a + b + c)³ é dado por: TG = 3! i!j!k! aⁱbʲcᵏ, i + j + k = 3. O termo geral de (a + b + c)ⁿ é dado por: TG = n! i!j!k! aⁱbʲcᵏ, i + j + k = n. Vamos enunciar a generalização do teorema. (x₁ + x₂ + ... + xₚ)ⁿ = ∑ n! a₁!a₂!...aₚ! x₁ᵃ¹x₂ᵃ²...xₚᵃᵖ, O somatório é feito para todos os valores inteiros não negativos de a₁, a₂, ..., aₚ tais que a₁ + a₂ + ... + aₚ = n. Exemplo 10. Considere a expressão (x² + 2x - 1)⁴. Responda: a. Quantos termos há na expressão? Solução: Fazendo x₁ = x², x₂ = 2x e x₃ = -1 temos k = 3 e n = 4. O número de termos é dado CR₄₃ = ( 3 + 4 - 1 4) = ( 6 4) = 15 termos. b. Qual a expressão do termo Geral? Solução: TG = 4! a₁!a₂!a₃! x₁ᵃ¹x₂ᵃ²x₃ᵃ³ , a₁ + a₂ + a₃ = 4. TG = 4! a₁!a₂!a₃! x²ᵃ¹(2x)ᵃ²(-1)ᵃ³ = (-1)ᵃ³2ᵃ² x²ᵃ¹⁺ᵃ² com . c. Existe algum termo da expressão que independe de ? Solução: Assim o coeficiente de neste termo deve valer zero. logo sujeito à condição a₂ + a₃ = 4. Logo, a₁ = 0, 4. Seu coeficiente é dado por: C = 4! 0!0 Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 a₁ a₂ a₃ Termo 0 4 0 16x⁴ 1 2 1 -48x⁴ 2 0 0 6x⁴ Somando temos que o termo em x⁴ do desenvolvimento é -26x⁴. O coeficiente vale -26. e. Determine a soma dos coeficientes desse desenvolvimento. Solução: A maior potência é x⁸. Assim P(x) = (x² + 2x - 1)⁴ = A₀ + A₁x + A₂x² + A₃x³ + A₄x⁴ + A₅x⁵ + A₆x⁶ + A₇x⁷ + A₈x⁸. Assim, P(1) = (1² + 2 × 1 - 1)⁴ = A₀ + A₁ + A₂ + A₃ + A₄ + A₄ + A₅ + A₆ + A₇ + A₈ = 16. f. Mostre que P(x) = (x² + 2x - 1)⁴ = x⁸ = 1 - 8x + 20x² - 8x³ - 32x⁶ + 8x⁵ + 20x⁶ + 8x⁷ + x⁸. Note que depois da redução dos termos semelhantes temos 9 termos. Solução: Ordem a₁ a₂ a₃ Termo 1 4 0 0 x⁸ 2 0 4 0 16x⁴ 3 0 0 4 1 4 3 1 0 8x⁷ 5 3 0 1 -4x⁶ 6 1 0 3 -4x² 7 1 3 0 32x⁵ 8 0 1 3 -8x 9 0 3 1 -32x³ 10 2 1 1 -24x⁵ 11 1 2 1 -48x⁴ 12 1 1 2 24x³ 13 2 2 0 24x⁶ 14 2 0 0 6x⁴ 15 0 2 2 24x² Da última coluna da tabela anterior obtemos: P(x) = (x² + 2x - 1)⁴ = x 20x⁶ + 8x⁵ 4 - 8 x² - 1. This page intentionally left blank.