croix sur un quadrillage

iliasse062 · 20-01-2026 14:35:03

Bonjour à tous,
Dans un exercice de dénombrement ils m'ont demandé de calculer le nombre de p cases qu'on peut cocher dans un quadrillage de M lignes et N colonnes, avec $p \le M$ et $p \le N$ et en supposant qu'au plus une case est cochée par ligne et par colonne.
Alors moi j'ai proposé comme solution : $\binom{\min(M,N)}{p}$ .
Et la solution donnée est $A_M^p$ $A_N^p$ .
Alors je veux savoir pourquoi ma solution proposée est fausse ?
Merci d'avance.

Dernière modification par iliasse062 (20-01-2026 14:35:54)

bridgslam · 20-01-2026 15:43:20

Bonjour,

En raisonnant sur les colonnes d'abord ( mais sur les lignes c'est tout aussi valable évidemment),
Vous devez affecter un choix en ligne pour la colonne n°1 la plus à gauche choisie ( M points croix possibles), puis pour la colonne suivante n°2 choisie il n'y a plus que M-1 croix possible vu qu'une ligne est proscrite, etc jusqu'à la colonne n°p choisie.
Remarquez que le calcul donne NxMx(N-1)x(M-1)x... avec un nombre de double-facteurs égal à p.
Je ne vois pas ce qui vous permet d'avancer votre expression, vous dénombrez juste le nombre choix de p rangées relativement à la plus petite dimension du tableau, ce qui n'a rien à voir...

Remarque: vu en projections, sur un plan ensembliste on a un produit cartésien d'injections pour l'ensemble des configurations possibles.

Bonne soirée

Dernière modification par bridgslam (20-01-2026 15:53:37)

Michel Coste · 20-01-2026 15:48:54

Bonjour,
Tu veux dire qu'on te demande le nombre d'ensembles de $p$ cases d'un quadrillage $M\times N$ avec $p\leq \min (M,N)$ , tels qu'il y a au plus une case de l'ensemble par ligne et au plus une par colonne ?
Peux-tu expliquer le raisonnement derrière ta réponse ?
Tu es sûr de la solution donnée ? Moi, je dirais que la solution est $\dfrac1{p!} \,A_M^p\,A_N^p$.
Le nombre $A_M^p\,A_N^p$ correspondrait au cas où on numérote de 1 à $p$ les cases choisies.
Si on préfère, la solution correcte peut aussi s'écrire $C_M^p\,A_N^p$ (on choisit l'ensemble des $p$ lignes, puis à chaque ligne on associe une colonne différente de celles associées aux autres lignes).
Bridgslam, ce que tu écris ne me semble pas correct, et je ne comprends pas ce que tu veux dire par "produit cartésien d'injections".

Dernière modification par Michel Coste (20-01-2026 16:02:53)

bridgslam · 20-01-2026 16:00:26

Bonjour,

@Michel
Moi je suis d'accord avec son expression, il faut bien affecter une étiquette dans chaque direction du tableau pour pouvoir distinguer les cases, donc les croix.

Chaque choix de configuration est caractérisé par l'ensemble de ses projections ( en ligne d'une part, en colonne d'autre part) si et seulement si ce sont des injections. D'où ma remarque.

Bonne soirée

Dernière modification par bridgslam (20-01-2026 16:10:49)

Michel Coste · 20-01-2026 16:06:09

Bridgslam, regarde le cas où $M=N=p=2$. Il n'y a que deux façons de cocher 2 cases correctement : soit on coche (1,1) et (2,2), soit on coche (1,2) et (2,1).

bridgslam · 20-01-2026 16:23:17

