Función generatriz

En matemáticas, una función generadora o función generatriz es una serie formal de potencias cuyos coeficientes codifican información sobre una sucesión an cuyo índice corre sobre los enteros no negativos.

Hay varios tipos de funciones generatrices: funciones generadoras ordinarias, funciones generadoras exponenciales, la serie de Lambert, la serie de Bell y la serie de Dirichlet; de las cuales abajo se ofrecen definiciones y ejemplos. Cada sucesión tiene una función generadora de cierto tipo. El tipo de función generatriz que es apropiada en un contexto dado depende de la naturaleza de la sucesión y los detalles del problema que se analiza.

Las funciones generadoras son expresiones cerradas en un argumento formal x. En ocasiones, una función de este tipo se «evalúa» en un valor específico x=a pero hay que tener en cuenta que las funciones generadoras son series formales de potencias, por lo que no se considera ni se analiza el problema de la convergencia en todos los valores de x.

Por lo mismo es importante observar que las funciones generatrices no son realmente funciones en el sentido usual de ser mapeos entre un dominio y un codominio; el nombre es únicamente el resultado del desarrollo histórico de su estudio.

Una función generadora es una cuerda de tender en la que colgamos una sucesión de números para mostrarla

Función generadora ordinaria

La función generadora ordinaria de una sucesión (an) = a0, a1, a2, a3 ... se define como

Es común usar la expresión función generadora sin mayor calificativo, para referirse a este tipo de función.

Ejemplo.
La sucesión de Fibonacci definida por la recurrencia

es la sucesión 0,1,1,2,3,5,8,13,21,...
Su función generatriz es

puesto que el desarrollo en serie de potencias de tal función es

.

y los coeficientes de tal desarrollo son precisamente 0,1,1,2,3,5,8,13,...

Es posible definir funciones generadoras sobre varias variables. Por ejemplo, la función generadora ordinaria en 2 variables de (am,n) donde n y m son índices que recorren los enteros no negativos, es

Aplicaciones

Si bien las funciones generatrices son una herramienta usada ampliamente en combinatoria, no existen métodos detallados que proporcionen solución a los problemas en cada situación. Sin embargo existen ideas generales que pueden ser modificadas y adaptadas en las diferentes situaciones que se presentan. A continuación se ilustran varios usos de las funciones generadoras junto con la idea general que se está usando.

Determinación de la función generadora a partir de una recurrencia

En esta situación lo que se hace es multiplicar ambos lados de la recurrencia por xn y sumar sobre todos los índices. Después se efectúan transformaciones para que la igualdad entre sumas que se obtiene se convierta en una ecuación que involucra la función generatriz y se procede a resolverla.

Como ilustración, considere la recurrencia

.

que da origen a la sucesión (an)=1,5,17,53,161,485,1457...

Multiplicando ambos lados por xn y sumando sobre todos los valores de n se obtiene:

.

El lado izquierdo es casi la función generadora, pero los índices están desfasados. Pero notando que

,

se deduce que el lado izquierdo es

.

El lado derecho se desarrolla como

.

Al final, se aplicó la fórmula para sumar una serie geométrica:[2]

.

Igualando ambas simplificaciones, se obtiene la ecuación

que al resolverse arroja por resultado

Ejemplo de aplicación práctica

Si cn es el número de formas en que se puede pagar n pesos usando monedas de 1, 2 y 5 pesos, entonces la función generatriz de la sucesión (cn) es

.

ya que el coeficiente de xn es igual al número de formas de escoger a, b, c tales que

y que corresponen a usar a monedas de 1 peso, b monedas de 2 pesos y c monedas de 5 pesos.

La aplicación de la fórmula de Taylor es demasiado compleja en este caso, por lo que aplicaremos el siguiente artificio debido a Ronald Graham.

Cada uno de los denominadores (1-x), (1-x2) y (1-x5) son divisores de (1-x10), por lo que podemos reescribir

para un A(x) en donde:

Finalmente, desarrollando la función generadora

obtenemos

.

De la expresión anterior se puede leer con detalle el valor exacto del coeficiente de xn, es decir, el número cn de formas de pagar n pesos con monedas de 1,2 y 5 pesos. Por ejemplo, el número de formas de pagar 77 pesos se obtiene calculando el término correspondiente a x77:

y se concluye que hay 328 formas de pagar 77 pesos con monedas de 1, 2 o 5 pesos.

Otras funciones generadoras

Función generadora exponencial

La función generadora exponencial de una sucesión an es

Función generadora de Poisson

