Análise Combinatória (Resumo)

Prévia do material em texto

Permutações 
circulares com 
𝑛 elementos é 
(𝑛 − 1)! 
Soluções inteiras não-negativas da 
equação 𝑥1 + 𝑥2 + … + 𝑥𝑛 = 𝑟 é 
𝑃𝑠+𝑟
𝑠,𝑟 =
(𝑠+𝑟)!
𝑠!𝑟!
, onde, 𝑠 = 𝑛 − 1 =
𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑠𝑖𝑛𝑎𝑖𝑠 (+). 
Dada 𝑓: 𝐴 → 𝐵, no qual, 𝐴 e 𝐵 tem respectivamente 𝑛 e 𝑟 elementos: 
• O número total de funções é 𝑟𝑛; 
• Funções injetivas 𝐴𝑟,𝑛 =
𝑟!
(𝑟−𝑛)!
; 
• Funções bijetivas é 𝑛!, quando, 𝑛 = 𝑟. 
Termo geral: 𝑇𝑘+1 = (
𝑛
𝑘
) 𝑥𝑛−𝑘𝑦𝑘 
 
ANÁLISE COMBINATÓRIA 
 
 Princípio Fundamental da Contagem 
Se um evento é composto por duas etapas independentes, tal que, a primeira possui 𝑚 
possibilidades e a segunda 𝑛 para dada 𝑚, então a possibilidade total do evento ocorrer é 𝑚 ∙ 𝑛. 
 
 Permutação Simples 
𝑃𝑛 = 𝑛 ∙ (𝑛 − 1) ∙ … ∙ 2 ∙ 1 = 𝑛! 
Obs.: 0! = 1 
 Permutação com repetição 
𝑃𝑛
𝛼,𝛽,𝛾
=
𝑛!
𝛼!𝛽!𝛾!
 
 Arranjo Simples 
𝐴𝑛,𝑝 = 𝐴𝑛
𝑝 =
𝑛!
(𝑛−𝑝)!
 
 Combinação Simples 
𝐶𝑛,𝑝 = 𝐶𝑛
𝑝 = (
𝑛
𝑝) =
𝑛!
𝑝!(𝑛−𝑝)!
 
 
 
 
 
 Binômio de Newton 
 
 (𝑥 + 𝑦)𝑛 = 𝐶𝑛
0𝑦0𝑥𝑛 + 𝐶𝑛
1𝑦1𝑥𝑛−1 + … + 𝐶𝑛
𝑛𝑦𝑛𝑥0 
 
 Triângulo de Pascal 
 
(𝑥 + 𝑦)0 → 
(𝑥 + 𝑦)1 → 
(𝑥 + 𝑦)2 → 
⋮ 
(𝑥 + 𝑦)𝑛 → 
 
(
0
0
) → 
(
1
0
) (
1
0
) → 
 (
2
0
) (
2
1
) (
2
2
) → 
⋮ 
(
𝑛
0
) (
𝑛
1
) (
𝑛
2
) ⋯ (
𝑛
𝑛
) → 
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
 Propriedades 
i. (Binomiais complementares: 
𝑛
𝑝) = (
𝑛
𝑛 − 𝑝) 
ii. (Relação de Stifel: 
𝑛
𝑝) + (
𝑛
𝑝 + 1) = (
𝑛 + 1
𝑝 + 1
) 
iii. (
𝑛
0
) + (
𝑛
1
) + (
𝑛
2
) + … + (
𝑛
𝑛 − 1
) + (
𝑛
𝑛
) = 2𝑛