Symbolic method (combinatorics) (original) (raw)
La Combinatòria analítica és una branca de la combinatòria que descriu fent servir funcions generadores, les de les quals sovint corresponen a funcions analítiques. Donada una funció generadora, la combinatòria analítica intenta descriure el d'una successió de fent servir tècniques algebraiques. Això sovint implica l'anàlisi de les singularitats de la funció analítica associada. Dos tipus de funcions generadores s'utilitzen comunament — i . Una tècnica important per obtenir funcions generadores és la .
| Property | Value |
|---|---|
| dbo:abstract | La Combinatòria analítica és una branca de la combinatòria que descriu fent servir funcions generadores, les de les quals sovint corresponen a funcions analítiques. Donada una funció generadora, la combinatòria analítica intenta descriure el d'una successió de fent servir tècniques algebraiques. Això sovint implica l'anàlisi de les singularitats de la funció analítica associada. Dos tipus de funcions generadores s'utilitzen comunament — i . Una tècnica important per obtenir funcions generadores és la . (ca) En mathématiques, et plus précisément en combinatoire, la combinatoire analytique (en anglais : analytic combinatorics) est un ensemble de techniques décrivant des problèmes combinatoires dans le langage des séries génératrices, et s'appuyant en particulier sur l'analyse complexe pour obtenir des résultats asymptotiques sur les objets combinatoires initiaux. Les résultats de combinatoire analytique permettent notamment une analyse fine de la complexité de certains algorithmes. (fr) In combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet and is detailed in Part A of his book with Robert Sedgewick, Analytic Combinatorics, while the rest of the book explains how to use complex analysis in order to get asymptotic and probabilistic results on the corresponding generating functions. During two centuries, generating functions were popping up via the corresponding recurrences on their coefficients (as can be seen in the seminal works of Bernoulli, Euler, Arthur Cayley, Schröder, Ramanujan, Riordan, Knuth, , etc.).It was then slowly realized that the generating functions were capturing many other facets of the initial discrete combinatorial objects, and that this could be done in a more direct formal way: The recursive nature of some combinatorial structures translates, via some isomorphisms, into noteworthy identities on the corresponding generating functions. Following the works of Pólya, further advances were thus done in this spirit in the 1970s with generic uses of languages for specifying combinatorial classes and their generating functions, as found in works by Foata and Schützenberger on permutations, Bender and Goldman on prefabs, and Joyal on combinatorial species. Note that this symbolic method in enumeration is unrelated to "Blissard's symbolic method", which is just another old name for umbral calculus. The symbolic method in combinatorics constitutes the first step of many analyses of combinatorial structures, which can then lead to fast computation schemes, to asymptotic properties and limit laws, to random generation, all of them being suitable to automatization via computer algebra. (en) La combinatoria analitica può definirsi come il settore della combinatoria che affronta i problemi delle configurazioni discrete mediante le tecniche ed il linguaggio delle serie generatrici; in particolare si utilizzano acquisizioni dell'analisi complessa per ottenere dei risultati sul comportamento asintotico delle cardinalità di configurazioni combinatorie. Molti risultati della combinatoria analitica forniscono strumenti efficaci per lo studio della complessità di vari algoritmi. (it) |
| dbo:wikiPageExternalLink | http://algo.inria.fr/flajolet/Publications/book.pdf) |
| dbo:wikiPageID | 986932 (xsd:integer) |
| dbo:wikiPageLength | 28730 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1059232078 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cartesian_product dbr:Robert_Sedgewick_(computer_scientist) dbr:Enumerative_combinatorics dbr:Euler_totient_function dbr:John_Riordan_(mathematician) dbr:Cycle_index dbr:Random_permutation_statistics dbr:Computer_algebra dbr:Analytic_Combinatorics dbr:Ordinary_generating_function dbr:Generating_function dbr:George_Pólya dbr:Graph_(discrete_mathematics) dbr:Multiset dbr:Daniel_Bernoulli dbr:Labelled_enumeration_theorem dbr:André_Joyal dbr:Leonhard_Euler dbr:Combinatorial_class dbr:Combinatorial_species dbr:Combinatorics dbr:Embedding dbr:Pólya_enumeration_theorem dbr:Algebra dbc:Combinatorics dbr:Ernst_Schröder_(mathematician) dbr:Exponential_generating_function dbr:Recurrence_relation dbr:Recursion dbr:Asymptotic_distribution dbr:Arthur_Cayley dbr:Disjoint_union dbr:Dominique_Foata dbr:Donald_Knuth dbr:Marcel-Paul_Schützenberger dbr:Philippe_Flajolet dbr:Srinivasa_Ramanujan dbr:Random_generation dbr:Sequence dbr:Set_(mathematics) dbr:Set_theory dbr:Umbral_calculus dbr:Union_(set_theory) dbr:Stirling_numbers_and_exponential_generating_functions_in_symbolic_combinatorics dbr:Stirling_numbers_of_the_second_kind dbr:Stirling_numbers_of_the_first_kind dbr:Tree_(graph) dbr:Integer_partition |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Ill dbt:Math dbt:Reflist dbt:Sub dbt:Nobold dbt:Mathcal |
| dct:subject | dbc:Combinatorics |
| rdfs:comment | La Combinatòria analítica és una branca de la combinatòria que descriu fent servir funcions generadores, les de les quals sovint corresponen a funcions analítiques. Donada una funció generadora, la combinatòria analítica intenta descriure el d'una successió de fent servir tècniques algebraiques. Això sovint implica l'anàlisi de les singularitats de la funció analítica associada. Dos tipus de funcions generadores s'utilitzen comunament — i . Una tècnica important per obtenir funcions generadores és la . (ca) En mathématiques, et plus précisément en combinatoire, la combinatoire analytique (en anglais : analytic combinatorics) est un ensemble de techniques décrivant des problèmes combinatoires dans le langage des séries génératrices, et s'appuyant en particulier sur l'analyse complexe pour obtenir des résultats asymptotiques sur les objets combinatoires initiaux. Les résultats de combinatoire analytique permettent notamment une analyse fine de la complexité de certains algorithmes. (fr) La combinatoria analitica può definirsi come il settore della combinatoria che affronta i problemi delle configurazioni discrete mediante le tecniche ed il linguaggio delle serie generatrici; in particolare si utilizzano acquisizioni dell'analisi complessa per ottenere dei risultati sul comportamento asintotico delle cardinalità di configurazioni combinatorie. Molti risultati della combinatoria analitica forniscono strumenti efficaci per lo studio della complessità di vari algoritmi. (it) In combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet and is detailed in Part A of his book with Robert Sedgewick, Analytic Combinatorics, while the rest of the book explains how to use complex analysis in order to get asymptotic and probabilistic results on the corresponding generating functions. (en) |
| rdfs:label | Combinatòria analítica (ca) Combinatoire analytique (fr) Combinatoria analitica (it) Symbolic method (combinatorics) (en) |
| owl:sameAs | wikidata:Symbolic method (combinatorics) dbpedia-ca:Symbolic method (combinatorics) dbpedia-fr:Symbolic method (combinatorics) dbpedia-it:Symbolic method (combinatorics) https://global.dbpedia.org/id/2mW3x |
| prov:wasDerivedFrom | wikipedia-en:Symbolic_method_(combinatorics)?oldid=1059232078&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Symbolic_method_(combinatorics) |
| is dbo:wikiPageRedirects of | dbr:Analytic_combinatorics dbr:Fundamental_Theorem_of_Combinatorial_Enumeration dbr:Fundamental_theorem_of_combinatorial_enumeration dbr:Flajolet-Sedgewick_fundamental_theorem dbr:Asymptotic_combinatorics dbr:Flajolet–Sedgewick_fundamental_theorem dbr:Symbolic_combinatorics dbr:Constructible_combinatorial_class dbr:Specifiable_combinatorial_class |
| is dbo:wikiPageWikiLink of | dbr:Ptolemaic_graph dbr:Analytic_Combinatorics dbr:Analytic_combinatorics dbr:Fundamental_Theorem_of_Combinatorial_Enumeration dbr:Fundamental_theorem_of_combinatorial_enumeration dbr:Fibonacci_number dbr:Flajolet-Sedgewick_fundamental_theorem dbr:Boltzmann_sampler dbr:Asymptotic_combinatorics dbr:Flajolet–Sedgewick_fundamental_theorem dbr:Symbolic_combinatorics dbr:Constructible_combinatorial_class dbr:Specifiable_combinatorial_class |
| is foaf:primaryTopic of | wikipedia-en:Symbolic_method_(combinatorics) |