Forum Expresso

injection légale

Posté par amethyste 29-11-15 à 03:16

salut ici une injection légale (faut bien lui donner un nom alors je l'appellerai comme ça vu qu'elle servira pour un autre sujet que j'ai commencé à écrire au mois de janvier mais l'écrivant ici ça sera pour éviter de l'alourdir)

car rien que ce topic est long à écrire (j'aurai plus qu'à faire un papier/collé pour l'autre topic)

au préalable deux et uniquement deux conventions de notation

première convention de notation : $\begin {pmatrix} \binom {n}{p} \end {pmatrix}=\sum _{i=0}^{p} \binom {n}{p}$

deuxieme convention de notation:   $\mathbb {N}^*_n=\{1,2,...,n\}$ avec $n\in  \mathbb {N}^*$

l'application $f: \mathbb {N}-\{0,1\} \rightarrow \mathcal {A}$ est une injection

par conséquent   $\forall x \in  \mathbb {N}-\{0,1\},\exists f(x) \in \mathcal {A}$ et $f(x)=f(y) \Rightarrow x=y$

où $\mathcal {A}$ désigne l'ensemble de toutes les suites finies et strictement croissantes d'entiers naturels non nuls $(x_1,...,x_h)$

donc $h\in  \mathbb {N}^*$ et $\forall i\in \mathbb {N}^*_h,x_i\in  \mathbb {N}^*$ et $x_i\leq x_j \Leftrightarrow i\leq j$

__________________________

l'injection que je décris ici et donc qui servira ailleurs se présente ainsi

f(2)=(1)
f(3)=(2)
f(4)=(1,2)
f(5)=(3)
f(6)=(1,3)
f(7)=(2,3)
f(8)=(1,2,3)
f(9)=(4)
et ainsi de suite
_____________________________________

Dans un premier temps il s'agit de déterminer la suite $f(x)=(x_1,...,x_h)$ à partir de x

$x_h$ est tel que $2^{x_h-1}<x \leq 2^{x_h}$

et h est le plus petit entier naturel non nul tel que

$x\leq 1+\sum _{i=1,j=1}^{i=x_h-1,j=i}\binom {i-1}{j-1}+\sum _{k=1 }^{k=h}\binom {x_h-1}{k-1}$

pour donner la valeur de h pour tout entier naturel $x\geq 2$ on le notera par l'application h(x)

par ailleurs on pose l'application g(x) definie par

$g(x)=x-1-\sum _{i=1,j=1}^{i=x_h-1,j=i}\binom {i-1}{j-1}-\sum _{k=1 }^{k=h-1}\binom {x_h-1}{k-1}$

-pour $x=1+2^{x_h-1}$ on obtiens $f(x)=(x_h)$

-pour $h=2$ on obtiens   $f(x)=(g(x),x_h)$

-pour $h\geq 2$ et pour $g(x)=1$ on obtiens $f(x)=(1,2,...,h-1,x_h)$

-pour $h\geq 2$ et pour $g(x)=\binom {x_h-1}{h-1}$ on obtiens $f(x)=(x_1,...,x_h)$ avec

$x_1=x_h-h+1$ et $x_i=x_{i-1}+1$    avec $i\in [2,h]$

-pour   $h\geq 3$ on obtiens $f(x)=(x_1,...,x_t,x_h)$ avec $t=h-1$

on pose alors $u=x_h-1$ et on détermine $x_i\in [1,u-t+1]$ tel que

$1+\sum _{i=1}^{i=x_1-1}(-1)^{i+1}.\binom {x_1-1}{i}. \binom {u-i}{t-i}  \leq g(x) \leq \sum _{i=1}^{i=x_1}(-1)^{i+1}.\binom {x_1}{i}. \binom {u-i}{t-i}$

alors

-pour $g(x)=1+\sum _{i=1}^{i=x_1-1}(-1)^{i+1}.\binom {x_1-1}{i}. \binom {u-i}{t-i}$ on obtiens $x_j=x_{j-1}+1$   avec $j\in [2,t]$

-pour $g(x)= \sum _{i=1}^{i=x_1}(-1)^{i+1}.\binom {x_1}{i}. \binom {u-i}{t-i}$

on obtiens $x_2=u-t+2$ et   $x_j=x_{j-1}+1$   avec $j\in [3,t]$

À présent il reste à déterminer pour tous les autres cas de g(x) la valeur des

$x_j\in [x_{j-1}+1,u-t+j]$ avec   $j\in [2,t]$

pour ce faire il s'agit de déterminer la valeur $w\in [1,a-b+1]$ et on obtiendra $x_j=x_{j-1}+w$

$w$ est tel que

$1+\sum _{i=1}^{i=w-1}(-1)^{i+1}.\binom {w-1}{i}. \binom {a-i}{b-i}  \leq c_j \leq \sum _{i=1}^{i=w}(-1)^{i+1}.\binom {w}{i}. \binom {a-i}{b-i}$

avec $a=u-x_{j-1}$ et $b=t-j+1$ et

$c_j=g(x)+w_{t-1}-w_t+\begin {pmatrix} \binom {u}{t-1} \end {pmatrix} +\sum _{k=0,l=1}^{k=t-2,l=w_{k+1}-w_k-1}\begin {pmatrix} \binom {u-w_{k+1}}{t-k-2} \end {pmatrix}-\begin {pmatrix} \binom {u-w_k}{t-k-1} \end {pmatrix}- \binom {u-w_k-l}{t-k-1}$

avec pour   $\forall n\in [1,j-1]$ on a $w_n=x_n$ et  pour   $\forall n\in [j,t]$ on a $w_n=w_{n-1}+1$

et ici

-pour $c_j=1+\sum _{i=1}^{i=w-1}(-1)^{i+1}.\binom {w-1}{i}. \binom {a-i}{b-i}$ alors on obtiens $x_g=x_{g-1}+1$ selon $\forall g\in [j+1,t]$

-pour $c_j=\sum _{i=1}^{i=w}(-1)^{i+1}.\binom {w}{i}. \binom {a-i}{b-i}$ alors on obtiens   $x_{j+1}=u+j-t+1$ et $x_{j+g}=x_{j+g-1}+1$ selon $\forall g\in [2,t-j]$

_________________________________________

À présent qu'on a construit cette injection on recherche la valeur de $x\geq 2$ à partir de $f(x)=(x_1,...,x_h)$

cette opération est beaucoup plus simple que la précédente qui consistait à construire cette injection

-pour $h=1$   et $x_1=1$ on obtiens $x=2$

-pour $h=1$   et $x_1=2$ on obtiens $x=3$

-pour tous les autres cas on doit au préalable déterminer $g(x)$ afin d'obtenir

$x=1+g(x)+\sum _{i=1,j=1}^{i=x_h-1,j=i}\binom {i-1}{j-1}+\sum _{k=1}^{k=h-1}\binom {x_h-1}{k-1}$

-pour $h=1$ on obtiens   $g(x)=1$

-pour $h=2$ on obtiens     $g(x)=x_1$

-pour $h\geq 3$ on pose $t=h-1$ , $u=x_h-1$ , $x_0=0$

alors

$g(x)= 1+x_t-x_{t-1}-\begin {pmatrix} \binom {u}{t-1} \end {pmatrix} +\sum _{i=0,j=1}^{i=t-2,j=x_{i+1}-x_i-1} \binom {u-x_i-j}{t-i-1}  +   \begin {pmatrix} \binom {u-x_i}{t-i-1} \end {pmatrix}-\begin {pmatrix} \binom {u-x_{i+1}}{t-i-2} \end {pmatrix}$

Posté par re : injection légale 29-11-15 à 03:26

je corrige juste une petite erreur d'écriture (il n'y en a pas d'autre j'ai vérifié plusieurs fois mais celle là était tellement visible que je l'ai oublié dans mes corrigés)

convention de notation : $\begin {pmatrix} \binom {n}{p} \end {pmatrix}=\sum _{i=0}^{p} \binom {n}{i}$

Posté par re : injection légale 03-12-15 à 18:25

...c'est d'ailleurs une bijection

l'application $f: \mathbb {N}-\{0,1\} \rightarrow \mathcal {A}$ est une bijection

où $\mathcal {A}$ désigne l'ensemble de toutes les suites finies et strictement croissantes d'entiers naturels non nuls $(x_1,...,x_h)$

avec $h\in \mathbb {N}^*$ et $\forall i\in \mathbb {N}^*_h,x_i\in \mathbb {N}^*$ et $(x_i < x_j) \Leftrightarrow (i < j)$

comme ces derniers jours j'étais malade je n'ai pas eu le temps de m'occuper du topic associé à celui-ci et qui utilise (donc) cette bijection