18 config sur 7 lignes:
-----
18 config sur 7 lignes:
Sans questions il n'y a que des problèmes sans réponses.
Liet,
La solution du msg #28 avec ses hypothèses ajoutées me semble répondre à la demande ?
Il faut comprendre que dans le cas L1_est_une_route(par exemple), le nombre de pavages possibles contenant cette route, comprend tout les pavages dans la grille sous la ligne en L1 soit cas(8,6) = 167089 pavages différents. Parmi ces 167089 pavages, on trouve des pavages sans autre route que L1, des pavages avec route en L2 et/ou route en L3 et/ou en L4 et/ou en L5 et/ou en L6 et/ou en L7.
C'est vrai aussi pour les cas route en L2 ou L3 ou L4 ou L5 ou L6 ou L7.
Biname
Salut,
Un petit dessin mal fait vaut mieux qu'un long texte :
Tous ces pavages sont inclus dans les cas(8,6) = 167089 pavages
Biname
Dernière modification par Biname ; 12/08/2023 à 23h16.
La probabilité d'avoir une route en L1 devrait être : nombre de pavages sans routes du rectangle 6*8 / nombre de pavages total du rectangle 7*8 ->comment connaître le nombre de pavage sans routes du rectangle 6*8 ?
Si on se penche sur la probabilité d'avoir une route en L3 on touche à une difficulté supplémentaire puisque la formule devient :
((nombre de pavages sans routes du rectangle 2*8)*(nombre de pavages sans routes du rectangle 4*8)) / nombre de pavages total du rectangle 7*8
Sans questions il n'y a que des problèmes sans réponses.
Liet,
@Biname = moi #32 et 33 : non, on a pas la solution ! Manquent à ce comptage toutes les routes qui ne comprennent pas la route en L1, exemple : une unique route en L3. Mais mon image montre la grille 6,8 ... et aussi la complexité du problème qui ne se résoudra pas en quelques heures ?
Oui, ce qui équivaut à dire : le nombre de cas de pavages ne comprenant qu'une seule route en L1 et plus généralement en L_i.
Supposons qu'on ait la formule qui calcule ce nombre de cas Ligne_unique_en_Li(m,n) ou Pas_de_ligne_en(m,n)
Il faudrait donner des noms corrects à ces fonctions : ??? n_cas(m,n) ou n_pav(m,n) = mon 'PI PI', n_sans(m,n) ... bon ça, non ?
n_sans(2,8), n_sans(4,8) et n_pav(7, 8) ou n_cas(7, 8) mais il faudra réécrire PI PI en permutant m et n ??? ligne, colonne c'est mieux.Si on se penche sur la probabilité d'avoir une route en L3 on touche à une difficulté supplémentaire puisque la formule devient :
((nombre de pavages sans routes du rectangle 2*8)*(nombre de pavages sans routes du rectangle 4*8)) / nombre de pavages total du rectangle 7*8
Biname
J'ai l'impression que cela ressemblerait de loin à le méthode pour dénombrer le nombre de partitions d'un nombre sans répétition, formule à rallonge. Mais avec une incertitude quand même sur le calcul des pavages sans routes.
Je ne sais pas si MissJenny est arrivée à ce problème en considérant comme valide l'existence d'une formule permettant de calculer le nombre de pavages d'un rectangle ?
Sans questions il n'y a que des problèmes sans réponses.
Salut,
EUREKA ? Ou un coup de latte sur les doigts ?
Par recurrence on trouve sans(l, c) le nombre de pavages sans routes
sans(l, c) est noté ici S_i, de même pour cas(l, c) qui est noté C_i ou i est l'indice de ligne
Résumé :
S_1 = 0
S_2 = C_2 - 1
S_3 = C_3 - 2 * S_2 - 1
S_4 = C_4 - 2 * S_3 - 3 * S_2 - 1
S_5 = C_5 - S_4 - 2 * S_3 - 2 * S_2 - S_2² - 1
S_6 = C_6 - 2 * S_5 - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_2² - 2 * S_2 * S_3 - 1
Avec C_7 - S_7 on a tous les pavages comportant au moins une ligne
et avec (C_7 - S_7)/C_7 la probabilité demandée au message #1
Reste à trouver l'algorithme ?
Le raisonnement est bon, la démo aussi mais une erreur d'addition des termes n'est pas exclue ?
Je voudrais aller faire du vélo avant la nuit, je balance ainsi
Démo par récurrence
Cliquez pour afficher
Soit g(l,c) une grille Grille rectangulaire faite de cases
Cette grille compte l lignes et c colonnes
On pave cette grille avec des dominos 1 x 2 cases
Soit une route une ligne horizontale composées uniquement de dominos horizontaux
Soit cas(l, c) le nombre de pavages différents possibles dans g(l,c)
Soit sans(l, c) le nombre de pavages possible dans g(l,c) sans aucune route
Cas(m,n) = C_n
#
Dans ce qui suit, on aura c constant, on va donc simplifier l'écriture en posant
C_l = cas(l,c) en pratique C_1, C_2, C_3, ...
S_l = sans(l,c) en pratique S_1, S_2, S_3, ...
Notons "xx00x00" les cas de routes en ligne 1,2 et 5
Notons "???????" tous les cas possibles
On commence :
Calculons S_1
pour "?" : C_1 cas
pour "0" est impossible = 0
pour "x" : C_1 = 1
pour "0" = S_1 = C_1 - 1 = 0
Calculons S_2
pour "??" : C_2 cas
pour "xx" : 1 cas
les autres "??" = "xx" ou "00" = S_2
pour "00" = S_2 = C_2 - 1
Calculons S_3
pour "???" : C_3 cas
pour "x00" : S_2 cas
pour "00x" : S_2 cas
pour "xxx" : 1 cas
les autres "???" = "xxx" ou "000" = S_3
pour "000" = S_3 = C_3 - 2 * S_2 - 1 ça prend forme Eureka ?
Calculons S_4
pour "????" : C_4 cas
pour "x000" : S_3 cas
pour "000x" : S_3 cas
pour "x00x" : S_2 cas
pour "xx00" : S_2 cas
pour "00xx" : S_2 cas
pour "xxxx" : 1 cas
les autres "????" = "xxxx" ou "0000" = S_4
pour "0000" = S_4 = C_4 - 2 * S_3 - 3 * S_2 - 1
Calculons S_5
pour "?????" : C_5 cas
pour "x0000" : S_4 cas
pour "00x00" : S_2² cas
pour "0000x" : S_4 cas
pour "xx000" : S_3 cas
pour "000xx" : S_3 cas
pour "xxx00" : S_2 cas
pour "00xxx" : S_2 cas
pour "xxxxx" : 1 cas
les autres "????" = "xxxxx" ou "00000" = S_5
pour "00000" = S_5 = C_5 - S_4 - 2 * S_3 - 2 * S_2 - S_2² - 1
Calculons S_6
pour "??????" : C_6 cas
pour "x00000" : S_5 cas
pour "00x000" : S_2 * S_3 cas
pour "000x00" : S_3 * S_2 cas
pour "00000x" : S_5 cas
pour "xx0000" : S_4 cas
pour "00xx00" : S_2² cas
pour "0000xx" : S_4 cas
pour "xxx000" : S_3 cas
pour "000xxx" : S_3 cas
pour "xxxx00" : S_2 cas
pour "00xxxx" : S_2 cas
pour "xxxxxx" : 1 cas
les autres "??????" = "xxxxxx" ou "000000" = S_6
pour "000000" = S_6 = C_6 - 2 * S_5 - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_2² - 2 * S_2 * S_3 - 1
On peut continuer, je laisse le prix Nobel à un autre, ça ne m'intéresse pas, fautque je parte faire du vélo avant que la nuit ne tombe.
Avec C_7 - S_7 on a tous les pavages comportant au moins une ligne
Et avec (C7 - S_7)/C_7 la probabilité demandée au message
Biname
Salut,
La récurrence fonctionne car lorsqu'on a une route au moins dans une grille de n lignes, le nombre de ligne sans routes dans cette grille est toujours inférieur à n. On le voit très bien dans la 'démo'.
Biname
Bonjour,
La probabilité demandée est.
GBZM,
Tu as utilisé 'mon' algorithme ?
Biname
@Biname
Tu peux me donner les valeurs pour les pavages 2*8, 3*8, 4*8 , 5*8 ,6*8 et 7*8 ?
Sans questions il n'y a que des problèmes sans réponses.
Salut,
cas(8C, 2L) = 33.99999999999999
cas(8C, 3L) = 153.0000000000001
cas(8C, 4L) = 2245.0
cas(8C, 5L) = 14824.00000000002
cas(8C, 6L) = 167089.0000000001
cas(8C, 7L) = 1292697.000000002
Les S_i peuvent se factoriser et l'algorithme doit être assez simple ...Code:for i in [2,3,4,5,6,7]: print (f"cas(8C, {i}L) = ", cas(8,i))
Dans C_7 - S_7, C_7 saute car S_7 = C_7 - .... f(S_6, ...)
Biname
Dernière modification par Biname ; 13/08/2023 à 19h57.
Je trouve comme toi avec ce code:
Je vais développer ma formule pour voir ce que je trouveCode:def formula(m, n): ... result = 1 ... for j in range(1, floor(m/2) + 1): ... for k in range(1, floor(n/2) + 1): ... result *= (4 * cos(pi * j / (m + 1))**2 + 4 * cos(pi * k / (n + 1))**2) ... return result ... >>> result = formula(6, 8) >>> print(result) 167089.0000000004
Dernière modification par Liet Kynes ; 13/08/2023 à 20h04.
Sans questions il n'y a que des problèmes sans réponses.
Salut,
Sauf erreurs, voici ce qu'on trouve pour S_7
Calculons S_7
pour "??????N" : C_7 cas
pour "x000000" : S_6 cas
pour "00x0000" : S_2 * S_4 cas
pour "000x000" : S_3² cas
pour "0000x00" : S_4 * S_2 cas
pour "000000x" : S_6 cas
pour "xx00000" : S_5 cas
pour "00xx000" : S_2 * S_3 cas
pour "000xx00" : S_3 * S_2 cas
pour "00000xx" : S_5 cas
pour "xxx0000" : S_4 cas
pour "0000xxx" : S_4 cas
pour "00xxx00" : S_2² cas
pour "xxxx000" : S_3 cas
pour "000xxxx" : S_3 cas
pour "xxxxx00" : S_2 cas
pour "00xxxxx" : S_2 cas
pour "xxxxxxx" : 1 cas
les autres "???????" = "xxxxxxx" ou "0000000" = S_7
pour "000000" = S_7 = C_7 - 2 * S_6 - 2 * S_5 - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_3²
- S_2² - 2 * S_2 * S_4 - 2 * S_2 * S_3 - 1
S_7 = C_7 - 2 * (S_6 + S_5 + S_4 + S_3 + S_2) - S_3² - S_2² - 2 * (S_2 * S_3 + S_2 * S_4) - 1
Qui sortira l'algorithme ? Moi, je vais Pythonner.
Biname
J'ai un petit doute, par exemple pour "00x0000" : S_2 * S_4 cas" mais il faut oter les cas déjà dans S2 et S4 non ? tu les as soustraits ?
Sans questions il n'y a que des problèmes sans réponses.
Liet msg #44
Dans mes valeurs de S_i
J'ai trouve une étrangeté
S_4 = C_4 - 2 * S_3 - 3 * S_2 - 1
normalement on a jamais 3 * S_i ? mais 2 * S_i ? Je ne vois pas l'erreur
et au mins une erreur, je crois que c'est ici, 2 * S_4 et non S_4
S_5 = C_5 - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_2² - 1
Biname
Quels cas ?
Tu as i cas sans route(S_?) dans le rectangle du haut et j cas sans routes(S_?) dans le rectangle du bas
P.S. 1
Au fond, oui peut-être ?????
P.S. 2
Non, S_i voir définition
Dernière modification par Biname ; 13/08/2023 à 20h28.
La partie difficile, c'est le dénombrement des pavages par dominos. Mais ça, c'est déjà connu.
Le reste, c'est la routine de la formule du crible de Poincaré pour calculer le cardinal de la réunion de L_i, où L_i est l'ensemble des configurations avec un chemin traversant horizontal en ligne n° i.
J'ai calculé en SageMath. C'est pratiquement du python, et avec un peu d'effort je pourrais traduire en code python pur.
[1, 1, 34, 153, 2245, 14824, 167089, 1292697]Code:# Nombre de pavages 8*n def Pav(n) : nb=1 for j in range(1,5) : nb *= prod(4*cos(j*pi/9)^2 + 4*cos(k*pi/(n+1))^2 for k in range(1,ceil(n/2)+1)) return round(nb) Pav=[Pav(n) for n in range(8)] Pav
463733Code:# Nombre de pavages 8*n avec chemin horizontal en lignes # de la liste L (numérotation des lignes de 0 à n-1) def PLH(L,n) : nb=Pav[L[0]] for i in range(len(L)-1) : nb *= Pav[L[i+1]-L[i]-1] nb *= Pav[n-1-L[-1]] return nb # Nombre de pavages 8*n avec au moins un chemin horizontal # (formule du crible de Poincaré) def H(n) : H=0 for k in range(n) : C=Combinations(range(n),k+1).list() H += (-1)^k * sum(PLH(L,n) for L in C) return H H(7)
Voilà les cas possibles de configurations différentes avec des lignes traversantes que je trouve, 16 configurations dont 3 sont symétriques (vert plus une croix = ligne traversante):
x x x x x x x
x 0 0 0 0 0 0
x x 0 0 0 0 0
x x x 0 0 0 0
x x x x 0 0 0
x x x x x 0 0
0 0 x 0 0 0 0
0 0 x x 0 0 0
1
0 0 x x x 0 0
x x x x 0 0 x
1
0 0 0 x 0 0 0
x x 0 0 x 0 0
x x x 0 0 x x
x x 0 0 0 0 x
x x x 0 0 0 x 1
x x 0 0 0 x x
Si je calcul pour la configuration suivante:
x x 0 0 x 0 0
Je commence par déterminer le de pavages sans ligne pour les deux groupes "00", un groupe 00 correspond au rectangle 2*8, pour ce rectangle on peut avoir la ligne 1 traversante ,la ligne 2 traversante et les deux lignes traversantes donc le nombre de pavages sans ligne traversantes est de 34-3=31 ensuite je combine les deux groupes "00" (donc sans ligne) et j'obtiens 31*31= 961 façons de paver de manière à ce que les ligne 1,2,5 soient traversantes.
je fait la même chose pour les autres configurations en sachant que la difficulté est de déterminer le pavage sans lignes traversantes , cela se complique très vite
Dernière modification par Liet Kynes ; 13/08/2023 à 20h51.
Sans questions il n'y a que des problèmes sans réponses.
Salut,
Avec les corrections je trouve
C_7 = 1292697.000000002
S_7 = 854901.0000000021
Cas Favorables C_7 - S_7 = 437796.0
Proba = (C_7 - S_7)/C_7 = 0.338668690342748
Sans la correction pour S_5, je trouve
C_7 = 1292697.000000002
S_7 = 850955.0000000021
Cas Favorables C_7 - S_7 = 441742.0
Proba = (C_7 - S_7)/C_7 = 0.3417212231481927
Python
Cliquez pour afficher
Code:S_1 = 0 S_2 = cas(m, 2) - 1 S_3 = cas(m, 3) - 2 * S_2 - 1 S_4 = cas(m, 4) - 2 * S_3 - 3 * S_2 - 1 # le 3* m'embête S_5 = cas(m, 5) - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_2**2 - 1 S_6 = cas(m, 6) - 2 * S_5 - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_2**2 - 2 * S_2 * S_3 - 1 S_7 = cas(m, 7) - 2 * S_6 - 2 * S_5 - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_3**2 - S_2**2 - 2 * S_2 * S_4 - 2 * S_2 * S_3 - 1 print ("C_7 = ",cas(m, 7)) print ("S_7 = ",S_7) print ("Cas Favorables C_7 - S_7 = ", cas(m, 7) - S_7) print ("Proba = (C_7 - S_7)/C_7 = ", (cas(m, 7) - S_7)/cas(m, 7))
Sauf erreurSSS
Sejam
GBZM,
Je me disais aussi avec mes petits dessins qu'un vrai matheux allait y reconnaître un cas connu.
Biname
Faut demander à GPT
Cliquez pour afficher
Code:import math from itertools import combinations def Pav(n): nb = 1 for j in range(1, 5): nb *= math.prod(4 * math.cos(j * math.pi / 9) ** 2 + 4 * math.cos(k * math.pi / (n + 1)) ** 2 for k in range(1, math.ceil(n / 2) + 1)) return round(nb) def PLH(L, n, Pav_list): nb = Pav_list[L[0]] for i in range(len(L) - 1): nb *= Pav_list[L[i + 1] - L[i] - 1] nb *= Pav_list[n - 1 - L[-1]] return nb def H(n): Pav_list = [Pav(n) for n in range(8)] print("Pav_list:", Pav_list) H_val = 0 for k in range(n): C = combinations(range(n), k + 1) H_val += (-1) ** k * sum(PLH(L, n, Pav_list) for L in C) return H_val result = H(7) print("Result:", result)
Echanges avec GPT
Cliquez pour afficher
User
Salut,
ChatGPT
Salut! Comment puis-je vous aider aujourd'hui?
User
Traduire de sagemath en python ?
ChatGPT
Bien sûr, je serais ravi de vous aider à traduire du code de SageMath en Python. N'hésitez pas à me fournir le code que vous souhaitez traduire, et je ferai de mon mieux pour vous aider.
User
# Nombre de pavages 8*n
def Pav(n) :
nb=1
for j in range(1,5) :
nb *= prod(4*cos(j*pi/9)^2 + 4*cos(k*pi/(n+1))^2
for k in range(1,ceil(n/2)+1))
return round(nb)
Pav=[Pav(n) for n in range(8)]
Pav
ChatGPT
Bien sûr, voici le code SageMath traduit en Python :
python
Assurez-vous d'avoir le module math importé pour les fonctions trigonométriques et la fonction prod. Le code Python produit la même liste de pavages que le code SageMath original.Code:import math def Pav(n): nb = 1 for j in range(1, 5): nb *= math.prod(4 * math.cos(j * math.pi / 9) ** 2 + 4 * math.cos(k * math.pi / (n + 1)) ** 2 for k in range(1, math.ceil(n / 2) + 1)) return round(nb) Pav_list = [Pav(n) for n in range(8)] print(Pav_list)
User
Et ceci aussi
# Nombre de pavages 8*n avec chemin horizontal en lignes
# de la liste L (numérotation des lignes de 0 à n-1)
def PLH(L,n) :
nb=Pav[L[0]]
for i in range(len(L)-1) :
nb *= Pav[L[i+1]-L[i]-1]
nb *= Pav[n-1-L[-1]]
return nb
# Nombre de pavages 8*n avec au moins un chemin horizontal
# (formule du crible de Poincaré)
def H(n) :
H=0
for k in range(n) :
C=Combinations(range(n),k+1).l ist()
H += (-1)^k * sum(PLH(L,n) for L in C)
return H
H(7)
ChatGPT
Bien sûr, voici le code SageMath traduit en Python :
python
Assurez-vous d'avoir le module math pour les calculs et le module itertools pour la fonction combinations. Le code Python produit le même résultat que le code SageMath original en calculant le nombre de pavages 8*n avec au moins un chemin horizontal selon la formule du crible de Poincaré.Code:import math from itertools import combinations def PLH(L, n, Pav): nb = Pav[L[0]] for i in range(len(L) - 1): nb *= Pav[L[i + 1] - L[i] - 1] nb *= Pav[n - 1 - L[-1]] return nb def H(n, Pav): H_val = 0 for k in range(n): C = combinations(range(n), k + 1) H_val += (-1) ** k * sum(PLH(L, n, Pav) for L in C) return H_val Pav = [Pav(n) for n in range(8)] result = H(7, Pav) print(result)
User
Possible de fusionner les deux codes ?
ChatGPT
Cela combine les fonctions Pav, PLH et H en un seul code, en calculant d'abord la liste de pavages Pav_list et en l'utilisant ensuite dans la fonction H. Le code produit toujours le même résultat que les codes originaux.Code:python import math from itertools import combinations def Pav(n): nb = 1 for j in range(1, 5): nb *= math.prod(4 * math.cos(j * math.pi / 9) ** 2 + 4 * math.cos(k * math.pi / (n + 1)) ** 2 for k in range(1, math.ceil(n / 2) + 1)) return round(nb) def PLH(L, n, Pav): nb = Pav[L[0]] for i in range(len(L) - 1): nb *= Pav[L[i + 1] - L[i] - 1] nb *= Pav[n - 1 - L[-1]] return nb def H(n): Pav_list = [Pav(n) for n in range(8)] H_val = 0 for k in range(n): C = combinations(range(n), k + 1) H_val += (-1) ** k * sum(PLH(L, n, Pav_list) for L in C) return H_val result = H(7) print(result)
User
Tu as oublié
Pav_list = [Pav(n) for n in range(8)]
print(Pav_list)
ChatGPT
Je m'excuse pour cet oubli. Voici le code corrigé en incluant la création et l'affichage de la liste Pav_list :
python
Maintenant, le code affiche la liste Pav_list avant de calculer le résultat de la fonction H.Code:import math from itertools import combinations def Pav(n): nb = 1 for j in range(1, 5): nb *= math.prod(4 * math.cos(j * math.pi / 9) ** 2 + 4 * math.cos(k * math.pi / (n + 1)) ** 2 for k in range(1, math.ceil(n / 2) + 1)) return round(nb) def PLH(L, n, Pav_list): nb = Pav_list[L[0]] for i in range(len(L) - 1): nb *= Pav_list[L[i + 1] - L[i] - 1] nb *= Pav_list[n - 1 - L[-1]] return nb def H(n): Pav_list = [Pav(n) for n in range(8)] print("Pav_list:", Pav_list) H_val = 0 for k in range(n): C = combinations(range(n), k + 1) H_val += (-1) ** k * sum(PLH(L, n, Pav_list) for L in C) return H_val result = H(7) print("Result:", result)
Et ça marche sortie python :
? 5 minutes ? Moins que pour rédiger ce msg. Tu aurais pu demander C++, HTML, et plein d'autres ... dont SageMathCode:Pav_list: [1, 1, 34, 153, 2245, 14824, 167089, 1292697] Result: 463733
Biname
Dernière modification par Biname ; 13/08/2023 à 21h54.
Liet msg #50,
Tu peux trouver ici un interpréteur python en ligne avec mon code domino python de référence (avec Poincaré) :
Si tu t'inscris, tu peux 'forker' ce code et en créer d'autres, c'est gratuit.
https://onlinegdb.com/E31SqcbHr
Je ne comprends pas pourquoi tu rejettes les symétriques ? Ca ne signifie pas que tu as tort
Biname
Plutôt que de jouer avec ChatGpt, il serait plus formateur de comprendre la formule du crible de Poincaré, comment elle intervient ici et dans pas mal d'autres problèmes.
Dernière modification par Liet Kynes ; 13/08/2023 à 23h08.
Sans questions il n'y a que des problèmes sans réponses.
Salut,
A mon âge, les formations !
Votre rejet de ChatGPT ou GPT est incompréhensible, voire pathologique ... mais bon. Il n'est pas bon à tout, mais pour écrire du code, il est devenu à mon avis indispensable, sauf dans le langage qu'on connait bien et encore, ce qui n'est pas mon cas pour Python.
Poincaré : https://www.techno-science.net/definition/6063.html
Crible de Poincaré : c'est la première fois que je vois une application pratique de la théorie des ensembles, je ne suis pas non plus une référence.
Il faut avoir fait les exercices pour se souvenir et comprendre, je lis tous, mais je ne vois pas comment ceci pourrait s'appliquer à notre cas. Je pourrais éventuellement faire un parallèle avec ton code, je vois (-1)^n chez les deux.
Merci
Biname
Tu peux expliquer pourquoi et comment tu raisonnes avec cette formule?
Un truc que je ne comprends pas c'est le fait que le pavage implique des règles implicites dans la formation des lignes traversantes, pour trouver tout les cas de lignes traversantes d'un rectangle 4*8 par exemple on ne peut pas dire qu'il y'en aura 2^4 car une traversante en position 2 ou en position 3 implique une traversante en position 1 ou en position 4, de même un écart de une case entre deux lignes traversantes implique que la ligne intermédiaire soit aussi traversante.
Sans questions il n'y a que des problèmes sans réponses.
Je trouve en excluant les symétries : 0.21946 (22%) avec les symétries 0.42158 (42%)
Détail du calcul dans le fichier joint
Sans questions il n'y a que des problèmes sans réponses.
Le problème n'est pas d'écrire du code (ce que ChatGpt peut faire), le problème est de comprendre ce que fait cette formule du crible et comment elle s'applique ici (et ça ChatGpt ne peut pas le faire à votre place !).
J'ai déjà donné l'essentiel, alors je répète en détaillant plus : soitl'ensemble des pavages par dominos de la grille 8x7. Je note
le sous-ensemble de
formé des pavages qui présentent un chemin traversant horizontal en ligne n°
(pour faire comme dans mon code, je numérote les lignes de 0 à 6).
La première chose à comprendre c'est que ce que l'on cherche à calculer, c'est le nombre d'éléments de la réunion despour
allant de 0 à 6. En effet, cette réunion est l'ensemble des pavages qui présentent au moins un chemin traversant horizontal. D'accord ?
C'est ici qu'intervient la formule du crible. Elle nous dit que le nombre d'éléments de cette réunion est la somme des nombres d'éléments des, moins la somme des nombres d'éléments de leurs intersections deux à deux, plus la somme des nombres d'éléments de leurs intersections trois à trois etc.
En formule,
où les barres désignent le cardinal d'un ensemble et.
Il reste à calculer ces. Je le fais sur l'exemple
. On a donc un chemin traversant en ligne 0, un autre en ligne 1, un autre en ligne 5. Au dessus de la ligne 0, on a un rectangle de largeur 8 et hauteur 0 : une seule façon de la paver !: Entre la ligne 0 et la ligne 1,un rectangle de largeur 0 et hauteur 8 : une seule façon de le paver. Entre la ligne 2 et la ligne 5, un rectangle de largeur 8 et hauteur 2 : 34 façons de le paver. Enfin en-dessous de la ligne 5, un rectangle de largeur 8 et hauteur 1 : une seule façon de paver. En conclusion, le nombre d'éléments de TEX]L_I[/TEX] est 1 x 1 x 34 x 1=34