un petit problème pour les vacances

[Liet Kynes]

@BINAME je pense que ton résultat est faux pour les "avec routes" pour n=7, GBZM trouve 463733

Perso j'ai affiné et fini par trouvé la bonne méthode mais pour n=6 je trouve 34340 et non 34168 ce qui fait que pour n=7 je trouve 463389

Je pense avoir une erreur dans mon calcul des routes traversantes avec n=6 mais je ne la trouve pas

@GBZM peux tu vérifier ton chiffre de 34168?

En PJ le calcul correct (sauf le 34168 que je ne trouve pas) sur tableur
-----

[Liet Kynes]

J'ai eu le code pour les combinaisons avec l'IA

Prompt;
n lampes sont disposées l'une à côté de l'autre, si l'avant dernière est allumée alors la dernière aussi, si la seconde est allumée alors la première aussi si entre deux lampes allumées il y a une seule lampe alors elle est allumée. génère un code pour calculer le nombre de combinaisons en fonction de n. Intègre au code la liste des combinaisons générées sous forme de 0 et 1.
Il faut que la liste puisse être copiée vers un tableur.

def lamp_combinations(n):
    # Générer toutes les combinaisons possibles
    combinations = [bin(i)[2:].zfill(n) for i in range(2**n)]
    
    # Vérifier chaque combinaison
    valid_combinations = []
    for combination in combinations:
        valid = True
        for i in range(n):
            # Si l'avant dernière est allumée alors la dernière aussi
            if i == n-2 and combination[i] == '1' and combination[i+1] == '0':
                valid = False
                break
            # Si la seconde est allumée alors la première aussi
            if i == 1 and combination[i] == '1' and combination[0] == '0':
                valid = False
                break
            # Si entre deux lampes allumées il y a une seule lampe alors elle est allumée
            if i > 0 and i < n-1 and combination[i-1] == '1' and combination[i+1] == '1' and combination[i] == '0':
                valid = False
                break
        if valid:
            valid_combinations.append(combination)
    
    return len(valid_combinations), valid_combinations

# Test du code avec n=7
num_combinations, combinations_list = lamp_combinations(7)
print("Nombre de combinaisons valides :", num_combinations)
for combination in combinations_list:
    print(combination)

[Liet Kynes]

Bon j'ai repris le code pour vérifier 34168 et c'est bien cela donc j'ai une erreur dans mon tableur que je vais finir pas trouver..

>>> from math import cos, pi, prod
>>> from itertools import combinations
>>>
>>> # 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, (n//2)+1)])
...     return round(nb)
...
>>> # Générer la liste Pav pour n allant de 0 à 7
>>> Pav = [Pav(n) for n in range(8)]
>>>
>>> # 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, 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
...
>>> # Nombre de pavages 8*n avec au moins un chemin horizontal
>>> # (formule du crible de Poincaré)
>>> def H(n, Pav):
...     H = 0
...     for k in range(n):
...         C = list(combinations(range(n), k + 1))
...         H += (-1) ** k * sum(PLH(L, n, Pav) for L in C)
...     return H
...
>>> print(H(6, Pav))
34168

[GBZM]

C'est bizarre cette obstination à se compliquer la vie, alors que l'application directe de l'inclusion-exclusion est vraiment sans problème !
Biname, tes résultats sont faux à partir de 7 lignes.

[Biname]

J'ai repris le problème avec la méthode que j'avais envisagé. Je prends une à une les combinaisons pour lesquelles au moins une ligne est présente parmi les n lignes, le nombre de combinaisons se définit selon https://oeis.org/A077855

Si j'utilise les résultats des calculs avec la formule du crible je trouve 511333 cas favorables soit 511333/1292697= 0.3955

Pour 7 lignes il y a 36 combinaisons avec des lignes traversantes.

Si les lignes 3,4 sont traversantes, on devrais avoir pour cette combinaison (mise en évidence dans la liste ci-dessous):

- nombre de pavages possibles des lignes 1 et 2 = 34
- nombre de pavages possibles des lignes 5,6 et 7 = 153

D'après les résultats de la formule du crible donnés plus haut par GBZM:

- nombre de pavage sans lignes traversantes parmi les 34 = 1
- nombre de pavage sans lignes traversantes parmi les 153= 67

Soit pour cette combinaison ((34*153)*(67*1))=5135

0011000

Pour ta ligne en rouge, mon code donne

dec: 24 = bin:0011000 OK=1 2Z:1 = avec:33 sans[2]^1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=2838

sans[] est la liste de la récurrence de nombre de cas sans lignes dans i=0 à 7 lignes pour C=8
Pour L=7, la liste sans(0 à 7) = [0, 0, 33, 86, 1973, 9398, 132921] (récurrence avec/sans routes)
OK la ligne est valide, elle ne contient pas de zéros isolés
2Z:1 1 est le nombre de double zéros = "00" isolés et lit dans la liste sans[] l'élément sans[2] élevé à la puissance du nombre de "00" comptés
3Z:1 ... itou
au total il y a 33^1 * 86^1 = 2838 pavages contenant cette combinaison de routes bin:0011000 sans autres routes que en 3 et en 4 par respect de la notation binaire bit_index(6543210)
...

Biname

[Liet Kynes]

C'est bizarre cette obstination à se compliquer la vie, alors que l'application directe de l'inclusion-exclusion est vraiment sans problème !
Biname, tes résultats sont faux à partir de 7 lignes.

