Warning: Declaration of action_plugin_captcha::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in /homepages/3/d170528928/htdocs/dokuwiki/lib/plugins/captcha/action.php on line 20

Warning: Declaration of action_plugin_translation::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in /homepages/3/d170528928/htdocs/dokuwiki/lib/plugins/translation/action.php on line 36

Warning: Declaration of action_plugin_wrap::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in /homepages/3/d170528928/htdocs/dokuwiki/lib/plugins/wrap/action.php on line 22

Warning: Cannot modify header information - headers already sent by (output started at /homepages/3/d170528928/htdocs/dokuwiki/lib/plugins/captcha/action.php:15) in /homepages/3/d170528928/htdocs/dokuwiki/inc/auth.php on line 384

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/3/d170528928/htdocs/dokuwiki/inc/auth.php on line 670

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/3/d170528928/htdocs/dokuwiki/inc/auth.php on line 670

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/3/d170528928/htdocs/dokuwiki/inc/auth.php on line 670

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /homepages/3/d170528928/htdocs/dokuwiki/inc/parser/handler.php on line 1378

Warning: preg_match(): Compilation failed: invalid range in character class at offset 3526 in /homepages/3/d170528928/htdocs/dokuwiki/inc/parser/lexer.php on line 115
A PCRE internal error occured. This might be caused by a faulty plugin

Warning: Cannot modify header information - headers already sent by (output started at /homepages/3/d170528928/htdocs/dokuwiki/lib/plugins/captcha/action.php:15) in /homepages/3/d170528928/htdocs/dokuwiki/inc/actions.php on line 203
pg3002:bijection_de_n_n_vers_n - Wiki Jeux et Mathématiques
Wiki Jeux et Mathématiques

