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 15

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 204

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 148

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: 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

Ensembles Partie II - 2^(n-2) bijections de N^n vers N - Partie III - (n-1)! bijections de N^n vers N

Fonctions de couplage de Skolem

Les fonctions de couplages sont des bijections de $ \mathbb N^n $ vers $ \mathbb N $.
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 $.
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 $.
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 $.
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.


Calculs de $ \mathbb N^n $ vers $ \mathbb N $ ou inversement

1. – Indiquez la dimension $ n $ de l'espace $ \mathbb N^n $.
2. – 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.

$n =$

n-uplet $x = (x_1, x_2,\cdots,x_n) = $ $\in \mathbb N^n $         $ y = $ $\in \mathbb N $      

Décomposition en somme de $ y = P(x_1, x_2,\cdots,x_n) $ :


Polynômes de Skolem

Pour la même valeur de $ n $, l'application donne le polynôme de couplage de $ \mathbb N^n $ vers $ \mathbb N $.

  

Algorithmes

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.

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

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) $ vers $ P(x_1, x_2,\cdots)$, soit le calcul inverse .
Les termes de cette somme sont les éléments des cases du tableau dont le fond est colorié en orange, (lorsqu'ils ne sortent pas du cadre du tableau).

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

$ T_{i,j} $ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 $ 0 $ $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $ $ 6 $ $ 7 $ $ 8 $ $ 9 $ $ 10 $ $ 11 $ $ 12 $ $ 13 $ $ 14 $ $ 15 $ $ 16 $
2 $ 0 $ $ 1 $ $ 3 $ $ 6 $ $ 10 $ $ 15 $ $ 21 $ $ 28 $ $ 36 $ $ 45 $ $ 55 $ $ 66 $ $ 78 $ $ 91 $ $ 105 $ $ 120 $ $ 136 $
3 $ 0 $ $ 1 $ $ 4 $ $ 10 $ $ 20 $ $ 35 $ $ 56 $ $ 84 $ $ 120 $ $ 165 $ $ 220 $ $ 286 $ $ 364 $ $ 455 $ $ 560 $ $ 680 $ $ 816 $
4 $ 0 $ $ 1 $ $ 5 $ $ 15 $ $ 35 $ $ 70 $ $ 126 $ $ 210 $ $ 330 $ $ 495 $ $ 715 $ $ 1001 $ $ 1365 $ $ 1820 $ $ 2380 $ $ 3060 $ $ 3876 $
5 $ 0 $ $ 1 $ $ 6 $ $ 21 $ $ 56 $ $ 126 $ $ 252 $ $ 462 $ $ 792 $ $ 1287 $ $ 2002 $ $ 3003 $ $ 4368 $ $ 6188 $ $ 8568 $ $ 11628 $ $ 15504 $
6 $ 0 $ $ 1 $ $ 7 $ $ 28 $ $ 84 $ $ 210 $ $ 462 $ $ 924 $ $ 1716 $ $ 3003 $ $ 5005 $ $ 8008 $ $ 12376 $ $ 18564 $ $ 27132 $ $ 38760 $ $ 54264 $
7 $ 0 $ $ 1 $ $ 8 $ $ 36 $ $ 120 $ $ 330 $ $ 792 $ $ 1716 $ $ 3432 $ $ 6435 $ $ 11440 $ $ 19448 $ $ 31824 $ $ 50388 $ $ 77520 $ $ 116280 $ $ 170544 $
8 $ 0 $ $ 1 $ $ 9 $ $ 45 $ $ 165 $ $ 495 $ $ 1287 $ $ 3003 $ $ 6435 $ $ 12870 $ $ 24310 $ $ 43758 $ $ 75582 $ $ 125970 $ $ 203490 $ $ 319770 $ $ 490314 $


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