un petit problème pour les vacances

[Merlin95]

@LK toujours pas.

À quoi servent les chiffres dans ce jeu puisqu'il n'y a pas vraiment de règles dessus (les dominos sont indicetnrnables puisque tous sont de cotés 1x2), ou alors j'ai loupé quelque chose ?
-----

[Biname]

Oui, la solution a été trouvée msg #39 et #49 mais il faudra lire plus pour comprendre !
Mon historique n'est peut être pas inutile :

• 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 Difficile : dénombrement, après code SageMath OK (traduction en python #53 13-21:52)

Biname

[Merlin95]

Ok merci pour cette synthèse.

[GBZM]

Je ne sais pâs pourquoi, mais Biname a un gros problème pour écrire que la résolution de la question, une fois connue la partie difficile qui est le dénombrement des pavages par dominos auxquels on n'impose aucune condition, est une application immédiate de la formule du crible de Poincaré (ou principe d'inclusion-exclusion).
Je lui ai déjà signalé, mais il ne peut pas s'y résoudre

[Biname]

Je ne sais pâs pourquoi, mais Biname a un gros problème pour écrire que la résolution de la question, une fois connue la partie difficile qui est le dénombrement des pavages par dominos auxquels on n'impose aucune condition, est une application immédiate de la formule du crible de Poincaré (ou principe d'inclusion-exclusion).
Je lui ai déjà signalé, mais il ne peut pas s'y résoudre

Le dernier message (#49) de l'historique est celui où tu expliques tout ça !
Il n'est pas interdit de publier un historique modifié.

[Liet Kynes]

Je ne sais pâs pourquoi, mais Biname a un gros problème pour écrire que la résolution de la question, une fois connue la partie difficile qui est le dénombrement des pavages par dominos auxquels on n'impose aucune condition, est une application immédiate de la formule du crible de Poincaré (ou principe d'inclusion-exclusion).
Je lui ai déjà signalé, mais il ne peut pas s'y résoudre

Le problème c'est que c'est une résolution en orientant la question pour être valide.

Je remet donc ici la question de MissJenny:

je voudrais soumettre à la sagacité des forumeurs un petit problème que je pense être assez difficile.
je joue assez souvent à un jeu appelé "dominosa". Un jeu de 28 dominos (le jeu standard) est disposé sur un plateau à 8x7 cases, et les bordures des dominos sont effacées (on ne voit plus que les chiffres). Le jeu consiste à reconstituer les positions des dominos.

Quand on a résolu le problème, on voit qu'il y a deux sortes de configuration : celles où une "rue" rectiligne apparaît qui traverse tout le tableau, et celles où il n'y a pas de telle traversée. Les images jointes montrent les deux types de configuration.

En supposant que toutes les configurations sont équiprobables, peut-on calculer la probabilité qu'il y ait au moins une traversée rectiligne?

