Combinatoire

Combinaisons, Permutations, Arrangements, ...

Monoïde libre.
Choisissez l'alphabet : 0 1, le morphisme : 0->1, 1->10 et le mot initial : 0.
Cette page vous permet de construire les images successives du mot initial. Dans cet exemple ce sont les mots de Fibonacci. Autres mots : mot de Prouhet-Thue-Morse, Look and Say sequence ...

Chemins sur une grille, dans le plan.
Un mot "babcacaccbcbacababacbc" code un chemin sur le plan pavé de triangles. Le morphisme "aa"->"", abab->ba, ... permet d'obtenir les trajets les plus courts en simplifiant les chemins.

Mot infini de Kolakoski
K = 1211212212... est auto-descriptif : les nombres d'éléments des blocs de chiffres identiques, à partir du second sont 1,2,1 ... De nombreuses questions restent ouvertes.
Cette page permet de rechercher les fréquences d'apparitions de sous-chaînes parmi quelques centaines de milliers de chiffres.
Généralisation Kol(m, n, ..., p) de la suite de Kolakoski.

Problème inverse de l'automate fini
Les algorithmes génétiques sont appliqués à la factorisation de mots. Une population évolue vers le morphisme qui a comme point fixe le mot donné.
On retrouve par exemple le morphisme 1->10 0->1 à partir du mot de Fibonacci ou encore 1->10 0->101 à partir de 1010110... lié à racine(2).

Mots de de Bruijn 1

Circuits hamiltoniens.

Mots de de Bruijn 2
Un mot circulaire de de Bruijn contient tous les mots de longueur n sur un alphabet de a lettres, sa longueur est n^a. Par exemple 01011100 contient les huit mots 000, 001, 111, (pensez à refermer circulairement 01011100 01)
Circuit eulérien.

Pi - Fréquences des sous-chaînes.
Fréquences des sous-chaînes du mot formé par les 10⁵ = 100 000 premiers chiffres de l'écriture décimale de Pi.

   

Distance de Levenshtein ou distance de similarité entre les mots.

Séquences de Skolem Applet. Systèmes triples de Steiner.

Tournoi par paires Promenade de demoiselles 5Kirkman, Steiner)

Suites linéaires à coefficients constants
Ce sont, en particulier, les suites de Fibonacci, Lucas, Perrin, Padovan etc.

Suites de Somos.

Suites d'Ulam.

Suites de Stöhr.

Nombre de carrés magiques de sommes 2

Somme des mêmes puissances n-ièmes des premiers naturels

Mélange parfait  Battage parfait d'un jeu de cartes.