Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

DM:nombres de catalan

Posté par alexghess (invité) 25-01-06 à 18:01

bonjour,j'aurait besoin de votre aide pour faire ce DM

sujet:
On note pour tout ntier naturel n non nul et tout entier relatif s,Cn l'ensemble des n-listes d'elements de {-1,1} et Cn, l'ensemble des n-listes d'elements de {-1,1} dont la somme des coordonnees vaut vaut s i.e. les ensembles suivants:
Cn={x=(x1,x2,...,xn);(xk=-1 ou xk=1)} et Cn,={x=(x1,x2,...,xn)Cn;(de k=1 a n)xk=s}

1)a)Soit (n,s) un element de *x.A quelle condition,necessaire et suffisante,l'ensemble Cn, est-il non vide?
b)Soit (p,m) un element de * different de (0,0).Determiner le cardianl de l'ensemble Cp+m,p-m.

On considere desormais un entier naturel n non nul et on note simplement C l'ensemble C2n,0.
2)a)Quel est le cardinal de l'ensemble C?
On note C+,C+barre,C1 et C-1 les ensembles suivants:
C+={x=(x1,x2,...,x2n)C;(k [1,2n])((de i=1 a k)xi0)},C+barre=C/C+,C1={xC;x1=1} et C-1={xC;x1=-1}
b)Dans le cas particuliers ou n=2 et n=3,determiner les elements de l'ensemble C+.

3)Soit x=(1,x2,...,x2n) un element de C1C+barre
a)Justifier l'existence d'un plus petit entier,note p,parmi les entiers k verifiant (de i=1 a k)xi<0.
A cet element x,on associe l'element (x)=(-x2,...,-xp,xp+1,...,x2n)(on a elimine la premiere coordonnée de x et,pour obtenir (x), on a change, dans x,chacune des p-1 coordonnees suivantes en leus opposee).
b)Verifier que (x) est element de C2n-1,3.
c)Montrer que l'application ainsi definie est bijective de C1C+barre sur C2n-1,3.
d)En deduire l'egalite:cardC+=(n-1 parmi 2n-1)-(n+1 parmi 2n-1), puis l'egalite card C+=(1/(n+1))*(n parmi 2n)

4)A l'issue d'une election opposant deux candidats A et B,departages par 2n votants,les deux candidats se trouvent a egalite de voix.Quelle est la probabilite pour qu'au cours du depouillement,bulletin par bulletin(aucun n'etant blanc ou nul), le candidat A se soit toujours trouve en tete (ou a egalite)?

5)On pose,pour tout entier naturel n,Cn=(1/(n+1))*(n parmi 2n).
Etablir,pour tout entier naturel n non nul,l'egalite Cn=(de p=1 a n)Cp-1*Cn-p.On observera que ,si x est un element de C+,on dispose d'entiers K tels que (de i=1 a k=xi=0

Merci beaucoup d'avance pour votre aide

Posté par
veleda
nombres de catalan 26-01-06 à 14:19

bonjour, il me semble que ton exo n'attire pas les foules!
il est vrai que le texte est assez pénible à déchiffrer
( je n'ai pas compris toutes les notations mais je vais  essayer de t'aider)
  1)  dans une n-liste
  je note :a le nombre d'éléments égaux à +1
           b le  """""""""""""""""""""""à -1
on a donc: a+b=n
    si la somme des xk pour k variant de 1 à n est s
on a       a-b=s
donc pour  (n,s) élément de N*.Z (a,b)est solution
a+b=n
a-b=s      d'où      2a=n+s      2b=n-s
  a et b sont des entiers naturels on doit donc avoir:
-n<=s<=n  et n et s de même parité (cns pour que Cn,s soit non vide)
es-tu d'accord?

Posté par
veleda
re:nombres de catalan 26-01-06 à 16:40

b) on cherche le nombre de p+m-listes dont la somme des éléments est s=p-m
avec les notations précédentes on a
   a+b=p+m
   a-b=p-m   d'où:  (a,b)=(p,m)  (on est dans le cas où "ça marche"   p+m etp-m ont la même parité)
  une telle p+m liste est bien déterminée si l'on connait la place des p éléments +1  et il y a  (m+p)!/(p!)(m!) façons de les placer  
donc le cardinal de Cp+m,p-m  =(m+p)!/(p)!(m)!
2)a)  il s'agit des 2n-listes dont s la somme des éléments  est nulle       a+b=2n
                          a-b =0      d'où....
  b)pour n=2  C+ = { (+1,+1) ,(+1,-1) }
    pour n=3  C+ = { (+1,+1,+1) ,(+1,+1,-1) ,(+1,-1,+1) }
  j'espère que ça va aller.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !