Le dénombrement de la ligue des champions

canasson29

Bonjour à toutes et tous,

pardon de parler football ici, mais je me pose une question s'agissant de la modification de la phase de poules des coupes européennes qui s'applique cette saison. En lieu et place des traditionnelles 32 équipes réparties en 8 poules de 4 en vue de la qualification pour les huitièmes de finale (chaque groupe est constitué de quatre équipes venant de quatre chapeaux de "niveau" différent),

cette fois-ci est constitué un championnat unique à 36 équipes, réparties en quatre groupes de niveau. Chaque équipe du championnat se verra affronter dans la phase de championnat deux équipes de chaque niveau. Elle jouera donc 8 matchs au total, avec la garantie de jouer 4 matchs à domicile et 4 matchs à l'extérieur.

Ma question est simple : combien de tirages au sort de championnat sont-ils possibles ?

Une question annexe : à l'issue de la phase de championnat, les huits premiers sont d'office qualifiés en huitième de finale et les seize suivants s'affrontent en match aller-retour pour se qualifier pour ce satde de la compétition. Peut-on arriver à une situation où le nombre de points ne suffit pas pour classer les équipes ?

lourrran

Combien de tirages possibles?
La question est simple, et la réponse aussi est simple : Beaucoup, des milliards de milliards de milliards.
Un nombre de l'ordre de $10^{25}$ ... voire plus.
Le calcul précis me paraît très compliqué, je n'ai pas le courage, et si je devais le faire, je serais assez embêté.
Mais les quelques calculs très approximatifs que j'ai faits montent très vite.
Même sans prendre en compte l'histoire de matches à l'extérieur ou à domicile.

