Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 18-03-2011 15:05:39

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

Dénombrement... ou pas

Déterminez [latex]a_n[/latex] en fonction de n, où [latex]a_n[/latex] est définie par la relation de récurrence ci-dessous :

(i) [latex]a_0=0[/latex] et [latex]a_1=1[/latex]
(ii) [latex]\forall n \ge 2[/latex], [latex]a_n=\sum_{k=1}^{n-1}a_{k}a_{n-k}[/latex]
(la définition de [latex]a_0=0[/latex] n'est pas indispensable, mais peut s'avérer utile !)

Question subsidiaire : que représente notamment [latex]a_n[/latex] en dénombrement ?

Indice 1 : Spoiler : [Afficher le message] il serait judicieux de fabriquer une série entière ...

Indice 2 : Spoiler : [Afficher le message] La définition de la suite ressemble fortement à un produit de Cauchy... Si on mettait la fonction définie par la série entière [latex]f(x)=\sum_{n\ge0}^{+\infty}a_nx^n[/latex] au carré ? On trouve une relation sur f qui permet de la calculer

  • |
  • Répondre

#0 Pub

 #2 - 18-03-2011 15:51:41

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1935
Lieu: 86310

Dénombrement.. ou pas !

Tu viens de corriger le [latex]a_{n_k}[/latex], bien !
Pourquoi définir un [latex]a_0[/latex] ?


The proof of the pudding is in the eating.

 #3 - 18-03-2011 16:03:01

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

énombrement... ou pas !

J'ai corrigé la définition de [latex]a_0[/latex], pas indispensable, mais potentiellement utile !

 #4 - 18-03-2011 17:03:18

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 495
Lieu: Ardèche

Dénobrement... ou pas !

