Calcul de l’ensemble des surjections

Calculez rapidement le nombre de surjections entre deux ensembles finis, visualisez la comparaison avec l’ensemble total des applications, et consultez un guide expert pour comprendre les formules, les cas limites et les usages concrets en combinatoire.

Calculateur interactif

Taille de l’ensemble de départ n

Taille de l’ensemble d’arrivée k

Méthode d’affichage

Graphique

Rappel mathématique : une surjection de E vers F existe seulement si |E| ≥ |F|, sauf le cas particulier n = 0 et k = 0.

Guide expert du calcul de l’ensemble des surjections

Le calcul de l’ensemble des surjections est un sujet central en combinatoire finie. Lorsqu’on considère deux ensembles finis E et F, de cardinal respectif n et k, une surjection est une application f : E → F telle que chaque élément de F possède au moins un antécédent dans E. En d’autres termes, aucun élément de l’ensemble d’arrivée n’est oublié. Le problème classique consiste à déterminer combien d’applications surjectives existent entre deux ensembles donnés. Cette question apparaît dans les cours de mathématiques discrètes, dans l’étude des partitions, dans certaines méthodes de répartition de tâches, en théorie de l’information et même en algorithmique.

Pour comprendre ce calcul, il faut distinguer trois familles d’objets. D’abord, l’ensemble total des applications de E vers F contient kⁿ éléments, car chacun des n éléments du domaine peut être envoyé indépendamment vers l’un des k éléments du codomaine. Ensuite, l’ensemble des injections existe lorsque n ≤ k. Enfin, l’ensemble des surjections existe lorsque n ≥ k, car pour toucher tous les éléments de F, il faut au moins autant d’éléments dans E que dans F, sauf dans le cas vide où n = 0 et k = 0. Le calcul des surjections est donc plus subtil que celui de toutes les applications, car il impose une contrainte globale sur l’image.

Définition précise et intuition combinatoire

Une application surjective couvre totalement son ensemble d’arrivée. Si vous distribuez n objets distincts dans k boîtes distinctes et que vous exigez qu’aucune boîte ne reste vide, vous comptez exactement des surjections de l’ensemble des objets vers l’ensemble des boîtes. Cette interprétation rend le problème intuitif. Le simple comptage de toutes les distributions donne kⁿ. Mais beaucoup de ces distributions laissent une ou plusieurs boîtes vides. Il faut donc retirer les cas interdits, ce qui conduit naturellement au principe d’inclusion-exclusion.

Formule clé : le nombre de surjections de n vers k vaut k! S(n,k), où S(n,k) désigne le nombre de Stirling de seconde espèce. Une forme équivalente très utilisée est Σ(-1)ⁱ C(k,i)(k-i)ⁿ pour i allant de 0 à k.

La formule par inclusion-exclusion

La méthode la plus directe part du nombre total d’applications, soit kⁿ. On soustrait ensuite les applications qui manquent au moins un élément du codomaine. Si un élément particulier de F est absent de l’image, les applications restantes sont au nombre de (k-1)ⁿ. Il existe C(k,1) manières de choisir cet élément absent. Mais cette soustraction retire trop de cas lorsque deux éléments sont absents simultanément. Il faut alors les rajouter avec C(k,2)(k-2)ⁿ. On poursuit en alternant soustraction et addition jusqu’au terme final. On obtient :

Nombre de surjections = Σ_i=0^k (-1)ⁱ C(k,i)(k-i)ⁿ

Cette formule a l’avantage d’être exacte, élégante et programmable facilement. Elle met aussi en lumière le cœur de la combinatoire : compter un ensemble sous contrainte à partir d’un ensemble plus large et corriger les surcomptages par inclusion-exclusion. C’est précisément la stratégie utilisée dans le calculateur ci-dessus.

La relation avec les nombres de Stirling

Les nombres de Stirling de seconde espèce, notés S(n,k), comptent le nombre de partitions d’un ensemble de n éléments en k sous-ensembles non vides et non ordonnés. Pour obtenir une surjection, il suffit ensuite d’assigner ces k blocs aux k éléments distincts du codomaine, ce qui se fait de k! façons. D’où la formule :

Surjections(n,k) = k! × S(n,k)

Cette écriture est particulièrement utile sur le plan théorique. Elle relie les surjections aux partitions d’ensemble et permet d’utiliser des récurrences connues. Par exemple, les nombres de Stirling satisfont la relation :

S(n,k) = k × S(n-1,k) + S(n-1,k-1)

Cette identité possède une interprétation simple. Pour placer le n-ième élément, soit on l’ajoute à l’un des k blocs déjà existants, soit on crée pour lui un nouveau bloc si l’on passe de k-1 à k blocs. Le calculateur peut donc présenter le résultat via inclusion-exclusion, via Stirling, ou comparer les deux approches pour confirmer la cohérence du résultat exact.

Cas limites à connaître absolument

Si k = 0 et n = 0, il existe exactement une application, l’application vide, qui est surjective.
Si k = 0 et n > 0, aucune surjection n’existe.
Si k > n, aucune surjection n’existe, car il est impossible de couvrir plus d’éléments que l’on ne possède dans le domaine.
Si k = 1, toute application est automatiquement surjective, donc il y en a 1ⁿ = 1.
Si k = n, les surjections sont exactement les bijections, donc leur nombre est n!.

