Comptine...

soland
soland
dans Arithmétique
Quelqu'un aurait-il une preuve simple comme quoi $$
f(x,y,z) := C^{3}_{x+y+z+2} + C^{2}_{x+y+1}+C^1_x
$$ est une bijection de $\mathbb{N}^3$ sur $\mathbb{N}$ ?

(Les $C_{...}^{...}$ sont des coefficients binomiaux.)

Réponses

  • GaBuZoMeu
    GaBuZoMeu
    Utiliser $C_n^k$ au lieu de $\binom{n}{k}$ pour les coefficients binomiaux, très bien, mais les écrire $C_k^n$, très mal !!

    [J'ai corrigé le message de Soland. ;-) AD]
  • GaBuZoMeu
    GaBuZoMeu
    À part ça, on peut avoir l'idée d'énumérer $\N^3$ en suivant l'ordre lexicographique des $(x+y+z,x+y,x)$.
  • soland
    soland
    Merci, AD.
    [À ton service. :-) AD]
  • jandri
    jandri
    C'est un cas particulier d'une propriété plus générale. Pour $p\in\N^*$ fixé on a:

    pour tout $n\in\N$ il existe un unique $(x_1,...,x_p)\in\N^p$ tel que $x_1<...<x_p$ et $n=\displaystyle\sum_{k=1}^p\binom{x_k}{k}$.
  • GaBuZoMeu
    GaBuZoMeu
    L'idée est la même pour $p$ que pour $3$ : numérotation dans l'ordre lexicographique (sur $(x_p,\ldots,x_1)$ pour la comptine de jandri).
  • soland
    soland
    Merci. On a sûrement une preuve ?
  • GaBuZoMeu
    GaBuZoMeu
    Je te l'ai pratiquement déjà donnée. N'as-tu pas vu ? On peut compléter par l'histoire des combinaisons avec répétitions pour voir comment apparaissent les coefficients binomiaux : le nombre de $k$-uplets d'entiers naturels de somme $<n$ est $C_{n+k-1}^k$.
  • soland
    soland
    @GBZM
    Ce qui me manque, c'est un procédé simple pour trouver $\;^rf(10^6)$, par exemple.
  • GaBuZoMeu
    GaBuZoMeu
    Ce n'est pas ce que tu demandais au début : tu demandais de démontrer qu'il s'agit d'une bijection, c'est fait. Maintenant tu veux autre chose.
  • jandri
    jandri
    Il suffit d'écrire un petit programme.

    $10^6=\displaystyle\binom{182}{3}+\binom{153}{2}+\binom{112}{1}$.

    $10^{20}=\displaystyle\binom{26053}{5}+\binom{23922}{4}+\binom{19585}{3}+\binom{12623}{2}+\binom{4602}{1}$.
  • soland
    soland
    ok. Donc pas de "closed form".
  • jandri
    jandri
    A ma connaissance il n'existe pas de formule explicite pour la bijection réciproque de $f$.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 5

alexisp +4 Invités