La méthode que j'utilise avec le tableur est-elle plus courte que celle du crible? Il faut générer les nombres binaires et compter les groupes de 0 (si 1 symbolise un chemin traversant) puis les formules intermédiaires sont assez simples.

Est ce que la formule du crible va permettre de dire combien de pavages il y a avec des chemins traversants en ligne 3 et 4 pour une grille 7*8?

[Liet Kynes]

Pour ta ligne en rouge, mon code donne

dec: 24 = bin:0011000 OK=1 2Z:1 = avec:33 sans[2]^1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=2838

sans[] est la liste de la récurrence de nombre de cas sans lignes dans i=0 à 7 lignes pour C=8
Pour L=7, la liste sans(0 à 7) = [0, 0, 33, 86, 1973, 9398, 132921] (récurrence avec/sans routes)
OK la ligne est valide, elle ne contient pas de zéros isolés
2Z:1 1 est le nombre de double zéros = "00" isolés et lit dans la liste sans[] l'élément sans[2] élevé à la puissance du nombre de "00" comptés
3Z:1 ... itou
au total il y a 33^1 * 86^1 = 2838 pavages contenant cette combinaison de routes bin:0011000 sans autres routes que en 3 et en 4 par respect de la notation binaire bit_index(6543210)
...

Biname

J'ai fais un mauvais copié collé, la formule est ((34-1)*(153-67))=2838 (je multiplie par 2 pour intégré la symétrie dans le fichier)

[GBZM]

Je répète une nouvelle fois.
1) il est facile de dire combien il y a de pavages en dominos présentant des chemins traversants horizontaux en lignes n° (et éventuellement des chemins traversants horizontaux ailleurs). Ici ce n'est pas la formule du crible qui intervient, c'est juste le comptage (en fonction de ) du nombre de pavages par dominos d'un rectangle ayant 8 colonnes et lignes.
2) À partir de là, l'application directe de la formule du crible permet de calculer, sans se casser la tête et sans faire d'erreurs, le nombre de pavages par dominos présentant au moins un chemin traversant horizontal.

Mais bien sûr, pourquoi faire simple quand on peut faire compliqué ?

[Biname]

Salut,

C'est bizarre cette obstination à se compliquer la vie, alors que l'application directe de l'inclusion-exclusion est vraiment sans problème !
Biname, tes résultats sont faux à partir de 7 lignes.

Pourquoi les miens et pas les tiens ? IIRC en 8 ça redevient bon

J e m ' a m u s e ! Et toi ?

Le principe d'inclusion-exclusion, j'ai compris. J'ai dû étudier ça il y a mille ans ???

 Cliquez pour afficher

Bref, au delà de 3 ensembles, il faut un code.

En bas de mon code main de python, il y a ceci :

 Cliquez pour afficher

''' GBZM
P(8,7) = 463733/1292697
n lignes et 8 colonnes, où n varie de 0 à 19 :
0,
1,
1,
67,
272,
5426,
34168,
463733,
3558245,
40423745,
341774922,
3543203530,
31430594248,
310092581147,
2815096255711,
27009936374613,
247773142270344,
2338769967876768,
21540614004729318,
201292564878142083
Ça te permettra de vérifier tes calculs.
'''

Biname

[Biname]

Je répète une nouvelle fois.
1) il est facile de dire combien il y a de pavages en dominos présentant des chemins traversants horizontaux en lignes n° (et éventuellement des chemins traversants horizontaux ailleurs). Ici ce n'est pas la formule du crible qui intervient, c'est juste le comptage (en fonction de ) du nombre de pavages par dominos d'un rectangle ayant 8 colonnes et lignes.
2) À partir de là, l'application directe de la formule du crible permet de calculer, sans se casser la tête et sans faire d'erreurs, le nombre de pavages par dominos présentant au moins un chemin traversant horizontal.

Mais bien sûr, pourquoi faire simple quand on peut faire compliqué ?

Est-ce que tu lis ce qu'on écrit ? Tu veux gagner la guerre ... mais quelle guerre

Biname

[Liet Kynes]

Bon ben perso j'ai trouvé mon erreur et j'obtiens quelque chose de juste sans avoir besoin d'utiliser de code, en tout cas pour le grille 8*7 , mêmes résultats que GBZM
Il faut juste un peu de méthode pour établir les combinaisons et écrire les nombres binaires mais cela reste faisable "à la main".

Voir le fichier en PJ qui est définitif

[Biname]

J'ai fais un mauvais copié collé, la formule est ((34-1)*(153-67))=2838 (je multiplie par 2 pour intégré la symétrie dans le fichier)

34-1 = 33, 153-63 = 86 sont les valeurs clés de mon algorithme, obtenues par récurrence et placées dans la liste sans[0 à 7]
que voici : sans(0 à 7) : [0, 0, 33, 86, 1973, 9398, 132921]
pour 1111100 tu as 33     = sans[2 = nbr de zéros successifs]  cas avec uniquement ces 5 routes et aucune autres
pour 1111000 tu as 86     = sans[3 = nbr de zéros successifs]  cas avec uniquement ces 4 routes et aucune autres
pour 1110000 tu as 1976   = sans[4 = nbr de zéros successifs]  cas avec uniquement ces 5 routes et aucune autres

