Matemáticas discretas | Generación de funciones: introducción y requisitos previos

Requisito previo: conceptos básicos de combinatoria , conjunto PnC generalizado 1 , conjunto 2

Definición: Las funciones generadoras se utilizan para representar secuencias de manera eficiente mediante la codificación de los términos de una secuencia como coeficientes de potencias de una variable (digamos) $\big x$ en una serie formal de potencias.

Ahora que hemos terminado la definición formal, podemos tomarnos un minuto para discutir por qué debemos aprender este concepto.

Este concepto se puede aplicar para resolver muchos problemas matemáticos. Hay una gran parte de las matemáticas que se ocupan solo de generar funciones.

Se puede utilizar para resolver fácilmente varios tipos de problemas de conteo.
Puede usarse para resolver relaciones de recurrencia traduciendo la relación en términos de secuencia a un problema sobre funciones .
Se puede utilizar para probar identidades combinatorias.

En palabras simples, las funciones generadoras se pueden usar para traducir problemas sobre secuencias a problemas sobre funciones que son comparativamente fáciles de resolver usando maniobras.

Algunos requisitos básicos…

Antes de comenzar, veamos algunas fórmulas básicas de combinatoria.

$%\documentclass{article} %\usepackage{amsmath} \newcommand*{\Perm}[2]{{}^{#1}\!P_{#2}}% \newcommand*{\Comb}[2]{{}^{#1}C_{#2}}% \begin{document} \Huge $\Perm{n}{k}=\frac{n!}{(n-k)!}$ $\binom nk=\Comb{n}{k}=\frac{n!}{k!(n-k)!}$ \end{document}$

Una función generadora es una serie de potencias «formal» en el sentido de que generalmente consideramos a x como un marcador de posición en lugar de un número. Solo en casos excepcionales evaluaremos realmente una función generadora dejando que x tome un valor de número real, por lo que generalmente ignoramos el problema de la convergencia.

$$g_0, g_1, g_2, g_3....$ of real numbers is the infinite series:
$%\documentclass{article} %\usepackage{amsmath} \begin{document} \huge \func G(x) = g_0+{g_1}x+{g_2}x^{2}..... = \sum_{k=0}^\infty g_k x^k. \end{document}$

$[g_{0},g_{1},g_{2},g_{3}...]\leftrightarrow g_{0} + g_{1}x+g_{2}x^{2}+g_{3}x^{3}....$

Nota: indicaremos la correspondencia entre una sucesión y su función generadora con una flecha de dos puntas.

Algunas secuencias importantes y sus resultados…

$\textup{Let }G_{n}=1+x+x^{2}+x^{3}+.....+x^{n-1}+x^{n}..........\hspace{1cm} eq^{n} (1)\\ \textup{Multiplying it with x } \\ xG_{n}=x+x^{2}+x^{3}+....\hspace{1cm} eq^{n} (2) \\ \\ \textup{subtracting equation (2) with (1) we will get.. } \\ G_{n}-xG_{n} =1 \\ \\G_{n}=\frac{1}{1-x}$

Si desea saber más sobre la derivación de las secuencias dadas, puede consultar aquí

$%\documentclass{article} %\usepackage{amsmath} \begin{document} \Large $\frac{1} {(1-x)}$ = 1 + x + x^2 + x^3.... \longleftrightarrow [1, 1, 1, 1...\normalsize\infty] \end{document}$

$%\documentclass{article} %\usepackage{amsmath} \begin{document} \Large $\frac{1} {(1+x)}$=1-x+x^2-x^3.... \longleftrightarrow [1, -1, 1, -1....\normalsize\infty] \end{document}$

$%\documentclass{article} %\usepackage{amsmath} \begin{document} \Large $\frac{1} {(1-ax)}$ = 1 + ax + {a^2}x^2 + {a^3}x^3.... \longleftrightarrow [1, a, a^2, a^3....\normalsize\infty] \end{document}$

$%\documentclass{article} %\usepackage{amsmath} \begin{document} \Large %$\frac{1} {(1-ax)}$ = 1 - ax + {a^2}x^2 - {a^3}x^3.... \longleftrightarrow [1, a, a^2, a^...\infty] $\frac{1} {(1-x^{2})}$ = 1 + x^2 + x^4.... \longleftrightarrow [1, 0, 1, 0...\normalsize\infty] \end{document}$

Tenga en cuenta que toda la serie anterior es infinita. Hay un resultado peculiar de series finitas que será muy útil, por lo que se recomienda recordar estos resultados para resolver problemas rápidamente.

Un resultado importante:

$%\documentclass{article} %\usepackage{amsmath} \begin{document} \LARGE %$\frac{1} {(1-ax)}$ = 1 - ax + {a^2}x^2 - {a^3}x^3.... \longleftrightarrow [1, a, a^2, a^.....] 1+x+x^2+x^3+....+x^n = $\frac{1 + x^{n+1}} {(1-x)}$ \end{document}$

Podemos usar estas operaciones para obtener nuevas secuencias de secuencias conocidas y nuevas funciones generadoras de funciones generadoras conocidas.

Escalamiento:
Multiplicar una función generadora por una constante escala cada término en la secuencia asociada por la misma constante.
$\textup{Scaling Rule} \newline[f_{0},f_{1},f_{2},f_{3}...]\leftrightarrow F(x) \newline [cf_{0},cf_{1},cf_{2},cf_{3}...]\leftrightarrow cF(x) \\$

$\textup{Example:} \newline [1,0,1,0,1,0...]\hspace{0.25cm}\leftrightarrow \hspace{0.25cm}1+x^{2}+x^{4}+x^{6}....\hspace{0.25cm}=\frac{1}{1-x^{2}} \\ \\ \textup{Multiplying the generating function by 2 gives}\\ \\ \frac{2}{1-x^{2}}=\hspace{0.15cm}2+2x^{2}+2x^{4}+2x^{6}..$

Suma:
Sumar funciones generadoras corresponde a sumar las dos sucesiones término por término.
$\newline[f_{0},f_{1},f_{2},f_{3},f_{4}..]\leftrightarrow F(x) \newline [g_{0},g_{1},g_{2},g_{3},g_{4}..]\leftrightarrow G(x)\newline \textup{Then}\newline [f_{0}+g_{0},f_{1}+g_{1},f_{2}+g_{2},f_{3}+g_{3},...]\leftrightarrow F(x)+G(x)$

$\textup{Example:} \newline [1,1,1,1,1,1,1,1....]\leftrightarrow \frac{1}{1-x} \hspace{1cm} \newline [1,-1,1,-1,1,-1....]\leftrightarrow \frac{1}{1+x} \newline \textup{Adding both equation we will get}\newline [2,0,2,0,2,0...]\leftrightarrow \frac{1}{1-x}+\frac{1}{1+x} \newline =\frac{2}{1-x^{2}}$

Desplazamiento a la derecha:
$\textup{Right Shifting Rule} \newline \textup{if}\hspace{0.25cm} [f_{0},f_{1},f_{2},f_{3}...]\leftrightarrow F(x) \newline \textup{then}\hspace{0.25cm} [\overbrace{\overset{\textup{k times}}{0,0,0,0,0,0} },f_{0},f_{1},f_{1}...]\leftrightarrow x^{k}F(x)$

$\newline \textup{Example:} \newline \newline [\overbrace{\overset{\textup{k times}}{0,0,0,0,0,0} },1,1,1,1,1,1,1...]\leftrightarrow x^{k}+x^{k+1}+x^{k+2}+x^{k+3}..... \newline \hspace{20cm} =x^{k}(1+x+x^{2}+x^{3}...) \newline \hspace{20cm}=\frac{x^{k}}{x-1}$

Derivación:
en general, derivar una función generadora tiene dos efectos en la secuencia correspondiente: cada término se multiplica por su índice y la secuencia completa se desplaza un lugar hacia la izquierda.
$\textup{Derivative Rule:} \newline [f_{0},f_{1},f_{2},f_{3}...] \leftrightarrow F(x) \newline [f_{1},2f_{2},3f_{3},4f_{4}...] \leftrightarrow F{}'(x)$

$\newline \textup{Example:} \newline 1+x+x^{2}+x^{3}+x^{4}+x^{5}... = \frac{1}{1-x} \newline \frac{\mathrm{d} }{\mathrm{d} x}(1+x+x^{2}+x^{3}+x^{4}...)=\frac{\mathrm{d} }{\mathrm{d} x}(\frac{1}{1-x}) \newline 1+2x+3x^{2}+4x^{3}....=\frac{1}{(1-x)^{^{2}}} \newline [1,2,3,4...]=\frac{1}{(1-x)^{2}}$

Ejemplo:
¿Qué secuencia está representada por la siguiente serie?
$%\documentclass{article} %\usepackage{amsmath} \begin{document} \Large 1 + 4x^2 + x^4 + \frac{x^5}{999} + 100x^6 + \cdots\text{?} \end{document}$
Solución Ahora debe tener esto, el coeficiente de a ₀ = 1, a ₁ = 0, a ₂ = 4, a ₃ = 0, a ₄ = 1, a ₅ = 1/999, a ₆ = 100.
Entonces, la secuencia es:
$\Large $[1, 0, 4, 0, 1, $\frac{1} {999}$, 100, ....] $$
Desde la perspectiva del examen GATE CS, los problemas de este tema se preguntan casi todos los años y los problemas se pueden resolver fácilmente con solo conocer los conceptos básicos.

Entonces, una vez hecho esto, a partir de la próxima publicación, podemos comenzar con algunos problemas de conteo interesantes y resolverlos con este enfoque. También veremos algunos problemas anteriores de GATE.
A continuación, veremos algunos problemas basados en el conteo y algunos problemas basados en la extracción de coeficientes.

REFERENCIAS:

Kenneth H Rosen: Matemáticas discretas y sus aplicaciones 6. ^° [Capítulo 2.4, 6.4]

Publicación traducida automáticamente

Artículo escrito por zerocool y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Algunos requisitos básicos…

Algunas secuencias importantes y sus resultados…

Deja una respuesta Cancelar la respuesta