Dénombrement de vecteurs entiers

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
MMVV
Membre Naturel
Messages: 12
Enregistré le: 03 Déc 2021, 23:55

Dénombrement de vecteurs entiers

par MMVV » 03 Déc 2021, 23:59

Bonjour (ou bonsoir ?),

On considère les vecteurs V à N composantes dont les valeurs sont prises dans E={1, 2, ..., K).
On suppose N>=K.
Combien y en a-t-il satisfaisant à la condition « contenir au moins une fois chaque élément de E » ?

J'avais d'abord pensé à une formule comme
arrangements(N,K)*K^(N-K)
mais elle compte plusieurs fois certains vecteurs et puis on voit facilement qu'elle est fausse, par exemple pour K=1.
En effet elle donne N alors qu'il n'y a qu'un vecteur possible (à savoir (1,1,1..., 1)).

C'est sans doute un problème classique de dénombrement, mais mes cours de maths sont bien loin.

Merci d'avance pour toute idée constructive



lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: Dénombrement de vecteurs entiers

par lyceen95 » 04 Déc 2021, 02:08

Je réfléchis tout haut.

Déjà, combien y a-t-il en tout de façons de mettre N objets dans K boites (... c'est un peu plus simple exprimé ainsi)
Il y a façons.
Parmi toutes ces dispositions , combien occupent au maximum j boites (avec j<= k) ?
Combien occupent uniquement les boites 1,2, 3... j :
Mais ici, j'ai imposé les boites 1 à j , mais il y a plein de façons de choisir j boites parmi les N ... donc en tout :


Ca doit être faux ... parce que les distributions qui occupent moins de j boites sont comptées plusieurs fois dans ce calcul.
Et là, pour corriger ça, il faut faire intervenir le crible de Poincaré.
Voilà le mot clé qui devrait t'aider à avancer.

Là, je suis parti sur la piste : les distributions qui occupent les k boites, ce sont toutes les distributions, sauf celles qui n'occupent pas toutes les boites.
Il y a peut-être d'autres pistes.

MMVV
Membre Naturel
Messages: 12
Enregistré le: 03 Déc 2021, 23:55

Re: Dénombrement de vecteurs entiers

par MMVV » 04 Déc 2021, 13:19

Un vecteur doit comprendre les chiffres
et les dispositions possibles sur les composantes forment un ensemble
, de taille . Un élément de peut être vu comme un vecteur de dimension avec composantes nulles.

Ces chiffres « libres »sont à choisir dans .
Pour eux, l'ensemble des dispositions est avec .
On est donc tenté de dire que le nombre cherché est simplement le
produit .

Mais on peut décrire un élément de comme un vecteur de
dimension , avec composantes nulles.

Pour construire l'ensemble cherché on prend toutes les paires d'éléments et l'on construit le vecteur .

Le problème est que cela crée des doublons. Et il ne s'agit pas d'une union au sens classique et la formule du crible de Poincaré ne s'applique pas. On notera d'ailleurs que l'intersection de et est vide.

MMVV
Membre Naturel
Messages: 12
Enregistré le: 03 Déc 2021, 23:55

Re: Dénombrement de vecteurs entiers

par MMVV » 04 Déc 2021, 15:40

Il manque un mot important vers la fin de mon dernier message :
« Pour construire l'ensemble cherché on prend toutes les paires d'éléments orthogonaux ...»

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Dénombrement de vecteurs entiers

par Ben314 » 04 Déc 2021, 22:52

Salut,
En fait, ton truc est plus connu sous l'intitulé du "nombre de surjections d'un ensemble à N éléments dans un ensemble à K éléments".
Et le résultat, c'est :

Et il y a plusieurs méthodes classiques pour le montrer dont la méthode du crible ou bien par récurrence en utilisant le fait évident (pourquoi ?) que :
Modifié en dernier par Ben314 le 05 Déc 2021, 13:32, modifié 1 fois.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

MMVV
Membre Naturel
Messages: 12
Enregistré le: 03 Déc 2021, 23:55

Re: Dénombrement de vecteurs entiers

par MMVV » 04 Déc 2021, 23:10

Merci, je me doutais bien que c'était un problème connu et résolu.
Personnellement, je suis plus à l'aise avec la démonstration par récurrence.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 20 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite