Nombre de k-uplets
Réponses
-
Bonjour
Comment pourrais-tu interpréter combinatoirement le coefficient $\binom{n}{k}$ ? -
concrètement, c'est le nombre de possibilités de prendre $k$ choses dans $n$ choses.Mais je pense avoir saisi le principe. Pour une combinaison d'entiers $(x_1,x_2,\dots,x_k)$ on ne peut en avoir d'autres car $1 \leq x_1 < x_2<\dots<x_k<n$.
-
Le plus simple ici je dirais est de se dire : "combien de façons de choisir $x_1$ ? " puis "combien de façons de choisir $x_2$ sachant qu'on a déjà choisi $x_1$ ? " etc.Lorsque notre cher Gebrane, le 😄 farceur, intervient dans une question d'algèbre, c'est une véritable joie pour les lecteurs.
-
Il y a $k$ parmi $n$ façon de choisir $k$ éléments parmi $n$, puis une seule façon de les ranger dans l'ordre strictement croissant ce qui donne $\binom{n}{k} \times 1=\binom{n}{k}$ possibilités.
-
@NicoLeProf
Oui ta méthode est intéressante. -
C'est la plus simple pour quelqu'un de très incompétent en dénombrement comme c'est mon cas ! xdQuoique simple, je ne sais pas au final !Lorsque notre cher Gebrane, le 😄 farceur, intervient dans une question d'algèbre, c'est une véritable joie pour les lecteurs.
-
Aussi, j'avais l'impression d'avoir posé cette question.je me demandais si l'application qui à $(x_1,x_2,\dots,x_k)$ associe $(x'_1,x'_2,\dots,x'_k)$ avec $(x_1,x_2,\dots,x_k) \in \mathbb N^k$ et $x'_i=\sum_{j=1}^{i}x^j$ est une bijection.Et par conséquent si je peux considérer que ces le nombre de combinaisons est le même dans les deux k-uplets.Merci.
-
Pour savoir si c'est une bijection, il y a 2 choses à vérifier ...
- injection
- surjection
Par ailleurs, parler de 'nombres de combinaisons identiques dans les 2 cas', quand on parle de nombres infinis, c'est chaud, on a vite fait d'écrire des trucs faux, attention.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
L'hypocrisie est pire qu'une vérité qui fait mal. Franck Ntasamara. -
@NicoLeProf Je trouve plus simple de dire que l'on choisit une partie à $k$ éléments de $[[1,n]]$. Dès lors, les valeurs des $x_i$ sont imposées. Il y a donc une bijection entre les parties à $k$ éléments de $[[1,n]]$ et les fonctions strictement croissantes de $[[1,k]]$ dans $[[1,n]]$
-
Oui oui, j'avais mal lu l'énoncé et je pensais à autre chose... Donc non, ça ne va pas pour ma première réponse, désolé.Lorsque notre cher Gebrane, le 😄 farceur, intervient dans une question d'algèbre, c'est une véritable joie pour les lecteurs.
-
Pour montrer que cette application est injective, je pense que cela est possible.Par contre pour la partie surjective, je pense qu'il est important de préciser que l'ensemble d'arrivée doit être $F=\{(x_1,x_2,\dots,x_n) \in \mathbb N^n\mid x_1\leq x_2\leq\dots\leq x_n\}$.@lourrran Je ne comprends pas le principe de nombre infinis pour le dénombrement
-
Si tu modifies l'ensemble d'arrivée comme tu le proposes, alors on a bien une bijection.
Sur l'histoire des nombres infinis, si tu fixes par exemple $k=2$, alors tu as un certain nombre de combinaisons qui vaut l'infini.
Et si tu fixes $k=10$, tu as (paradoxalement) le même nombre de combinaisons, qui vaut toujours l'infini.
Et il faut être précis, ça évite de faire des erreurs.
le nombre de combinaisons est le même dans les deux k-uplets.
Non : le nombre de combinaisons est le même dans les deux ensembles de k-uplets.
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
L'hypocrisie est pire qu'une vérité qui fait mal. Franck Ntasamara. -
Exercice :
Soit $n,p \in \N^{*}$. Déterminer le nombre d'applications strictement croissantes de $[|1,p|]$ dans $[|1,n|]$.
Prendre l'exemple $p=3$ et $n=9$ peut être utile. -
C'est exactement l'exercice qui a été donné en début de fil... (à ceci près que ton $p$ s'appelle $k$ dans l'énoncé)
-
J'ai une petite question : qu'est-ce que signifie $E^F$ avec $E$ et $F$ deux ensembles finis ?Aussi, dans une autre question, on me demande de dénombrer les $k$-uplets $(x_1,x_2,\dots,x_k)$ tels que $1\leq x_1 \leq x_2 \leq\dots\leq x_k \leq n$
La technique consiste à poser $x'_i=x_i+i-1$
Dans ce cas, on obtient $1\leq x'_1 < x'_2 <\dots< x'_k \leq n+k-1$
On en déduit à partir du premier résultat que le nombre de k-uplets $(x'_1,x'_2,\dots,x'_k)$ est $\binom{n+k-1}{k}$Mais ma question est de savoir pourquoi peut-on dire qu'il y a autant de $k$-uplets $(x_1,x_2,\dots,x_k)$ que de $k$-uplets $(x'_1,x'_2,\dots,x'_k)$ ?
Merci. -
Vérifie que $(x_1,...,x_k)\mapsto (x'_1,....,x'_k)$ est bijective.
-
Je ne comprends pas ta question.
-
Si je comprends bien la question : oui, les bijections sont la technique générale à appliquer en dénombrement, car c'est la définition même de la notion de cardinal.
-
-
Dans un autre exemple, je dois trouver toutes les solutions de l'équation $x_1+x_2+\dots+x_k=n$ avec $(x_1,x_2,\dots,x_k) \in \mathbb N^k$ et $n\in \mathbb N$.La technique est de poser $x'_i=\sum_{j=1}^i x_j$ et de déterminer le nombre de possibilité pour $(x'_1,x'_2,\dots,x'_k)$ qui est le même que celui de $(x_1,x_2,\dots,x_k)$.
Je dois donc prouver que l'application qui à $(x_1,x_2,\dots,x_k)$ associe $(x'_1,x'_2,\dots,x'_k)$ est bijective.Prouver que cette application est bijective, est-ce une condition nécessaire et suffisante pour que $(x_1,x_2,\dots,x_k)$ et $(x'_1,x'_2,\dots,x'_k)$ aient le même nombre de combinaisons ?Merci. -
En général, si tu parviens à montrer qu'il existe une bijection entre deux ensembles finis $E$ et $F$, tu peux en déduire que $card E = card F$.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.6K Toutes les catégories
- 64 Collège/Lycée
- 22.2K Algèbre
- 37.7K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 343 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.4K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 805 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres