Séance de cours

Comptage avancé: génération de fonctions et relations de récurrence

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, disc ...

Description

Cette séance de cours couvre les techniques de comptage avancées utilisant des fonctions génératrices et des relations de récurrence, y compris des solutions aux relations de récurrence, aux équations caractéristiques et à la génération de fonctions pour les séquences. Il explore également les combinaisons, les k-combinaisons et les k-combinaisons avec la répétition.

Enseignant·e

Karl Aberer

Co-Founder of LinkAlong Sarl, 2017.Vice-president EPFL for Information Systems, 2012 –2016.Director of the Swiss National Centre for Mobile Information and Communication Systems NCCR MICS (mics.ch), 2005 -2012.Member of the Swiss Research and Technology Council SWTR, consulting the Swiss Federal government, 2004 - 2011.

Source officielle

Concepts associés (30)

Linear recurrence with constant coefficients

In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is linear in the various iterates of a variable—that is, in the values of the elements of a sequence. The polynomial's linearity means that each of its terms has degree 0 or 1.

Série génératrice

En mathématiques, et notamment en analyse et en combinatoire, une série génératrice (appelée autrefois fonction génératrice, terminologie encore utilisée en particulier dans le contexte de la théorie des probabilités) est une série formelle dont les coefficients codent une suite de nombres (ou plus généralement de polynômes) ; on dit que la série est associée à la suite. Ces séries furent introduites par Abraham de Moivre en 1730, pour obtenir des formules explicites pour des suites définies par récurrence linéaire.

Suite récurrente linéaire

En mathématiques, on appelle suite récurrente linéaire d’ordre p toute suite à valeurs dans un corps commutatif K (par exemple R ou C ; on ne se placera que dans ce cas dans cet article) définie pour tout par une relation de récurrence linéaire de la forme où , , ... sont p scalaires fixés de K ( non nul). Une telle suite est entièrement déterminée par la donnée de ses p premiers termes et par la relation de récurrence. Les suites récurrentes linéaires d’ordre 1 sont les suites géométriques.

Stirling numbers of the first kind

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed points as cycles of length one). The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices. This article is devoted to specifics of Stirling numbers of the first kind.

Suite de Lucas

En mathématiques, les suites de Lucas U(P, Q) et V(P, Q) associées à deux entiers P et Q sont deux suites récurrentes linéaires d'ordre 2 à valeurs entières qui généralisent respectivement la suite de Fibonacci et celle de Fibonacci-Lucas, correspondant aux valeurs P = 1 et Q = –1. Elles doivent leur nom au mathématicien français Édouard Lucas. Soient P et Q deux entiers non nuls tels que (pour éviter les cas dégénérés). Les suites de Lucas U(P, Q) et V(P, Q) sont définies par les relations de récurrence linéaire et Notons l'une des deux racines carrées de Δ (éventuellement dans C).

Afficher plus

Séances de cours associées (64)

Compter avec les relations de récurrence: Résumé

Explore le comptage avec les relations de récurrence, les relations de récurrence linéaires, la génération de fonctions et les principes de comptage.

Générer des fonctions: Comptage avancé

Couvre la définition des fonctions génératrices et leur application dans la résolution des relations de récurrence.

Comptage avancé: Exemples

Couvre les techniques de comptage avancées, y compris les relations de récurrence linéaire et les fonctions génératrices, avec des exemples de la séquence de Fibonacci et des différences entre les dés et les cartes de poker.

Relations de récurrence linéaire

Explore les relations de récurrence linéaires, y compris des exemples comme les nombres de Fibonacci et la preuve de théorèmes liés.

Comptage avancé: relations de récurrence homogènes linéaires et fonctions génératrices

Explore la résolution de relations de récurrence homogènes linéaires et la génération de fonctions pour les formules de séquence.

Afficher plus

Concepts associés (30)

Linear recurrence with constant coefficients

Série génératrice

Suite récurrente linéaire

Stirling numbers of the first kind

Suite de Lucas

Afficher plus