Nombre de k-uplets

math65

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.

Heuristique

Bonjour
Comment pourrais-tu interpréter combinatoirement le coefficient $\binom{n}{k}$ ?

math65

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$.

NicoLeProf

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.

OShine

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. 

OShine

@NicoLeProf
Oui ta méthode est intéressante. 

NicoLeProf

C'est la plus simple pour quelqu'un de très incompétent en dénombrement comme c'est mon cas ! xd

Quoique simple, je ne sais pas au final !

math65

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.

lourrran

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.

Heuristique

@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]]$

NicoLeProf

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é.

math65

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

lourrran

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.

OShine

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. 

Heuristique

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é)

math65

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.

JLapin

Vérifie que $(x_1,...,x_k)\mapsto (x'_1,....,x'_k)$ est bijective.

math65

@JLapin c'est donc la technique générale à appliquer dans ce genre de situation?

JLapin

Je ne comprends pas ta question.

Heuristique

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.

nicolas.patrois

math65 a dit :

J'ai une petite question : qu'est-ce que signifie $E^F$ avec $E$ et $F$ deux ensembles finis ?

Ici.

math65

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.

JLapin

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$.