pour 0011000 tu as 33 = sans[2 = nbr de zéros successifs] * sans[3 = nbr de zéros successifs]  cas avec uniquement ces 2 routes et aucune autres
pour 0011100 tu as 33 = sans[2 = nbr de zéros successifs] * sans[2 = nbr de zéros successifs]  cas avec uniquement ces 3 routes et aucune autres
                                  = sans[2 = nbr de zéros successifs] ^ 2  cas avec uniquement ces 3 routes et aucune autres

on élève sans[nombre_de _zeros] à la puissance du nombre de "n_zero" trouvés

Exercice :
Cas 001000100010010000100   sans[2]^3  * sans[3]^2 * sans[4]^1 = 33^3 * 86^2 *1973^1 =  524403772596 cas 
cas avec uniquement ces 5 routes et aucune autres.

[GBZM]

"Pourquoi les miens et pas les tiens ? "
Parce que la méthode que j'utilise est bête comme chou, ce qui permet d'écrire un petit code facilement vérifiable et d'éviter les erreurs. Tout simplement.

[Biname]

Salut,
En comparant avec l'ods OK de Liet, je trouve cette
Erreur de mon code
dec: 73 = bin:1001001 OK=1 2Z:1 = avec:33 sans[2]^1 n_tot_avec_route=33 ****
devrait être
dec: 73 = bin:1001001 OK=1 2Z:1 = avec:33 sans[2]^2 n_tot_avec_route=1089 ****

462677 - 33 + 1089 = 463733

Belle unanimité !

Pourtant il en a trouvé d'autres
dec: 8 = bin:0001000 OK=1 3Z:2 = avec:7396 sans[3]^2 n_tot_avec_route=7396
dec: 19 = bin:0010011 OK=1 2Z:2 = avec:1089 sans[2]^2 n_tot_avec_route=1089
...

Pourquoi pas celui-là ? P.S. parce que le "1" central appartient aux deux pattern, c'est le seul cas pour cette série, 100010001 pose le même problème

 Cliquez pour afficher

Voici le code qui doit être fautif ? On va trouver ?

def get_pattern_count(i_zero, binary_number):
    count = 0
    n_zero = "0" * i_zero
    # cas "10001" dans le nombre binaire avec n zero
    count += binary_number.count("1" + n_zero + "1") 
    # cas "1000" à droite avec n zero
    if binary_number[:i_zero + 1] == n_zero + "1":
        count += 1
    # cas "0001" à gauche avec n zero
    if binary_number[-(i_zero + 1):] == "1" + n_zero:
        count += 1

     return count

100010001 devrait aussi poser probleme.
Je vais demander à GPT de creer un code qui teste cette fonction !

def get_pattern_count(i_zero, binary_number):
    count = 0
    n_zero = "0" * i_zero
    # cas "10001" dans le nombre binaire avec n zero
    count += binary_number.count("1" + n_zero + "1") 
    # cas "1000" à droite avec n zero
    if binary_number[:i_zero + 1] == n_zero + "1":
        count += 1
    # cas "0001" à gauche avec n zero
    if binary_number[-(i_zero + 1):] == "1" + n_zero:
        count += 1

    return count

test_cases = [("1001001", 2), ("100010001", 3), ("00100100100", 2)]

for binary_number, i_zero in test_cases:
    result = get_pattern_count(i_zero, binary_number)
    print(f"Binary Number: {binary_number}, i_zero: {i_zero}  |  Result: {result}")

Sortie:
Binary Number: 1001001, i_zero: 2 | Result: 1
Binary Number: 100010001, i_zero: 3 | Result: 1
Binary Number: 00100100100, i_zero: 2 | Result: 3

Ce sont les "1" isoles entre deux pattern identiques qui posent pb, le find next pointe sur le "0" derrière le "1" ...
CQFD, c'est un pb de code.

Biname

[Liet Kynes]

Si on est d'accord, on peut passer à l'idée de chiralité des grilles = le fait de dire que pour une grille avec 7 lignes uniquement des chemins traversants en ligne 3 et 4 est la même grille qu'uniquement des chemins traversants en lignes 4 et 5.

Dans ce cas, avec la méthode que j'ai utilisé, je ne coéficiente plus les combinaisons et la proba tombe à 258021/1292697=0.1995

Que donne la formule du crible selon cette considération ?

[GBZM]

La probabilité n'a plus grand sens alors ! Surtout si tu comptes les pavages avec chemin traversant horizontal modulo symétrie d'axe horizontal et que tu continues à compter les pavages en général sans tenir compte de la symétrie.
Bref, ça devient un peu n'importe quoi (Excuse moi si je suis un peu brutal).
Ce qui peut faire sens, c'est de commencer par compter les pavages en dominos d'un rectangle modulo les symétries de ce rectangle (axe horizontal, axe vertical, demi-tour). Mais ça, ça paraît bien coton.

[Liet Kynes]

Je ne comprends pas ce que tu veux dire: je parle de chiralité entre deux grilles, pas de la chiralité au sein d'une même grille:

[Biname]

Salut,

"Pourquoi les miens et pas les tiens ? "
Parce que la méthode que j'utilise est bête comme chou, ce qui permet d'écrire un petit code facilement vérifiable et d'éviter les erreurs. Tout simplement.