[[pg3001:Ensembles]] [[pg3003:bijection_de_n_n_vers_n|Partie II - 2^(n-2) bijections de N^n vers N]] - [[pg3004:bijection_de_n_n_vers_n|Partie III - (n-1)! bijections de N^n vers N]] ====== Fonctions de couplage de Skolem ====== <html> <style type="text/css"> input.tt0, input.tt1 { height:24; font-size:14px;font-weight:bolder;BORDER:2px solid #7F9DB9; PADDING: 1px 2px } input.tt0, tt0 { width:30;color:#3f00ff;} input.tt1 { width:180;color:#3f00ff;} </style> <script src="http://linenn.davalan.eu/data/js/mathtex4.js" type="text/javascript"> </script> Les fonctions de couplages sont des bijections de $ \mathbb N^n $ vers $ \mathbb N $. <br> Les fonctions présentées dans cette page sont des polynômes de degré $ n $ en $ x = (x_1, x_2, \cdots , x_n) $, c'est-à-dire en $ n $ variables $x_1, x_2,\cdots, x_n $. Lorsque $ n = 2 $, on retrouve le polynôme de Cantor qui est une bijection de $ \mathbb N^2 $ vers $ \mathbb N $, dans le cas particulier $ n=2 $. <br /> Toute permutation $ \sigma $ des variables $ x_1, x_2, \cdots , x_n $ permet d'obtenir une nouvelle fonction de couplage $ P $ $ \circ $ $ \sigma $, si $ P $ est un polynôme de degré $ n $, alors $ P $ $ \circ $ $ \sigma $ est aussi un polynôme de degré $ n $. <br> La première image représente la fonction de Cantor, l'image dans $ \mathbb N $ est indiquée en face du point de coordonnées $ (x_1, x_2) $ de $ \mathbb N^2 $. </html> {{ :pg3002:sko1em2.jpg?300 |}} <html> <br clear=all> La deuxième image représente la fonction de Skolem de $ \mathbb N^3 $ vers $ \mathbb N $, seules quelques valeurs sont indiquées sur le schéma de gauche. </html> {{ :pg3002:skolem3b.jpg?750 |}} <html> <br clear=all> </html> <html> <script type="text/javascript"> var p=[]; var maxi=8, maxj=16 function colortab(liste) { for(var i=1; i<=maxi; i++) for(var j=0; j<= maxj; j++) document.getElementById("t_"+i+"_"+j).style.backgroundColor="#fff" //alert(liste) for(var i in liste) { if(document.getElementById(liste[i])!=null) document.getElementById(liste[i]).style.backgroundColor="#fb0" } } function pinit() { var l=10, k=10 for(var i=-1; i<=l; i++) p[i]=[] for(var i=0; i<=k;i++) { p[-1][i]=0 p[0][i]=1; } for(var i=1; i<=l; i++) { p[i][0]=0 p[i][1]=1 } for(var i=1; i<=l; i++) { for(var j=1; j<=k; j++) { p[i][j]= p[i][j-1]+ p[i-1][j] } } } pinit() /* y 0 0 0 0 0 0 x 0 1 1 1 1 1 0 1 2 (3) 4 5 p[2][3]=3 = C(3,2) 0 1 3 6 10 15 p[x][y]= C(x+y-2, y-1) 0 1 4 10 20 35 T(x,y) = p[x][y] = choose(x+y-2, y-1) = binomial(x+y-2, y-1) */ function T(x,y) { if(p[x]==null) { for(var i=1; i<=x; i++) { if(p[i]==null) { p[i]=[]; p[i][0]=0; p[i][1]=1; p[i][2]=i; } } } if(p[x][y]==null) { if(x==-1) p[x][y]=0 else if(x==0) p[x][y]=1 else if(x==1) p[x][y]=y else p[x][y]=T(x,y-1)+T(x-1,y); } return p[x][y]; } var liste = [] function cantor(m, n) { var tb=[], x=n, s1=" $\\displaystyle "+n+" = "; tb[0]=0 var liste = [] for(var i=m; i>0; i--) { var j=0; while (T(i,j+1)<= x) j++; tb[i]=j s1 = s1 + ((i!=m)?"+":"")+T(i,j) x=x-T(i,j) liste[i-1] = "t_"+i+"_"+j } var s="" for(var j=1; j<=m; j++) { s = s +(tb[j]-tb[j-1])+" " } document.getElementById("Somme").innerHTML=s1+" $ " replaceMath( document.body ) colortab(liste) return s } function inversecantor(m, s) { var u = s.replace(/^\s+/,""), s1=""; u = u.replace(/\s+$/,""); var l = u.split(/\s+/g); var c= 1*l[0], v=p[1][c]; s1 = s1 + v var liste = [] liste[0] = "t_"+1+"_"+c; for(var i=2; i<=m; i++) { c += 1*l[i-1] v += 1*p[i][c] s1 = s1 + "+" + p[i][c] liste[i-1] = "t_"+i+"_"+c //print(c+" "+v) } s1 = "$\\displaymath "+v+"="+s1+" $ " document.getElementById("Somme").innerHTML=s1 replaceMath( document.body ) colortab(liste) return v } function litn() { var n = parseInt(document.frm1.n.value) if(n<1) n=2 document.frm1.n.value=n; return n; } function f1ton() { var n = litn() var x = parseInt(document.frm1.x.value) if(x<0) x=0 document.frm1.x.value = x var l = cantor(n, x) document.frm1.l.value = l; } function fnto1() { var n = litn() var l = document.frm1.l.value var x = inversecantor(n, l) document.frm1.x.value = x; } // retourne x1+x2+x3+...xk function sumv(k) { var x="x1" for(var i=2; i<=k; i++) x = x+"+x"+i return x } // retourne (x1+x2+x3+...xk+n-2)(x1+x2+x3+...xk+n-3)...(x1+x2+x3+...xk)/k! function elemt(k) { if(k==1) return "x1" var s="", s1, v=sumv(k), f=1 for(var i=1; i<=k; i++) { s1=((i>1)?"*":"")+"("+v if(k-i>0) s1=s1+"+"+(k-i) s1 = s1+")" s = s+s1 f *= i } if(f != 1) s = s+"/"+f return s } function polynomial(n) { var s="" for(var i=n; i>=1; i--) { s = s + ((i<n)?"+":"")+elemt(i) } return s } function polynome() { var n = litn() var x = polynomial(n) document.getElementById("IdPoly").innerHTML = x; } </script> </html> <html> <h3>Calculs de $ \mathbb N^n $ vers $ \mathbb N $ ou inversement</h3> 1. &ndash; Indiquez la dimension $ n $ de l'espace $ \mathbb N^n $. <br> 2. &ndash; Donnez le n-uplet $ x = (x_1, x_2,\cdots,x_n) $ et calculez son image $ y = P(x) $ ou inversement donnez $ y $ et retrouvez le n-uplet. <br><br> <form name="frm1" action="" > <span class="math" id="math0">$n =$</span> <input class="tt0" type="text" value="4" name="n" onKeyPress="if (event.keyCode == 13) cycles()" /> <br /><br /> n-uplet $x = (x_1, x_2,\cdots,x_n) = $ <input type="text" class="tt0" value=" 1 1 0 3" name="l" onKeyPress="if (event.keyCode == 13) cycles()" /> $\in \mathbb N^n $&nbsp;&nbsp; <input type="button" name="" onclick="fnto1()" value="-->" /> &nbsp;&nbsp; <input type="button" name="" onclick="f1ton()" value="<--" /> &nbsp;&nbsp; $ y = $ <input type="text" class="tt0" value="78" name="x" onKeyPress="if (event.keyCode == 13) cycles()" /> $\in \mathbb N $ &nbsp;&nbsp; &nbsp;&nbsp; <br /><br /> Décomposition en somme de $ y = P(x_1, x_2,\cdots,x_n) $ : <br /> <div id="Somme"></div> <br /><br /> <h3>Polynômes de Skolem</h3> Pour la même valeur de $ n $, l'application donne le polynôme de couplage de $ \mathbb N^n $ vers $ \mathbb N $. <br /> <br /> <input type="button" name="poly" onclick="polynome()" value="Polynome P(x1, x2, ...) " /> &nbsp;&nbsp; <br /> <br /> <div id="IdPoly"> </div> <h3>Algorithmes</h3> Plusieurs propriétés simples du triangle de Pascal du permettent d'obtenir les algorithmes élémentaires utilisés dans les applications qui précèdent, on obtient aussi l'expression du polynôme de Skolem. <br /> <br /> Le tableau $ T = [T_{i,j}] $ ci-dessous est une partie du triangle de Pascal, ses éléments sont $ T_{i,j} = $ $ \binom{i+j-1}{i} $. <br /> Ainsi l'image de $x = (x_1, x_2,\cdots,x_n) $ s'obtient en ajoutant les éléments du tableau $ T_{1,x_1}+T_{2,x_1+x_2}+T_{3,x_1+x_2+x_3}+\cdots $. <br /><br /> La décomposition en somme est indiquée par l'application ci-dessus après que vous ayez utilisé l'un des calculs ci-dessus, soit de $ x=(x_1, x_2,\cdots) $ <input type="button" name="" onclick="fnto1()" value="-->" /> vers $ P(x_1, x_2,\cdots)$, soit le calcul inverse <input type="button" name="" onclick="f1ton()" value="<--" />. <br> Les termes de cette somme sont les éléments des cases du tableau dont le fond est <span style="background-color:#fb0;">colorié en orange</span>, (lorsqu'ils ne sortent pas du cadre du tableau). <br> <br> Le polynôme est donc $\displaystyle P(x_1,x_2,\ldots,x_n) = $ $\displaystyle T_{1,x_1}+ T_{2,x_1+x_2}+\cdots + T_{n,x_1+x_2+\cdots+x_n} = $ $\displaystyle \binom {x_1} 1 + \binom {x_1 + x_2 + 1} 2 +\cdots +\binom {x_1 + x_2 +\cdots+ x_n + n-1} n $. <br> <br> <center> <table> <tr> <th>$ T_{i,j} $</th> <th> 0 </th> <th> 1 </th> <th> 2 </th> <th> 3 </th> <th> 4 </th> <th> 5 </th> <th> 6 </th> <th> 7 </th> <th> 8 </th> <th> 9 </th> <th> 10 </th> <th> 11 </th> <th> 12 </th> <th> 13 </th> <th> 14 </th> <th> 15 </th> <th> 16 </th></tr> <tr><th> 1 </th> <td id="t_1_0" > $ 0 $</td> <td id="t_1_1" > $ 1 $</td> <td id="t_1_2" > $ 2 $</td> <td id="t_1_3" > $ 3 $</td> <td id="t_1_4" > $ 4 $</td> <td id="t_1_5" > $ 5 $</td> <td id="t_1_6" > $ 6 $</td> <td id="t_1_7" > $ 7 $</td> <td id="t_1_8" > $ 8 $</td> <td id="t_1_9" > $ 9 $</td> <td id="t_1_10" > $ 10 $</td> <td id="t_1_11" > $ 11 $</td> <td id="t_1_12" > $ 12 $</td> <td id="t_1_13" > $ 13 $</td> <td id="t_1_14" > $ 14 $</td> <td id="t_1_15" > $ 15 $</td> <td id="t_1_16" > $ 16 $</td></tr> <tr><th> 2 </th> <td id="t_2_0" > $ 0 $</td> <td id="t_2_1" > $ 1 $</td> <td id="t_2_2" > $ 3 $</td> <td id="t_2_3" > $ 6 $</td> <td id="t_2_4" > $ 10 $</td> <td id="t_2_5" > $ 15 $</td> <td id="t_2_6" > $ 21 $</td> <td id="t_2_7" > $ 28 $</td> <td id="t_2_8" > $ 36 $</td> <td id="t_2_9" > $ 45 $</td> <td id="t_2_10" > $ 55 $</td> <td id="t_2_11" > $ 66 $</td> <td id="t_2_12" > $ 78 $</td> <td id="t_2_13" > $ 91 $</td> <td id="t_2_14" > $ 105 $</td> <td id="t_2_15" > $ 120 $</td> <td id="t_2_16" > $ 136 $</td></tr> <tr><th> 3 </th> <td id="t_3_0" > $ 0 $</td> <td id="t_3_1" > $ 1 $</td> <td id="t_3_2" > $ 4 $</td> <td id="t_3_3" > $ 10 $</td> <td id="t_3_4" > $ 20 $</td> <td id="t_3_5" > $ 35 $</td> <td id="t_3_6" > $ 56 $</td> <td id="t_3_7" > $ 84 $</td> <td id="t_3_8" > $ 120 $</td> <td id="t_3_9" > $ 165 $</td> <td id="t_3_10" > $ 220 $</td> <td id="t_3_11" > $ 286 $</td> <td id="t_3_12" > $ 364 $</td> <td id="t_3_13" > $ 455 $</td> <td id="t_3_14" > $ 560 $</td> <td id="t_3_15" > $ 680 $</td> <td id="t_3_16" > $ 816 $</td></tr> <tr><th> 4 </th> <td id="t_4_0" > $ 0 $</td> <td id="t_4_1" > $ 1 $</td> <td id="t_4_2" > $ 5 $</td> <td id="t_4_3" > $ 15 $</td> <td id="t_4_4" > $ 35 $</td> <td id="t_4_5" > $ 70 $</td> <td id="t_4_6" > $ 126 $</td> <td id="t_4_7" > $ 210 $</td> <td id="t_4_8" > $ 330 $</td> <td id="t_4_9" > $ 495 $</td> <td id="t_4_10" > $ 715 $</td> <td id="t_4_11" > $ 1001 $</td> <td id="t_4_12" > $ 1365 $</td> <td id="t_4_13" > $ 1820 $</td> <td id="t_4_14" > $ 2380 $</td> <td id="t_4_15" > $ 3060 $</td> <td id="t_4_16" > $ 3876 $</td></tr> <tr><th> 5 </th> <td id="t_5_0" > $ 0 $</td> <td id="t_5_1" > $ 1 $</td> <td id="t_5_2" > $ 6 $</td> <td id="t_5_3" > $ 21 $</td> <td id="t_5_4" > $ 56 $</td> <td id="t_5_5" > $ 126 $</td> <td id="t_5_6" > $ 252 $</td> <td id="t_5_7" > $ 462 $</td> <td id="t_5_8" > $ 792 $</td> <td id="t_5_9" > $ 1287 $</td> <td id="t_5_10" > $ 2002 $</td> <td id="t_5_11" > $ 3003 $</td> <td id="t_5_12" > $ 4368 $</td> <td id="t_5_13" > $ 6188 $</td> <td id="t_5_14" > $ 8568 $</td> <td id="t_5_15" > $ 11628 $</td> <td id="t_5_16" > $ 15504 $</td></tr> <tr><th> 6 </th> <td id="t_6_0" > $ 0 $</td> <td id="t_6_1" > $ 1 $</td> <td id="t_6_2" > $ 7 $</td> <td id="t_6_3" > $ 28 $</td> <td id="t_6_4" > $ 84 $</td> <td id="t_6_5" > $ 210 $</td> <td id="t_6_6" > $ 462 $</td> <td id="t_6_7" > $ 924 $</td> <td id="t_6_8" > $ 1716 $</td> <td id="t_6_9" > $ 3003 $</td> <td id="t_6_10" > $ 5005 $</td> <td id="t_6_11" > $ 8008 $</td> <td id="t_6_12" > $ 12376 $</td> <td id="t_6_13" > $ 18564 $</td> <td id="t_6_14" > $ 27132 $</td> <td id="t_6_15" > $ 38760 $</td> <td id="t_6_16" > $ 54264 $</td></tr> <tr><th> 7 </th> <td id="t_7_0" > $ 0 $</td> <td id="t_7_1" > $ 1 $</td> <td id="t_7_2" > $ 8 $</td> <td id="t_7_3" > $ 36 $</td> <td id="t_7_4" > $ 120 $</td> <td id="t_7_5" > $ 330 $</td> <td id="t_7_6" > $ 792 $</td> <td id="t_7_7" > $ 1716 $</td> <td id="t_7_8" > $ 3432 $</td> <td id="t_7_9" > $ 6435 $</td> <td id="t_7_10" > $ 11440 $</td> <td id="t_7_11" > $ 19448 $</td> <td id="t_7_12" > $ 31824 $</td> <td id="t_7_13" > $ 50388 $</td> <td id="t_7_14" > $ 77520 $</td> <td id="t_7_15" > $ 116280 $</td> <td id="t_7_16" > $ 170544 $</td></tr> <tr><th> 8 </th> <td id="t_8_0" > $ 0 $</td> <td id="t_8_1" > $ 1 $</td> <td id="t_8_2" > $ 9 $</td> <td id="t_8_3" > $ 45 $</td> <td id="t_8_4" > $ 165 $</td> <td id="t_8_5" > $ 495 $</td> <td id="t_8_6" > $ 1287 $</td> <td id="t_8_7" > $ 3003 $</td> <td id="t_8_8" > $ 6435 $</td> <td id="t_8_9" > $ 12870 $</td> <td id="t_8_10" > $ 24310 $</td> <td id="t_8_11" > $ 43758 $</td> <td id="t_8_12" > $ 75582 $</td> <td id="t_8_13" > $ 125970 $</td> <td id="t_8_14" > $ 203490 $</td> <td id="t_8_15" > $ 319770 $</td> <td id="t_8_16" > $ 490314 $</td></tr> </table> </center> </form> <br /> </html> <html> <script type="text/javascript"> //window.mathPreamble = '\newcommand{\RR}{\mathbb{R}}\usepackage[usenames]{color}\color{} \gammacorrection{1.3}\png \normal '; replaceMath( document.body ); </script> </html>


Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/3/d170528928/htdocs/dokuwiki/inc/auth.php on line 670
Please fill or disable this placeholder (:wiki:navigation_sidebar) ]
QR Code: URL of current page
Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : GNU Free Documentation License 1.3