Des idées pour en finir avec ce petit parasite?

bridgslam · 22-02-2022 17:19:56

Bonjour,

Pour terminer un dénombrement relativement pénible ( nombre de circuits fermés de longueur totale paire égale à 2n depuis un point origine de départ O d'une chenille sur un quadrillage infini de maille de côté 1, où la chenille peut faire absolument ce quelle veut (hélas) , repasser par des noeuds ou des fils déjà empruntés..., bref la liberté :-) totale, seule contrainte la longueur fixée et le retour en 0 à la fin).

J'aurai besoin de montrer l'égalité suivante ( qui concorde après quelques essais numériques de mon cru ) pour clore cette petite énigme:

$\binom{2n}{n}^2 = \sum_\limits{ \alpha = 0}^{\alpha = n} \binom{2n}{\alpha} \binom{2n-\alpha}{\alpha} \binom{2\beta}{\beta}$

avec $ \beta$ tel que $ \alpha + \beta = n$.

Merci d'avance aux courageux

A.

Dernière modification par yoshi (22-02-2022 17:59:33)

Michel Coste · 22-02-2022 18:21:15

Bonsoir,

C'est bizarre, pour ton décompte de circuits je verrais plutôt [tex]\large \sum_{\alpha+\beta=n} \binom{2n}{2\alpha}\binom{2\alpha}{\alpha}\binom{2\beta}{\beta}[/tex]. Ça revient au même, mais c'est plus symétrique alors je préfère.

Et j'ajoute que c'est assez facile de voir combinatoirement que cette somme fait bien [tex]\large\binom{2n}{n}^2[/tex].

Dernière modification par Michel Coste (22-02-2022 21:15:14)

bridgslam · 22-02-2022 23:04:50

Bonsoir,

En fait, j'avoue ne pas avoir trop regardé le côté algébrique après avoir sur sué un bon moment pour trouver la réponse elle-même, la question était posée sur le site de Christophe Bertault.
Du coup je pense que c'est sans doute faisable sans pb.
Je pensais aussi prendre la maille triangulaire pour changer un peu aussi la question et poser des soucis d'équilibre à Becky la chenille.

Merci d'avoir regardé et amélioré l'esthétique de l'expression...
A.

Michel Coste · 23-02-2022 07:31:09

Il n'y a en fait rien d'algébrique.

Le dénombrement exprimé par la somme, que ce soit sous la forme où tu l'as écrite ou sous la forme où je l'ai écrite, c'est le compte du nombre de façon de diviser [tex]E=\{1,\ldots,2n\}[/tex] en quatre parties [tex]G,D,H,B[/tex] (pour gauche, droit, haut, bas bien sûr) avec autant de [tex]G[/tex] que de [tex]D[/tex] et autant de [tex]H[/tex] que de [tex]B[/tex].
Par ailleurs [tex]\large\binom{2n}{n}^2[/tex] est le nombre de couples [tex](X,Y)[/tex] de parties à [tex]n[/tex] éléments de [tex]E[/tex].
Il y a une façon très simple de mettre en bijection l'ensemble des [tex](G,D,H,B)[/tex] et l'ensemble des [tex](X,Y)[/tex], prouvant ainsi l'égalité. Vois-tu, Alain ?

bridgslam · 23-02-2022 07:55:02

Bonjour,

Effectivement on n'en sort pas de ces dénombrements :-).

(G,D,H,B) --> (G U H , D U B) ?

Sinon je pense que pour dénombrer des circuits où la chenille ne peut pas repasser par des côtés déjà utilisés, ça doit être moins évident.
On sait faire normalement pour des chemins croissants dans un quadrillage pour aller d'un point A à un point B, voire sous la diagonale, avec
notamment les nombres de Catalan
On m'avait donné dans une bibliothèque des bouquins vétustes d'arithmétique qui allaient partir à la broyeuse ( dont E. Lucas je crois) je replongerai plus avant dans tout cela une fois en retraite.

A.

Dernière modification par bridgslam (23-02-2022 08:38:24)

Michel Coste · 23-02-2022 09:00:29

Oh, on s'en sort assez bien tout de même.

Ce que tu proposes ne va visiblement pas marcher puisque [tex]G\cup H[/tex] et [tex]D\cup B[/tex] sont complémentaires.
Par contre, que penses-tu de [tex](G,D,H,B)\mapsto (G\cup H, G\cup B)[/tex] ? Peux-tu expliciter la bijection réciproque ?

bridgslam · 23-02-2022 09:33:52

Oui j'étais justement en train de penser à "croiser" parce-que cela ne marchait pas... puisque on peut faire varier à loisir chaque partie pour compléter avec le reste ( et obtenir X ou Y)

Excuses...
A.

bridgslam · 23-02-2022 09:45:29

Re-bjr,

$(X,Y) -->( X \cap Y, ( X\cup Y)^c , ( X\backslash Y), Y \backslash X) )$ sauf erreur
A.