Je voulais aller au bout de ma méthode. Oui, le "crible" est la bonne voie, mais il fallait __voir__ qu'elle s'appliquait à notre cas, ce que je ne vois pas encore très bien, il me faudrait creuser ...
L'erreur de la fonction pattern, c'est moi qui ai demandé à GPT de simplifier en utilisant le "Tally" du basic, GPT fait ce qu'on lui demandes, même s'il sait qu'il fait une erreur, JAMAIS il ne dit "vous vous trompez", ... les lois d'Azimov, vla que j'y pense !

Il serait amusant de récapituler les étapes de la progression vers ta solution qui est sortie très tôt. Ma version :

• Miss Jenny #1 08-12:56 pose le problème

• Miss Jenny #5 08-20:01 réduit le problème à un pavage domino "sans les chiffres sur les dominos"

• Liet #9 09-19:58 fait une recherche en français avec "pavage domino"

• Biname #9 10-02:10 fait la même recherche en anglais avec "domino tilling/tile/tilings " dénombrement est acquis formule PI PI:
  

• Biname #15 10 10:54 dénombre les cas = cas_dessus * cas_en_dessous
  

• Liet #24 12-07:57 essayes de compter le nombre de routes possibles

• Liet #25 12-08:54 petits dessins symbolisant les cas

• Biname #27 12-11:32 lache innocemment "exclure toutes les routes sauf"

• Biname #37 13-17:28 ma méthode récurrente et notation horizontale

• GBZM #39 13-18:53 le laconique "La probabilité demandée est ."

• GBZM #49 13-20:48 code SageMath OK (traduction en python par GPT #53 13-21:52)

Le problème est résolu.

Biname

[Biname]

Salut,
Voici le nombre de cas donné par mon code corrigé pour tous les cas de route dans une grille(7L,8C)

 Cliquez pour afficher