Des risques d'ex-aequos ?
On fait un mini championnat, chaque équipe joue 8 matches. Au mieux le premier marque 24 points (je suppose que comme en championnat classique, la victoire donne 3 points, le nul 1 point, et la défaite donne 0 point), et au pire, le dernier marque 0 points. 
On a donc 25 totaux possibles (total forcément entre 0 et 24).
On a donc 36 équipes, qui ont toutes un certain total, entre 0 et 24.
Donc forcément, on aura des ex-aequos (36 objets à caser dans 25 boites).
Le 8ème peut-il être ex-aequo avec le 9ème : oui, et statistiquement, ce sera fréquent.
Le 24ème peut-il être ex-aequo avec le 25ème : oui, et statistiquement, ce sera fréquent.
J'imagine qu'il y a des critères type goal-average et plus pointu encore pour départager les ex-aequos. Un truc assez classique pour départager les ex-aequos, c'est de compter le total des points des équipes rencontrées. Ca se fait dans les compétitions d'échecs, et on est dans une configuration assez similaire (beaucoup d'équipes, et assez peu de matches). Et statistiquement, ça réduit de beaucoup le risque d'avoir des ex-aequos.
Total des points, 
puis total des points des équipes rencontrées
puis goal-average ... on n'est pas 100% à l'abri, mais on est pas mal.
Et l'histoire du total des points des équipes rencontrées....il peut boucler, et là, on est vraiment à l'abri. 

JLapin

canasson29 a dit :

cette fois-ci est constitué un championnat unique à 36 équipes, réparties en quatre groupes de niveau.

Ma question est simple : combien de tirages au sort de championnat sont-ils possibles ?

Un seul :  contrairement aux poules, le niveau d'une équipe ne dépend pas d'un tirage au sort.

Par exemple, à l'issue de la saison 2023-2024, il y a un unique championnat 2024-2025 de Ligue 1 (modulo les relégations financières) qui est fonction du niveau atteint la saison précédente.

Ou alors, je n'ai pas compris la procédure que tu décris dans ton message.

Titi le curieux

Bonjour,

@JLapin : je crois que tu es un peu de mauvaise foi là, il y a quatre ensembles d'équipes et on veut savoir combien de poules on peut définir en respectant les règles définies.  Edit après lecture de la réponse de JLaplin : désolé

 @canasson29

  De ce que tu dis, on peut déduire qu'il y a autant d'équipes dans chaque groupes de niveau (9 équipes par groupe de niveau), sinon il ne serait pas possible que chaque équipe rencontre exactement 2 équipes de chaque groupe de niveau (c'est bête, mais il fallait le préciser et moi, ça m'a fait bugguer au début).

  Si on s'intéresse juste à qui rencontre qui sans s'intéresser à là où se passe (*), on peut faire le produit ce que @marco appelle le nombre de doubles fonctions bijectives dans ce fil en suivant les liens de l'OEIS tu devrais trouver des formules (ça devrait ressembler à celle que je vais décrire ci-dessous, mais avec 2 à la place des 3, des $n$ à la place des $n-1$ et des carrés sur pas mal de facteurs)

  Il faut aussi savoir dénombrer le nombre de "doubles dérangements" (pour les rencontres au sein d'un même groupe de niveau) d'un ensemble de taille $n$ (égal à 9 ici), si on impose que le graphe du double dérangement n'a qu'une seule composante connexe (**), ça doit être $\frac{(n-1)! (n-2)!}{2}$.

   Je dis peut être une bêtise mais je crois que pour compter le nombre totale de double dérangements (si on n'impose pas qu'il n'y a qu'une composante connexe) d'un ensemble de cardinal $n$ il faut considérer l'ensemble $A_n$ défini ainsi: les éléments $Z$ de $A_n$ sont les fonctions partielles de $|[3,n]|$ dans $\mathbb{N}\setminus \{0\} $ (ça signifie que $Z$ est un ensemble de couple $(x,y)$ avec $x\in |[3,n]|$ et $y$ un entier supérieur ou égal à 1, et il n'y a pas deux éléments distincts de $Z$ qui ont le même $x$) qui vérifient $ \displaystyle \sum_{(x,y)\in Z} xy = n$ (on en déduit que les $y$ sont plus petit ou égal à $n/3$): le nombre total de "doubles dérangements" doit alors être: $\displaystyle \sum_{Z \in A_n} n! \prod_{(x,y)\in Z} \frac{1}{y!}\left(\frac{(x-1)!(x-2)!}{x!2}\right)^y$ 

Bien sûr le $n!$ peut être mis en facteur et les $\frac{(x-1)!}{x!}$ se simplifie en $\frac{1}{x}$, mais je préfère écrire ainsi pour que l'utilisation de la formule précédente et des coefficients multinomiaux apparaîssent clairement.

  Edit après lecture du post de LOU16 : J'ai fait n'importe quoi. Le nombre de "double dérangement connexe" n'est pas du tout égal à $\frac{(n-1)!(n-2)!}{2}$ mais tout simplement à la moitié du nombre de dérangement (comme il l'a fait). En remplaçant ce type de facteur dans la formule finale, on doit trouver la même chose que son $N_{11}$ (dans sa formule on respectivement les résultat pour 1 composante connexe, pour deux composantes connexes : 6/3, 4/5 et le cas avec trois composante connexes de trois éléments chacune).

  C'est à peu près tout ce que je peux produire sur le sujet sans trop me prendre le chou, j'espère que ça aidera, bon courage pour la suite, comme l'a dit lourrran, le résultat sera vachement grand.

(*) : il faut savoir qu'avec prise en compte des emplacements des rencontres ça va faire un truc plus de $2^{10} = 1024$ fois plus grand et aussi que la formule générale va être absolument ignoble.

(**) : pour l'histoire d'unique composante connexe : c'est à dire que si on prend deux équipes de même niveau, il existe un chemin d'équipe qui va de l'une à l'autre par le graphe dont les sommets sont les équipes d'un groupe de niveau et les arêtes l'existence d'une rencontre entre les deux.

LOU16

Bonjour,

C'est en effet assez compliqué.

Je note $N$ le nombre cherché. Alors $\boxed{N =N_{11}^4\times N_{12}^6\approx 7.2\times 10^{78}}\:$  où:

$N_{11}= $ nombre de tournois opposant exclusivement les équipes de la poule $ 1,$ qui doivent chacune disputer deux matchs.

$N_{12}=$ nombre de tournois opposant exclusivement les équipes des poules $1$ et $2$,  où chaque équipe doit affronter deux équipes de la poule à laquelle elle n'appartient pas.

$N_{11} =\text{ nombre de graphes }2\text{- réguliers  d'ordre } 9= \displaystyle \dfrac{8!}2 +\binom 93\dfrac{5!}2\dfrac{2!}2+\binom 94\dfrac{4!}2 \dfrac{3!}2 +\dfrac{9!}{6^4}$

$$\boxed{N_{11}=9!\left(\dfrac 1{18}+\dfrac1{72}+ \dfrac 1{80}+ \dfrac 1{1296}\right)=30\: 016.}$$

(les composantes connexes de ces graphes sont des cycles de longueur supérieure à $3$.)

$N_{12}= \text{ nombre de graphes }2\text{- réguliers bipartis }(9,9), \text{ dont la partition est fixée par les deux poules.}$

$\cancel {N_{12}}=\overline{N_{12}} =\displaystyle\dfrac{9!8!}2+\binom 92^2\dfrac{7!6!}2+\binom 93^2\dfrac{3!2!}2\dfrac{6!5!}2+\binom94^2\dfrac {4!3!}2\dfrac{5!4!}2+\dfrac {9!}{6^4}\dfrac{9!}{6^3}\left(\dfrac{3!2!}2\right)^3.$

(les composantes connexes de ces graphes sont des cycles "bipartis" de longueur (paire) supérieure à $4$.)

Edit 1. Cette évaluation "$\overline{N_{12}}$" de $N_{12}$ est fausse: je n'ai considéré que $\text{ les partitions de }18$ suivantes,(définies par les effectifs des composantes connexes du graphe associé à l'organisation du tournoi): $18,\:\:4+14,\:\:6+12,\:\:8+10,\:\: 6+6+6$ et oublié ( je ne sais trop pourquoi) les partitions $4+4+10, \:\:4+6+8,\:\:4+4+4+6.\:\:$ Ainsi, une "réparation" de $N_{12}$ s'impose:

$N_{12} =\overline{N_{12}}+\dfrac {9!}{2^3.5!}\dfrac{9!}{2^2.5!}\dfrac{5!.4!}2+\left(\dfrac{9!}{2!3!4!}\right)^2\dfrac{3!2!}2\dfrac{4!3!}2+\dfrac{9!}{2!^3.3!^2}\dfrac{9!}{2!^3.3!}\dfrac{3!2!}2.$

$$\boxed{N_{12}=9!^2\left(\dfrac1{18}+\dfrac 1{56}+ \dfrac 1{72} +\dfrac 1{80}+\dfrac 1{1296} +\dfrac 1{320} +\dfrac 1{192}+\dfrac 1{2304}\right)=14\: 398\:171\: 200.}$$

Edit 2. Le dénombrement précédent suppose bien entendu que les $4$ poules ont été préalablement constituées. Sinon, il faut multiplier $N$ par $\dfrac{36!}{4!9!^4}.$ (nombre de partitions d'un ensemble de cardinal $36$ en $4$ parties de cardinal $9$.)

D'autre part, il ne tient pas compte non plus du lieu où se déroulent les rencontres. Pour prendre en compte cette localisation, il suffit d'orienter tous les cycles présents dans le graphe. (que j'ai privés d'orientation dans le décompte opéré précédemment, à coups de divisions par $2$.)

JLapin

Pas de mauvaise foi : simplement j'ai mal lu la consigne !

canasson29

Le dénombrement de Lou16 me laisse sans voix. Il y a effectivement 4 groupes de niveau constitué chacun de 9 équipes.

Pour ce qui est de la prise en compte des maths à domicile et à l'extérieur, j'imagine qu'ils vont respecter une stricte alternance. Pour les cas d'égalité de points,  il y a dix critères de départage ! Je vais essayer de décortiquer vos solutions !

lourrran

Après 2 petites heures de marche (pendant lesquelles j'ai un peu cogité la question), je reviens.
Pas pour répondre à tes 2 questions, je pense qu'on a fait le tour ou quasiment.
Mais pour évaluer les intérêts du système mis en place, et surtout, pour mettre en lumière une certaine iniquité dans le truc mis en place ( ... si tu as un lien pour avoir une description précise, peut-être plus complète, ce serait bien)

Cas général ... très simple.
On a 36 équipes, on a un rang pour chaque équipe, basée sur les performances passées. On a donc une 'force' pour chaque équipe. Pour simplifier à l'extrême, je vais considérer que l'équipe la plus forte a une force de 36, puis on enlève 1 pour chaque équipe. C'est une simplification extrême, mais a priori, les remarques à venir restent valables avec des modélisations plus sérieuses.
Si on fait des tirages totalement aléatoires (sans groupes de niveau), l'équipe n°1 va rencontrer 8 équipes dont la force est en moyenne un nombre entre 1 et 35, la somme des 8 forces en question sera en moyenne 144 ;L'équipe n°2 va rencontrer également 8 équipes, mais la somme des forces possible est un tout petit peu plus forte (elle peut tomber contre l'équipe 1, alors que l'équipe 1 avait l'assurance de ne pas tomber contre elle-même, lapalissade). En moyenne, la somme des forces des équipes rencontrées par l'équipe 2 est de 144.28
Et si on continue, on trouve 144.57 pour l'équipe 3, etc etc , cette force moyenne augmente de 2/7=0.28 à chaque équipe. 
Mais problème, on peut avoir une équipe très chanceuse, qui rencontrerait par exemple 8 équipes toutes très faibles. 
On a une très forte variance autour de ces différentes moyennes (peut-être devrais-je employer le mot espérance au lieu du mot moyenne, peu importe).

Création de 4 groupes, chaque équipe rencontre 2 équipes de chaque groupe.
Du coup, pour limiter cette variance, l'UEFA a décidé de créer des groupes de niveau (homogènes) ...
On a maintenant l'assurance qu'aucune équipe ne rencontrera 8 équipes toutes très faibles. C'est bien.
L'équipe n°1 va rencontrer 2 équipes du groupe 1 (la somme des forces sera en moyenne de 63, puis 2 équipes du groupe n°2 (somme des forces en moyenne de 46)  puis 2 équipes du groupe 3 (somme des forces en moyenne de 28) et enfin 2 équipes du groupe n°4 (somme des forces en moyenne de 10) ; Total pour l'équipe 1 : 147
Pour l'équipe 2, le même calcul donne 147.25
Et on augmente de 0.25, jusqu'à l'équipe 9 où ce calcul donne 149
Pour l'équipe n°10, on retrouve 147, comme pour l'équipe n°1 , et c'est un peu problématique, n'est-ce pas ?
Et évidemment, la même séquence, avec +0.25 à chaque rang, jusqu'à un total de 149 pour l'équipe n°18 , et ça continue idem sur les groupes n°3 et 4.

L'équipe classée n°9 est donc statistiquement désavantagée, elle rencontre 'statistiquement' des équipes plus fortes que les équipes rencontrées par l'équipe n°10
L'équipe classée n°8 est également désavantagée, dans une moindre mesure, et idem les équipes classées 17 ou 18.

Cette fonction 'somme des forces des équipes potentiellement rencontrées' n'est plus monotone comme dans le cas basique, il y a des effets de seuils. La base quand on crée des seuils, c'est de vérifier que ça ne crée pas des points de discontinuité.

Accessoirement, très accessoirement, ça accentue le risque d'ex-aequo à la 8ème place. On a un système qui pénalise un peu les équipes classées 7ème, 8ème ou 9ème, ça les rapproche du ventre mou, ça augmente le risque d'ex-aequo. 

  

canasson29

Le système de niveau existait déjà pour le tirage au sort de chacune des 8 poules de 4. Les 4 équipes étaient de de 4 chapeaux différents. Cela était-il plus équitable ? Sachant qu'il y avait un reversement dans l'autre compétition européenne pour les troisièmes, ce qui faisait des deux autres compétitions de vraies usines à gaz.

 La vraie raison est que l'organisateur veut se prémunir d'un risque d'une compétition parallèle en laissant croire que la compétition sera plus élitiste auprès des clubs huppés

canasson29

Petite précision sur les matchs à domicile et à l'extérieur. Lors des confrontations avec deux équipes d'un même groupe de niveau, un match est à domicile, l'autre est à l'extérieur. Ca complique les choses ! Je vous fais grâce de l'impossibilité d'affronter une équipe de son championnat, qui est le summum de l'inéquité sportive.

lourrran

Tu m'as envoyé en privé le lien vers le règlement, mais je le recopie ici, c'est intéressant.
En particulier, toutes les règles annexes pour départager les ex-aequos sont données (article 18). Et vu le nombre de critères qui peuvent être appliqués, on est couvert !
L'iniquité que je dénonce, elle est minime, évidemment. C'est plus une question d'exercice mathématique qu'une question de justice.
En terme d'intérêt, j'aime assez bien cette évolution. Le fait de devoir jouer 2 matchs aller-retour contre je ne sais quelle équipe de 5ème zone, c'était assez ridicule.

Je dis ça, je ne dis rien. Je ne m'intéresse pas du tout au foot.

Titi le curieux

Re-bonsoir,

  Outre celle concernant JLapin (pardon JLapin), j'ai fait une énorme boulette dans mon premier message, je l'ai édité.

  En ce qui concerne le nombre de possibilité avec prise en compte des lieux : la dernière information de canasson29 est intéressante

canasson29 a dit :

Petite précision sur les matchs à domicile et à l'extérieur. Lors des confrontations avec deux équipes d'un même groupe de niveau, un match est à domicile, l'autre est à l'extérieur. Ca complique les choses !

  En fait non, au contraire même, ça simplifie pas mal le problème. Si par bonheur on devait en plus considérer qu'une équipe d'un certain niveau devait lors de ses rencontre avec les deux équipes d'un autre niveau en faire une à domicile et l'autre l'extérieur, il suffirait de reprendre les formules de LOU16 en se contentant de faire sauter tous les facteurs 1/2 (enfin pas exactement car il y a au moins un qui est caché, le $\frac{9!}{6^4}$ du $N_{11}$ devient alors $\frac{9!}{6\times 9}$), tout simplement parce qu'alors pour chaque composante connexe de l'un de ses graphes, on a exactement deux possibilités pour les emplacements.