Amusement en dénombrement

gebrane

Bonjour,

Il y a 7 garçons et 3 filles qui doivent être alignés en une rangée. Montrer que  le nombre de façons de les disposer de sorte que chaque garçon soit adjacent à au plus une fille est $$\text{2xx6800}$$ On n'accepte pas les situations ..FGF..
Il faut trouver le chiffre $\text x $ que j'ai caché

Velvet

import itertools

def test(p):
    for i in range(8):
        if [p[i], p[i+1], p[i+2]] == ['F', 'G', 'F']:
            return 0
    return 1

eleves = ['F']*3 + ['G']*7
compteur = 0

for p in itertools.permutations(eleves):
    compteur += test(p)

print(compteur)

Guego

$2116800 \quad(=70\times 7! \times 3!)$

gebrane

Bingo

gebrane

Bonjour @Velvet, ton programme ne s'exécute pas rapidement pour F=20 et G=30. Une amélioration peut être ! 

LOU16

Bonjour,

J'ai apparemment raté quelque chose, car je n'ai rien aperçu de simple et de direct dans ce décompte.

 Soit $n\in \N_{\geqslant 3},\quad A_n :=\text{card}\Big\{(x_1,x_2,x_3)\in[\![1;n]\!]^3\mid x_1<x_2<x_3, \:\:x_2-x_1\neq 2, \: x_3-x_2 \neq 2\Big\}$

Le dénombrement demandé par @gebrane est alors donné par $A_{10}\times 3!\times 7!\:$ où $\:\forall n\in \N_{\geqslant 4},\:\:A_n =\dfrac{(n-3)(n^2-6n+20)}{6}.$

gebrane

Bonjour LOU 16, En supposant dans un premier temps que les filles sont identiques et aussi les garçons 

Il en résulte que les arrangements admissibles sont des quatre types suivants 

$$\begin{aligned}G^p F^3 G^q, & \qquad p+q = 7, \\G^p F G^{2+q} F^2 G^r \quad \text{ou} \quad G^p F^2 G^{q+2} F G^r, & \qquad p+q+r = 5, \\G^p FG^{2+q} F G^{2+r} F G^s, & \qquad p+q+r+s = 3,\end{aligned}$$

où \(p\), \(q\), \(r\), \(s\) sont des entiers \(\geq 0\). Le nombre de ces arrangements est :  

\[\binom{8}{1} + 2 \cdot \binom{7}{2} + \binom{6}{3} = 70.\]

En tenant compte maintenait qu'il ne sont pas identiques  , on obtient :  

\[7! \cdot 3! \cdot 70 = 2\,116\,800\]

configurations admissibles.

LOU16

Bonjour Gebrane,

Oui, c'est bien ce que j'ai commencé par faire pour $n=10$, mais je trouve  que ce n'est pas particulièrement simple (forum "Collège, lycée".)

gebrane

peut être que @Guego a mieux  et simple

incognito

En notant F le nombre de filles (supposées identiques) et G le nombre de garçons (supposés identiques), je pense que le nombre d'arrangements admissibles est donné par la formule :

\[ \sum_{k=0}^{F-1} (-1)^k\binom{F-1}k \binom{G+F-2k}{F-k}\]

LOU16

Bonsoir,

Bravo @incognito

Ce "crible de Poincaré" marche ici remarquablement.  Même si j' y avais pensé, j'aurais tout de même crédité ce dénombrement d'une certaine difficulté.

jandri

Je n'ai pas répondu ce matin car je pensais qu'il fallait laisser le temps de chercher à d'éventuels lycéens intéressés.
Maintenant que plusieurs réponses ont été fournies je peux proposer la mienne.
Je généralise à 3 F et $m$ G et je m'intéresse à la position des F.

Il y a $\dbinom{m+3}{3}$ façons de placer les 3 F.
Il faut retirer les façons pour lesquelles au moins deux des 3 F sont séparées par un G et je les dénombre en les classant par la position du premier FGF : il y a alors $k$ places avant et $m-k$ places après ($0\leq k\leq m$).
Si $k=0$ ou $k=1$ il y a $m$ façons de placer le 3ème F alors que si $k\geq2$ il n'y en a que $m-1$ (car il ne peut pas être deux places à gauche de FGF).
Il y a donc $\dbinom{m+3}{3}-2m-(m-1)^2=\dfrac{m^3+11m}6$ façons qui conviennent pour placer les 3 F (c'est la formule de @LOU16 en posant $n=m+3$).

Comme il y a $3!$ façons d'ordonner les filles et $m!$ pour les garçons on obtient finalement $(m^3+11m)m!$

incognito

Quelques lignes pour expliquer d'où sort la formule que j'ai proposée plus haut (je pense que @LOU16 le sait déjà).
Pour un rangement donné, je note $d_1$ le nombre de garçons placés avant la première fille, $d_2$ le nombre de garçons entre la première et la deuxième fille, etc, et  $d_{F+1}$ le nombre de garçons placés après la dernière fille, on a évidemment $d_1+\cdots d_{F+1}=G$.  
 
Soit $S=\{d=(d_1,\ldots,d_{F+1})\in\mathbb{N}^{F+1}~/~ d_1+\cdots+d_{F+1}=G\}$, il est connu que $\#S=\binom{F+G}{F}$. L'ensemble des rangements admissibles est $A=\{d\in S~/~d_i\neq 1\text{ pour }2\leqslant i\leqslant F\}$ qu'il s'agit de dénombrer.
 
Pour $2\leqslant i\leqslant F$, on pose $S_i=\{d\in S~/~d_i=1\}$, on a alors $S\setminus A =\bigcup_{i=2}^{F} S_i$, et par la formule du crible on a :
\[\#(S\setminus A)= \sum_{k=1}^{F-1} (-1)^{k-1} \left(\sum_{2\leqslant i_1<\cdots<i_k\leqslant F} \#(S_{i_1}\cap\cdots\cap S_{i_k}) \right)\]
 
Dans la somme à l'intérieur il y a $\binom {F-1}k$ termes, et il est facile de voir $\#(S_{i_1}\cap\cdots\cap S_{i_k}) = \binom{F+G-2k}{F-k}$ car c'est le nombre de $(F-k)$-uplets de naturels tels que $n_1+\cdots+n_{F-k}=G-k$.
 
On en déduit alors que :
\[
\#A = \binom{F+G}F - \sum_{k=1}^{F-1} (-1)^{k-1} \binom {F-1}k\binom{F+G-2k}{F-k} = \sum_{k=0}^{F-1} (-1)^k \binom {F-1}k\binom{F+G-2k}{F-k}
\]  

gebrane

Est-ce que le calcul de ce dénombrement est hors de portée d’un brillant lycéen ? J’ai pensé qu’il était possible de décomposer les différentes situations : soit les trois filles sont juxtaposées, soit deux filles sont juxtaposées avec l’autre à leur gauche ou à leur droite, soit chaque fille est entourée de garçons.
Ce serait bien qu’un professeur de lycée donne cet énoncé à ses brillants étudiants pour voir