Principes de dénombrement. Dénombrement desp-listes, des arrangements et des permutations. Exemples de situations dont l’étude se ramène aux cas précédents. Dany-Jack Mercier IUFM de Guadeloupe, Morne Ferret, BP399, Pointe-à -Pitre cedex 97159, France dany-jack.mercier@univ-ag.fr 28 mai 2002 ¤Si F est un ensemble …ni, on note #F son cardinal. Si p 2 N on pose N = f1; :::; pg.p En…n, dans toute la suite, A désigne l’ensemble …ni A = fa ; :::;a g de cardinal n ¸ 1.1 n Le premier paragraphe est constitué de rappels. Pour un exposé de 25 minutes, on se contentera de rappeler brièvement le principe du berger. 1 Principes de dénombrement Le langage privilégié du dénombrement est celui des ensembles. Il suppose connu la notion de cardinal d’un ensemble …ni, et celle de partition d’un ensemble. Tous les problèmes de dénombrement se résolvent en utilisant les deux principes ci-dessous, et l’on remarquera que le principe du berger provient directement de celui de la somme, si bien que l’on puisse a¢rmer de faç on abrupte qu’un seul principe est àla base de toutes les opérations de dénombrement : le principe de la somme. Lemme 1 Principe de la somme Si A ; :::; A est une partition de l’ensemble … ni A, alors #A = #A + ::: + #A .1 k 1 k Preuve : On raisonne par récurrence sur k. La propriété est triviale si k = 1. Si k = 2, considérons une partition A ; A de A. Si l’on note n le cardinal de A , on sait l’existence1 2 i i de deux bijections f : N ! A (i = 1;2) et on véri…e que ...