Exemples concrets

n = 3, k = 2 : il y a 2³ = 8 applications au total. Parmi elles, 2 ne touchent qu’une seule valeur du codomaine. Il reste donc 6 surjections.
n = 4, k = 2 : le nombre de surjections vaut 2⁴ – C(2,1)1⁴ = 16 – 2 = 14.
n = 5, k = 3 : 3⁵ – C(3,1)2⁵ + C(3,2)1⁵ = 243 – 96 + 3 = 150.
n = 6, k = 3 : 3⁶ – 3×2⁶ + 3×1⁶ = 729 – 192 + 3 = 540.

n	k	Applications totales k^n	Surjections	Part des surjections
3	2	8	6	75,00 %
4	2	16	14	87,50 %
5	3	243	150	61,73 %
6	3	729	540	74,07 %
7	4	16384	8400	51,27 %
8	4	65536	40824	62,29 %

Ces valeurs montrent un phénomène intéressant. Pour k fixé, lorsque n augmente, la part des applications qui sont surjectives tend à augmenter. C’est intuitif : plus le domaine est grand, plus il est probable que tous les éléments du codomaine soient atteints au moins une fois. En revanche, lorsque k augmente pour un n fixé, la contrainte devient plus exigeante et la proportion de surjections chute souvent sensiblement.

Pourquoi ce calcul est important en pratique

Au premier regard, les surjections semblent relever d’un exercice académique. Pourtant, elles modélisent un grand nombre de situations. Si l’on affecte des tâches à des équipes en exigeant que chaque équipe reçoive au moins une tâche, on compte des surjections. Si l’on répartit des éléments de données dans des classes de sortie non vides, on retombe sur la même structure combinatoire. Dans l’analyse de partitions, dans certains schémas de codage, dans le calcul de distributions sans case vide, la surjection est omniprésente.

En informatique théorique, ces objets servent aussi à estimer des espaces de recherche et à raisonner sur des mappages contraints. En probabilités discrètes, ils permettent de répondre à des questions de type coupon collector ou occupation problem lorsque les variables sont finies et distinctes. Pour cette raison, maîtriser le calcul des surjections n’est pas seulement utile pour réussir un examen ; c’est aussi un excellent entraînement à la modélisation.

Table de comparaison avec les nombres de Stirling

n	k	S(n,k)	k!	k! × S(n,k)
4	2	7	2	14
5	3	25	6	150
6	3	90	6	540
7	4	350	24	8400
8	4	1701	24	40824

Cette seconde table montre très bien la structure factorisée du problème. D’abord, on partitionne le domaine en k paquets non vides. Ensuite, on donne à chaque paquet une étiquette du codomaine. Cette vision est souvent plus parlante pour les étudiants qui ont déjà travaillé sur les partitions d’ensembles.

Méthode de calcul étape par étape

Identifier le cardinal du domaine n et celui du codomaine k.
Vérifier immédiatement si une surjection est possible. Si k > n, la réponse est 0.
Choisir une méthode de calcul :
- Inclusion-exclusion pour un calcul direct.
- Stirling si l’on veut exploiter une récurrence ou des tables connues.
Calculer éventuellement le nombre total d’applications kⁿ afin de comparer.
Interpréter le résultat : valeur exacte, pourcentage parmi toutes les applications, et comportement quand n ou k varie.

Erreurs fréquentes

Confondre surjection et injection. Une injection interdit les collisions, une surjection interdit les valeurs du codomaine non atteintes.
Oublier le cas k > n, qui impose immédiatement un résultat nul.
Écrire kⁿ comme réponse finale alors qu’il s’agit seulement du nombre total d’applications.
Négliger les signes alternés dans la formule d’inclusion-exclusion.
Confondre S(n,k) avec le nombre final de surjections sans multiplier par k!.

Comment lire le graphique du calculateur

Le graphique associé au calcul présente, pour un n fixé, l’évolution du nombre de surjections lorsque la taille du codomaine varie de 1 à k. Deux modes sont proposés. Le premier utilise une échelle log10, très utile lorsque les valeurs deviennent gigantesques. Le second affiche la part des surjections parmi toutes les applications possibles. Cette double lecture est intéressante : le nombre absolu de surjections peut augmenter alors même que leur proportion relative diminue ou progresse plus lentement.

Ressources académiques et institutionnelles

Pour approfondir le sujet, vous pouvez consulter des ressources de référence en combinatoire et en fonctions génératrices. Voici trois liens particulièrement utiles :

Conclusion

Le calcul de l’ensemble des surjections repose sur une idée simple mais puissante : compter toutes les applications, puis corriger pour exclure celles qui ne couvrent pas entièrement le codomaine. Cette logique conduit à une formule d’inclusion-exclusion robuste, et à une seconde formulation via les nombres de Stirling de seconde espèce. Retenez le principe suivant : les surjections sont des applications sans case vide, et leur nombre révèle la structure profonde des partitions d’ensembles. Avec le calculateur de cette page, vous pouvez obtenir le résultat exact, comparer les méthodes de calcul, mesurer la proportion de surjections parmi toutes les applications et visualiser l’évolution en fonction de la taille du codomaine. C’est l’outil idéal pour étudier le sujet sérieusement, vérifier des exercices et développer une intuition combinatoire solide.

Calcul De L Ensemble Des Surjection