Vérification d'une Formule de dénombrement

Bonjour,

Je ne sais pas si mon sujet peut s'inscrire ici, car c'est surtout une vérification par des matheux d'une formule de dénombrement dont j'ai besoin dans la rédaction d'un tuto pour vérification d'échantillons de tests. J'ai cherché un forum Maths ou statistiques, mais je n'ai pas trouvé, alors je post ici car mes souvenirs sont un peu lointain dans ce domaine.

Voici le sujet :

Je dois effectuer des tests sur un grand nombre de possibilités. Je n'ai pas déterminé les limites de mes paramètres et c'est pour cette raison que j'ai besoin d'une justification théorique. Je n'en suis donc pas encore à élaborer un algorithme.

Problème : Je voudrais savoir combien il y a de possibilités d'avoir des échantillons de 100 entreprises déterminées qui se répartissent dans un échantillon de 1000 villes prises dans un ensemble de toutes les villes de France, soit 39192 villes, villages etc avec un code postal...
Les couples résultats ont le format suivant : (entreprises, ville) dans cet ordre et il ne doit pas y avoir deux couples semblables dans l'ensemble des couples viables.

Pour des raisons de limites logicielles et matérielles, nous prenons un échantillon test de 1000 villes par exemple (sans répétition de villes dans l'échantillon). Mais je voudrais connaitre au final, le nombre de tests possibles sur l'ensemble des villes de France par le biais des tests sur les échantillons.

Variables du problème:

- Ei = {1..100} entreprises distinctes (E).
- Vi = {1...39192} villes (V).
- On sélectionne un échantillon de k villes distinctes parmi ces 39192 (pas de doublon de ville dans chaque échantillon).
- On cherche le nombre de façons distinctes d'affecter ces 100 entreprises (toutes utilisées, chacune dans une ville différente) à 1000 villes prises dans un échantillon choisi.
- Dans chaque couple, l’entreprise est en première position et la ville en seconde, et chaque couple doit être unique.

On veut compter le nombre de possibilités maximales pour tous les échantillons possibles de villes (sans répétition de villes ni doublon de couple).

Ntotal : nombre total de villes (ici 39192)
k : taille de l’échantillon de villes (exemple : 1000, etc.)
p : nombre d’entreprises à positionner (=100, déterminées)

Formules :

- Choisir un échantillon de k villes parmi 39192 => pas de répétition, ni ordre, que paris soit en 10ème ou en 100ème position dans l'échantillon n'a pas d'importance du moment que l'on a pas deux fois Paris...
donc pour moi, c'est une combinaison : C(Ntotal,k). ëtes-vous d'accord?
- Ensuite, il me faut Associer les n entreprises déterminées aux villes de l'échantillon, sans doublons, mais ici l'ordre est important car le couple (Textronic, Paris) est différent de (Paris, Textronic) qui doit être écarté.
donc, c’est un arrangement sans répétition : A(p,k). êtes-vous d'accord?
- et donc, j'arrive à ma formule finale qui prend en compte tous les couples possibles pour les tests sur tous les échantillons :

Nombre total=C(Ntotal,k)×A(k,p).

Merci de me dire s'il y a une faille dans mon raisonnement!
A+

La question n'est pas totalement claire.
Tu parles de villes et d'entreprises, et dans mon monde à moi, je comprends qu'on a un recensement des entreprises existantes (l'usine de chaussures xxx existe, dans la ville de Lyon). A priori, je fais fausse route.
On aurait donc en fait 100 entreprises 'nouvelles', nommées E001, E002,... E100.
Et on a 39192 communes C00001 , C00002, ... C39192
Les entreprises n'existent pas encore, et on va implanter ces 100 entreprises dans 100 villes. Et on s'intéresse au nombre de façons de choisir les villes pour chacune des 100 entreprises.

Clarification n°1 : Est-ce qu'il peut y avoir plusieurs entreprises dans la même ville ? Dans la suite, je pars du principe que OUI, il peut y avoir plusieurs entreprises dans la même ville.

Pour des raisons diverses, tu commences par choisir un échantillon de 1000 villes. Mais cette étape ne fait que perturber le raisonnement. Et même en terme de programmation, je doute que ça apporte quoi que ce soit.

Pour l'entreprise E001, on a 39192 choix possibles.
Pour l'entreprise E002, on a 39192 choix possibles.
Etc
Au final, on a 39192^100 choix possibles.

Merci tbc92 d'avoir pris le temps d'examiner le problème.

Citation:

---

Envoyé par tbc92

La question n'est pas totalement claire.
Tu parles de villes et d'entreprises, et dans mon monde à moi, je comprends qu'on a un recensement des entreprises existantes (l'usine de chaussures xxx existe, dans la ville de Lyon). A priori, je fais fausse route.
On aurait donc en fait 100 entreprises 'nouvelles', nommées E001, E002,... E100.
...
Clarification n°1 : Est-ce qu'il peut y avoir plusieurs entreprises dans la même ville ? Dans la suite, je pars du principe que OUI, il peut y avoir plusieurs entreprises dans la même ville.

Pour des raisons diverses, tu commences par choisir un échantillon de 1000 villes. Mais cette étape ne fait que perturber le raisonnement. Et même en terme de programmation, je doute que ça apporte quoi que ce soit.
...

---

J'ai pris cet exemple de couple (entreprise, ville) de manière totalement fictive et ne correspond pas à une réalité d'un processus réel... J'aurais pu prendre (livre, étagère) ou (étudiants, université)...
Oui, je n'ai peut être pas été assez clair!

Le but de mon test est de quantifier un nombre de possibilités qui puissent être représentées dans le pire des cas aux possibilités graphiques maximales d'un écran, donc par un pixel. Ainsi, un écran de 1000 X 800 = surface de dessin maximal = 800 000 pixels, donc 800 000 couples solutions. Cela dans le but de rechercher des valeurs limites et de sécurité, y compris en terme de temps d'exécution de rafraichissement d'écran de gestion mémoire... La représentation graphique d'une entité (couple solution : entreprise/ville) peut se représenter par un pixel de couleur ou une petite grille. Un clic sur la grille ou un pixel et on extrait l'information.

Clarification n°1 : non, une ville = une entreprise (une enseigne). Mais une même enseigne (par exemple "Auchan") pourra se trouver dans d'autres villes. Mon exemple ne semble peut être pas réaliste, mais ça n'est pas le but, c'est uniquement pour un test d'extraction d'une information sur une grille qui représente un ensemble de possibilités.

Je crois que pour tester la solution que je propose, on pourrait ramener les variables à de toutes petites valeurs et lister les solutions. Par exemple:
- Ei = {1..2} échantillon de 2 entreprises distinctes: E1 et E2.
- Vi = {1..6} 6 villes = ensemble des villes : V1..V6
- k = taille de l'échantillon de villes = par exemple k = 3 villes parmi les 6
=> étape 1 : choisir un échantillon de 3 villes parmi 6 => avec la formule donnée, je trouve 20 échantillons possibles.
=> Et ensuite pour l'étape 2, je répartis mes 2 entreprises dans 2 des 3 villes sélectionnées de mon échantillon (car je n'ai que 2 entreprises), ça me donne avec ma formule, 6 façons (couples) de prendre 2 entreprises dans un échantillon de 3 villes.
et donc au final, avec tous les échantillons ma formule finale me donne :

Nombre total = C(6,3) × A(3,2)= 20 × 6 = 120. Je vais lister les 120 couples (entreprises/villes) pour vérifier s'il n'y a pas de doublons...

On va commencer par une question plus simple.
Il y a 1000 Villes en France. Du coup, je supprime l'étape 1 (choisir 1000 villes parmi les 39192). Si on arrive à se comprendre avec cette simplification, on pourra ensuite voir l'impact de cette première étape.
L'entreprise E001 peut être dans l'une ou l'autre des 1000 villes.
L'entreprise E002 peut être dans l'une ou l'autre des 999 villes restantes.
L'entreprise E003 peut être dans l'une ou l'autre des 998 villes restantes.
etc.
Au total, on a 1000*999*998*997* ...*902*901 possibilités.

Dans ton comptage ( les 120 solutions), tu as des doublons.
Tu peux par exemple choisir dans l'étape 1 les villes (V001, V002, V003) , ou encore les villes (V001, V002, V004).
Et dans ces 2 choix, tu peux au final avoir la combinaison (E001-V001, E002-V002) ; cette solution est donc comptée 2 fois (et même plus)

Citation:

---

Envoyé par tbc92

On va commencer par une question plus simple.
Il y a 1000 Villes en France. Du coup, je supprime l'étape 1 (choisir 1000 villes parmi les 39192). Si on arrive à se comprendre avec cette simplification, on pourra ensuite voir l'impact de cette première étape.

---

Exact, tu m'a convaincu, il faut supprimer l'étape 1.
Je réfléchis à la suite ...
Bonne soirée!

Bonjour :coucou:

• Il y a un sous-forum mathématiques.
• Ne parle pas d'arrangement. C'est faux. Il n'existe pas d'entreprise "Paris" et pas de ville "Textronic".
• De ce que je comprends, on calcule ceci :
  
  • On tire 1000 villes parmi 39192, indépendamment de l'ordre et sans répétition. C'est donc une combinaison. Jusqu'ici, on est d'accord.
  • On tire 1000 entreprises parmi 100, dans l'ordre (car affecter Textronic à Paris et Suptronic à Lyon n'est pas la même chose qu'affecter Suptronic à Paris et Textronic à Lyon), et avec répétition (nécessairement puisque 1000>100). C'est donc une p-liste.
  
  En gros, ton premier tirage est un sous-ensemble, et le second est un anagramme.

Conclusion, la quantité de situations possibles est :


[edit] Arf. Latex est à nouveau en rade. Voici :
C_{39192}^{1000} \times 100^{1000}
[/edit]

:ccool: Bon courage !

A mon avis, ce n'est pas ça. De ce que je comprends, l'étape intermédiaire avec un tirage de 1000 villes est totalement artificielle, elle est là pour alléger la base de données.
Au final, la seule chose qui nous intéresse, c'est quelles sont les 100 villes avec une entreprise, et quelle est l'entreprise dans chacune de ces 100 villes.
Cette étape intermédiaire, elle pourrait consister à choisir 400 villes, ou 2000, ça ne devrait avoir aucun impact sur le dénombrement.

C'est comme ça que je comprends la demande, mais je peux tout à fait me tromper.

Bonjour,

Je me trompe peut être, mais il me semble manquer une donnée : le nombre d'agences par société.

Quelques présupposés :

• Chacune des Ns société peut implanter une (et une seule) agence dans n'importe quelle des V villes dans la limite de son nombre d'agences As.
• Les implantations des sociétés sont indépendantes

Pour une société S qui a As agences, le nombre de répartitions possibles dans les V villes sera Cs = C(V, As). Le pire des cas (au sens du plus nombreux) est si As = V/2 soit Cs_max = C_max = C(V, V/2) = V! / ((v/2)!)².

Pour Ns sociétés, comme les choix sont indépendants, le pire des cas devient simplement C_max^Ns. Ca fait beaucoup, pour 10 villes et 10 sociétés cela fait environ 10²⁴.

Si on veut inventorier tous les cas possibles (en faisant varier le nombre d'agences de 0 à V), c'est encore pire : 2^V*Ns.

Coté pratique, cliquer sur un pixel précis dans une image n'est pas simple, il faudrait prévoir une aide à la localisation (par exemple le plus proche point non noir).

Salutations

Bonjour,

Pourquoi faire compliqué quand on peut faire simple?
C'est vrai que si je prends deux ensembles finis :
- E = {E1...Ex} un ensemble d'"entreprises"
- V = {V1...Vy} un ensemble de "villes"

Et que l'on souhaite constituer tous les couples (Ei,Vj) avec les contraintes suivantes :
- Les couples sont uniques (pas de doublons)
- Une entreprise peut apparaître sur plusieurs villes, mais une ville ne peut recevoir qu'une seule entreprise
- L'ordre est strict : (Entreprise, Ville)
La solution est un produit cartésien: N=E ×V. Exemple E = 2, V = 3 => N = 6 : {(e1,v1),(e1,v2),(e1,v3),(e2,v1),(e2,v2),(e2,v3)}

Étape 1: Objectif Mon véritable objectif est de trouver les bonnes valeurs limites et interdépendantes du nombre d'entreprises Ep et de villes Vn (ça pourrait être n'importe quel autre paramètres) pour obtenir un nombre de possibilités représentées sur un écran d'ordinateur. Par exemple un Écran de 1000 × 800 pixels => 800 000 pixels.
Donc, je suis obligé d'introduire un échantillon d'entreprises ou de villes pour approcher et voir qu'elles seraient les contraintes!

Soit un échantillon de k Villes, le nombre d'échantillons possibles serait N = E × k, mais au final ce que je veux, c'est combien de couples maximum uniques (entreprises, villes) est possible à partir de E Entreprises associées à k villes prises dans V Villes?

Étape 2 : Solution nombre de couples Possibles

D'après moi :

- Il y a répétitivité une entreprise peut être associée à plusieurs villes.
- il y a importance de l'ordre => couples ordonnés (Entreprise, Ville).

J'avais pensé à un arrangement, mais il semble que non, parce qu'un arrangement se fait sur un même ensemble d'après ce que j'ai compris, or on a deux ensembles, il s'agit donc bien d'un produit cartésien.

Le nombre de solution semble bien : N = E × k si k = échantillon de villes ou encore N = k × V si k = échantillon d'Entreprises

Bon si c'est ça, ça me simplifie le reste.

Étape 3 : Valeurs limites

Notre Limite est la Taille de la surface graphique d'un écran SCR : On prends 800 000 pixels
La contrainte est donc : N ≤ 800 000 couples, soit E × k ≤ 800 000

donc, je peux intervenir en fixant une variable à une valeur et calculer l'autre variable.

Si je prend E = 100 entreprises => E × 100 ≤ 800000 => E ≤ 8000

La formule finale est donc E × k villes ≤ SCR ou k Entreprises × V ≤ SCR

Bon, si vous êtes d'accord avec mon raisonnement, je mets résolu. merci pour votre aide.