indice (qui n'en est pas vraiment un) : il me semble que Wendelin Werner a étudié des problèmes similaires.

je précise que je ne connais pas la réponse.

Cela implique que l'on ne peut pas ne pas tenir compte du fait qu'un jeu de plateau ne s'observe pas que depuis l'un de ses bords et un seul : une position aux échecs reste la même, que l'on joue avec les noirs ou avec les blancs.

Cela dit ce qui est trouvé pour l'instant demande à être affiné et le plateau donné est de 7*8 ce qui n'est pas énorme.

[Liet Kynes]

Un lien qui donne une partie du contexte : http://villemin.gerard.free.fr/Pavag...oMi.htm#soluce

[Biname]

Liet msg186,

Cela implique que l'on ne peut pas ne pas tenir compte du fait qu'un jeu de plateau ne s'observe pas que depuis l'un de ses bords et un seul : une position aux échecs reste la même, que l'on joue avec les noirs ou avec les blancs.

Mon code peut résoudre ton pb de mirror assez facilement.

Cela dit ce qui est trouvé pour l'instant demande à être affiné et le plateau donné est de 7*8 ce qui n'est pas énorme.

Les codes résolvent ça en fonction de L lignes et C colonnes (C pair), si c'est la question que tu poses.

Avec ceci tout est pré calculé pour C de 2 à 24 et L de 1 à 20/24, on pourrait passer en notation scientifique, mais c'est moins rigolo

 Cliquez pour afficher

def get_tot_pav_count(L, C):            # C pair   de 2 à 24    et    L de 1 à 24    mp64 64 = décimales  # récurrence precaculée
# exemples
L=7;C=8
print(f"cas({L},{C}) = {get_tot_pav_count(L,C)}")
L=24;C=24
print(f"cas({L},{C}) = {get_tot_pav_count(L,C)}")
print 

def get_count_sans_route(L, C):         # C pair   de 2 à 24    et    L de 1 à 20    mp64 64 = décimales
#exemples :
L=2;C=8
print(f"sans_route({L},{C}) = {get_count_sans_route(L, C)}")
L=20;C=24
print(f"sans_route({L},{C}) = {get_count_sans_route(L, C)}")

Pour des valeurs élevées de C et de L le temps de calcul est divisé par ?10000. Il fallait IIRC 7 secondes de calcul pour une liste sans_route ?

A inclure dans un code python

 Cliquez pour afficher

def get_tot_pav_count(L, C): # C pair de 2 à 24 et L de 1 à 24 mp64 64 = décimales
cas = [[0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025], [0, 1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061, 51205, 145601, 413351, 1174500, 3335651, 9475901, 26915305, 76455961, 217172736, 616891945, 1752296281, 4977472781, 14138673395, 40161441636], [0, 1, 13, 41, 281, 1183, 6728, 31529, 167089, 817991, 4213133, 21001799, 106912793, 536948224, 2720246633, 13704300553, 69289288909, 349519610713, 1765722581057, 8911652846951, 45005025662792, 227191499132401, 1147185247901449, 5791672851807479, 29242880940226380], [0, 1, 34, 153, 2245, 14824, 167089, 1292697, 12988816, 108435745, 1031151241, 8940739824, 82741005829, 731164253833, 6675498237130, 59554200469113, 540061286536921, 4841110033666048, 43752732573098280, 393139145126822976, 3547073578562248192, 31910388243436818432, 287665106926232829952, 2589464895903294291968, 23333526083922816925696], [0, 1, 89, 571, 18061, 185921, 4213133, 53175517, 1031151241, 14479521761, 258584046368, 3852472573499, 65743732590821, 1012747193318519, 16848161392724968, 264499788583572512, 4337452956682508800, 68829675768134025216, 1119577238373960908800, 17874911934649248776192, 289415868852204579323904, 4636763679433683600670720, 74879006808407274833313792, 1202001705294409615208873984, 19382410440110541833689366528], [0, 1, 233, 2131, 145601, 2332097, 106912793, 2188978117, 82741005829, 1937528668711, 65743732590821, 1666961188795475, 53060477521960000, 1412218550274852608, 43242613716069408768, 1185802123987680231424, 35457442115448211505152, 990424779934371806183424, 29185565059934260478083072, 824590653947610216854978560, 24080710136742581358112538624, 685180756689863670880706494464 , 198984090103398175096407830036 48, 568656710189250388280007865663 488, 164577256636171299946774454138 30656], [0, 1, 610, 7953, 1174500, 29253160, 2720246633, 90124167441, 6675498237130, 259423766712000, 16848161392724970, 722364079570222336, 43242613716069408768, 1974622635952709566464, 112202208776036179509248, 5338532535620005189910528, 293251198441417299606896640, 14334395712551020987554988032, 770166905309440525238085353472 , 383212143607115305198581322874 88, 202925625366709503659551141081 9072, 102158525916518679226428353106 935808, 535828298775050696982040999295 4511360, 271840117338896029965580742743 361060864, 141689018831701838002814181634 81959464960], [0, 1, 1597, 29681, 9475901, 366944287, 69289288909, 3710708201969, 540061286536921, 34741645659770712, 4337452956682508800, 313196612952258183168, 35457442115448211505152, 2764079753958605105135616, 293251198441417299606896640, 24080184063411168531038863360, 244488877025089277888130396979 2, 208052155041922490815062306979 840, 204983052302257188441486104062 85312, 178778606191653150449766983417 2006400, 172539486039611536146601260573 400236032, 153062978200912979155580088502 83382177792, 145632503280407557866133121232 7997260431360, 130721650285998974133330593908 683831842439168, 123159019756165838502227514554 60163164250832896], [0, 1, 4181, 110771, 76455961, 4602858719, 1765722581057, 152783289861989, 43752732573098280, 4652799879944138752, 1119577238373960908800, 135818983640055284760576, 29185565059934260478083072, 3870940598132705563076722688, 770166905309440525238085353472 , 108711792217836883982550527115 264, 204983052302257188441486104062 85312, 302397264845308990107683029622 4038912, 548943583215388372205723455281 495539712, 835753389133842666081989054134 84033343488, 147667121698033340066223987111 66344091402240, 229958418214813991600608769388 5784797592158208, 398527001518856158664618965084 036910231549116416, 630772181843406655127995653873 18897568107091460096, 107811057472647014823459470476 82950071027260201107456], [0, 1, 10946, 413403, 616891945, 57737128904, 45005025662792, 6290652543875133, 3547073578562248192, 623139489426439798784, 289415868852204579323904, 58902468764522024737439744, 24080710136742581358112538624, 542206591613212664730501093785 6, 202925625366709503659551141081 9072, 490984130367164831394055000468 488192, 172539486039611536146601260573 400236032, 439834203244515688975997043185 24245671936, 147667121698033340066223987111 66344091402240, 391122269677601288964650060977 5944283853946880, 126998401125623580601732356367 6759532051128909824, 346013281079871746327829041531 446340501158011863040, 109623091622343592016443641813 801447289467924551565312, 304979977004326071604470186964 28933543571235311108227072, 948853726307991626541932743513 3404512743336232513628536832], [0, 1, 28657, 1542841, 4977472781, 724240365697, 1147185247901449, 259009513044645824, 287665106926232829952, 83456125990631339196416, 74879006808407274833313792, 25545661075321868421393547264, 198984090103398175096407830036 48, 759533805919360600070439932683 8784, 535828298775050696982040999295 4511360, 221788093470479632510847568947 0703697920, 145632503280407557866133121232 7997260431360, 639959951198183484950984816169 236489979297792, 398527001518856158664618965084 036910231549116416, 183146623325178302063074788902 287004943715850518528, 109623091622343592016443641813 801447289467924551565312, 521087566210454442207494587192 05276510786857054614061056, 302737004922316013061661792858 35642485274205289929164980224, 147633564567162629807367665319 332075658840005865506186345840 64, 838593524181795466365159308869 343961990947144547268538329464 8320], [0, 1, 75025, 5757961, 40161441636, 9084693297025, 29242880940226380, 10664383939345915904, 23333526083922816925696, 11177167872295391509610496, 19382410440110541833689366528, 110791032578937703928386048491 52, 164577256636171299946774454138 30656, 106400456827687657528266865421 61379328, 141689018831701838002814181634 81959464960, 100194941822184982026876827459 59750180012032, 123159019756165838502227514554 60163164250832896, 931307222092221623091356563336 1207594616761614336, 107811057472647014823459470476 82950071027260201107456, 857867271800031551749792147031 9821719401854947551084544, 948853726307991626541932743513 3404512743336232513628536832, 785127665819840170243142945781 588776321614252747223017612902 4, 838593524181795466365159308869 343961990947144547268538329464 8320, 715160288838589811774517750997 251516386590971965057428485052 9828864, 743577567912292261921820113796 635673822034917478324998812793 6879788032]]
return int(cas[round(C/2) - 1][L])
L=7;C=8
print(f"cas({L},{C}) = {get_tot_pav_count(L,C)}")
L=24;C=24
print(f"cas({L},{C}) = {get_tot_pav_count(L,C)}")
print
def get_count_sans_route(L, C): # C pair de 2 à 24 et L de 1 à 20 mp64 64 = décimales
sans = [[0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1], [0, 0, 4, 2, 19, 18, 95, 126, 492, 802, 2617, 4868, 14197, 28772, 78104, 167386, 433867, 964366, 2426003, 5522178, 13624880], [0, 0, 12, 16, 212, 518, 4115, 13384, 83943, 319606, 1766536, 7357544, 37902856, 166198900, 822819453, 3715938912, 17986277429, 82610947860, 394755659072, 1830704020392, 8684135841264], [0, 0, 33, 86, 1973, 9398, 132921, 828964, 9430571, 68012000, 689376319, 5397536294, 51310411581, 421071672686, 3860401981419, 32544264094500, 292288144266577, 2502340065789280, 22212118568368962, 191846580248680895, 1691579703538198900], [0, 0, 88, 394, 17008, 142626, 3782264, 41709440, 886601656, 11350808416, 213917769179, 2987718244292, 52530853003951, 772679782591832, 13041217131128051, 197862720420451699, 3259382101021328868, 50378542065746810716, 817954361662591054992, 12784101511069825851280, 205777970313944032229604], [0, 0, 232, 1666, 141572, 1989202, 101567352, 1908192816, 76993475776, 1698679745462, 60063732674464, 1460043276177032, 47688921829148991, 1231326506260167467, 38294816744799512120, 1027042510075407191064, 30977491152595708540180, 850969727923995057828664, 25177097849193481908529212, 702203030620016245816935668, 20524936591934531182208365896], [0, 0, 609, 6734, 1159204, 26541232, 2654341920, 83247097214, 6448339072183, 241171345239240, 16130940415244416, 672828720579586022, 41077857338274647755, 1838504386621932182777, 105840449717532065020158, 4961864322773133015577400, 274874871748119433861473194, 13288289035527614767738481327, 717709639406673442012764934347 , 354116229254236809466443743492 59, 188077706234029645266365684190 9674], [0, 0, 1596, 26488, 9418136, 345474950, 68477779324, 3541645167270, 531072551450852, 33337806471330935, 4246666693101177369, 301237451345893298564, 34582431856276447263252, 2660679323370691638966900, 285045925045459960022665220, 23177922008885777918415325980, 236928606384596653332399628023 2, 200134157964082215367091194316 788, 198099959427259948241542680665 49864, 171806541911187090603101303395 5850719, 166326055239503888114720532458 341287185], [0, 0, 4180, 102410, 76238600, 4432585168, 1755719699580, 148607731434494, 43395538363142779, 4543990340742349041, 1108011965998324181396, 132901165295822478647204, 28829084110904485264047976, 3791385927397915949648778812, 759488511075936621450181305556 , 106519429343007022284166552767 624, 201841969580123891492872605053 70024, 296312306584433379854961988669 1584915, 539816962382918315020891161559 296963389, 818783762541869952011706977421 27014296092, 145038287719543593408399939436 71756290730376], [0, 0, 10945, 391512, 616076085, 56383965392, 44881478306224, 6187052352540954, 3532805672125552674, 614643604002380223471, 287931450862164687965750, 58183324387296332021432649, 23934117914345847448239357314, 536007905508994737449443242905 8, 201520844648598726903822909957 7057, 485577985043624989208338666598 758406, 171218647424136354560866980787 972934188, 435080876459535018414776414980 14162558105, 146441005694104330118280389514 46926423251948, 386918912116397193885166892131 7940335442277491, 125870426985881347515163650968 8015575888033354179], [0, 0, 28656, 1485528, 4974415756, 713465796640, 1145655784895764, 256428480320214895, 287092254748064531593, 82788470739533105263792, 74687078802063045206210064, 25366835505347968802594454528, 198375745720704919136749713823 76, 754649421305592400336984229374 5856, 533960458632753895618867063537 9909224, 220437065599878500298489181007 1856405855, 145070380051267380306189057487 8299155655761, 636190010836281309170139263098 586019292346832, 396857879992053855404475315791 157042625635071264, 182087918472083600184109285199 754525957751935110264, 109132130813882629348878892295 703896045143716857502996], [0, 0, 75024, 5607912, 40150000739, 8998747571138, 29223904630493614, 10599850539086294601, 23310419520504420632316, 11124411642986377989673991, 19357431796924345256441345147, 110343024874136751817173051660 99, 164322721429504733967124853316 90069, 106011916040795340905094961802 83529037, 141438261108979163613443327214 72422295396, 998534376170513853310292380965 4172456623772, 122917163440649307622585438080 73380415295703403, 928277557420347309376132275736 0021294375196148565, 107581070677898022300890734197 65971942443478082986195, 855161096543725690342488116411 1292878093151858492089640, 946688358274817320384379218080 1549108261641023765298379629]]
return int(sans[round(C/2) - 1][L])
L=2;C=8
print(f"sans_route({L},{C}) = {get_count_sans_route(L, C)}")
L=20;C=24
print(f"sans_route({L},{C}) = {get_count_sans_route(L, C)}")

Sauf erreurssss

Biname

[GBZM]

Cela implique que l'on ne peut pas ne pas tenir compte du fait qu'un jeu de plateau ne s'observe pas que depuis l'un de ses bords et un seul :

Non, cela n'implique absolument pas. Tu tiens à tordre le problème, mais MissJenny parle bien de configurations et pas de configurations à symétrie près. Tu poses un autre problème, soit, mais le problème posé par Miss Jenny a été complètement résolu.
Ton argument avec le jeu d'échec est d'ailleurs assez bancal : vu les règles, la position avec un seul pion noir avancé et toutes les pièces blanches à leur place est impossible.

Biname, tu dis "Mon code peut résoudre ton pb de mirror assez facilement." Tu sais compter les pavages à symétrie près ? J'aimerais bien voir ça.

[Biname]

Biname, tu dis "Mon code peut résoudre ton pb de mirror assez facilement." Tu sais compter les pavages à symétrie près ? J'aimerais bien voir ça.

Nombre de cas sans ligne avec Mirror horizontal oui !
Est-ce que tu peux m'écrire un élément d'un ensemble qui entre dans le crible pour L7 et C8 ... par ebzemple.
Biname

[Liet Kynes]

[QUOTE=GBZM;7124661
Ton argument avec le jeu d'échec est d'ailleurs assez bancal : vu les règles, la position avec un seul pion noir avancé et toutes les pièces blanches à leur place est impossible.
[/QUOTE]

Tu as les blancs, tu joues e4 et tu n'as pas la force de retourner le plateau de façon à avoir les noirs ?

[gg0]

Bizarre, ce que tu racontes, Liet Kynes ! Manifestement, tu n'as rien compris à ce que disait GBZM. Retourner le plateau ne change pas la couleur des pièces.
Le jeu d'échec n'est pas un jeu symétrique.

[Liet Kynes]

Bizarre, ce que tu racontes, Liet Kynes ! Manifestement, tu n'as rien compris à ce que disait GBZM. Retourner le plateau ne change pas la couleur des pièces.
Le jeu d'échec n'est pas un jeu symétrique.

On s'en fiche de la couleur des pièces, on s'attarde juste au fait que des cases soient occupées par elles.

[GBZM]

Nombre de cas sans ligne avec Mirror horizontal oui !

Il peut le faire !!!
Tu rigoles, Biname ?
Je n'ai toujours rien vu. Explique ce que tu comptes, et comment tu le comptes.
Je te demande si tu sais compter le nombre de pavages par dominos d'une grille m x n modulo symétrie (des pavages différents mais images l'un de l'autre par une symétrie du rectangle ne comptent que pour un). Après, compter modulo symétrie les pavages avec ou sans chemin traversant, c'est de la routine.

Est-ce que tu peux m'écrire un élément d'un ensemble qui entre dans le crible pour L7 et C8 ... par ebzemple.

Heu, ça veut dire quoi ? C'est marrant, tu me fais penser à un certain B....e qui s'exprime souvent de façon aussi claire que toi.

[Biname]

Il peut le faire !!!
Tu rigoles, Biname ?
Je n'ai toujours rien vu. Explique ce que tu comptes, et comment tu le comptes.
Je te demande si tu sais compter le nombre de pavages par dominos d'une grille m x n modulo symétrie (des pavages différents mais images l'un de l'autre par une symétrie du rectangle ne comptent que pour un). Après, compter modulo symétrie les pavages avec ou sans chemin traversant, c'est de la routine.

Heu, ça veut dire quoi ? C'est marrant, tu me fais penser à un certain B....e qui s'exprime souvent de façon aussi claire que toi.

Et mon élément ? Tu en es incapable ? Donne-moi un élément d'un de ces ensembles. Ce sont bien des ensembles, qui comme tous les ensembles sont composés d'éléments, qui entrent dans le crible ?

Biname

[gg0]

On s'en fiche de la couleur des pièces, on s'attarde juste au fait que des cases soient occupées par elles.

Comme quoi, tu n'as rien compris à ce que disait GBZM. Merci de confirmer ! Mais peut-être ne connais-tu pas non plus les échecs (c'est toi qui en as parlé) ?

[GBZM]

Que veut dire "un ensemble qui entre dans le crible pour L7 et C8 " ?
Tu veux parler par exemple de l'ensemble des pavages qui on un chemin traversant de dominos horizontaux en ligne n° 4 ?
Facile : le pavage où tous les dominos sont horizontaux. (Celui-ci, il est même dans tous les pour allant de 0 à 7).

Ma réponse n'a pas plus d'intérêt que ta question, mais elle est exacte.
Si tu voulais demander autre chose, exprime-toi plus clairement.

J'ai répondu à ta question, pourrais-tu répondre à la mienne , que je rappelle :

Je te demande si tu sais compter le nombre de pavages par dominos d'une grille m x n modulo symétrie (des pavages différents mais images l'un de l'autre par une symétrie du rectangle ne comptent que pour un).

[Liet Kynes]

Comme quoi, tu n'as rien compris à ce que disait GBZM. Merci de confirmer ! Mais peut-être ne connais-tu pas non plus les échecs (c'est toi qui en as parlé) ?

L'idée c'est de bien définir l'univers dont on parle, on considère que pour que chaque pavage soit équiprobable, il faut qu'il ne soit pas le "retourné" d'un 1/4 ou 1/2 tour d'un autre. Cela correspond à la figure en #174 (4 figures représente un seul et même pavage). Dans le dénombrement que nous avons utilisé, les 4 sont comptés.Désolé si l'exemple des échecs est mal adapté.

[GBZM]

En regardant la page de Gérard Villemin mise en lien par Liet Kynes, j'ai compris que nous avons sans doute fait fausse route depuis le début dans l'interprétation de la question de Miss Jenny.
Dans un pavage par dominos, les dominos sont des pâtés de maisons et les frontières entre les dominos des voies de circulation. Comme à New-York, une rue est une voie de circulation qui traverse en ligne droite le grillage de gauche à droite, et une avenue une voie de circulation qui traverse en ligne droite le grillage de bas en haut. Ce que Gérard Villemin appelle "pavage sans faute" est un pavage sans rue ni avenue.
À relire le message de Miss Jenny, je suis persuadé que c'est de ça qu'il est question.

Il n'est pas difficile de calculer le nombre de pavages sans rue ni avenue, toujours à l'aide de la formule du crible de Poincaré. Il s'agit ici, à l'aide de cette formule, de calculer le nombres d'éléments de la réunion des ensembles L_i de pavages présentant une rue entre la ligne i et la ligne i+1 (i allant de 0 à n-2) et des ensembles C_j de pavages présentant une avenue entre la colonne j et la colonne j+1 (j allant de 0 à p-2).

Voici un code python - non commenté - qui fait ça :

rom sympy import symbols, sqrt, I
from sympy.polys.polytools import resultant
from sympy.polys.orthopolys import chebyshevu_poly
from math import prod
from itertools import combinations

def PAVrec(n,p):
    x=symbols('x')
    chebyshev_p = chebyshevu_poly(p, I * x / 2)
    chebyshev_n = chebyshevu_poly(n, x / 2)
    result = sqrt(abs(resultant(chebyshev_p, chebyshev_n,x)))
    return result

def PRA(I,J,n,p,P) :
    nb=1
    If=I+[n-1] ; Jf=J+[p-1]
    derl=-1
    for i in If :
        derc=-1
        for j in Jf :
            nb *= P[i-derl][j-derc]
            derc=j
        derl=i
    return nb

def SANSRUEAVE(n,p) :
    P=[[PAVrec(i,j) for j in range(p+1)] for i in range(n+1)]
    S = 0
    Truc=[]
    for k in range(n+p-1):
        C = list(combinations(range(n+p-2), k))
        for K in C :
            I=[] ; J=[]
            for i in K :
                if i<n-1 :
                    I=I+[i]
                else :
                    J=J+[i-n+1]
            cont = PRA(I,J,n,p,P)
            S += ((-1) ** k) * cont
    return S

Les pavages sans rue ni avenue sont relativement peu nombreux :

SANSRUEAVE(7,8)

13514

[GBZM]

on considère que pour que chaque pavage soit équiprobable, il faut qu'il ne soit pas le "retourné" d'un 1/4 ou 1/2 tour d'un autre.

Je ne vois aucune logique à considérer ça.
Par exemple, considère la situation suivante : on colorie au hasard les sommets d'un carré en bleu ou en rouge. Si on veut que les coloriages soient équiprobables, faut-il compter pour un seul les quatre coloriages avec un sommet rouge et les autres bleus, vu qu'ils se correspondent par symétrie de rotation du carré ?

[Liet Kynes]

Je ne vois aucune logique à considérer ça.
Par exemple, considère la situation suivante : on colorie au hasard les sommets d'un carré en bleu ou en rouge. Si on veut que les coloriages soient équiprobables, faut-il compter pour un seul les quatre coloriages avec un sommet rouge et les autres bleus, vu qu'ils se correspondent par symétrie de rotation du carré ?

Ton univers serait

r

r

r

r

b

r

r

r

r

r

r

b

r

r

b

r

r

b

r

r

b

b

r

r

b

r

r

b

r

r

b

b

r

b

b

r

b

b

b

r

b

b

r

b

b

