Combinatoria: Variaciones, Combinaciones y Permutaciones
$$ \left\{\begin{array}{l} \hbox{Con orden } \left\{\begin{array}{l}
\hbox{No todos } \mathbf{\hbox{(Variaciones)}} \left\{\begin{array}{l}
\hbox{Sin repetición: } V_{n,k}=\displaystyle{\frac{n!}{(n-k)!}}=n \cdot (n-1)
\cdots (n-k+1)\\ \hbox{Con repetición: } VR_{n,k}=n^k \end{array}\right.\\ \\
\hbox{Todos } \mathbf{\hbox{(Permutaciones)}} \left\{\begin{array}{l}
\hbox{Sin repetición: } P_{n}=n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1\\
\hbox{Con repetición: }
PR_{n}^{\alpha_1,\alpha_2,\cdots,\alpha_k}=\displaystyle{\frac{n!}{\alpha_1!
\cdot \alpha_2!\cdots \alpha_k!}} \end{array}\right.\\ \end{array}\right.\\ \\
\hbox{Sin orden } \mathbf{\hbox{(Combinaciones)}}
\left\{\begin{array}{l} \hbox{Sin repetición: } C_{n,k} =
\displaystyle{\binom{n}{k}} = \displaystyle{\frac{n!}{(n-k)! \cdot k!}}\\
\hbox{Con repetición: } CR_{n,k} = C_{n+k-1,k} = \displaystyle{\binom{n+k-1}{k}}
= \displaystyle{\frac{(n+k-1)!}{(n-1)! \cdot k!}}\\ \end{array}\right.\\
\end{array}\right. $$ $$ \left.\begin{array}{l} \mathbf{\hbox{ (Permutaciones
circulares)}} PC_n=(n-1)!\\ \end{array}\right. $$
Números Combinatorios
$$\left\{\begin{array}{l} \mathbf{\hbox{(Factorial de n) }} n! = n \cdot (n-1)
\cdot (n-2) \cdots 2 \cdot 1 \hbox{ , } \forall n \in \mathbb{N}\\
\mathbf{\hbox{(Propiedades)}} \left\{\begin{array}{l} n! = n \cdot (n-1)!\\ 0! =
1\\ \end{array}\right.\\ \mathbf{\hbox{(Número combinatorio) }} \hbox{Dados n,
m} \in \mathbb{N},n \geq m, \displaystyle{\binom{n}{m}} =
\displaystyle{\frac{n!}{m!(n-m)!}} \\ \mathbf{\hbox{(Propiedades)}}
\left\{\begin{array}{l} \displaystyle{\binom{n}{0}} = 1, \hbox{ }
\displaystyle{\binom{n}{1}} = n, \hbox{ } \displaystyle{\binom{n}{n}} = 1\\
\displaystyle{\binom{n}{m}} = \displaystyle{\binom{n}{n-m}}, \hbox{ }
\displaystyle{\binom{n}{m}} + \displaystyle{\binom{n}{m+1}} =
\displaystyle{\binom{n+1}{m+1}}\\ \end{array}\right.\\ \end{array}\right. $$
Triángulo de Tartaglia (o de Pascal)
$$\left.\begin{array}{ccccccccc} & & & &
\displaystyle{\binom{0}{0}}=1 & & & & \\ & & &
\displaystyle{\binom{1}{0}}=1 & & \displaystyle{\binom{1}{1}}=1 &
& & \\ & & \displaystyle{\binom{2}{0}}=1 & &
\displaystyle{\binom{2}{1}}=2 & & \displaystyle{\binom{2}{2}}=1 &
& \\ & \displaystyle{\binom{3}{0}}=1 & &
\displaystyle{\binom{3}{1}}=3 & & \displaystyle{\binom{3}{2}}=3 &
& \displaystyle{\binom{3}{3}}=1 & \\ \displaystyle{\binom{4}{0}}=1 &
& \displaystyle{\binom{4}{1}}=4 & & \displaystyle{\binom{4}{2}}=6
& & \displaystyle{\binom{4}{3}}=4 & &
\displaystyle{\binom{4}{4}}=1\\ & & & & \vdots & & &
& \\ \end{array}\right. $$
Algunas resultados teóricos importantes
-
\(C_{n,k} = \displaystyle{\frac{V_{n,k}}{P_{k}}}\)
Demostración:
$$C_{n,k} = \displaystyle{\binom{n}{k}} = \displaystyle{\frac{n!}{(n-k)!
\cdot k!}} =$$ $$= \displaystyle{\frac{n \cdot (n-1) \cdots (n-k+1) \cdot
(n-k)!}{(n-k)! \cdot k!}} =$$ $$= \displaystyle{\frac{n \cdot (n-1) \cdots
(n-k+1)}{k!}} = \displaystyle{\frac{V_{n,k}}{P_{k}}}$$
-
\(\displaystyle{\binom{n}{m}} + \displaystyle{\binom{n}{m+1}} =
\displaystyle{\binom{n+1}{m+1}}\)
Demostración:
$$\displaystyle{\binom{n}{m}} + \displaystyle{\binom{n}{m+1}} =$$ $$=
\displaystyle{\frac{n!}{m!(n-m)!}} +
\displaystyle{\frac{n!}{(m+1)!(n-(m+1))!}} =$$ $$=
\displaystyle{\frac{n!}{m!(n-m)!}} +
\displaystyle{\frac{n!}{(m+1)!(n-m-1)!}} =$$ $$=
\displaystyle{\frac{(m+1)n!}{(m+1)!(n-m)!}} +
\displaystyle{\frac{(n-m)n!}{(m+1)!(n-m)!}} =$$ $$=
\displaystyle{\frac{((m+1)+(n-m))n!}{(m+1)!(n-m)!}} =
\displaystyle{\frac{(m+1+n-m)n!}{(m+1)!(n-m)!}} =$$ $$=
\displaystyle{\frac{(n+1)n!}{(m+1)!(n-m)!}} =
\displaystyle{\frac{(n+1)!}{(m+1)!(n-m)!}} =$$ $$=
\displaystyle{\frac{(n+1)!}{(m+1)!((n+1)-(m+1))!}} =
\displaystyle{\binom{n+1}{m+1}}$$