La función generadora de Poisson de una sucesión an es

Serie de Lambert

La serie de Lambert de una sucesión an es

Nótese que en una serie de Lambert, el índice n comienza en el 1, no en 0.

Serie de Bell

La serie de Bell de una función aritmética f(n) y un número primo p es

Función generadora de la serie de Dirichlet

Las series de Dirichlet a menudo se clasifican como funciones generatrices, aunque no son estrictamente series formales de potencias. La función generadora de la serie de Dirichlet de una sucesión an es

La función generatriz de la serie de Dirichlet es especialmente útil cuando an es una función multiplicativa, cuando tiene una expresión de producto de Euler en términos de la serie de Bell de la función

Si an es un carácter de Dirichlet, entonces su función generadora de la serie de Dirichlet se llama serie L de Dirichlet.

Funciones generadoras de sucesiones polinómicas

El concepto de funciones generatrices puede extenderse a sucesiones de otros objetos. Así, por ejemplo, las sucesiones polinómicas de tipo binomial se generan por

donde pn(x) es una sucesión de polinomios y f(t) es una función de cierta forma. Las sucesiones de Sheffer se generan de modo similar. Véase el artículo principal polinomio generalizado de Appell para más información.

Ejemplos

Cuando se trabaja con funciones generadoras, es importante reconocer las expresiones de algunas sucesiones fundamentales.

Funciones generadoras ordinarias

La más fundamental de todas es la sucesión constante 1,1,1,1,..., cuya función generatriz ordinaria es

La expresión de la derecha se puede justificar multiplicando la serie de potencias de la izquierda por , y comprobando que su resultado sea la serie constante de potencias 1; en otras palabras, que todos los coeficientes desaparezcan excepto el de X0. (Por lo demás, no puede haber otra serie de potencias con esta propiedad, ya que un anillo de series de potencias como Z[[X]] es un dominio de integridad.) El lado de la derecha, por lo tanto, designa la inversa de en el anillo de series de potencias.

Fácilmente se derivan para ésta expresiones para la generación ordinaria de otras sucesiones. Por ejemplo, para la serie geométrica 1,a,a2,a3,... para cada constante a se tiene

y en particular

También se pueden introducir «brechas» regulares en la sucesión sustituyendo X por alguna potencia de X; así, por ejemplo, para la sucesión1,0,1,0,1,0,1,0,.... se obtiene la función generadora

Calculando el cuadrado de la función generatriz inicial, fácilmente se ve que los coeficientes forman la sucesión 1,2,3,4,5,..., así que se tiene

y el cubo tiene como coeficientes los números triangulares 1,3,6,10,15,21,... cuyo término n es el coeficiente binomial , de manera que

Dado que , se puede encontrar la función generadora ordinaria para la sucesión 0,1,4,9,16,... de números cuadrados por combinación lineal de las sucesiones precedentes;

Función generadora exponencial

Serie de Bell

Función generadora de la serie de Dirichlet

Aplicaciones

Las funciones generadoras se emplean para

  • encontrar una forma cerrada para una sucesión dada en una relación de recurrencia. Por ejemplo, considérense los números de Fibonacci;
  • encontrar relaciones de recurrencia para sucesiones: la forma de una función generadora puede sugerir una fórmula de recurrencia;
  • encontrar relaciones entre sucesiones: si las funciones generatrices de dos sucesiones tienen una forma similar, entonces las propias sucesiones probablemente están relacionadas;
  • explorar el comportamiento asintótico de las sucesiones;
  • demostrar identidades que implican sucesiones;
  • resolver problemas de enumeración en combinatoria;
  • evaluar sumas infinitas.

Otras funciones generadoras

Ejemplos de sucesiones polinómicas generadas por funciones generadoras más complejas son:

Véase también

Referencias

Notas

  1. Wilf, Herbert (1994). generatingfunctionology (2.ª edición). A. K. Peters. ISBN 978-1-56881-279-3. 
  2. Como se mencionó en la introducción, realmente no importa el radio de convergencia de una serie, ya que sólo se busca manipular formalmente (es decir, «mecánicamente») las expresiones. En general es suficiente que una serie sea convergente en un disco abierto (no determinado) alrededor de cero para poder usarla. En el ejemplo, la serie geométrica es convergente en el disco -1<x<1.

Enlaces externos

Read other articles:

العلاقات الآيسلندية السريلانكية آيسلندا سريلانكا   آيسلندا   سريلانكا تعديل مصدري - تعديل   العلاقات الآيسلندية السريلانكية هي العلاقات الثنائية التي تجمع بين آيسلندا وسريلانكا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدول�...

 

 