r

b

b

r

b

b

b

b

r

b

r

r

b

r

b

b

b

b

b

tandis que je restreint à :

r	r	r	r
b	r	r	r
b	b	r	r
b	b	b	r
b	r	b	r
b	b	b	b

Sommes nous d'accord la dessus ?

[GBZM]

Oui, et quand on parle d'équiprobabilité, le premier univers à 2^4=16 éléments est bien évidemment beaucoup plus naturel. (on tire au hasard la couleur de chaque sommet.

[Liet Kynes]

Il faut donc d'abord définir parfaitement l'évènement que l'on considère. Si la grille possède des coordonnées ou pas.

[Biname]

Pour une grille L7 C8, le total des pavages possibles présentant au moins une route en ne comptant qu'une fois les grilles possédant un symétrique horizontale est de : 241396 contre 463733 pour tous les pavages présentant au moins une route.

 Cliquez pour afficher

pour L=7 et C=8
                                              Total des cas avec au moins une route :     463733
                           Total des cas avec au moins une route sans les miroirs H :     241396

Temps de calcul :   2.00 ms
Temps de  print :   2.11 ms
Temps     total :   4.12 ms


pour L=15 et C=16
                                   Total des cas avec au moins une route :     902262054525389707703742292
                Total des cas avec au moins une route sans les miroirs H :     458798674561709253370390936

