Nombres d'Hipparque

Série d'exercices

Cet exercice fait partie d'une série :

Hipparque, mathématicien et astronome grec (2e siècle avant JC) a affirmé qu’il y avait 103 049 propositions affirmatives composées à partir de 10 propositions élémentaires. Or ce nombre correspond au nombre de façons d'insérer des parenthèses dans une suite de 10 symboles !

L'insértion des parenthèses dans une suite de n symboles doit se faitre selon deux règles :

  • toute paire de parenthèses entoure au moins deux symboles ou groupes parenthésés,
  • les parenthèses ne doivent pas entourer la suite en entier.

Exemple

  • 1 symbole / 1 possibilité : a

  • 2 symboles / 1 possibilité : ab

  • 3 symboles / 3 possibilités : abc, (ab)c, a(bc)

  • 4 symboles / 11 possibilités : abcd, (ab)cd, ab(cd), a(bc)d, (abc)d, a(bcd), (ab)(cd), ((ab)c)d, (a(bc))d, a((bc)d), a(b(cd))

On admettra que :

  • \(s_0=1\).
  • Une formule pour calculer \(s_n\) avec \(n>3\) est :
\[s_n = \frac{\left((6n-9)s_{n-1} - (n-3)s_{n-2}\right)}n\]

Écrire une fonction telle que hipparque(n) renvoie le nombre entier \(s_n\).

Tests

Le problème peut se résoudre de manière itérative ou récursive.

Cependant, les tests seront effectués avec des grandes valeurs de \(n\) : il est donc indispensable de stocker les valeurs intermédiaire.

Exemples 
>>> hipparque(3)
3
>>> hipparque(4)
11
>>> hipparque(5)
45

===

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10
.1280134U2ny6g3p )TrPvq1-=;oa_ckmi*u5(,e:éts]Shl970[wRbf8.+/d050$0H0K0w0B0P0L0k0y0P0w0L0L0t010K0B0j010406050L0D0A0A0w0n0f040N0v0P0D0`0v0e0k020w0A0j0u0k0V0H140n0q0D0H0L050#111315170 0j041v1C051F0#1F1H1C0 0$0B0p0/0;0?0^0O0B0h0O0P1V0O0K0}050*0W0P0H1Q0=0@011U1W1Y1W0K1(1*1$0K0W0v0$171%0n1D0K0O0/1a0L0j0w0e0^0d011,1S010X0,0H0e1i0H1$27292e1.2h1*2k0A2m040a0k0o0n0v0j0v0L0B1d1f0(250n0n0H0y2H1v2o0e1D0#232T0K2120220$2q0^1Y0e2j2E1$1N1P0:1-2%0B2)0e1}1O1$0j2M1D2R2T2~10281f2/2f2@0n140P0}0k0r2Q320~312p341.36383a0d3d293f2R2$013k0w39040k0i3o2S0 3r3i0^3u3w0k0b3A3q323s3G3a0E3K3C3M3E3t0v373v3a0g3R3g331R3j3W3l3x0R3#3D3(3F3*3Y3x0Y3.3T3:3V3X3H0Q3_3h3{3O040r0S403%2:3|3+0r3c1w3e1E2|1v2-2W0$2!3s0y1}2w0%1O1D2{0H2}4f4e3p054o0(4w41490e0}1U0j281q1s0x2v0A3K0k3$3s0v0}0t4Q4S3U0|040T3K4Y3{0A0B0}4d303/494!0G4X4/2f4*4,4%4@1.4;4?3`494_444{502f4~4y2S4R4|0^523z584D48560}0M3R063S4E2f0z0}0(0X545o1.0U3a5u5h3j0X4H0{4K1r0H5z3s4!0F5I3U4G040e5M3{4!0l0I3R0k5X5a553j0}0B4 5v0^4U044W5f5Z5)3t0W0}2t5R4:0}5L5f4(4F5D4J155G4N1o5^5i040l5W5Y5}5p0}0U1U1*5(5A3F0}5Q5.6b1.5+020h0K0u5-2~5/6i3t5$654}0}5V5f065Y6G6w3N5r0B0X0X0H2M0e0y5H6m5b015+6u3e6I4Z5`6A5c4+043!6T5!5*0}0C6h6J045%6+5:5+0s6:3U523 5|6U5T6{3{5+6/6@6x5O4I5F4M4O6$014!4$6 6,6y6=72496_7l4^6(4-4f705j7o6o0}6`765J6#7h5:5O6?6v6n6-047y7G6U5d7d717z3U747v6j0479617b647C6x7f7d7E7T6V7x7)523n7!7A045k6E6H6a6U5O111O290K7)6W7)5O1N6M6O2j6R7 0}0#0#816z7?7@6Z425 7a0H634P7/7R0}0Z7%0}0w4J2j0$7O7B4.7i7`0D7|0e7~8n5S0}688e7@7H7j7F6Y8M5+0!6X3p8g517q695X8M5q042M0K0D0n6l7L8A8i7X8k7c8G5_4#8r5P8x7;3#0#4B4v4g8 0#4j1v0K4l942Y2U1|1~2W0w1)914j1B5g3s2M0A0x0X0w0z8k0O0i0}1n1p5G0.6D301I3f1C0c2)0k0A0J234p0k0n0J0y8)2F0p0H0G0k0w9Q0y0k0D9E8t2{0v0y0O1+051o040m2C0k0$0v0U6l9+0k1t0K0k0J0h3v1o2j9`2D0?0B9e0k0I0 9A4r2.3{1:1X1Z1#4t4h9z308~9i5N8.4L8:7Z8,6^4V7)7$8=7p4`ax6B044=7Q4)8XaA0^57as6x527r4z7taC7,6(5e8z5:4!7=2~5n6x8#5s7d5x3x7%5C7V5E8/8`5{aU776k8`5U8Y8V6c6=5taE5~8_a~2f6p6r0u815=045@aH7e8y7s8-5P0Wa@7d7nbaaM8`9y3e6F8f8M78a-ap8lbi8p8^9!8va/0Fa:bd7Da?ba7Sbk6(6*a;4T7+bJ0}6~bM6!67bw0475bS8ha,60apa/8^8+bE6xbjbY8Wazb-668Jb:7w7Jb%ba5Ob)aO7ib,b*3s7Nba7Pb?7IbXc0anb!8jb_c57jb|2S8QbOcd7-a@b=c873898bb`bGcdc4bo6G8!0}8%8)cfa)7_ao628;ct0}7gcdb{8`aXbo1val902T931K3f920)0+0-04.