Oui en première colonne on a deux choix, puis un seul pour la deuxième.
Tu as raison je pense, il y a une erreur dans sa formule , effectivement.
Mon erreur provient du fait que dans mon choix en colonne j'en compte p! fois trop, alors que les choix sont les p-uplets parmi {1,...,N} strict. croissants, ce qui est plus restrictif: nombre de combinaisons de p parmi N.
Par exemple avec p =3 et N =5 je comptais par exemple
(2,4,5) (4,2,5)... etc (6 fois) pour un seul cas réel.
Après au niveau des croix pour les choix 1,2,3 des lignes,
par exemple, (1,2,3) se retrouvait avec (2,1,3) ...etc (6 fois) alors que c'est pareil.
Ok avec toi pour résumer.

Dernière modification par bridgslam (20-01-2026 17:01:17)

bridgslam · 20-01-2026 18:28:51

Bonsoir,

On retombe aussi sur la même expression car à partir d'un quadrillage pxp, ce n'est plus qu'une affaire de bijection, donc un facteur p!
afin d'affecter à chaque ligne sa colonne dans le quadrillage (ou vice versa ).

Bonne soirée

Michel Coste · 20-01-2026 18:58:10

Pour dire les choses de manière succinctes : on choisit un sous-ensemble $E$ de $p$ lignes, puis on choisit une injection $f$ de $E$ dans l'ensemble des colonnes (les cases cochées sont les $(i,f(i))$ pour $i\in E$).

Bernard-maths · 20-01-2026 20:51:04

Bonsoir à tous !

On dispose d'un tableau de M lignes sur N colonnes, ce qui fait M*N cases.

On choisit une case, il y a M*N façons de le faire. Ensuite il faut retirer la ligne prise ET la colonne prise, il reste donc (M-1)*(N-1) cases possibles, on a donc (M-1)*(N-1) façons de choisir la 2ème case. ETC ... !

Au fur et à mesure, le nombre de choix est : (M*N) * ((M-1)*(N-1)) * ((M-2)*(N-2)) * ... ((M-(p-1))*(N-(p-1))

=M*(M-1)*(M-2) *... *(M-(p-1)) * N*(N-1)*(N-2)* ... *(N-(p-1)) = A_M^p * A_N^p

Je crois bien que c'est ça, sauf grosse erreur de ma part sur les indices ...!

Bernard-maths

bridgslam · 20-01-2026 23:03:39

Bonsoir,

Hélas tu reprends ce que j'ai fait avec la même erreur, ça ne tient pas la route... Tu auras un facteur p! sur le bon résultat.
Voir les divers messages de ce fil ...

En désignant par $L_p$ , $C_p$ respectivement les sous-ensembles de p lignes et les sous-ensembles de p colonnes, $S_p$ l'ensemble des bijections s entre eux , C l'ensemble des configurations cherché, alors C
est en bijection avec le produit cartésien de ces trois ensembles, autant donc qu'un choix groupé de p lignes , de p colonnes , et d'une bijection s ( ou injection) entre eux.
Une façon de voir peut-être plus "géométrique".

Dernière modification par bridgslam (20-01-2026 23:56:02)

Bernard-maths · 21-01-2026 08:25:19

Bonjour à tous !

Pardon bridgslam, je n'avais pas bien lu tous les posts, et le tien en 2, pour moi va vers la solution !

Alors en "réfléchissant un peu plus", ce raisonnement marche pour remplir les lignes consécutives ... donc s'il en reste, il faut envisager en plus (par produit) des permutations de p lignes parmi M ???

B-m

PS : je viens de voir la réponse de Michel ci-après moi, et je pencherais vers la réponse qu'il donne : C_M^p * A_N^p

Dernière modification par Bernard-maths (21-01-2026 08:38:52)

Michel Coste · 21-01-2026 08:29:35

Hum hum, Bridgslam. Peux-tu préciser ce qu'est ton ensemble $S_p$ ? "L'ensemble des bijections entre eux", ça ne tient pas tellement la route vu que les ensembles de départ de ces bijections et les ensembles d'arrivée varient respectivement dans $L_p$ et dans $C_p$. Ton produit cartésien ne fait pas sens.
Je rappelle la description succincte que j'ai donnée plus haut :
1°) On fait le choix d'une partie $E$ à $p$ élément de l'ensemble des lignes ; il y a $C_M^p$ choix possibles.
2°) $E$ étant choisi, on fait le choix d'une injection $f$ de $E$ dans l'ensemble des colonnes ; il y a $A_N^p$ choix possibles.
Les cases cochées sont les $(i,f(i))$ pour $i\in E$.
Ceci montre que le nombre de façons de cocher correctement $p$ cases dans la grille est $C_M^p\times A_N^p$.
Si l'on tient absolument à voir un produit cartésien, on peut numéroter chaque $E$ de 1 à $p$ dans l'ordre des indices de lignes, ce qui identifie une injection de $E$ dans l'ensemble des colonnes à une injection de $\{1,\ldots,p\}$ dans l'ensemble des colonnes. Dans ta description, il faudrait numéroter chaque élément de ton $L_p$ comme ci-dessus, numéroter aussi chaque élément de ton $C_p$ dans l'ordre des indices de colonnes, de sorte que ton $S_p$ serait simplement l'ensemble des permutations de $\{1,\ldots,p\}$.
Je préfère ma description succincte.

