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
.128013s3o_;8bcdufvgU/T0lyq n7apS.r1-meh,(P2=4:+twki9][5R*)é6050j0G0Q0y0T0s0b0v0i0s0y0b0b0M010Q0T0z010406050b0k0F0F0y0C0t040A0d0s0k0`0d0w0v020y0F0z0f0v0Y0G140C0u0k0G0b050p111315170 0z041v1C051F0p1F1H1C0 0j0T0m0/0;0?0^0H0T0n0H0s1V0H0Q0}050*0h0s0G1Q0=0@011U1W1Y1W0Q1(1*1$0Q0h0d0j171%0C1D0Q0H0/1a0b0z0y0w0^0L011,1S010l0,0G0w1i0G1$27292e1.2h1*2k0F2m040a0v0K0C0d0z0d0b0T1d1f0(250C0C0G0i2H1v2o0w1D0p232T0Q2120220j2q0^1Y0w2j2E1$1N1P0:1-2%0T2)0w1}1O1$0z2M1D2R2T2~10281f2/2f2@0C140s0}0v0D2Q320~312p341.36383a0L3d293f2R2$013k0y39040v0c3o2S0 3r3i0^3u3w0v0N3A3q323s3G3a0X3K3C3M3E3t0d373v3a0$3R3g331R3j3W3l3x0x3#3D3(3F3*3Y3x0g3.3T3:3V3X3H0U3_3h3{3O040D0r403%2:3|3+0D3c1w3e1E2|1v2-2W0j2!3s0i1}2w0%1O1D2{0G2}4f4e3p054o0(4w41490w0}1U0z281q1s0e2v0F3K0v3$3s0d0}0M4Q4S3U0|040W3K4Y3{0F0T0}4d303/494!0I4X4/2f4*4,4%4@1.4;4?3`494_444{502f4~4y2S4R4|0^523z584D48560}0V3R063S4E2f0S0}0(0l545o1.0R3a5u5h3j0l4H0{4K1r0G5z3s4!0J5I3U4G040w5M3{4!0!0O3R0v5X5a553j0}0T4 5v0^4U044W5f5Z5)3t0h0}2t5R4:0}5L5f4(4F5D4J155G4N1o5^5i040!5W5Y5}5p0}0R1U1*5(5A3F0}5Q5.6b1.5+020n0Q0f5-2~5/6i3t5$654}0}5V5f065Y6G6w3N5r0T0l0l0G2M0w0i5H6m5b015+6u3e6I4Z5`6A5c4+043!6T5!5*0}0Z6h6J045%6+5:5+0E6: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!7A045k6E6H6a6U5O111O290Q7)6W7)5O1N6M6O2j6R7 0}0p0p816z7?7@6Z425 7a0G634P7/7R0}0B7%0}0y4J2j0j7O7B4.7i7`0k7|0w7~8n5S0}688e7@7H7j7F6Y8M5+0P6X3p8g517q695X8M5q042M0Q0k0C6l7L8A8i7X8k7c8G5_4#8r5P8x7;3#0p4B4v4g8 0p4j1v0Q4l942Y2U1|1~2W0y1)914j1B5g3s2M0F0e0l0y0S8k0H0c0}1n1p5G0.6D301I3f1C0o2)0v0F0#234p0v0C0#0i8)2F0m0G0I0v0y9Q0i0v0k9E8t2{0d0i0H1+051o040q2C0v0j0d0R6l9+0v1t0Q0v0#0n3v1o2j9`2D0?0T9e0v0O0 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~2f6p6r0f815=045@aH7e8y7s8-5P0ha@7d7nbaaM8`9y3e6F8f8M78a-ap8lbi8p8^9!8va/0Ja: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.