Temps de calcul : 1023.55 ms
Temps de  print : 132.98 ms
Temps     total : 1156.53 ms

Sauf erreurss ...
Biname

[Biname]

En regardant la page de Gérard Villemin mise en lien par Liet Kynes, j'ai compris que nous avons sans doute fait fausse route depuis le début dans l'interprétation de la question de Miss Jenny.
Dans un pavage par dominos, les dominos sont des pâtés de maisons et les frontières entre les dominos des voies de circulation. Comme à New-York, une rue est une voie de circulation qui traverse en ligne droite le grillage de gauche à droite, et une avenue une voie de circulation qui traverse en ligne droite le grillage de bas en haut. Ce que Gérard Villemin appelle "pavage sans faute" est un pavage sans rue ni avenue.
À relire le message de Miss Jenny, je suis persuadé que c'est de ça qu'il est question.

Il n'est pas difficile de calculer le nombre de pavages sans rue ni avenue, toujours à l'aide de la formule du crible de Poincaré. Il s'agit ici, à l'aide de cette formule, de calculer le nombres d'éléments de la réunion des ensembles L_i de pavages présentant une rue entre la ligne i et la ligne i+1 (i allant de 0 à n-2) et des ensembles C_j de pavages présentant une avenue entre la colonne j et la colonne j+1 (j allant de 0 à p-2).

Voici un code python - non commenté - qui fait ça :

