Mathematics desk
< June 7	<< May \| June \| Jul >>	June 9 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 8

3x3 arrangements of D&D alignments...

Sparked by a puzzle in a D&D game. There are 9! ways that the numbers 1-9 can be placed into a 3x3 grid. In how many of them are *none* of the opposites in the "normal" placements placed side by side (or just above below). Or to put it another way, the number where 1 is not adjacent (H or V) to 9 and similarly 2 to 8, 3 to 7 and 4 to 6? (my guess is that the easiest way to start is to split it into 3 cases based on where 5 is (center, side, corner), but I'm not sure where to go from there.Naraht (talk) 13:19, 8 June 2019 (UTC)[reply]

If you have one arrangement then you can get others by swapping opposites, for 2⁴=16, and by permuting the sets {1, 9}, {2, 8}, {3, 7}, {4, 6}, for another factor of 24. In other words it's 16⋅24 times the number of near-perfect matchings of the graph of allowable placements. The graph of adjacent placements is P₃×P₃, so the problem reduces to finding the near-perfect matchings of the complement of P₃×P₃ where P₃ denotes the Path graph with three vertices. For the case where the unmatched vertex (the 5) is in the center then you have to find the the number of perfect matchings of C₈ where is the Cycle graph with 8 vertices. Finding the number of perfect matchings on C_2n in general is not that hard; you can combine the inclusion–exclusion principle with the fact that the number of k-edge matchings of C₈ is given by the coefficients of the Lucas polynomials. For C₈ the result is 7⋅5⋅3⋅1 - 8⋅5⋅3⋅1 + 20⋅3⋅1 - 16⋅1 + 2 = 31, so the number of arrangements with 5 in the center is 16⋅24⋅31 = 11904. There are more for the 5 on a side or in a corner but there is less symmetry with them so their enumeration will probably be more tedious, but I assume the easiest way is to find the matching polynomial for the corresponding graphs. As a guestimate I'd say 100,000 for the total. Another approach might be to start by computing the matching polynomial for the complement of P₃×P₃. There is a well-known formula for the number of perfect matchings of P_m×P_n where mn is even, but I don't know about imperfect matchings. (Note, this is all assuming I've understood the question correctly.) --RDBury (talk) 17:09, 8 June 2019 (UTC)[reply]

Actually the problem is much easier if you compute the matching polynomial for the complement of P₃×P₃; I get 1 + 12x + 44x² + 56x³ + 18x⁴, from which the number of near-perfect matchings is 9⋅7⋅5⋅3⋅1-12⋅7⋅5⋅3⋅1+44⋅5⋅3⋅1-56⋅3⋅1+18=195 and the total number of arrangements is 16⋅24⋅195 = 74880. --RDBury (talk) 17:54, 8 June 2019 (UTC)[reply]

(Note: I made a correction to the previous computation.) --RDBury (talk) 18:30, 8 June 2019 (UTC)[reply]

The 3x3 grid is small enough for easy hand enumeration (via backtracking) of all solutions modulo opposite swapping, set permutation, and (for other than the five-in-the-center case) rotation. In addition to the 31 with five in the center (mentioned by RDB above), there are 22 with five in the middle of a given side and 19 with five in a given corner. Those 72 fundamental solutions yield the 16⋅24(31+4⋅22+4⋅19) = 16⋅24(195) = 74880 from RDB's more elegant method. -- ToE 03:09, 10 June 2019 (UTC)[reply]