Dernière modification par bridgslam (23-02-2022 10:35:22)

Michel Coste · 23-02-2022 10:23:41

Désolé, mais j'ai énormément de mal à comprendre ce que tu écris. Il faut m'expliquer très clairement et très précisément pour que je comprenne ; sinon, c'est trop flou pour moi.

bridgslam · 23-02-2022 10:30:33

J'étais en train de le taper clairement (désolé).

Bon sujet en tout cas du début à la fin. Je pense qu'une preuve de l'égalité doit se faire aussi à partir du développement du binôme de Newton, en le calculant de deux façons.

Merci Michel

Alain

Dernière modification par bridgslam (23-02-2022 10:38:25)

Michel Coste · 23-02-2022 10:40:38

Là, je comprends. C'est bien ça.

bridgslam · 23-02-2022 10:47:44

En fait j'avais pas mal pataugé à l'exercice initial car je partais sur des vrais chemins ( sans repasser, comme en principe dans la vie courante, sauf si on est arrivé dans un "toul car" avec sa bagnole ...) , à la fin j'ai eu un doute, et ça a été relativement simple.
J'aurais du terminer pour mieux faire en me posant correctement la question sur l'égalité finale ( dont l'expression est heureusement donnée dans l'exercice de C. Bertault )

Merci en tous cas pour ces échanges fructueux

Alain

Michel Coste · 23-02-2022 11:04:03

On aurait pu arriver directement au résultat en constatant que parmi les 2n pas il y en a n qui augmentent x+y (x et y les deux coordonnées sur la grille) et n qui augmentent x-y, et que la connaissance de ces deux parties à n éléments détermine entièrement le circuit.

Les circuits sur grille à maille triangulaire donnent un problème autrement plus difficile.

bridgslam · 23-02-2022 11:09:22

super,

merci!
A.

Michel Coste · 23-02-2022 14:08:03

Une autre question dans le prolongement : quel est le nombre de circuits de longueur [tex]2n[/tex] revenant à 0 dans un réseau cubique ?

Bernard-maths · 23-02-2022 17:34:22

Bonjour à tous deux !

Je vois que vous vous amusez beaucoup, et moi je regarde de loin ...

Michel, quand tu parle de réseau cubique ... s'agit-il bien d'un cube 3D ?

Alors on pourrait aussi rester en surface du cube ... dans ce cas ne pourrait-on pas projeter sur les faces un chemin interne ?

Juste pour un peu de sel ...

B-m

Michel Coste · 23-02-2022 18:10:43

Quand je parle d'un réseau cubique, ça veut dire qu'on se déplace dans [tex]\mathbb Z^2[/tex] et on change une et une seule coordonnée de [tex]\pm1[/tex] à chaque pas.
Comme le quadrillage plan, mais en 3d.
Je ne comprends pas ça :

Alors on pourrait aussi rester en surface du cube ... dans ce cas ne pourrait-on pas projeter sur les faces un chemin interne ?

Bernard-maths · 23-02-2022 18:19:19

Ok !

Moi je voyais ça dans l'espace 3D, en ne considérant que les points de coordonnées entières pour un cube de côté entier n par ex, ou n/2, n/3 ... selon les contraintes sur la longueur du parcours ...

Soit dans le volume, soit en restant en surface du cube ... Il faut fixer le début O !

Mais ce ne sont que des variantes possibles au problème de départ !

B-m

Dernière modification par Bernard-maths (23-02-2022 18:21:45)

Michel Coste · 23-02-2022 18:51:27

Moi je voyais ça dans l'espace 3D, en ne considérant que les points de coordonnées entières

Autrement dit dans [tex]\mathbb Z^3[/tex], comme je l'ai écrit. ;)

Bernard-maths · 23-02-2022 19:17:33

J'ai hésité, mais comme j'ai vu Z², j'ai poussé mes précisions ... no problem !

Michel Coste · 23-02-2022 19:23:05

Oui, tu as raison, j'ai écrit [tex]\mathbb Z^2[/tex] alors que je voulais écrire [tex]\mathbb Z^3[/tex].
Il vaut mieux que je zoome, sinon j'ai du mal à lire les exposants.

Dernière modification par Michel Coste (23-02-2022 19:24:44)

bridgslam · 24-02-2022 08:39:02

Bonjour,

Oui c'est faisable aussi avec une maille cubique. C'est la même idée, il faut faire jouer cette fois $\alpha$, $\beta$, $\gamma$
(pour rajouter la profondeur) avec leur somme égale à n (pour un trajet de longueur 2n).
Sauf erreur on obtient une expression en somme indicée analogue au grillage plan.
Je n'ai pas regardé plus, mais l'expression doit sans doute se simplifier aussi.