rom sympy import symbols, sqrt, I
from sympy.polys.polytools import resultant
from sympy.polys.orthopolys import chebyshevu_poly
from math import prod
from itertools import combinations

def PAVrec(n,p):
    x=symbols('x')
    chebyshev_p = chebyshevu_poly(p, I * x / 2)
    chebyshev_n = chebyshevu_poly(n, x / 2)
    result = sqrt(abs(resultant(chebyshev_p, chebyshev_n,x)))
    return result

def PRA(I,J,n,p,P) :
    nb=1
    If=I+[n-1] ; Jf=J+[p-1]
    derl=-1
    for i in If :
        derc=-1
        for j in Jf :
            nb *= P[i-derl][j-derc]
            derc=j
        derl=i
    return nb

def SANSRUEAVE(n,p) :
    P=[[PAVrec(i,j) for j in range(p+1)] for i in range(n+1)]
    S = 0
    Truc=[]
    for k in range(n+p-1):
        C = list(combinations(range(n+p-2), k))
        for K in C :
            I=[] ; J=[]
            for i in K :
                if i<n-1 :
                    I=I+[i]
                else :
                    J=J+[i-n+1]
            cont = PRA(I,J,n,p,P)
            S += ((-1) ** k) * cont
    return S

Les pavages sans rue ni avenue sont relativement peu nombreux :

SANSRUEAVE(7,8)

13514

Une avenue faite de 7 cases pavées avec des dominos de deux cases, c'est fort.

Par contre des avenues dans l'espace laissé par des routes, c'est faisable, avec le crible et mon code.

Biname

[Biname]

Pour les miroirs verticaux, toutes les grilles ont un miroir vertical mais ... ???

[GBZM]

C'est clair, Biname ne sait pas lire. Recopier in extenso un message que j'ai écrit, ce n'est pas lire (et ça ne sert à rien d'autre qu'à alourdir le fil).
Mais je ne suis loin d'être le seul objet de cette incompréhension : Biname n'a pas plus compris la page de Gérard Villemin que ce que j'ai écrit.
À défaut de lire, Biname pourra peut-être comprendre un dessin d'avenue de longueur 3 ?

[GBZM]

À part cela, Biname n'explique toujours pas ce qu'il compte exactement en tenant compte des symétries ni comment il fait pour le compter. Pour ma part, je ne peux donc en conclure que "c'est du pipeau" !

[Liet Kynes]

C'est clair, Biname ne sait pas lire. Recopier in extenso un message que j'ai écrit, ce n'est pas lire (et ça ne sert à rien d'autre qu'à alourdir le fil).
Mais je ne suis loin d'être le seul objet de cette incompréhension : Biname n'a pas plus compris la page de Gérard Villemin que ce que j'ai écrit.
À défaut de lire, Biname pourra peut-être comprendre un dessin d'avenue de longueur 3 ?

La rue dont parle MissJenny corresponds à deux rues immédiatement parallèles de ton interprétation ici en ligne 1:




Proposition de définitions :

Si dans une grille, il existe une ligne de la grille, qui n'est pas un bord et qui n'est pas coupée par un segment de dominos alors le pavage n'est pas parfait.
On appelle rue le fait que deux lignes immédiatement parallèles de la grille ne soit pas coupées par un segment de dominos
On appelle avenue le fait que les deux lignes externes pour trois lignes immédiatement parallèles de la grille ne soit pas coupées par un segment de dominos.

On cherche bien d'après l'exemple de MissJenny des rues de longueur 8 cases de la grille ou 4 dominos.

Reste à définir l'objet pavage correctement, ce qui n'est pas encore fait.

[Liet Kynes]

Pour le pavage, on peut envisager l'objet selon trois modes :

1 - un pavage miroir horizontal et/ou vertical d'un autre est différent de l'autre -> le problème est résolu avec la formule du crible,

2 - un pavage miroir vertical d'un autre est identique à l'autre et un miroir horizontal d'un autre est différent de l'autre,

3 - un pavage miroir vertical et/ou horizontal d'un autre est différent des autres.

1 la grille est "clouée" au plan
2 la grille peut être tournée d'un 1/2 tour sur le plan
3 la grille n'est pas liée au plan ("volante")