·
Cursos Gerais ·
Matemática Discreta
Send your question to AI and receive an answer instantly
Recommended for you
16
Teoria_morgado_binomiodenewton
Matemática Discreta
UFC
16
Teoria_morgado_binomiodenewton
Matemática Discreta
UFC
16
Teoria_morgado_binomiodenewton
Matemática Discreta
UFC
16
Teoria_morgado_binomiodenewton
Matemática Discreta
UFC
2
Avaliação Antiga
Matemática Discreta
UFC
11
Lista 1 Resolvida-2022 2
Matemática Discreta
UFC
3
P3 - 2023-1
Matemática Discreta
UFC
3
Avaliação 3-2021 2
Matemática Discreta
UFC
100
Inducao Matematica - Matematica Discreta - Apresentacao Power Point
Matemática Discreta
UFC
66
Logica Matematica Discreta - Argumento Valido e Raciocinio Dedutivo
Matemática Discreta
UFC
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 termos. vamos expandir o somatório: (x + a)^n = \binom{n}{n} x^{n-0} + \binom{n}{n-1} a x^{n-1} + \binom{n}{n-2} a^2 x^{n-2} + \ldots + \binom{n}{0} a^n. 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} 1 Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 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} a x + \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 + 4a^3 x + a^4 = = \binom{4}{0} x^4 + \binom{4}{1} a x^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 tempo 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: Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 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^{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} \left(\frac{1}{3}\right)^k (1)^{65-k} = \binom{65}{k}\left(\frac{1}{3}\right)^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} = \left(\begin{array}{c} 65 \\ k-1 \end{array}\right) \frac{1}{3^{k-1}} = \frac{65!}{k!(66-k)!3^{k-1}}. Vamos arrumar de modo conveniente e cancelando 65! \frac{65!}{k!(66-k)!}3^k > \frac{65!}{(k-1)!(66-k)!}3^{k-1}. Simplificando \frac{(66-k)!(65-k)!}{(65-k)!} > \frac{k(k-1)!}{(k-1)!}3^k > \frac{k(k-1)!}{(k-1)!}3^{k-1}. 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 é T_{17} = \left(\begin{array}{c} 65 \\ 16 \end{array}\right). 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_{x+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} \left(\begin{array}{c} 9 \\ k \end{array}\right)x^k. Solução: Assim T_{k+1} = \left(\begin{array}{c} 9 \\ k \end{array}\right), k = 0, 1, 2, \ldots, 10. Logo T_1 = T_{10} = \left(\begin{array}{c} 9 \\ 0 \end{array}\right) = \left(\begin{array}{c} 9 \\ 9 \end{array}\right) = 1, T_2 = T_9 = \left(\begin{array}{c} 9 \\ 1 \end{array}\right) = \left(\begin{array}{c} 9 \\ 8 \end{array}\right) = 9, T_3 = T_8 = \left(\begin{array}{c} 9 \\ 2 \end{array}\right) = \left(\begin{array}{c} 9 \\ 7 \end{array}\right) = 36, T_4 = T_7 = \left(\begin{array}{c} 9 \\ 3 \end{array}\right) = \left(\begin{array}{c} 9 \\ 6 \end{array}\right) = 84, T_5 = T_6 = \left(\begin{array}{c} 9 \\ 4 \end{array}\right) = \left(\begin{array}{c} 9 \\ 5 \end{array}\right) = 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 T_{k+1} = \left(\begin{array}{c} 9 \\ k \end{array}\right), k = 0, 1, 2, \ldots, 10, e T_{k=k-1+1} = \left(\begin{array}{c} 9 \\ k-1 \end{array}\right), k = 1, 2, \ldots, 10. Assim, T_{k+1} = T_k, \left(\begin{array}{c} 9 \\ k \end{array}\right) = \left(\begin{array}{c} 9 \\ k-1 \end{array}\right). Logo como k \neq k-1 e usando as propriedades de combinações complementares temos: k+k-k-1 = 9, 2k = 10, k = 5. Logo T_5 = T_6. Quando T_{k+1} < T_k? 9! < \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 Universidade Federal do Ceará DEMA Semestre 2020.1 e \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad k > 5. Isto quer dizer: T_7 < T_6, T_8 < T_7, T_9 < T_8, T_{10} < T_9, T_{11} < T_{10}. Para \quad k \ = 1, 2, 3, 4, 5 \ \ \ \temos Tk+1 > Tk Logo T_1 < T_2 < T_3 < T_4 < T_5. Juntando tudo temos: T_1 < T_2 < T_3 < T_4 < T_5 = T_6 > T_7 > T_8 > T_9 > T_{10} > T_{11}. T_5 e T_6 são os termos com valores máximos. Esta técnica será empregada em Probabilidade I para calcular a moda das variáveis discretas como a Poisson, Pascal e a Binomial. > > 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 Universidade Federal do Ceará DEMA Semestre 2020.1 P(x) = \sum_{i=0}^{m} A_ix^i = A_0 + A_1x + A_2x^2 + \ldots + A_mx^m. O valor numérico de \ P(x)\ para \ x = 1\ nos dará a soma pretendida. P(1) = \sum_{i=0}^{m} A_i1^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) = (1^3 - 2 \times 1^2)^{15} = (-1)^{15} = -1. Vamos fazer de outra maneira usando O software R: Note que o termo geral é dado por: T_k = \binom{15}{k} (-2x^2)^k (x^3)^{15-k} = \binom{15}{k} (-1)^{k}x^{45-k}. Para x = 1 temos o expoente m = 45 que é o grau do 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} = note que \ \ \quad \quad \quad \quad \quad \quad \quad \quad\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quadI^{15-k} = 1, belo truque não? \ multiplicar por \ 1\ não altera. Seja \quad 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 Universidade Federal do Ceará DEMA 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)!} = \frac{(n-1)!}{(k-1)!(n-k)!} = \binom{n-1}{k-1}. Logo, S = \sum_{k=1}^{n}k\binom{n}{k}x^k = \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. Dessa maneira S = \sum_{k=1}^{n} \binom{n}{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, cujá derivada em relação a x é dada por: 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 , cujá derivada em relação a x é dada por: f'(x) = \sum_{k=0}^{n} \binom{n}{k} k x^{k-1}. Igualando as duas temos: \sum_{k=0}^{n} \binom{n}{k} k x^{k-1} = n(1+x)^{n-1}, multiplicando ambos os lados por x temos \sum_{k=0}^{n} \binom{n}{k} k x^k = nx(1+x)^{n-1}. Exemplo 7. Usando o exemplo 6 mostre que: \sum_{k=0}^{n} \binom{n}{k} k = n2^{n-1}. Solução: Note que: f(1) = \sum_{k=0}^{n} \binom{n}{k} 1^k = n \times 1 \times ( Exemplo 7. Mostre que Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará 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. Exemplo 8. Mostre que \sum_{k=0}^{n} (-1)^k \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 = -1 e x = 1 temos: (1-1)^n = \sum_{k=0}^{n} \binom{n}{k} (-1)^k1^{n-k} = \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0^n = 0. Exemplo 9. 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+\ldots e (x-a)^n = T_1-T_2+T_3-T_4 Subtraindo as duas expressões temos: (x-a)^n = 2[T_2+T_4+\ldots]. Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA 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=3⁴−(−1)⁴2=81−12=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 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⎞⎠=( 13 Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA 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ₚ)ⁿ=∑a₁!a₂!...aₚ!x₁ᵃ¹x₂ᵃ²...xₚᵃᵖ,a₁+a₂+...+aₚ=n. Exemplo 10. Considere a expressão (x²+2x−1)⁴. Responda: a. Quantos termos há na expressão? Solução: Fazendo a₁=x²,a₂=2x e a₃=−1 temos k=3 e n=4. O número de termos é dado CR₃⁴=(3+4−1)(4)=(64)(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₃!(2x)²(−1)³ᵃ₃=(−1)ᵃ₃2ᵃ₂la₂! com a c. Existe algum termo da expressão que independe a ? 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! d. Determine o coeficiente de Solução: Assim o coeficiente de neste termo deve valer zero, logo sujeito à condição 4. As possíveis soluções são: 14 Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 a₁a₂a₃Termo 04016x⁴ 211−48x⁴ 2006x⁴ 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₈=16. f. Mostre que P(x)=[x²+2x−1]⁴=1−8x+20x²−8x³−26x⁴+8x⁵+20x⁶+8x⁷+x⁸. Note que depois da redução dos termos semelhantes temos 9 termos. Solução: Ordem a₁a₂a₃Termo 1 400x⁸ 2 04016x⁴ 3 0011 4 3108x⁷ 5 301−4x⁶ 6 103−4x² 7 13032x⁵ 8 013−8x³ 9 031−32x³ 10 212−24x⁵ 11 121−48x⁴ 12 1224x³ 13 22024x⁶ 14 2006x⁴ 15 02224x² Da última coluna ta tabela anterior obtemos: P(x)=[x²+2x−1]⁴=x+20x⁶+8x⁵−48x²−1. 15
Send your question to AI and receive an answer instantly
Recommended for you
16
Teoria_morgado_binomiodenewton
Matemática Discreta
UFC
16
Teoria_morgado_binomiodenewton
Matemática Discreta
UFC
16
Teoria_morgado_binomiodenewton
Matemática Discreta
UFC
16
Teoria_morgado_binomiodenewton
Matemática Discreta
UFC
2
Avaliação Antiga
Matemática Discreta
UFC
11
Lista 1 Resolvida-2022 2
Matemática Discreta
UFC
3
P3 - 2023-1
Matemática Discreta
UFC
3
Avaliação 3-2021 2
Matemática Discreta
UFC
100
Inducao Matematica - Matematica Discreta - Apresentacao Power Point
Matemática Discreta
UFC
66
Logica Matematica Discreta - Argumento Valido e Raciocinio Dedutivo
Matemática Discreta
UFC
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 termos. vamos expandir o somatório: (x + a)^n = \binom{n}{n} x^{n-0} + \binom{n}{n-1} a x^{n-1} + \binom{n}{n-2} a^2 x^{n-2} + \ldots + \binom{n}{0} a^n. 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} 1 Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 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} a x + \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 + 4a^3 x + a^4 = = \binom{4}{0} x^4 + \binom{4}{1} a x^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 tempo 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: Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 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^{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} \left(\frac{1}{3}\right)^k (1)^{65-k} = \binom{65}{k}\left(\frac{1}{3}\right)^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} = \left(\begin{array}{c} 65 \\ k-1 \end{array}\right) \frac{1}{3^{k-1}} = \frac{65!}{k!(66-k)!3^{k-1}}. Vamos arrumar de modo conveniente e cancelando 65! \frac{65!}{k!(66-k)!}3^k > \frac{65!}{(k-1)!(66-k)!}3^{k-1}. Simplificando \frac{(66-k)!(65-k)!}{(65-k)!} > \frac{k(k-1)!}{(k-1)!}3^k > \frac{k(k-1)!}{(k-1)!}3^{k-1}. 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 é T_{17} = \left(\begin{array}{c} 65 \\ 16 \end{array}\right). 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_{x+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} \left(\begin{array}{c} 9 \\ k \end{array}\right)x^k. Solução: Assim T_{k+1} = \left(\begin{array}{c} 9 \\ k \end{array}\right), k = 0, 1, 2, \ldots, 10. Logo T_1 = T_{10} = \left(\begin{array}{c} 9 \\ 0 \end{array}\right) = \left(\begin{array}{c} 9 \\ 9 \end{array}\right) = 1, T_2 = T_9 = \left(\begin{array}{c} 9 \\ 1 \end{array}\right) = \left(\begin{array}{c} 9 \\ 8 \end{array}\right) = 9, T_3 = T_8 = \left(\begin{array}{c} 9 \\ 2 \end{array}\right) = \left(\begin{array}{c} 9 \\ 7 \end{array}\right) = 36, T_4 = T_7 = \left(\begin{array}{c} 9 \\ 3 \end{array}\right) = \left(\begin{array}{c} 9 \\ 6 \end{array}\right) = 84, T_5 = T_6 = \left(\begin{array}{c} 9 \\ 4 \end{array}\right) = \left(\begin{array}{c} 9 \\ 5 \end{array}\right) = 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 T_{k+1} = \left(\begin{array}{c} 9 \\ k \end{array}\right), k = 0, 1, 2, \ldots, 10, e T_{k=k-1+1} = \left(\begin{array}{c} 9 \\ k-1 \end{array}\right), k = 1, 2, \ldots, 10. Assim, T_{k+1} = T_k, \left(\begin{array}{c} 9 \\ k \end{array}\right) = \left(\begin{array}{c} 9 \\ k-1 \end{array}\right). Logo como k \neq k-1 e usando as propriedades de combinações complementares temos: k+k-k-1 = 9, 2k = 10, k = 5. Logo T_5 = T_6. Quando T_{k+1} < T_k? 9! < \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 Universidade Federal do Ceará DEMA Semestre 2020.1 e \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad k > 5. Isto quer dizer: T_7 < T_6, T_8 < T_7, T_9 < T_8, T_{10} < T_9, T_{11} < T_{10}. Para \quad k \ = 1, 2, 3, 4, 5 \ \ \ \temos Tk+1 > Tk Logo T_1 < T_2 < T_3 < T_4 < T_5. Juntando tudo temos: T_1 < T_2 < T_3 < T_4 < T_5 = T_6 > T_7 > T_8 > T_9 > T_{10} > T_{11}. T_5 e T_6 são os termos com valores máximos. Esta técnica será empregada em Probabilidade I para calcular a moda das variáveis discretas como a Poisson, Pascal e a Binomial. > > 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 Universidade Federal do Ceará DEMA Semestre 2020.1 P(x) = \sum_{i=0}^{m} A_ix^i = A_0 + A_1x + A_2x^2 + \ldots + A_mx^m. O valor numérico de \ P(x)\ para \ x = 1\ nos dará a soma pretendida. P(1) = \sum_{i=0}^{m} A_i1^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) = (1^3 - 2 \times 1^2)^{15} = (-1)^{15} = -1. Vamos fazer de outra maneira usando O software R: Note que o termo geral é dado por: T_k = \binom{15}{k} (-2x^2)^k (x^3)^{15-k} = \binom{15}{k} (-1)^{k}x^{45-k}. Para x = 1 temos o expoente m = 45 que é o grau do 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} = note que \ \ \quad \quad \quad \quad \quad \quad \quad \quad\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quadI^{15-k} = 1, belo truque não? \ multiplicar por \ 1\ não altera. Seja \quad 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 Universidade Federal do Ceará DEMA 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)!} = \frac{(n-1)!}{(k-1)!(n-k)!} = \binom{n-1}{k-1}. Logo, S = \sum_{k=1}^{n}k\binom{n}{k}x^k = \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. Dessa maneira S = \sum_{k=1}^{n} \binom{n}{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, cujá derivada em relação a x é dada por: 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 , cujá derivada em relação a x é dada por: f'(x) = \sum_{k=0}^{n} \binom{n}{k} k x^{k-1}. Igualando as duas temos: \sum_{k=0}^{n} \binom{n}{k} k x^{k-1} = n(1+x)^{n-1}, multiplicando ambos os lados por x temos \sum_{k=0}^{n} \binom{n}{k} k x^k = nx(1+x)^{n-1}. Exemplo 7. Usando o exemplo 6 mostre que: \sum_{k=0}^{n} \binom{n}{k} k = n2^{n-1}. Solução: Note que: f(1) = \sum_{k=0}^{n} \binom{n}{k} 1^k = n \times 1 \times ( Exemplo 7. Mostre que Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará 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. Exemplo 8. Mostre que \sum_{k=0}^{n} (-1)^k \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 = -1 e x = 1 temos: (1-1)^n = \sum_{k=0}^{n} \binom{n}{k} (-1)^k1^{n-k} = \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0^n = 0. Exemplo 9. 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+\ldots e (x-a)^n = T_1-T_2+T_3-T_4 Subtraindo as duas expressões temos: (x-a)^n = 2[T_2+T_4+\ldots]. Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA 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=3⁴−(−1)⁴2=81−12=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 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⎞⎠=( 13 Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA 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ₚ)ⁿ=∑a₁!a₂!...aₚ!x₁ᵃ¹x₂ᵃ²...xₚᵃᵖ,a₁+a₂+...+aₚ=n. Exemplo 10. Considere a expressão (x²+2x−1)⁴. Responda: a. Quantos termos há na expressão? Solução: Fazendo a₁=x²,a₂=2x e a₃=−1 temos k=3 e n=4. O número de termos é dado CR₃⁴=(3+4−1)(4)=(64)(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₃!(2x)²(−1)³ᵃ₃=(−1)ᵃ₃2ᵃ₂la₂! com a c. Existe algum termo da expressão que independe a ? 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! d. Determine o coeficiente de Solução: Assim o coeficiente de neste termo deve valer zero, logo sujeito à condição 4. As possíveis soluções são: 14 Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 a₁a₂a₃Termo 04016x⁴ 211−48x⁴ 2006x⁴ 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₈=16. f. Mostre que P(x)=[x²+2x−1]⁴=1−8x+20x²−8x³−26x⁴+8x⁵+20x⁶+8x⁷+x⁸. Note que depois da redução dos termos semelhantes temos 9 termos. Solução: Ordem a₁a₂a₃Termo 1 400x⁸ 2 04016x⁴ 3 0011 4 3108x⁷ 5 301−4x⁶ 6 103−4x² 7 13032x⁵ 8 013−8x³ 9 031−32x³ 10 212−24x⁵ 11 121−48x⁴ 12 1224x³ 13 22024x⁶ 14 2006x⁴ 15 02224x² Da última coluna ta tabela anterior obtemos: P(x)=[x²+2x−1]⁴=x+20x⁶+8x⁵−48x²−1. 15