Adolfo Zaldívar Presidente del Senato del CileDurata mandato12 marzo 2008 –13 marzo 2009 PredecessoreEduardo Frei Ruiz-Tagle SuccessoreJovino Novoa Ambasciatore del Cile in ArgentinaDurata mandato16 aprile 2010 –27 febbraio 2013 PredecessoreMiguel Otero SuccessoreMilenko Skoknic Presidente del Partito Regionalista degli IndipendentiDurata mandato2009 –2010 PredecessoreJaime Mulet SuccessoreEduardo Díaz del Río Presidente del Partito Democrati...

 

 

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article présente des problèmes à corriger. Vous pouvez aider à l'améliorer ou bien discuter des problèmes sur sa page de discussion. Il ne cite pas suffisamment ses sources. Vous pouvez indiquer les passages à sourcer avec {{référence nécessaire}} ou {{Référence souhaitée}}, et inclure les références utiles en les liant aux notes de bas de page. (Marqué depuis mars 2015) Certaines informations...

Pour les articles homonymes, voir Toccata (homonymie). Vous lisez un « article de qualité » labellisé en 2020. Dinu Lipatti à l'œuvre sur un piano C. Bechstein. La toccata (de l'italien : toccare, « toucher » ; pl. toccate ; en espagnol : tocar) est, dans la musique baroque, une composition de forme libre pour les instruments à clavier — orgue, clavecin ou piano. Elle est caractérisée par ses figures brillantes, sa virtuosité et son ...

 

 

Stampo per colata in sabbia (aperto) Esempio di manufatti in bronzo (a sinistra) e in alluminio (a destra) di una colata in sabbia La colata in sabbia è un processo di produzione industriale del tipo fusione. La prima fase consiste nella creazione di un modello di materiali vari, attorno a cui sarà costruita la forma. Solitamente, è previsto un piano di simmetria per l'apertura corretta della stessa senza danneggiare il modello. Approntata la forma, con tutte le necessarie anime e incavi p...

 

 

Kristján Flóki Finnbogason Nazionalità  Islanda Altezza 190 cm Peso 82 kg Calcio Ruolo Attaccante Squadra  KR Reykjavík CarrieraGiovanili  FH Hafnarfjörður2013-2015 CopenaghenSquadre di club1 2012-2013 FH Hafnarfjörður2 (0)2015-2017 FH Hafnarfjörður49 (16)2017-2018 Start23 (6)2018→  Brommapojkarna11 (2)[1]2019 Start13 (1)2019- KR Reykjavík20 (7)Nazionale 2011-2012 Islanda U-1713 (2)2012-2014 Islanda U-1918 (6)2015-2016 Is...

ФинансыФинансовое право Финансовая система Публичные финансы Международные Государственные Муниципальные Частные финансы Корпоративные Финансы домохозяйств Финансовые рынки Валютный рынок Рынок золота Рынок капитала Денежный рынок Страховой рынок Мировые финансо...

 

 

Mountain range in Spain This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Picos de Europa – news · newspapers · books · scholar · JSTOR (July 2016) (Learn how and when to remove this message) You can help expand this article with text translated from the corresponding article in Spanish. (December 2016) C...

 

 

NeyUn esemplare di ney turcoInformazioni generaliOrigineIran Classificazione421.111.1 Aerofoni labiali FamigliaFlauti diritti UsoMusica dell'Asia Occidentale Il ney (detto anche nai, nye o nay) è un flauto caratteristico soprattutto della musica tradizionale colta della Persia, della Turchia e di altri paesi del Medio Oriente, anche se è ampiamente diffuso nella musica popolare di diverse zone del Mediterraneo e dell'Asia occidentale. In alcune di queste tradizioni musicali, è l'unico stru...

Station in Perth, Western Australia Ranford Roadunderconstruction Feb 2024General informationLocationRanford Road, LeemingAustraliaCoordinates32°04′32″S 115°53′45″E / 32.075491°S 115.895717°E / -32.075491; 115.895717 (Ranford Road Station) Owned byPublic Transport AuthorityOperated byTransperthLine(s)     Thornlie linePlatforms2 (1 island)Tracks2Bus stands14ConnectionsBusConstructionStructure typeGroundParkingYesAccessibleYe...

 

 

