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 - 08-08-2016 11:32:53

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Entre parenthèses..

Bonjour à tous,
Un curieux problème vu sur un site voisin, et qui n'a pas suscité l'intérêt qu'il mérite...
Il s'agit de trouver toutes les combinaisons possibles qu'on peut faire en ajoutant des paires de parenthèses à une suite ordonnée de 6 lettres A B C D E F :

Par exemple:
A B C D E F
(A) B C (D) E F
((AB) C D ) E F
...

Toutes les combinaisons possibles conservent l'ordre des lettres.

Les parenthèses peuvent contenir de 1 à 5 lettres, elles mêmes pouvant être contenues dans des parenthèses strictement plus petites : le cas ((A B...)) est interdit sinon on pourrait mettre une infinité de parenthèses.

Pour les plus courageux: généralisation possible ? ça semble plus compliqué que la formule de partition d'un ensemble....

Comptez bien !



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 08-08-2016 17:53:33

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Entre parenhtèses...

Attention Shadock, les lettres restent dans le même ordre dans toutes les combinaisons.
Je vais le préciser, je pensais que les qq exemples auraient suffi à lever l'ambiguïté, mais....

 #3 - 08-08-2016 18:35:29

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Entre parrenthèses...

Bonjour Nodgim

C'est un problème assez connu sauf qu'ici on autorise les parenthèses entourant un seul nombre . Le problème original est le suivant : on effectue la même opération entre n éléments , de combien de façons différentes peut-on conduire le calcul sans changer l'ordre des éléments ? Il y a une relation de récurrence ( mais pas de formule fermée ) permettant d'obtenir le résultat . Il suffit alors de multiplier ce résultat par [latex]2^n[/latex] pour obtenir la solution .

Vasimolo

 #4 - 09-08-2016 12:43:40

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,469E+3

Entre parentthèses...

C'est en rapport avec les nombres de Catalan ?

 #5 - 09-08-2016 13:19:29

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Entre parentèses...

Je ne sais pas Gwen. Quand on aura fait le décompte, on pourra toujours faire la comparaison.

 #6 - 10-08-2016 18:30:52

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

nEtre parenthèses...

Si pour 6 lettres, ça semble compliqué, ramener le problème à d'abord 2 lettres, puis 3.

 #7 - 14-08-2016 18:48:31

dbab3000
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 110

Entre parenthèsse...

Si on considère [latex]U_{n}[/latex] le nombre de combinaisons possibles pour n caractères la formule est
[TeX]U_{n}=\sum_{k=1}^{n-1}(n+1-k)(U_{k}+1)[/TeX]
Avec [latex]U_{1}=0[/latex]
Si on utilise la relation alors [latex]U_{6}=395[/latex]

PS: Si tu veux la démonstration de la formule dis le moi, je ne l'ai pas écrit car c'est plus facile de le trouver que de l'expliquer.

Bonne soirée.

 #8 - 14-08-2016 19:52:31

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Ente parenthèses...

Salut Dbab,
Et merci pour ta réponse, mais je crains que cette formule ne corresponde pas tout à fait à l'énoncé. Comme l'a fait remarquer Vasimolo, il semblerait que cette formule parte du principe qu'une paire de parenthèses entoure 2 lettres au minimum. Le nombre que j'obtiens avec 6 lettres, lorsque une paire de parenthèses peut entourer 1 seule lettre, monte à :

12608.

Voici le détail :
G2 = 4  (4 façons différentes de présenter avec 2 lettres)
G3 = (G2, 1 ) ou (1,1,1) = 24
G4 = (G3, 1 ) ou (G2, G2) ou (G2, 1 , 1 ) ou ( 1 , 1 , 1 , 1 ) = 176
etc...

 #9 - 14-08-2016 20:19:37

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,469E+3

Entre parentèses...

Ce qui correspondrait  la somme des nombre de catalan de rang 0 à n  fois 2^6 (possibilités pour des parenthèses à un caractère )

 #10 - 14-08-2016 20:26:11

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Enntre parenthèses...

Il serait cool de généraliser à des parenthèses "marquées", par exemple des parenthèses de couleurs pour différencier (()) de (()) par exemple, mais bon n'abusons pas big_smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
 

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 ?

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