Répondre à la discussion
Affichage des résultats 1 à 12 sur 12

suites de -1 et de 1



  1. #1
    blouseman

    suites de -1 et de 1


    ------

    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

    -----

  2. Publicité
  3. #2
    unepierre

    Re : suites de -1 et de 1

    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

  4. #3
    blouseman

    Re : suites de -1 et de 1

    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?

  5. #4
    GuYem

    Re : suites de -1 et de 1

    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.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  6. A voir en vidéo sur Futura
  7. #5
    rvz

    Re : suites de -1 et de 1

    Citation Envoyé par GuYem Voir le message
    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

  8. #6
    edpiste

    Re : suites de -1 et de 1

    Citation Envoyé par GuYem Voir le message
    Warning cependant : probas inside.

    Just kidding.

  9. Publicité
  10. #7
    GuYem

    Re : suites de -1 et de 1

    Citation Envoyé par rvz Voir le message
    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
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  11. #8
    edpiste

    Re : suites de -1 et de 1

    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)

  12. #9
    GuYem

    Re : suites de -1 et de 1

    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.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  13. #10
    blouseman

    Re : suites de -1 et de 1

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

  14. #11
    Sylvestre

    Re : suites de -1 et de 1

    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é.
    Programming is understanding

  15. #12
    blouseman

    Re : suites de -1 et de 1

    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

  16. Publicité

Discussions similaires

  1. suites
    Par prune-elle dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 11/09/2007, 23h43
  2. T°S suites
    Par alis dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 09/09/2007, 11h01
  3. suites
    Par sensor dans le forum Mathématiques du supérieur
    Réponses: 15
    Dernier message: 11/11/2006, 19h54
  4. Encore des Suites, toujours des suites...
    Par Famous-BiBi dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 26/09/2006, 17h50
  5. Pb suites...
    Par Mafia dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 20/01/2006, 20h07