Le problème des cheveaux

[csamborski]

Alors que je discutais avec un ami, voilà il m'a posé un problème :

On répartit 8 chevaux numérotés dans 8 box d’une place, eux-mêmes numérotés.
1. Combien y a-t-il de répartitions possibles ?
2. Combien y a-t-il de répartitions possibles de telles manière qu’aucun des chevaux ne soit dans
le box qui porte son numéro ?
3. On répartit n cheveaux, combien y a-t-il de répartitions possibles de telles manière qu’aucun des chevaux ne soit dans
le box qui porte son numéro ?

Après l'avoir résolu, je l'ai trouvé très intéressant et vous propose donc d'essayer de le résoudre à vôtre tour.

Je vous conseille de tester les cas avec peu de cheveaux pour voir comment le nombre de cas "dérangés" évolue.

[sc]

C'est un problème très intéressant et plutôt délicat!!
Ce phénomène est important en théorie des ensembles. Tu devrais peut être leur donner une piste sur la manière dont tu as procédé :
Récurrence sur le complémentaire ? Diagramme de Venn ? Programmation afin de conjecturer la réponse ?

[csamborski]

J'ai plutôt travaillé sur la récurrence avec le complémentaire et observant les combinaisons.

Une relation m'a bien aidé :
Si on note les événements suivants :
A : le cheval 1 est dans son box
B : le cheval 2 est dans son box
C : le cheval 3 est dans son box
Alors
( A union B union C ) = ( (A union B) union C )
et
( (A union B) inter C ) = ( (C inter A) union (C inter B) )