L=7 liste sans(0 à 7) : [0, 0, 33, 86, 1973, 9398, 132921] (récurrence avec/sans routes)
dec: 0 = bin:0000000 OK=0 none single zero = 0000000
dec: 1 = bin:0000001 OK=1 6Z:1 = avec:132921 sans[6]^1 n_tot_avec_route=132921
dec: 2 = bin:0000010 OK=0 none single zero = 0000011
dec: 3 = bin:0000011 OK=1 5Z:1 = avec:9398 sans[5]^1 n_tot_avec_route=9398
dec: 4 = bin:0000100 OK=1 2Z:1 = avec:33 sans[2]^1 4Z:1 = avec:1973 sans[4]^1 n_tot_avec_route=65109
dec: 5 = bin:0000101 OK=0 none single zero = 0000111
dec: 6 = bin:0000110 OK=0 none single zero = 0000111
dec: 7 = bin:0000111 OK=1 4Z:1 = avec:1973 sans[4]^1 n_tot_avec_route=1973
dec: 8 = bin:0001000 OK=1 3Z:2 = avec:7396 sans[3]^2 n_tot_avec_route=7396
dec: 9 = bin:0001001 OK=1 2Z:1 = avec:33 sans[2]^1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=2838
dec: 10 = bin:0001010 OK=0 none single zero = 0001111
dec: 11 = bin:0001011 OK=0 none single zero = 0001111
dec: 12 = bin:0001100 OK=1 2Z:1 = avec:33 sans[2]^1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=2838
dec: 13 = bin:0001101 OK=0 none single zero = 0001111
dec: 14 = bin:0001110 OK=0 none single zero = 0001111
dec: 15 = bin:0001111 OK=1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=86
dec: 16 = bin:0010000 OK=1 2Z:1 = avec:33 sans[2]^1 4Z:1 = avec:1973 sans[4]^1 n_tot_avec_route=65109
dec: 17 = bin:0010001 OK=1 2Z:1 = avec:33 sans[2]^1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=2838
dec: 18 = bin:0010010 OK=0 none single zero = 0010011
dec: 19 = bin:0010011 OK=1 2Z:2 = avec:1089 sans[2]^2 n_tot_avec_route=1089
dec: 20 = bin:0010100 OK=0 none single zero = 0011100
dec: 21 = bin:0010101 OK=0 none single zero = 0011111
dec: 22 = bin:0010110 OK=0 none single zero = 0011111
dec: 23 = bin:0010111 OK=0 none single zero = 0011111
dec: 24 = bin:0011000 OK=1 2Z:1 = avec:33 sans[2]^1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=2838
dec: 25 = bin:0011001 OK=1 2Z:2 = avec:1089 sans[2]^2 n_tot_avec_route=1089
dec: 26 = bin:0011010 OK=0 none single zero = 0011111
dec: 27 = bin:0011011 OK=0 none single zero = 0011111
dec: 28 = bin:0011100 OK=1 2Z:2 = avec:1089 sans[2]^2 n_tot_avec_route=1089
dec: 29 = bin:0011101 OK=0 none single zero = 0011111
dec: 30 = bin:0011110 OK=0 none single zero = 0011111
dec: 31 = bin:0011111 OK=1 2Z:1 = avec:33 sans[2]^1 n_tot_avec_route=33
dec: 32 = bin:0100000 OK=0 none single zero = 1100000
dec: 33 = bin:0100001 OK=0 none single zero = 1100001
dec: 34 = bin:0100010 OK=0 none single zero = 1100011
dec: 35 = bin:0100011 OK=0 none single zero = 1100011
dec: 36 = bin:0100100 OK=0 none single zero = 1100100
dec: 37 = bin:0100101 OK=0 none single zero = 1100111
dec: 38 = bin:0100110 OK=0 none single zero = 1100111
dec: 39 = bin:0100111 OK=0 none single zero = 1100111
dec: 40 = bin:0101000 OK=0 none single zero = 1111000
dec: 41 = bin:0101001 OK=0 none single zero = 1111001
dec: 42 = bin:0101010 OK=0 none single zero = 1111111
dec: 43 = bin:0101011 OK=0 none single zero = 1111111
dec: 44 = bin:0101100 OK=0 none single zero = 1111100
dec: 45 = bin:0101101 OK=0 none single zero = 1111111
dec: 46 = bin:0101110 OK=0 none single zero = 1111111
dec: 47 = bin:0101111 OK=0 none single zero = 1111111
dec: 48 = bin:0110000 OK=0 none single zero = 1110000
dec: 49 = bin:0110001 OK=0 none single zero = 1110001
dec: 50 = bin:0110010 OK=0 none single zero = 1110011
dec: 51 = bin:0110011 OK=0 none single zero = 1110011
dec: 52 = bin:0110100 OK=0 none single zero = 1111100
dec: 53 = bin:0110101 OK=0 none single zero = 1111111
dec: 54 = bin:0110110 OK=0 none single zero = 1111111
dec: 55 = bin:0110111 OK=0 none single zero = 1111111
dec: 56 = bin:0111000 OK=0 none single zero = 1111000
dec: 57 = bin:0111001 OK=0 none single zero = 1111001
dec: 58 = bin:0111010 OK=0 none single zero = 1111111
dec: 59 = bin:0111011 OK=0 none single zero = 1111111
dec: 60 = bin:0111100 OK=0 none single zero = 1111100
dec: 61 = bin:0111101 OK=0 none single zero = 1111111
dec: 62 = bin:0111110 OK=0 none single zero = 1111111
dec: 63 = bin:0111111 OK=0 none single zero = 1111111
dec: 64 = bin:1000000 OK=1 6Z:1 = avec:132921 sans[6]^1 n_tot_avec_route=132921
dec: 65 = bin:1000001 OK=1 5Z:1 = avec:9398 sans[5]^1 n_tot_avec_route=9398
dec: 66 = bin:1000010 OK=0 none single zero = 1000011
dec: 67 = bin:1000011 OK=1 4Z:1 = avec:1973 sans[4]^1 n_tot_avec_route=1973
dec: 68 = bin:1000100 OK=1 2Z:1 = avec:33 sans[2]^1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=2838
dec: 69 = bin:1000101 OK=0 none single zero = 1000111
dec: 70 = bin:1000110 OK=0 none single zero = 1000111
dec: 71 = bin:1000111 OK=1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=86
dec: 72 = bin:1001000 OK=1 2Z:1 = avec:33 sans[2]^1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=2838
dec: 73 = bin:1001001 OK=1 2Z:2 = avec:1089 sans[2]^2 n_tot_avec_route=1089 ndlr : ici était l'erreur
dec: 74 = bin:1001010 OK=0 none single zero = 1001111
dec: 75 = bin:1001011 OK=0 none single zero = 1001111
dec: 76 = bin:1001100 OK=1 2Z:2 = avec:1089 sans[2]^2 n_tot_avec_route=1089
dec: 77 = bin:1001101 OK=0 none single zero = 1001111
dec: 78 = bin:1001110 OK=0 none single zero = 1001111
dec: 79 = bin:1001111 OK=1 2Z:1 = avec:33 sans[2]^1 n_tot_avec_route=33
dec: 80 = bin:1010000 OK=0 none single zero = 1110000
dec: 81 = bin:1010001 OK=0 none single zero = 1110001
dec: 82 = bin:1010010 OK=0 none single zero = 1110011
dec: 83 = bin:1010011 OK=0 none single zero = 1110011
dec: 84 = bin:1010100 OK=0 none single zero = 1111100
dec: 85 = bin:1010101 OK=0 none single zero = 1111111
dec: 86 = bin:1010110 OK=0 none single zero = 1111111
dec: 87 = bin:1010111 OK=0 none single zero = 1111111
dec: 88 = bin:1011000 OK=0 none single zero = 1111000
dec: 89 = bin:1011001 OK=0 none single zero = 1111001
dec: 90 = bin:1011010 OK=0 none single zero = 1111111
dec: 91 = bin:1011011 OK=0 none single zero = 1111111
dec: 92 = bin:1011100 OK=0 none single zero = 1111100
dec: 93 = bin:1011101 OK=0 none single zero = 1111111
dec: 94 = bin:1011110 OK=0 none single zero = 1111111
dec: 95 = bin:1011111 OK=0 none single zero = 1111111
dec: 96 = bin:1100000 OK=1 5Z:1 = avec:9398 sans[5]^1 n_tot_avec_route=9398
dec: 97 = bin:1100001 OK=1 4Z:1 = avec:1973 sans[4]^1 n_tot_avec_route=1973
dec: 98 = bin:1100010 OK=0 none single zero = 1100011
dec: 99 = bin:1100011 OK=1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=86
dec:100 = bin:1100100 OK=1 2Z:2 = avec:1089 sans[2]^2 n_tot_avec_route=1089
dec:101 = bin:1100101 OK=0 none single zero = 1100111
dec:102 = bin:1100110 OK=0 none single zero = 1100111
dec:103 = bin:1100111 OK=1 2Z:1 = avec:33 sans[2]^1 n_tot_avec_route=33
dec:104 = bin:1101000 OK=0 none single zero = 1111000
dec:105 = bin:1101001 OK=0 none single zero = 1111001
dec:106 = bin:1101010 OK=0 none single zero = 1111111
dec:107 = bin:1101011 OK=0 none single zero = 1111111
dec:108 = bin:1101100 OK=0 none single zero = 1111100
dec:109 = bin:1101101 OK=0 none single zero = 1111111
dec:110 = bin:1101110 OK=0 none single zero = 1111111
dec:111 = bin:1101111 OK=0 none single zero = 1111111
dec:112 = bin:1110000 OK=1 4Z:1 = avec:1973 sans[4]^1 n_tot_avec_route=1973
dec:113 = bin:1110001 OK=1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=86
dec:114 = bin:1110010 OK=0 none single zero = 1110011
dec:115 = bin:1110011 OK=1 2Z:1 = avec:33 sans[2]^1 n_tot_avec_route=33
dec:116 = bin:1110100 OK=0 none single zero = 1111100
dec:117 = bin:1110101 OK=0 none single zero = 1111111
dec:118 = bin:1110110 OK=0 none single zero = 1111111
dec:119 = bin:1110111 OK=0 none single zero = 1111111
dec:120 = bin:1111000 OK=1 3Z:1 = avec:86 sans[3]^1 n_tot_avec_route=86
dec:121 = bin:1111001 OK=1 2Z:1 = avec:33 sans[2]^1 n_tot_avec_route=33
dec:122 = bin:1111010 OK=0 none single zero = 1111111
dec:123 = bin:1111011 OK=0 none single zero = 1111111
dec:124 = bin:1111100 OK=1 2Z:1 = avec:33 sans[2]^1 n_tot_avec_route=33
dec:125 = bin:1111101 OK=0 none single zero = 1111111
dec:126 = bin:1111110 OK=0 none single zero = 1111111
dec:127 = bin:1111111 OK=1 nZ=0_count=1 cas=1

