Nombre de k-uplets — Les-mathematiques.net The most powerful custom community solution in the world

Nombre de k-uplets

Modifié (May 2023) dans Combinatoire et Graphes
Bonjour,
$k \in \mathbb N$, $\ 1 \leq x_1 < x_2<\dots <x_k \leq n$.
On me demande le nombre de $k$-uplets $(x_1,x_2,\dots,x_k)$ possible et je sais que la réponse est le nombre de combinaisons de $k$ dans $n$.
Mais ce résultat ne fait pas intervenir l'ordre. Il manque donc des solutions ?
Merci.

Réponses

  • Modifié (May 2023)
    Bonjour
    Comment pourrais-tu interpréter combinatoirement le coefficient $\binom{n}{k}$ ?
  • Modifié (May 2023)
    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$.
  • Modifié (May 2023)
    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. :)
  • 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. 
  • Modifié (May 2023)
    C'est la plus simple pour quelqu'un de très incompétent en dénombrement comme c'est mon cas ! xd :D:D
    Quoique simple, je ne sais pas au final ! :D
  • Modifié (May 2023)
    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.
  • Modifié (May 2023)
    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
  • @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]]$
  • Modifié (May 2023)
    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é. :(
  • Modifié (May 2023)
    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
  • 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é)
  • Modifié (May 2023)
    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.
  • @JLapin c'est donc la technique générale à appliquer dans ce genre de situation?
  • 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.
  • math65 a dit :
    J'ai une petite question : qu'est-ce que signifie $E^F$ avec $E$ et $F$ deux ensembles finis ?
    Ici.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Modifié (May 2023)
    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.
  • Modifié (May 2023)
    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.
Success message!