Bernard-maths · 21-01-2026 09:45:07

Désolé, j'en reste à la solution donnée !!!

Faites un essai avec M=4, N=3 et p=2 ...

B-m

Dernière modification par Bernard-maths (21-01-2026 09:49:36)

Michel Coste · 21-01-2026 12:27:41

Alors s'il te plait, Bernard-maths, explique nous comment tu fais pour compter 4 façons de cocher correctement 2 cases sur un quadrillage 2x2 ? Il te faut en trouver deux de plus que ceux-là :

Bernard-maths · 21-01-2026 13:24:20

Hello !

Moi je trouve choisir une ligne A₂¹ = 2, puis une colonne A₁¹ = 1, en tout 2*1 = 2, c'est tout !

B-m

bridgslam · 21-01-2026 13:27:29

Bonjour ,

C'est vrai que le troisième facteur du produit cartésien dépend des choix des éléments dans les deux premiers.
Je suis d'accord avec toi et ça ne fait pas sens.
Je voulais exprimer formellement les coupes graphiques
( horizontales-verticales),
puis les affections bijectives horizontales-verticales après ces coupes.
En revenir à ta formulation succinte est suffisant et plus simple.
As-tu en bonus une idée de la solution à la question annexe "exprimer sous forme d'ensemble l'ensemble des configurations" ?
Par exprimer j'entends une expression formelle entre ensembles à déterminer et opérations usuelles entre eux.
Ta démarche consistant à exprimer une réunion d'ensembles de couples, je me pose juste la question.
Merci

Michel Coste · 21-01-2026 13:54:03

Bernard-maths a écrit :

Moi je trouve choisir une ligne A₂¹ = 2, puis une colonne A₁¹ = 1, en tout 2*1 = 2, c'est tout !

M'enfin, Bernard-maths, qu'est-ce que tu racontes ??? Il y a deux colonnes. Donc ton nombre de choix possibles d'une colonne, c'est 2 et pas 1. Si $M=N=p=2$, ton $A_M^p*A_N^p$ c'est bien $2\times 2=4$.

Dernière modification par Michel Coste (21-01-2026 14:54:18)

bridgslam · 21-01-2026 15:04:09

Bonsoir,

@Bernard:
Graphiquement cela s'interprète en un sous-quadrillage p x p ( combien ?) , puis par exemple pour chaque ligne spécifier à quelle colonne on place sa croix, ce qui donne pour chaque quadrillage choisi p x p , p! options.

Si tu raisonnes (comme je l'ai fait à tort ) choix de cases les uns après les autres (donc dans un ordre quelconque ) les mêmes réseaux de croix vont se retrouver à permutations près, le résultat sera p! fois trop grand.

Bernard-maths · 21-01-2026 15:21:06

Bon, j'ai du mal à raisonner, je suis dans mon espace 3D !

Alors M = N = 2, on choisit la ligne : 2 façons, puis la conne : 2 façons, en tout 4, Ok.

ALORS soit une répartition de p cases sur les M*N. Comme les cases ne sont pas nommées, il y a un certain nombre de façons de tirer ces p cases : autrement dit il faut choisir p cases parmi M*N ...?

On obtient alors C_M*N^p façons ??? Ce n'est pas ça ...

A toi, maintenant (:-)

B-m

Je subodore une grosse embrouille.

Les p cases peuvent se répartir de façons variables entre lignes et colonnes. Par si p = 20 = 1*20 = 2*10 = 4*5, on peut répartir sur 4 lignes et 5 colonnes ou sur 5 lignes et 4 colonnes ...?

Dernière modification par Bernard-maths (21-01-2026 15:33:08)

Bernard-maths · 21-01-2026 15:52:58

Et pourquoi pas A_M^p * A_N^p / p! ???

B-m

Michel Coste · 21-01-2026 16:09:34

As-tu lu et réfléchi aux messages du fil ??? Es-tu au courant que $C_M^p=A_M^p/p!$ ?

Dernière modification par Michel Coste (21-01-2026 16:10:42)

Bernard-maths · 21-01-2026 16:33:55

Donc c'est ce que tu as écs en #12 ...?

Michel Coste · 21-01-2026 16:59:03

J'ai expliqué la solution correcte dès mon premier message #3 ci-dessus... :(

Bernard-maths · 21-01-2026 17:15:05

Bravo ! Mais j'ai vraiment suivi cela en survolant, et du coup retrouvé le bon fil en fin de conte (ou compte ?) !

Merci pour tes relances ...

B-m

Dernière modification par Bernard-maths (21-01-2026 17:15:47)

Bernard-maths · 21-01-2026 18:32:53

Et qu'en pense iliasse062 ???

Forum de mathématiques - Bibm@th.net

#1 20-01-2026 14:35:03

croix sur un quadrillage

#2 20-01-2026 15:43:20

Re : croix sur un quadrillage

#3 20-01-2026 15:48:54

Re : croix sur un quadrillage

#4 20-01-2026 16:00:26

Re : croix sur un quadrillage

#5 20-01-2026 16:06:09

Re : croix sur un quadrillage

#6 20-01-2026 16:23:17

Re : croix sur un quadrillage

#7 20-01-2026 18:28:51

Re : croix sur un quadrillage

#8 20-01-2026 18:58:10

Re : croix sur un quadrillage

#9 20-01-2026 20:51:04

Re : croix sur un quadrillage

#10 20-01-2026 23:03:39

Re : croix sur un quadrillage

#11 21-01-2026 08:25:19

Re : croix sur un quadrillage

#12 21-01-2026 08:29:35

Re : croix sur un quadrillage

#13 21-01-2026 09:45:07

Re : croix sur un quadrillage

#14 21-01-2026 12:27:41

Re : croix sur un quadrillage

#15 21-01-2026 13:24:20

Re : croix sur un quadrillage

#16 21-01-2026 13:27:29

Re : croix sur un quadrillage

#17 21-01-2026 13:54:03

Re : croix sur un quadrillage

#18 21-01-2026 15:04:09

Re : croix sur un quadrillage

#19 21-01-2026 15:21:06

Re : croix sur un quadrillage

#20 21-01-2026 15:52:58

Re : croix sur un quadrillage

#21 21-01-2026 16:09:34

Re : croix sur un quadrillage

#22 21-01-2026 16:33:55

Re : croix sur un quadrillage

#23 21-01-2026 16:59:03

Re : croix sur un quadrillage

#24 21-01-2026 17:15:05

Re : croix sur un quadrillage

#25 21-01-2026 18:32:53

Re : croix sur un quadrillage

Réponse rapide

Pied de page des forums