debug_3 : L=7 cas(8,7)=1292697 n_tot=463733 sans_lignes : [0, 0, 33, 86, 1973, 9398, 132921, 828964]
Nombre de pavages de 0 à 7 : [1, 1, 34, 153, 2245, 14824, 167089, 1292697]
sans_lignes_list de 0 à 7 : [0, 0, 33, 86, 1973, 9398, 132921, 828964]
avec_lignes_list de 0 à 7 : [0, 1, 1, 67, 272, 5426, 34168, 463733]
proba avec lignes de 0 à 7 : ['1.0000', '1.0000', '0.0294', '0.4379', '0.1212', '0.3660', '0.2045', '0.3587']

Grille(8,7) pav_possibles=1292697
pav_sans_routes=828964 pav_avec_routes=463733
probalilité au moins une route = 0.3587
Done in 0.0302 seconde


Format csv
i, sans_routes, avec_routes, proba, pav possibles
0, 0, 0, 1.0000, 1
1, 0, 1, 1.0000, 1
2, 33, 1, 0.0294, 34
3, 86, 67, 0.4379, 153
4, 1973, 272, 0.1212, 2245
5, 9398, 5426, 0.3660, 14824
6, 132921, 34168, 0.2045, 167089
7, 828964, 463733, 0.3587, 1292697


*** FINISHED ***

Mes résultats pour Grille([17,18,19], 8) diffèrent encore très légèrement de ceux de GBZM

2338769967876768,       moi:   2338769967876770  ...768 >> ...770    +2
21540614004729318,      moi:  21540614004729320  ...318 >> ...320    +2
201292564878142083      moi: 201292564878142304  ...083 >> ...304  +221

Tous nos résultats :

 Cliquez pour afficher

''' GBZM
P(8,7) = 463733/1292697
n lignes et 8 colonnes, où n varie de 0 à 19 :
0,
1,
1,
67,
272,
5426,
34168,
463733,
3558245,
40423745,
341774922,
3543203530,
31430594248,
310092581147,
2815096255711,
27009936374613,
247773142270344,
2338769967876768,       moi:   2338769967876770  ...768 >> ...770    +2
21540614004729318,      moi:  21540614004729320  ...318 >> ...320    +2
201292564878142083      moi: 201292564878142304  ...083 >> ...304  +221
Ça te permettra de vérifier tes calculs. 

Résultats Code Biname corrigé OK ?
Format csv
  i,         sans_routes,         avec_routes,   proba,       pav possibles
  0,                   0,                   0,  1.0000,                   1
  1,                   0,                   1,  1.0000,                   1
  2,                  33,                   1,  0.0294,                  34
  3,                  86,                  67,  0.4379,                 153
  4,                1973,                 272,  0.1212,                2245
  5,                9398,                5426,  0.3660,               14824
  6,              132921,               34168,  0.2045,              167089
  7,              828964,              463733,  0.3587,             1292697
  8,             9430571,             3558245,  0.2739,            12988816
  9,            68012000,            40423745,  0.3728,           108435745
 10,           689376319,           341774922,  0.3314,          1031151241
 11,          5397536294,          3543203530,  0.3963,          8940739824
 12,         51310411581,         31430594248,  0.3799,         82741005829
 13,        421071672686,        310092581147,  0.4241,        731164253833
 14,       3860401981419,       2815096255711,  0.4217,       6675498237130
 15,      32544264094500,      27009936374613,  0.4535,      59554200469113
 16,     292288144266578,     247773142270344,  0.4588,     540061286536922
 17,    2502340065789280,    2338769967876770,  0.4831,    4841110033666050
 18,   22212118568369040,   21540614004729320,  0.4923,   43752732573098360
 19,  191846580248680992,  201292564878142304,  0.5120,  393139145126823296
'''

