suites de -1 et de 1

[invite9f74ae56]

Bonjour,
je cherche a créer un programme maple permettant, pour un entier n donné, de me sortir toutes les listes à n éléments de -1 et de 1 tels que leur somme fasse zero.
par ex, pour n=4, on obtiendrait [1,1,-1,-1],[1,-1,1,-1],[1,-1,-1,1], et les trois autres listes "de signe contraire".
Il y a binomial(n,n/2) listes pour un n fixé (il suffit de choisir la position des 1 pour avoir celles des -1), et bien sur, n doit etre pair
Mais je n arrive pas a trouver de piste pour ce programme
Merci d avance pour toute aide, ou toute référence bibliographique
-----

[invite91417959]

Voila une idée:
La suite est de longueur 2n
on commence par la suite:
[1,1,1,1,....,1,-1....-1]
On déplace le n ieme un 1 coup à droite jusqu'à ce ne soit plus possible
On déplace alors le n-1 un 1 case à droite et on ramène le n ieme à la case juste à sa droite et on se remet à déplacer le n ième un

quand on cherche à déplacer le j ieme un
soit il est en position n+j et on ne peut pas le déplacer et alors on essaye de deplacer le j-1 ieme
soit on peut et alors on le fait et on met tous les autre 1 à la suite.

une illustration de la methode pour 2n=6:

[1,1,1,-1,-1,-1]
[1,1,-1,1,-1,-1]
[1,1,-1,-1,1,-1]
[1,1,-1,-1,-1,1] on ne peut plus déplacer le 3ieme un:
[1,-1,1,1,-1,-1] puis on se remet à déplacer le 3ieme
[1,-1,1,-1,1,-1]
[1,-1,1,-1,-1,1]on avance le 2ieme
[1,-1,-1,1,1,-1]
[1,-1,-1,1,-1,1]on avance le 2ieme
[1,-1,-1,-1,1,1]on avance le premier car le 2ieme est en position 3+2=5
[-1,1,1,1,-1,-1]
etc
on voit que l'on ne produit jamais deux fois la même suite

Il devrait être possible aussi de programmer ca sous la forme d'une réccurence sur n

[invite9f74ae56]

Merci beaucoup, c est bien astucieux.
Je m intéresse aussi a une fonction que l on peut construire a partir de telles suites, c est une fonction affine par morceaux qui relie les points [i,somme(u[i],i=1..n)], c est pour etre plus clair la fonction qui represente la position d un bonhomme qui se deplace sur un axe, qui part de zero et qui va a droite au temps i si u[i]=1 et a gauche si u[i]=-1
quelqu un aurait il des references sur ce genre de fonctions, par exemple comment calculer rapidement son nombre de zéros?

[invitedf667161]

Salut, ton bonhomme suit presque une marche aléatoire dans Z.

Pour être plus précis, il suit toutes les marches aléatoires de Z qui partent de 0 et reviennent à 0 en un temps n fixé. Il y a beaucoup de résultats là dessus, peut-être que faire une recherche sur ces marches t'aidera. Warning cependant : probas inside.

[A voir en vidéo sur Futura]

[invite6b1e2c2e]

Warning cependant : probas inside.

Salut,

Là, je trouve que tu y vas fort. Tu veux lui faire peur ? Si tu prends une marche aléatoire centrée, il est assez clair que ça induit sur les ponts une loi uniforme. Une fois ça compris, les probas ne sont plus vraiment nécessaires, selon l'utilisation qu'on veut en faire (notamment ici, je n'ai pas l'impression que rajouter la formalisation probabiliste puisse aider à créér l'algorigthme : Si c'est le cas, je serais curieux de voir comment ? ).

__
rvz

[invite10a6d253]

Warning cependant : probas inside.

Just kidding.

[invitedf667161]

Salut,

Là, je trouve que tu y vas fort. Tu veux lui faire peur ? Si tu prends une marche aléatoire centrée, il est assez clair que ça induit sur les ponts une loi uniforme. Une fois ça compris, les probas ne sont plus vraiment nécessaires, selon l'utilisation qu'on veut en faire (notamment ici, je n'ai pas l'impression que rajouter la formalisation probabiliste puisse aider à créér l'algorigthme : Si c'est le cas, je serais curieux de voir comment ? ).

__
rvz

Non bien sur, je ne veux pas lui faire peur ! D'ailleurs ma remarque est déplacée ; il n'y a pas besoin de ça pour son problème of course !
Maintenant, utiliser les probas pour générer la suite de 1 et de -1 que l'auteur demande, cela semble difficile. Un truc barbare : on sait combien il y a de chemins possibles, donc on tire n fois une pièce, pleins pleins pleins de fois, on note tous les chemins qui sont revenus à 0, on les compte, et si on en a trouvé le nombre qu'il faut, c'est qu'on les a tous !
Des fois, ça peut-être plus rapide de faire ça que de se casser la tête à trouver un "vrai" algo

[invite10a6d253]

L'algo que tu proposes n'est-il pas de toute façon aussi compliqué que par exemple l'algo de unepierre ? (il faut calculer le nombre d 'éléments cherchés, générer aléatoirement les 1 et -1 et tester à chaque boucle si on a compté le bon nombre d'éléments)

[invitedf667161]

Je n'ai pas vraiment saisi l'algo de unepierre, mais il semble qu'il soit plus fiable que le mien. Avec le mien, on peut trés bien attendre trois plombes que le hasard soit en notre faveur.
Il me semble que celui de une pierre ne fais pas appel à l'aléatoire mais se contente de déplacer des -1.

[invite9f74ae56]

C est pas bete de faire plein de lancers de n pieces et garder que ceux qui marchent, on doit avoir binomial(n,n/2) elements, mais pour savoir si c est raisonnable, il faudrait calculer le temps moyen pour reussir a obtenir toutes les listes désirées, je pense que c est possible mathématiquement (avec des theoremes style theoreme d arret de Doob) mais ca doit pas etre simple...

[invite6acfe16b]

Bonjour,

Je vous propose le petit algorithme récursif suivant qui énumère les suites de longeur n contenant d (1) et n-d (-1).

Enumeration(n,d) {
Si n>0 {
Si d>0 {
Afficher le résultat de Enumeration(n-1,d-1) en ajoutant un (1) à la fin de chacune des suites.

Si n>d {
Afficher le résultat de Enumeration(n-1,d) en ajoutant un (-1) à la fin de chacune des suites.
} sinon {
Affiune suite contenant n (1).
}
} sinon {
afficher une suite contenant n (-1).
}
}
}

J'espère que cela marche, je ne l'ai pas encore testé.

[invite9f74ae56]

Bonjour,
je m'intéresse toujours a ces suites de -1 et de 1, et j'ai l'impression d 'avoir démontré une formule de combinatoire connue, sum((binomial(n,k)**2,k=0..n)= binomial(2n,n) assez simplement avec ces suites. Alors j'aurai aimé savoir i cette démo est correcte, si elle est connue et si vous connaissiez des démos de ce genre en combinatoire.
Il y a binomial(2n,n) suites de -1 et de 1 de cardinal 2n dont la somme fait zéro, et donc pour démontrer la formule, je classe ces suites en n+1 familles: la famille des suites qui ont k (1) dans leurs n premiers éléments et k (-1) dans leur n derniers, pour k variant de 0 a n, cette famille contient exactement binomial(n,k)**2 éléments car il faut choisir la position des k (1) et des k (-1), et on voit que toute suite appartient a une de ces familles
Merci pour votre verification et vos reférences,
bonne soirée