1999 compilation album by KC and the Sunshine Band25th Anniversary CollectionCompilation album by KC and the Sunshine BandReleased1999GenreDiscoLength113:54LabelRhinoKC and the Sunshine Band chronology Get Down Live!(1995) 25th Anniversary Collection(1999) I'll Be There for You(2001) 25th Anniversary Collection is a compilation album by KC and the Sunshine Band, released in 1999. It is the most comprehensive KC and the Sunshine Band collection to date, containing nearly every single r...

 

 

Helaran Kuda Renggong. Kuda Renggong (aksara Sunda: ᮊᮥᮓ ᮦᮛᮀᮍᮀᮧ) adalah salah satu seni pertunjukan helaran yang berasal dari Kabupaten Sumedang. Kata renggong merupakan metatesis dari kata ronggeng yang berarti kamonesan (keterampilan) cara berjalan kuda yang dilatih menari dan mengikuti irama musik yang didominasi oleh kendang.[1] Kesenian ini sering dijadikan hiburan arak-arakan anak khitanan atau sunat, menerima tamu kehormatan, perayaan hari besar, dan pengisi ac...

Type of Motorboat which has a cabin for the captain and passengers This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Cabin cruiser – news · newspapers · books · scholar · JSTOR (January 2007) (Learn how and when to remove this message) Numerous cabin cruisers moored at a marina in the United Kingdom. A cabin c...

 

 

Swedish military officer and politician (1614–1685) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (May 2023) (Learn how and when to remove this message) Gustaf Otto Stenbock; engraving by Nicolas Pitau Gustaf Otto Gustafsson Stenbock (17 September 1614, Torpa stenhus – 24 September 1685, Stockholm) was a Swedish military officer and politician. Biography...

 

 

いすゞ自動車 > いすゞ自動車の製品一覧 いすゞ自動車の製品一覧(いすゞじどうしゃのせいひんいちらん)では、いすゞ自動車から生産・発売している、自動車、エンジン、その他製品について述べる。 過去に販売していた車種・製品についても述べる。 トラック 車種 初登場年 現行型 備考 発表 マイナーチェンジ 小型 ELF MIO エルフミオ 2024年7月24日 2024年7月24�...

Cet article est une ébauche concernant une unité ou formation militaire et les Émirats arabes unis. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Forces armées émiriennesالقوات المسلحة لدولة الإمارات العربية المتحدة Emblème des Forces armées émiriennes Fondation 1951 Forme actuelle 1971 Branches Armée de terreForces aériennesMarine Commandement Commandant supr�...

 

 

Binary star system in the constellation Cygnus This article is about ο2/3 Cygni. For other star systems with this Bayer designation, see ο Cygni. 32 Cygni Location of 32 Cygni (circled) Observation dataEpoch J2000      Equinox J2000 Constellation Cygnus Right ascension 20h 15m 28.32421s[1] Declination +47° 42′ 51.2139″[1] Apparent magnitude (V) 3.98[2] (3.90 - 4.14[3]) Characteristics Spectral...

 

 

田島道治 田島 道治(たじま みちじ、1885年(明治18年)7月2日 - 1968年(昭和43年)12月2日[1])は、日本の実業家、銀行家。 戦後、第2代宮内府長官、初代宮内庁長官(宮内府長官時代を含め、在任 1948年(昭和23年) - 1953年(昭和28年)[2])を歴任し、GHQ(連合国軍最高司令官総司令部)の占領下にあって宮中・皇室改革に尽力した。 生涯 生い立ち 1885年(明�...

Stade Emmanuel-HielGénéralitésNom complet Emmanuel HielstadionAdresse Emmanuel HielstraatGandConstruction et ouvertureOuverture 1905Rénovation 1922 (grande tribune en bois)1960 (modernisation) 1982 (modernisation)UtilisationClubs résidents K. RC Gent-Zeehaven (1905-2010)Propriétaire Ville de GandÉquipementSurface Pelouse naturelleCapacité 6.500Affluence record 15.000 (1953 derby contre La Gantoise)LocalisationCoordonnées 51° 02′ 30″ N, 3° 45′ 34″...

 

 

Last Habsburg Emperor from 1916 to 1918 Karl I redirects here. For other uses, see Charles I (disambiguation). CharlesCharles I, c. 1919Emperor of Austria King of Hungary (more...) Reign21 November 1916 – 12 November 1918Coronation30 December 1916PredecessorFranz Joseph ISuccessorMonarchy abolishedBorn(1887-08-17)17 August 1887Persenbeug-Gottsdorf, Austria-HungaryDied1 April 1922(1922-04-01) (aged 34)Funchal, Madeira, PortugalSpouse Zita of Bourbon-Parma ​ ​(m...