Biname

[GBZM]

Biname : tu oublies de dire dans ton historique que ma seule contribution est la remarque que, à partir du moment où on sait compter le nombre de pavages par dominos d'un rectangle, compter le nombre de pavages présentant un chemin horizontal traversant est une simple application directe de la formule du crible de Poincaré. le code est accessoire, c'est juste la mise en oeuvre de cette remarque.

Voici un code python abondamment commenté :

from math import cos, pi, prod
from itertools import combinations

# Le but est de calculer le nombre de pavages par dominos 
# qui ont 2*P colonnes et au plus N-1 lignes et qui présentent 
# au moins un chemin traversant horizontal (constitué uniquement 
# de dominos horizontaux).

N=10 ; P=4

# Nombre de pavages à n lignes et 2*P colonnes (formule connue)
def Pav(n):
    nb = 1
    for j in range(P):
        nb *= prod([4*cos((j+1)*pi/(2*P+1))**2 + 4*cos(k*pi/(n+1))**2\
                    for k in range(1, (n//2)+1)])
    return round(nb)

# Générer la liste Pav du nombre de pavages par dominos
# pour n allant de 0 à N-1

Pav = [Pav(n) for n in range(N)]

# Étant donné une liste I de numéros de lignes
# (dans l'ordre croissant, enttre 0 et n-1), on compte
# le nombre de pavages à n lignes et 2*P colonnes 
# avec chemin traversant horizontal en lignes dont les n°
# sont dans la liste I (numérotation des lignes de 0 à n-1).
# Il peut y avoir d'autres chemins traversants horizontaux 
# sur des lignes dont le numéro n'est pas dans I.

def PLH(I, n):
    nb = Pav[I[0]]  # nombre de pavages du rectangle au dessus de 
    # la première ligne de la liste
    for i in range(len(I) - 1):         
        nb *= Pav[I[i + 1] - I[i] - 1] # multiplier par le nombre de
        # pavages du rectangle entre deux lignes successives 
        # de la liste
    nb *= Pav[n - 1 - I[-1]] # multiplier par le nombre de pavages
    # du rectangle en-dessous de la dernière ligne de la liste
    return nb

# Nombre de pavages à n lignes et 2*P colones avec au moins un 
# chemin traversant horizontal. C'est le nombre d'éléments de la
# réunion des L_i où L_i est l'ensemble des pavages présentant un 
# chemin traversant horizontal en ligne n°i (et éventuellement 
# d'autres chemins traversants horizontaux ailleurs).
# Le calcul du nombre d'éléments de cette réunion se fait par
# une application directe de la formule du crible de Poincaré.

def H(n):
    H = 0
    for k in range(n):
        C = list(combinations(range(n), k + 1)) # On fait la liste 
        # des parties à k+1 éléments de {0,...,n-1}. Chacune de ces 
        # parties se présente comme une liste I ordonnée dans l'ordre
        # croissant et peut donc entrer comme argument dans la fonction
        # PLH(I,n) qui donne le nombre d'éléments de 
        # l'intersection des L_i pour i dans I (ingrédient de la 
        # formule du crible)
        H += (-1) ** k * sum(PLH(I, n) for I in C)
    return H

Une mise en garde : ce code va donner un résultat faux à partir de 16 lignes. C'est la "faute de Python" qui calcule la formule donnant le nombre de pavages avec des flottants pas assez précis.
Les résultats donnés par SageMath sont, eux, corrects (au moins jusqu'à 19. Je l'ai vérifié en utilisant une autre formule pour ce nombre de pavages qui passe par un calcul exact (sans flottants) et utilise un résultant de deux polynômes de Tchebychev. Un peu lourd à implémenter en Python, mais en SageMath pas de problème, voici le code :

R.<x>=PolynomialRing(QQ,'x')
def Pavbis(n) :
    return sqrt(abs(chebyshev_U(8,I*x/2).resultant(chebyshev_U(n,x/2))))

Je te laisse le soin de demander à ChatGPT de traduire en Python ....

[Liet Kynes]

Il serait amusant de récapituler les étapes de la progression vers ta solution qui est sortie très tôt. Ma version :

• Liet #135 20-08 09:55: Propose d'envisager de ne pas compter deux fois les grilles qui possèdent une chiralité du point de vue des chemins traversants et donne une probabilité de 0.1995

[GBZM]

En fait Biname, tu te heurtes au même problème : Python fait du calcul approché et se goure dans l'évaluation de la formule du nombre de pavages pour un nombre de lignes pas très petit (à partir de 16).

[GBZM]

Liet, tu n'as pas compris ma remarque : ta probabilité ne fait pas sens puisqu'au numérateur (cas favorables) tu comptes les pavages modulo symétrie et qu'au dénominateur (tous les cas) tu les comptes sans prendre en compte la symétrie !

[Biname]

GBZM:
Biname : tu oublies de dire dans ton historique que ma seule contribution est la remarque que, à partir du moment où on sait compter le nombre de pavages par dominos d'un rectangle, compter le nombre de pavages présentant un chemin horizontal traversant est une simple application directe de la formule du crible de Poincaré. le code est accessoire, c'est juste la mise en oeuvre de cette remarque.

msg #???

Quelle message t'a fait pensé au crible ?

Traduction code SageMath par GPT : en 1 minutes, pas testé.

from sympy import symbols, sqrt, chebyshev_U, I
from sympy.polys.polytools import resultant

def Pavbis(n):
    x = symbols('x')
    chebyshev_8 = chebyshev_U(8, I * x / 2)
    chebyshev_n = chebyshev_U(n, x / 2)
    result = sqrt(abs(resultant(chebyshev_8, chebyshev_n)))
    return result

[Biname]

En fait Biname, tu te heurtes au même problème : Python fait du calcul approché et se goure dans l'évaluation de la formule du nombre de pavages pour un nombre de lignes pas très petit (à partir de 16).

Oui, la précision des "doubles" ... mais normalement ...
201292564878142083 moi: 201292564878142304 ...083 >> ...304 +221 18 chiffres significatifs.
??? on ne va pas tout résoudre dans ce fil.

[Liet Kynes]

Liet, tu n'as pas compris ma remarque : ta probabilité ne fait pas sens puisqu'au numérateur (cas favorables) tu comptes les pavages modulo symétrie et qu'au dénominateur (tous les cas) tu les comptes sans prendre en compte la symétrie !

Je ne sais pas, dans mon tableur il est possible de faire le distinguo et d'ajuster les cas favorables. Je met les deux tableaux en PJ. J'ai tenu compte de ces ajustements et j'obtiens 270719/1292697

[GBZM]

msg #???

#49 (mon deuxième message, juste après l'annonce du résultat :

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.

Quelle message t'a fait pensé au crible ?

Quel message m'a fait penser au crible ? Aucun, ça s'impose et ça devient réalisable à partir du moment où on sait compter le nombre de pavages par dominos d'un rectangle. Ça oui, je l'ai appris en regardant le fil.

201292564878142083 moi: 201292564878142304 ...083 >> ...304 +221 18 chiffres significatifs. ???

Pas compris. Peux-tu décoder ?

Merci pour le code python. J'ai dû le modifier pour qu'il marche :

from sympy import symbols, sqrt, I
from sympy.polys.polytools import resultant
from sympy.polys.orthopolys import chebyshevu_poly

def PAVbis(n):
    x = symbols('x')
    chebyshev_8 = chebyshevu_poly(8, I * x / 2)
    chebyshev_n = chebyshevu_poly(n, x / 2)
    result = sqrt(abs(resultant(chebyshev_8, chebyshev_n)))
    return result

Avec ce calcul du nombre de pavages, on obtient les résultats corrects. Pour un nombre de lignes de 16 à 19, on a :
540061286536921, 4841110033666048, 43752732573098281, 393139145126822985
tandis qu'avec l'évaluation en python de la formule à cosinus, chez moi :
540061286536923, 4841110033666074, 43752732573098472, 393139145126824256
Ç déconne à partir de 17 lignes, et de plus en plus après.

[GBZM]

Liet, comment te l'expliquer ?
Prenons ton exemple (sauf qu'il n'est pas de la bonne dimension, mais c'est pour te faire comprendre) : au numérateur, tu le comptes une fois dans tes 258021 pavages favorables à symétrie près. Au dénominateur tu le comptes deux fois dans tes 1292697 pavages de grille 7x8, puisqu'il s'agit de deux pavage différents.
Tu trouves ça correct comme façon de calculer une proba ?

[Liet Kynes]

Liet, comment te l'expliquer ?
Prenons ton exemple (sauf qu'il n'est pas de la bonne dimension, mais c'est pour te faire comprendre) : au numérateur, tu le comptes une fois dans tes 258021 pavages favorables à symétrie près. Au dénominateur tu le comptes deux fois dans tes 1292697 pavages de grille 7x8, puisqu'il s'agit de deux pavage différents.
Tu trouves ça correct comme façon de calculer une proba ?

Oui j'ai modifié la façon de procéder dans ma dernière pièce jointe.. mais c'est pas encore cela à priori.

Mais l'idée reste de considérer la grille comme un plateau de jeu de société, physiquement si je fais tous les pavages possibles, parmi ceux qui sont favorables, la majorité peut être considérée comme comptée 2 fois (si je regarde le plateau depuis un côté ou de l'autre). Le problème est que dans les pavages non favorables le même problème existe, je n'y avais pas pensé, pour autant est-ce que le fait qu'il n'est peut-être pas possible de dénombrer les "doubles" dans les pavages sans chemins traversants rend les résultats que nous avons totalement pertinents ?

[GBZM]

Les résultats sont totalement pertinents puisqu'ils répondent à la question de MissJenny.
Tu peux poser une autre question,mais alors il faut que tu commences à compter les pavages à demi-tour près. Et ça, ça n'a pas l'air coton. Peut-être en examinant attentivement la démonstration de la formule de comptage de pavages ?