Par-contre avec un maillage plan en forme de triangles équilatéraux, c'est effectivement très difficile (puisqu'on peut parfois court-circuiter en diagonale, mais pas toujours selon les arêtes successives empruntées...).
En empruntant seulement deux directions parmi trois dans tous les trajets, je pense ( en faisant pivoter légèrement le système de coordonnées pour être // aux mouvements élémentaires à deux directions) , que le nombre de trajets sera au moins égal à 3 fois celui qu'on a dénombré précédemment.
Je dis ça à la louche.

A.

bridgslam · 24-02-2022 08:50:35

Et encore, c'est pas sûr il y a des trajets communs à différents types de trajets ( par exemple ceux en ligne avec aller et retour) , qu'on va alors compter... deux fois,
... effectivement pas simple du tout.

Une démarche possible (?) pour minorer le nombre de chemins sur mailles triangulaires (de côtés égaux):

- compter à part les trajets en lignes ( dans une des 3 directions possibles)
- pour les autres , par catégories de deux directions réellement utilisées , on se ramène donc à des trajets carrés , déjà évalués mais auxquels il faut retrancher les "en-ligne"...

Compliqué.

A.

Dernière modification par bridgslam (24-02-2022 09:11:14)

bridgslam · 24-02-2022 09:59:31

Bonjour,

Avec ce procédé, avec un calcul rapide ( que j'espère juste) , pour un maillage plan équi-triangulaire on a au moins $3\binom{2n}{n}\{ \binom{2n}{n} -1\}$ trajets linéaires ou à deux directions, auxquels il faudrait encore rajouter les trajets utilisant toutes les 3 directions ( et pas seulement 2).

Je ne sais pas si des techniques plus élaborées ( théorèmes à l'appui ) existent dans ce genre de questions ni si la théorie des graphes peut venir à la rescousse... en tous cas ce ne doit pas être de la tarte.

A.

Michel Coste · 24-02-2022 10:04:34

Bonjour,

Pour le réseau cubique dans l'espace, le nombre de circuits de longueur 2n se calcule assez facilement et on trouve la suite 1, 6, 90, 1860, 44730, 1172556, 32496156, 936369720 ... qui figure dans OEIS : A002896. Il semble bien par contre qu'il n'y a pas de jolie formule close du genre [tex]\binom{2n}{n}^2[/tex].

Pour le réseau triangulaire plan, on peut le voir comme projection du réseau cubique dans l'espace pour faire le comptage.

Forum de mathématiques - Bibm@th.net

#1 22-02-2022 17:19:56

Des idées pour en finir avec ce petit parasite?

#2 22-02-2022 18:21:15

Re : Des idées pour en finir avec ce petit parasite?

#3 22-02-2022 23:04:50

Re : Des idées pour en finir avec ce petit parasite?

#4 23-02-2022 07:31:09

Re : Des idées pour en finir avec ce petit parasite?

#5 23-02-2022 07:55:02

Re : Des idées pour en finir avec ce petit parasite?

#6 23-02-2022 09:00:29

Re : Des idées pour en finir avec ce petit parasite?

#7 23-02-2022 09:33:52

Re : Des idées pour en finir avec ce petit parasite?

#8 23-02-2022 09:45:29

Re : Des idées pour en finir avec ce petit parasite?

#9 23-02-2022 10:23:41

Re : Des idées pour en finir avec ce petit parasite?

#10 23-02-2022 10:30:33

Re : Des idées pour en finir avec ce petit parasite?

#11 23-02-2022 10:40:38

Re : Des idées pour en finir avec ce petit parasite?

#12 23-02-2022 10:47:44

Re : Des idées pour en finir avec ce petit parasite?

#13 23-02-2022 11:04:03

Re : Des idées pour en finir avec ce petit parasite?

#14 23-02-2022 11:09:22

Re : Des idées pour en finir avec ce petit parasite?

#15 23-02-2022 14:08:03

Re : Des idées pour en finir avec ce petit parasite?

#16 23-02-2022 17:34:22

Re : Des idées pour en finir avec ce petit parasite?

#17 23-02-2022 18:10:43

Re : Des idées pour en finir avec ce petit parasite?

#18 23-02-2022 18:19:19

Re : Des idées pour en finir avec ce petit parasite?

#19 23-02-2022 18:51:27

Re : Des idées pour en finir avec ce petit parasite?

#20 23-02-2022 19:17:33

Re : Des idées pour en finir avec ce petit parasite?

#21 23-02-2022 19:23:05

Re : Des idées pour en finir avec ce petit parasite?

#22 24-02-2022 08:39:02

Re : Des idées pour en finir avec ce petit parasite?

#23 24-02-2022 08:50:35

Re : Des idées pour en finir avec ce petit parasite?

#24 24-02-2022 09:59:31

Re : Des idées pour en finir avec ce petit parasite?

#25 24-02-2022 10:04:34

Re : Des idées pour en finir avec ce petit parasite?

Réponse rapide

Pied de page des forums