a0=0
a1=1
a2=1
a3=2
a4=5
Ça ressemble à [latex]a_n=\frac {(2n-2)!}{(n-1)!n![/latex].
Au décalage de 1 près de n, ce sont les nombres de Segner ou nombres de Catalan.

Les liens suivants donnent des réponses à la question subsidiaire :
http://oeis.org/A000108
http://fr.wikipedia.org/wiki/Nombre_de_Catalan

 #5 - 18-03-2011 18:12:00

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1106
Lieu: Jacou

Dénombrement.. ou pas !

Ce sont les nombres de Catalan.
Ils servent dans beaucoup de domaines différents.
C'était intéressant de se replonger dedans.

http://fr.wikipedia.org/wiki/Nombre_de_Catalan
http://oeis.org/A000108

La définition donnée est légèrement différente...

 #6 - 18-03-2011 18:20:19

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

DDénombrement... ou pas !

@halloduda: oui !
@rivas : oui !

J'attends tjs une petite demo, si qqun se sent :-)

 #7 - 19-03-2011 12:07:27

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

dénombrement... iu pas !

Tiens tiens ! L'expression qui définit a_n ressemble aux coefficients du carré d'un polynôme de coefficients a_i... je vais y réfléchir. En revanche, aucune idée relative à du dénombrement.

 #8 - 19-03-2011 13:22:54

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

Dénomberment... ou pas !

@gasole: il y a de l'idée, pousse encore plus loin que les ********s !

 #9 - 19-03-2011 16:05:38

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Dénombrement.. ou pas !

Tu veux parler d'un produit de Cauchy ? pfff j'ai jamais fait ça moi avec mon petit niveau bac+2 en math...merci wikipedia !
'tain vous me faites faire de ces trucs les gars ! big_smile

 #10 - 19-03-2011 21:44:31

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

Dénomrement... ou pas !

Indice 1 : Spoiler : [Afficher le message]  il serait judicieux de fabriquer une série entière ...

 #11 - 19-03-2011 23:29:20

Tromaril
Habitué de Prise2Tete
Enigmes résolues : 20
Messages : 45

Dénombrement... ou as !

Mes souvenirs sur les séries entières sont très lointains, mais si je néglige le pb de convergence, ça me donne quelque chose comme ça :

Soit f(x)=[latex]\sum_{n=0}^\infty c_nx^n[/latex]
[TeX]f(x)^2=f(x)-x[/TeX]
donc [latex]f(x)=\frac {1+/-\sqrt{1-4x}}{2}[/latex]
On retient[latex]f(x)=\frac {1-\sqrt{1-4x}}{2}[/latex] parce que ça s'annule en zéro.
Après de laborieux calculs sur le développement de [latex](1-4x)^{1/2}[/latex] on obtient [latex]c_n=2\frac{(2n-3)!}{(n-2)!n!}[/latex]

 #12 - 19-03-2011 23:32:02

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

Dénombremet... ou pas !

Oui Tromaril, pour quelqu'un qui a des lointains souvenirs, c'est plutôt très bien smile
Tu peux juste simplifier un peu ton expression en multipliant par 2n-2 numérateur et dénominateur.

 #13 - 20-03-2011 00:04:11

Tromaril
Habitué de Prise2Tete
Enigmes résolues : 20
Messages : 45

Dénombremen... ou pas !

T'as pas vu mes brouillons big_smile

ça fait donc [latex]c_n=\frac 1 n C_{2n-2}^{n-1}[/latex]

 #14 - 20-03-2011 00:22:23

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

Déonmbrement... ou pas !

Ca m'a l'air d'etre les nombres catalans ou la solution au premier probleme de Schroeder,
selon OEIS


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #15 - 21-03-2011 02:05:02

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

débombrement... ou pas !

@dhrm77: c'est bien ça smile

Indice 2 : Spoiler : [Afficher le message] La définition de la suite ressemble fortement à un produit de Cauchy... Si on mettait la fonction définie par la série entière [latex]f(x)=\sum_{n\ge0}^{+\infty}a_nx^n[/latex] au carré ? On trouve une relation sur f qui permet de la calculer

 #16 - 21-03-2011 11:24:22

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Dénombreement... ou pas !

Utilisons les séries génératrices.
[TeX]\sum_{n=0}^{\infty}a_nX^n=X+\sum_{n=0}^{\infty}\sum_{k=0}^{n}a_k a_{n-k} X^n=(\sum_{n=0}^{\infty}a_n X^n)^2[/TeX][TeX]f(X)=X+(f(X))^2 [/TeX][TeX]\Delta=1-4X[/TeX][TeX]f(X)=\frac{1-(1-4X)^{\frac{1}{2}}}{2}[/TeX][TeX]a_n=-\frac{1}{2} \binom{0.5}{n}(-4)^n[/TeX]
Il est facile de simplifier cette expression en calculant le coefficient binomial généralisé...


Un mathématicien complet est topologiquement fermé!

 #17 - 21-03-2011 18:13:53

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1106
Lieu: Jacou

Dénombrement... ou ppas !

Il y a surement de belles démonstrations (encore cachées).
J'ai trouvé 2 liens intéressants néanmoins que je souhaite partager:
http://homepages.ulb.ac.be/~sfiorini/ma … /demos.pdf
et
http://www.les-mathematiques.net/phorum … 187,636203

 #18 - 21-03-2011 18:19:16

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

dénombrement... oy pas !

Ton premier lien est la démo à laquelle je pensais smile

Pour le second lien, il faut d'abord intuiter la valeur de [latex]a_n[/latex] avant de pouvoir la montrer par récurrence, mais quand on connaît la valeur exacte des nombres de C******, c'est une démo originale !

 #19 - 26-03-2011 18:23:52

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

dénombtement... ou pas !

Tiens j'ai oublié de clore ce sujet sur les nombres de Catalan, qu'il fallait donc reconnaître.

On utilise ici les séries entières pour trouver une formule pour [latex]a_n[/latex], en remarquant que la définition de [latex]a_n[/latex] fait penser à un produit de Cauchy.
Je ne vais pas refaire la démo, certains l'ont très bien fait.
On arrive à :
[TeX]a_n=\frac 1 n C_{2n-2}^{n-1}[/TeX]
On arrive au résultat suivant : [latex]a_n=[/latex]
Les [latex]a_n[/latex] ne sont pas exactement les nombres de Catalan, ils sont décalés d'un indice. En revanche, cette définition de [latex]a_n[/latex] permet de donner le nombre de parenthésages d'une expression à n éléments
Exemple : (x*y)*z et x*(y*z) pour a_3=2

La page Wikipédia sur les nombres de Catalan vous en apprendra beaucoup sur leurs nombreuses applications.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Mots clés des moteurs de recherche

Mot clé (occurences)
Nombre de catalan demonstration (8) — Nombre de catalan serie entiere (4) — Somme des coefficients binomiaux au carre (3) — Exercice nombre de catalan (2) — Nombre catalan demonstration (2) — Denombremetn (2) — Nombres de catalan demonstration (2) — Numero 0826 (2) — Denombrements enigme (2) — Demonstration nombre catalan (2) — Exercice serie entiere nombres de catalan (1) — Probleme nombre de catalan et series entieres en pdf (1) — Nombres de catalan series entieres (1) — Serie d exercices corriges sur denombrement 1s (1) — Definition enigme subsidiaire (1) — Denombrement series generatrices (1) — Serie entiere catalan nombre (1) — Developper en serie entiere sqrt(1-4x) (1) — Enigme denombrement (1) — Nombres de catalan demonstration par denombrement (1) — Probleme nombre de catalan (1) — Nombre de catalan demo serie entiere (1) — Nombre catalan (1) — Denombrement series entieres (1) — ?nigme catalan (1) — Somme de coefficients binomiaux au carre (1) — Corrige exercice les nombres de catalan (1) — Catalan denombrement (1) — Nombre de catalan preuve serie entiere (1) — Enigmes catalogne (1) — Enigmes de logique et solutions a imprimer (1) — Exercice de denombremebt (1) — Produit de cauchy et denombrement (1) — Denombrement fonctions generatrices (1) — Probleme corrige nombre de catalan (1) — Nombre de catalan demonstration suites (1) — Somme des carres des coefficients binomiaux (1) — Enigmes catalanes (1) — Catalan nombre (1) — Demontrer cn suites des nombres catalan (1) — Exercice catalan nombre (1) — Problemes series generatrices (1) — Exemples serie generatrice denombrement (1) — Nombre catalan correction (1) — Nombre de catalan serie generatrice produit de cauchy catalan (1) — Des jolis enigme logique corrige+pdf (1) — Demonstration nombre de catalan (1) — Enigme catalan (1) — Series generatrices denombrement (1) — Les nombres catalan (1) — Denombrement (1) — Denombrement et serie entiere (1) — Nombres catalans (1) — Serie entiere de catalan (1) — Exercices + corriges sur les suites de catalan (1) — Exercices corriges deenombrement (1) — Le nombre de catalan demonstration (1) — Enigme catalans (1) — Exercices corriges sur les nombres de catalan (1) — Demonstration nombres de catalan (1) — Nombre de catalan deux expressions demo (1) — Enigme math serie generatrices (1) — Nombres catalan (1) — Fonction generatrice catalan (1) — Probleme nombre catalan (1) — Nombre de catalan serie generatrices (1) — Fonction generatrice nombre de catalan (1) — Denombremebt exercice de grenouille (1) — Serie generatrice (1) — Probleme serie entiere denombrement (1) — Nombre de catalan fonction (1) — Serie generatrice denombrement exemple (1) — Nombres de catalan (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete