Montées d'une permutation - Page 2 — Les-mathematiques.net The most powerful custom community solution in the world

Montées d'une permutation

2»

Réponses

  • La 4a est évidente
  • C'est le nombre de partitions en 2 parties d'un ensemble de $n$ éléments mais je ne vois pas combien ça vaut.
  • Je le répète, c'est évident.

    Tu as qu'à essayer pour des petites valeurs de n...
  • C'est loin d'être évident pour moi, je suis toujours à réfléchir dessus 2 heures après.

    Pour $n=4$, je trouve :
    $(\{1 \}, \{2,3,4 \})$
    $(\{2 \}, \{1,3,4 \})$
    $(\{3 \}, \{1,2,4 \})$
    $(\{4 \}, \{1,2,3 \})$
    $(\{1,2 \}, \{3,4 \})$
    $(\{1,3 \}, \{2,4 \})$
    $(\{1,4\}, \{2,3 \})$

    Je ne vois pas en quoi ça m'aide pour le cas général.
  • T'en as oublié la moitié...
  • Je n'ai pas mis toutes les parties, juste les couples de parties non vides.

    Si j'ajoute $( \{1 \} , \{2 \} , \{3 \} , \{4 \})$ ce n'est pas un couple de parties bien que ce soit une partition de $[|1,4|]$.
  • ... bon tant pis
  • Le nombre de partition de $[|1,n|]$ en $2$ parties est obtenu en choisissant 2 sous-ensembles disjoints de $[|1,n|]$. Or il y en a $2^n$ donc le nombre de partition est $\binom{2^n}{2}$
  • Encore mieux! :)o
  • Bon allez jte donne la solution parce que bon tu vas pas passer 3 jours dessus
    Soit A une partie de I = 1,n

    Alors B = I \ A et donc l'ensemble des A,B qui conviennent sont les A, I\A pour A écrivant P(I) et card(A)>0, card(I\A)>0. On exclut donc I et l'ensemble vide pour A

    Le cardinal est donc 2^n - 2


    Ps : la 4b est un ptit chouilla plus dure (donc impossible pour toi)

    Ps2 : tu as toujours pas repondu pour n=4 tu sais pas cd qu'est un couple quoi. Tu as trop tendance quand on te reprend à penser que tu as raison et nous tord...
  • Merci.

    J'ai fait la grosse erreur $(a,b)=(b,a)$ :-(

    En effet, c'était pas dur mais fallait y penser à écrire $(A,B)=(A, I \backslash A)$

    Prendre le nombre de parties $2^n$ et enlever l'ensemble vide et $[|1,n|]$.

    $E_n(2)= card \{a \in S_n \ M(a)=2 \}$

    D'après la question 3)b) $E_n(2)=E_n(n+1-2)=E_n(n-1)$

    Si on a 2 montées, ces 2 montées forment une partition de $[|1,n|]$ elle sont donc incluses dans les $2^n-2$ partitions. Mais mon raisonnement n'aboutit pas.

    Montrons par récurrence que $E_n(2)=2^n-(n+1)$

    Au rang $n=2$ $E_2(2)=1$ et $2^2 - (2+1)= 4-3=1$ l'égalité est vérifiée.

    Puis j'y arrive pas. En effet, cette question est dure :-o J'ai réfléchis 30 minutes et je m'en sors pas.
  • Pour $n=4$, après rectification :

    $(\{1 \}, \{2,3,4 \})$ et $( \{2,3,4 \} , \{1 \} )$
    $(\{2 \}, \{1,3,4 \})$ et $( \{1,3,4 \} , \{2 \} )$
    $(\{3 \}, \{1,2,4 \})$ et $ ( \{1,2,4 \} , \{3 \} )$
    $(\{4 \}, \{1,2,3 \})$ et $( \{1,2,3\} , \{4 \} )$
    $(\{1,2 \}, \{3,4 \})$ et $(\{3,4 \}, \{1,2 \})$
    $(\{1,3 \}, \{2,4 \})$ et $(\{2,4 \}, \{1,3 \})$
    $(\{1,4\}, \{2,3 \})$ et $(\{2,3 \}, \{1,4 \})$

    Votre formule est juste il y en a $2^4-2=16-2=14$
  • Fallait surtout penser en fait.
  • J'ai décroché.
    Dans l'avant dernier message, OShine liste 14 'trucs'. Que représentent ces 14 trucs ?
    J'essaie de trouver une logique dans ce recensement, et je ne suis pas sûr d'en trouver une.
  • Les manieres de partitionner [1,4] en 2 ensembles non vide.

    Il doit trouver ensuite le nombre de permutations de [1,n] à 2 montées
  • Le lien avec la question précédent n'est pas évident.
  • La partition {{1,2}{3,4}} ou la partition {{3,4},{1,2}}, c'est la même. On pourrait même la noter {{1,2},{4,3}} puisque l'ordre des éléments dans un ensemble n'a pas d'importance.
    Il y a 7 manières de partitionner [1,4] en 2 ensembles non vides.
  • Oui lourran, sauf qu'ici on parle de couples solutions et que ça a une importance pour l'énoncé!
  • Oshine : Parmi les partitions que tu as énumérées, quelles sont celles auxquelles on va pouvoir associer une permutation ayant exactement deux montées ?
  • Bisam je n'ai pas trop compris. Dans mon exemple on a des couples d'ensembles donc pas d'ordre alors que pour les montées et les descentes ce sont des listes.
  • Pour n = 9
    A = {2,3,6,4} et B = {5,1,7,9,8}

    Quelles sont les listes "naturelles" qu'on peut associer au couple (A,B) qui ont 2 montées?


    Et à
    A = {2,3,1,4} et B = {5,6,7,9,8} ?
  • C'est dur BECEAS en maths en fait.

    Je n'ai pas trop compris c'est quoi une liste associée à un couple (A,B) :-S
  • Oh là là mais c'est pas possible tu arrives à faire un truc de toi même ????
  • Bah je ne comprends pas à quoi sert ce couple $(A,B)$ et ça veut dire quoi les listes d'un couple.
  • Oshine : on dirait que tu restes complètement coincé dans le formalisme, sans essayer de comprendre le sens des mots en français associés aux objets que tu manipules.
    Comme je te l'ai déjà fait remarquer et je suis loin d'être le seul), le mot "montée" n'a pas été choisi au hasard.
    Une "montée", c'est une suite finie de nombres écrits dans l'ordre strictement croissant.

    Si je te donne deux ensembles disjoints $A$ et $B$, vois-tu comment tu peux faire de chacun d'eux une "montée" ?
    Vois-tu dans quel cas il est impossible de former une suite finie $a$ dont l'ensemble des valeurs est $A\cup B$ et tel que les montées de $a$ aient pour ensemble de valeurs respectifs $A$ et $B$ et uniquement eux ?

    Je ne vais pas renouveler le constat alarmiste de noobey : tu n'en as pas besoin. Cependant, il faut que tu aies conscience du fait que, pour l'instant, tu ne fais pas de progrès.
    Tu es sur ton vélo, et le vélo avance... mais ce vélo a des petites roues ... et en plus, on te tient la main... et en plus il y a quelqu'un qui te pousse dans le dos. Est-ce que tu sais faire du vélo pour autant ? J'en doute fort.
  • Bisam non je ne vois pas.

    J'ai très bien compris ce que c'est qu'une montée et je sais trouver les montées pour n'importe quelle liste d'entiers. Mais je n'ai pas compris le sens d'une montée d'ensemble disjoints.

    Par exemple je ne comprends pas le sens de la question :

    "Pour n = 9
    A = {2,3,6,4} et B = {5,1,7,9,8}

    Quelles sont les listes "naturelles" qu'on peut associer au couple (A,B) qui ont 2 montées? "
  • Pour répondre à la question de Bisam;

    Il faut mettre dans l'ordre strictement croissant les éléments de $A$ et les éléments de $B$.
    Le cas à exclure est : le dernier éléments de $A$ est strictement inférieur au dernier élément de $B$ sinon on aurait qu'une montée.

    A = {2,3,6,4} et B = {5,1,7,9,8}

    Les montées sont (2,3,4,6) et (1,5,7,8,9)

    A = {2,3,1,4} et B = {5,6,7,9,8}

    Les montées sont (1,2,3,4) et (5,6,7,8,9)
  • ça avance

    Du coup, réponse à la question?
  • $E_n(2)= 2^n -2 - x$

    Où $x$ est le nombre de couples $(A,B)$ qui ne peuvent pas donner $2$ montées.
    Il faut montrer que $x=n-1$

    $(A,B)=(A, [|1,n |] \backslash A)$

    Je bloque à ce stade.
  • J'ai encore testé sur un exemple mais rien n'y fait je ne vois pas comment faire pour dénombrer $E_n(2)$ en utilisant les couples.105394
    1.png 570.1K
  • (2,3,4,6) et (1,5,7,8,9) : Si ces 2 montées sont la décomposition d'une liste L, cette liste L, elle peut être L1=(2,3?4,6,1,5,7,8,9) ou bien L2=(1,5,7,8,9,2,3,4,6) ;
    Ces 2 listes L1 et L2 ont bien toutes les 2 montées, les 2 montées proposées au début.

    (1,2,3,4) et (5,6,7,8,9) : avec ces 2 montées, si je reproduis la phrase ci-dessus, est-ce que ça marche encore ?
    Tu dois deviner que si je pose la question, la réponse est non...
  • Non ça ne marche pas, il y a soit une unique montée L1=(1,2,3,4,5,6,7,8,9) soit L2= (5,6,7,8,9,1,2,3,4) il y a 3 montées.


    Il faut :

    1) Ranger dans l'ordre strictement croissant les éléments de $A$ et les éléments de $B$

    2) Que le dernier élément de la liste de $A$ strictement supérieur au premier élément de la liste de $B$. Même chose pour $A$.

    Mais comment dénombrer tout ça ?
  • 3 montees dans L2?

    A quelle condition le plus grand élément d'une liste de k éléments est plus petit que le plus petit élément de la liste d'ordre n-k

    Ps : reste au niveau des couples (A,B) où tu concatenes A et B dans ce sens vu que l'énoncé est comme ca.
  • 2 montées dans L2 pardon erreur d'étourderie.

    C'est le cas qu'il faut exclure.

    Soit la liste $(a_1, \cdots a_{k-1} , a_k)$ et la liste $(a_{k+1} , \cdots a_n)$

    On veut le nombre de listes telles que : $a_k < a_{k+1} $ avec $1 \leq a_k \leq k$ et $ k+1 \leq a_{k+1} \leq n$

    La condition est que cet élément de l'ensemble $A$ est plus petit que les $n-k$ éléments de la liste de l'ensemble $B$.
  • Pourquoi $a_k \leq k$

    De toute façon une montée ça veut dire qu'on est en présence de la liste ...
    Et y a ... manières d'obtenir la liste ....
  • Parce qu'on a 2 ensembles $A$ et $B$.

    Ah oui, une montée c'est la liste $(a_1, a_2, \cdots ,a_k, a_{k+1}, \cdots a_n)$ rangé dans l'ordre strictement croissant il y $1$ façon de l'obtenir

    Du coup à $2^n-2$ on soustrait $1$. Mais il faut encore soustraire $n$ je ne vois pas trop à quoi ça correspond ....
  • C'est quoi cette liste en question... quel est le moyen de l'obtenir...
  • J'avoue que je n'ai pas compris comment trouver la solution à cette question.

    Je passe à la suite.

    5)a) Ils s'écrivent $(a_1,a_2, \cdots a_n, a_{n+1})$ où on peut permuter tous les éléments de $(n+1)!$ façons avec $\forall i \in [|1,n|] \ a_{n+1} > a_i$.
    Ce sont les éléments du groupe symétrique $S_{n+1}$ avec la condition $\forall i \in [|1,n|] \ a_{n+1} > a_i$.

    5)b) Les valeurs possibles sont $M(a)=k$ si $a_{n+1}$ est situé à la fin d'une montée. Il sera "inclus" dans cette montée.

    On a $M(a)=k+1$ si $a_{n+1}$ est situé en début de liste car $a_{n+1}$ est plus grand que tous les autres $a_i$.
    On a aussi $M(a)=k+1$ si $a_{n+1}$ si $a_{n+1}$ est situé au milieu d'une montée.105644
    1.png 471.8K
  • Non mais si tu n'as pas compris ça ne sert à rien de passer à la suite désolé.
    Ta réponse à la 5a c'est du n'importe quoi.
    La 5b est fausse aussi mais bon au moins tu as compris la question... la 5a c'est du Hs incroyable.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!