Counting $m\times n$ $\bigl({1\atop1}{1\atop0}\bigr)$-free $(0,1)$-matrices

Question

Let $G_{m,n}$ denote the number of $m\times n$ $(0,1)$-matrices that avoid the submatrix $\bigl({1\atop1}{1\atop0}\bigr)$. (Submatrices need not be contiguous.) Here are some small values (not yet on the OEIS):

G_{m,n} n=0    n=1      n=2       n=3         n=4         n=5       n=6
m=0       1      1        1         1           1           1         1
m=1       1      2        4         8          16          32        64
m=2       1      4       15        54         189         648      2187
m=3       1      8       54       330        1888       10304     54272
m=4       1     16      189      1888       16927      140626   1103671
m=5       1     32      648     10304      140626     1725320  19559448
m=6       1     64     2187     54272     1103671    19559448
m=7       1    128     7290    278016     8286710   208565440
m=8       1    256    24057   1392640    60046325
m=9       1    512    78732   6848512   422565500
m=10      1   1024   255879  33161216  2901715625
m=11      1   2048   826686 158466048 19513912500

Notice that $G_{m,n}=G_{n,m}$. Empirical evidence suggests that the doubly exponential generating function of $G_{m,n}$ has the form $$G(w,z)=\sum_{m,n\ge0}G_{m,n}{w^m\over m!}{z^n\over n!}=\sum_{m\ge0}{w^m\over m!}e^{(m+1)z}p_m(z),\tag{1}$$ where $p_m(z)$ is a real polynomial. The first few polynomials are $$p_0(z)=1;$$ $$p_1(z)=1;$$ $$p_2(z)=1+z;$$ $$p_3(z)=1+4z+3z^2+{1\over3}z^3;$$ $$p_4(z)=1+11z+27z^2+{64\over3}z^3+{71\over12}z^4+{19\over30}z^5+{1\over45}z^6.$$ Write $p_m(z)=\sum_{n\ge0}p_{mn}z^n$, so that $p_m^{(n)}(0)=n!p_{mn}$. Here are some small values:

n!p_{mn} n=0  n=1   n=2     n=3       n=4      n=5    n=6    n=7  n=8
m=0        1    0     0       0         0        0      0      0    0
m=1        1    0     0       0         0        0      0      0    0
m=2        1    1     0       0         0        0      0      0    0
m=3        1    4     6       2         0        0      0      0    0
m=4        1   11    54     128       142       76     16      0    0
m=5        1   26   300    1880      6946    15884  23472  22624     
m=6        1   57  1340   17410    141626   774346                   
m=7        1  120  5306  127120   1931510 20291152                   
m=8        1  247 19530  804580  20863052                            
m=9        1  502 68592 4639152 193826220      

For fixed $m$, the sequence $p_m^{(n)}(0)$ appears to be a unimodal sequence of positive integers followed by zeroes. It seems that $\deg(p_m)={m\choose2}$, at least for $m\le4$. The conjectured generating function (1) implies the identity $$G_{m,n}=\sum_{0\le k\le n}{n\choose k}(m+1)^{n-k}p_m^{(k)}(0);\tag{2}$$ the binomial transform then yields $$p_m^{(n)}(0)=\sum_{0\le k\le n}(-1)^{n-k}{n\choose k}(m+1)^{n-k}G_{m,k}.\tag{3}$$ Consequently for fixed $m$, the values of $G_{m,0}$, $G_{m,1}$, …, $G_{m,\deg(p_m)}$ determine $G_{m,n}$ for all $n$. Brute-force computation thus gives rise to (conjectured) closed-form formulas for $m\le4$: $$G_{0,n}=1;$$ $$G_{1,n}=2^n;$$ $$G_{2,n}=(n+3)3^{n-1};$$ $$G_{3,n}={4^{n-3}\over3}(n^3+33n^2+158n+192);$$ $$G_{4,n}={5^{n-7}\over36}(4 n^6+ 510 n^5 + 21265 n^4 + 339300 n^3+ 1862971 n^2+3963450 n+2812500).$$ It is easy to prove these formulas for $m=0$ and $m=1$. The $m=2$ case can be proven by regarding an $m\times n$ matrix as an $n$-letter word over the alphabet formed by the $2^m$ possible $(0,1)$-vectors such that $\bigl({1\atop0}\bigr)$ never appears after $\bigl({1\atop1}\bigr)$ (see OEIS A006234); approaching the $m>2$ cases with a similar idea seems possible but daunting.

We can also get the closed-form formula $p_m^{(1)}=2^m-m-1=\bigl\langle{m\atop 1}\bigr\rangle$ (an Eulerian number), as well as $p_m^{(2)}=3^{m-1}(3+m) + (1+m)(1+m-2^{m+1})$. Formulas for larger $n$ are significantly messier.

Question

Can the conjectured form given in (1) for the generating function $G(w,z)$ be proven? Perhaps a slightly simpler problem would be to find a recurrence satisfied by the polynomials $p_m(z)$.

Past work and motivation. Such matrices were investigated by Anna Lubiw in “Doubly Lexical Orderings of Matrices” [SIAM J. Computing 16 (1987), 854–879], due to connections with totally balanced matrices and chordal graphs. She called them $\Gamma$-free matrices, and gave an efficient algorithm for recognizing them. Jeremy Spinrad proved in “Nonredundant $1$'s in $\Gamma$-free matrices” [SIAM J. Discrete Math. 8 (1995), 251–257] that $G_{n,n}$ is proportional to $2^{\Theta(n\log^2n)}$. Another motivation for considering $G_{m,n}$ is the related array $B_{m,n}$ of poly-Bernoulli numbers that counts (among other things) the number of $m\times n$ $(0,1)$-matrices that avoid both $\bigl({1\atop1}{1\atop0}\bigr)$ and $\bigl({1\atop1}{1\atop1}\bigr)$ as submatrices. (Note that some of the literature also calls these matrices $\Gamma$-free.) The poly-Bernoulli numbers satisfy nice and simple recurrences; their doubly exponential generating function is given by $B(w,z)=\sum_{m,n\ge0}B_{m,n}{w^m\over m!}{z^n\over n!}={e^{w+z}\over e^w+e^z-e^{w+z}}$.

---

Update (02 April 2024). The coefficients of $p_m(z)$ up to $m=10$ are positive unimodal (and in fact log-concave). While $p_m(z)$ can have complex roots, every root (up to $m=10$ at least) has negative real part. Future work should involve finding a pattern in the polynomials $p_m(z)$, as well as finding a symmetrical expression for the generating function $G(w,z)$ (which should exist since $G_{m,n}=G_{n,m}$). Equation (2) above together with $G_{m,n}=G_{n,m}$ implies that $$\sum_{k=0}^n{n\choose k}(m+1)^{n-k}p_m^{(k)}(0) =\sum_{j=0}^m{m\choose j}(n+1)^{m-j}p_n^{(j)}(0),\tag{4}$$ which may shed light on the behavior of $p_m(z)$.

With the help of Command Master's code, here are the important values for $0\le m\le10$.

# p[m][n] = p_m^{(n)}(0) = n!p_{mn}
p=[
[1],
[1],
[1, 1],
[1, 4, 6, 2],
[1, 11, 54, 128, 142, 76, 16],
[1, 26, 300, 1880, 6946, 15884, 23472, 22624, 13932, 5016, 800],
[1, 57, 1340, 17410, 141626, 774346, 2987352, 8421352, 17734972, 28254360, 34132900, 30943548, 20476456, 9359736, 2640032, 344256],
[1, 120, 5306, 127120, 1931510, 20291152, 155798148, 909069860, 4146509580, 15092895008, 44504438320, 107421348428, 213529205692, 350139205456, 472256396524, 519652241172, 459652808672, 319150683664, 167514423696, 62437064208, 14694734336, 1633799808],
[1, 247, 19530, 804580, 20863052, 376424904, 5029924620, 51944265396, 427548763836, 2870285538180, 15997542124112, 75054021111976, 299614616546344, 1026084675675480, 3032616734001356, 7765153282957044, 17258637881089952, 33293567020311548, 55629381810428180, 80164367086150248, 98959382417001852, 103632625278125008, 90821575639611000, 65358585875011424, 37595418924046144, 16607124529246656, 5282541936985856, 1074755763143296, 104647493787648],
[1, 502, 68592, 4639152, 193826220, 5608020936, 120436425516, 2011100302904, 26992164587336, 298479933377132, 2771764023341164, 21944299736543100, 149932098887309656, 892827550090024112, 4671231134380231584, 21612428965882924868, 88883165983291662680, 326209646611556327280, 1071473572382581376124, 3155585719244749819392, 8340270160466130800160, 19781612386953510860460, 42062670216512804930916, 80027299556405484401272, 135828708245590762160536, 204818517612782561749920, 272907267007577183458784, 319074159566634865137344, 324420365965776634783968, 283568819007897264157440, 209898861866186510341664, 128952800734902421771264, 63946415163201106666496, 24572746999262747128832, 6857509133191460522496, 1234189258486537131776, 107221621194649165824],
[1, 1013, 233472, 25087590, 1622953140, 71886998228, 2353842847456, 59928310877112, 1229396869539932, 20864874822655752, 298953388931032540, 3674620435342298712, 39252531027349970032, 368292196553410857636, 3062177765044120776240, 22729884313512787473768, 151562001092425370000152, 912574447961676454473212, 4983229067787771186459492, 24766489042969964629256524, 112351178576008563232500116, 466260513333439055104923332, 1773156282271563840900881040, 6186293384663623463201343768, 19813343446152823578339214372, 58263576227444441928904656792, 157257608499140430462011230932, 389278081945880700008726456080, 882657983695609823876998150452, 1829963840588028163330691765984, 3461074683502991777858778992264, 5954468039937144461368660420240, 9285270790103466921199378782608, 13067310264580694609231342757176, 16509654459271914636448552680256, 18607146365543376560197414587696, 18561978745039691239824310326272, 16232457949447949567125190657280, 12294243681375954851670106196288, 7940182125447866043828628645504, 4284085669434775345061460250112, 1877291823349643811428320049920, 641242071937694449344137820416, 159984561364611626433746347008, 25889930932042065552484190208, 2034739297082631061190983680]
]

Closed-form formulas for $G_{m,n}$ with $0\le m\le 10$:

G_{0, n} = 1
G_{1, n} = 2**n
G_{2, n} = 3**n*(n + 3)/3
G_{3, n} = 4**n*(n**3 + 33*n**2 + 158*n + 192)/192
G_{4, n} = 5**n*(4*n**6 + 510*n**5 + 21265*n**4 + 339300*n**3 + 1862971*n**2 + 3963450*n + 2812500)/2812500
G_{5, n} = 6**n*(5*n**10 + 1656*n**9 + 218757*n**8 + 15070860*n**7 + 579047595*n**6 + 12307090320*n**5 + 139879643143*n**4 + 785515085820*n**3 + 2174816371140*n**2 + 2829503247984*n + 1371372871680)/1371372871680
G_{6, n} = 7**n*(7172*n**15 + 5022010*n**14 + 1516857895*n**13 + 263469636885*n**12 + 29287778089479*n**11 + 2183274807498785*n**10 + 111041477503856185*n**9 + 3840804449137711055*n**8 + 88688615533375058201*n**7 + 1327974755057528002425*n**6 + 12417218090679284102220*n**5 + 68877470860438979753560*n**4 + 220188257628998326857648*n**3 + 392273535466733951303280*n**2 + 358010627702919752131200*n + 129338843688663296688000)/129338843688663296688000
G_{7, n} = 8**n*(4254687*n**21 + 5535462002*n**20 + 3236805075385*n**19 + 1137737037763410*n**18 + 269890043000536182*n**17 + 45868313363013979572*n**16 + 5779961885423967055890*n**15 + 550654038240229787100020*n**14 + 40031085114021359454862507*n**13 + 2223966107987773793305529322*n**12 + 93953073584368156351833321045*n**11 + 2985730317299394710655124899930*n**10 + 70218953609639715079742053386192*n**9 + 1196268095686712452861126712835632*n**8 + 14387061503097492660581697964205200*n**7 + 118452007138432718282353655167585440*n**6 + 643856896398277384129377240034338432*n**5 + 2240856087348558145808907379383593472*n**4 + 4848789119267411781930080716202772480*n**3 + 6229691229266579397970067981904691200*n**2 + 4310149880201857661824841516285952000*n + 1227163456674763699451885550305280000)/1227163456674763699451885550305280000
G_{8, n} = 9**n*(9732839824*n**28 + 21510574745199*n**27 + 21905790920472285*n**26 + 13752768550769415297*n**25 + 5990302268782439939955*n**24 + 1928572726594084442915355*n**23 + 477076331629226261625096300*n**22 + 93008278492164038900365995240*n**21 + 14535507778763830609101662469015*n**20 + 1841686124199050948055535207320840*n**19 + 190505952186817511889570558226095450*n**18 + 16143998148128961808244381910349267695*n**17 + 1121210443838766782651798834281107757785*n**16 + 63660694385180000872701309242603213112735*n**15 + 2939896657954471788548796424085381910955500*n**14 + 109571868162566098284680817016113193374878130*n**13 + 3261813089818956767385873318278486912722620645*n**12 + 76546764960010792286599776182367158889680272095*n**11 + 1393886395672406152749780685646019398245851661025*n**10 + 19333712544356286722935384024039462708130142220710*n**9 + 199963678539305208522049699362136061076304541505576*n**8 + 1504917657203608102346264302744484226540186317383776*n**7 + 8017835851869554535877546809391698276509184342439440*n**6 + 29440740769443471982488291044077721669413794118952928*n**5 + 72598628239494065541217078001835235816640790514867200*n**4 + 116464028266776044789178364713898939297651929000000000*n**3 + 115397575833842174610976252244702073017837928353280000*n**2 + 63638494412318746169559773638195831127703093227520000*n + 14840270971928074950285438360018175178581281792000000)/14840270971928074950285438360018175178581281792000000
G_{9, n} = 10**n*(5817145247105532*n**36 + 20440457449138693195*n**35 + 33645920418531889628615*n**34 + 34700276444003002783315050*n**33 + 25253262314677585963981397576*n**32 + 13833205509569761905802881248580*n**31 + 5937949710640589338344732799999460*n**30 + 2052457082601287461131469949292268400*n**29 + 582393102597883193537610681014984571072*n**28 + 137588363291022916232002532988992820376050*n**27 + 27346260359139066929488028599430007987355050*n**26 + 4607918482876278399461528323230764953933258500*n**25 + 661919202834014512833835079276617211300235479880*n**24 + 81362053749153046565128581864420052877985793856100*n**23 + 8576274831257092945550191255865465930305195576685700*n**22 + 775815686090825646090196420741412606241923047514496000*n**21 + 60191942332182800759221459151318877736060906370552299620*n**20 + 3997637542634025454040835409605166100097441784078783731675*n**19 + 226542332193402841853416084147427781952317092595897279315975*n**18 + 10904227109997986351429148758687926836474614493334958890561250*n**17 + 443166496956177492594642995940008549206044933622304059833861328*n**16 + 15096563591658037432505685378054378319675195094536472998388422080*n**15 + 427263358321474717143959277558269673876666776945223615079208294560*n**14 + 9942687049086898229801556074717504427479842724605928996273044363200*n**13 + 187960649411346282497403449215291628886027622593561884400265688199424*n**12 + 2847091881096494779214185849944511445869571087610739701671114612312320*n**11 + 34020762863632900767923822133674291946816500572365526531882085900547840*n**10 + 315121245737405680207605743109572161890785447434088853908436854881497600*n**9 + 2218307089911673058415411424815400304470071968145739118390707746864365568*n**8 + 11611801721515722298109279142808688659789211758322597272489505712015360000*n**7 + 44192391378927137929998257396575396841793584839601930951571644368596172800*n**6 + 119572720228698307462720761986383318098352083516133060016533828755210240000*n**5 + 224393494425063044090093425102767576118454122218059620455872771327262720000*n**4 + 282433806367096306196880598832507387724824209734633454118581725167616000000*n**3 + 225632922439434622789177742552643864377377178366356183475486365581312000000*n**2 + 102725235919486921078433925550128305961211943163126512026110866227200000000*n + 20181929621847939315755178393600000000000000000000000000000000000000000000)/20181929621847939315755178393600000000000000000000000000000000000000000000
G_{10, n} = 11**n*(44156668773494597682096*n**45 + 234399390348285974346801222*n**44 + 589688956166319451804215061296*n**43 + 939967725345980003814519672520061*n**42 + 1069386350872838981357892437066111427*n**41 + 926681420685098049479394805524155695376*n**40 + 637165125936064418148749261635913931328182*n**39 + 357462608162703759002642406734419009118010737*n**38 + 166963049437217516570453135552776680432904864563*n**37 + 65913903699657016072081264729146681978570607921060*n**36 + 22250397633740356336029265357847074832988798301972128*n**35 + 6480959132410875958159963034713998212642418490395481258*n**34 + 1640542096937433213052885803810379385238544265691627125214*n**33 + 362941760299384867868086444452149535075423998514845234753704*n**32 + 70487945255777607152974299819748957941543070601815124671600644*n**31 + 12058828948044226566183394917374501166818523846021186181801741434*n**30 + 1821830313017579327023209356513547773995291142695863386522750526510*n**29 + 243489159943903027528733076766397141759569136051048924086100131655238*n**28 + 28817699233560898244432266138746838943260489986314004022097099358225960*n**27 + 3021235709023148119521757343785286231668732249097586661615576642916921145*n**26 + 280478710265583690865823193061687809988394102674963444963321554409554377799*n**25 + 23033403878929420535677300419231131525582306068840678088720493919418951849608*n**24 + 1670389467144340404702041418421200825359147604648571934490786904078604734998774*n**23 + 106717499035428277962828192283844567977116767560982498038451391839696081033370709*n**22 + 5987651735929997477533146329153123546181479842827264062312712434345913302404777743*n**21 + 293899860914552299280483093613645877207030661969228864575876719124489591227587874304*n**20 + 12561480494637687594403493962495395613490234019794502897031360243538396650243473180888*n**19 + 464938491681728414059946198463859894608197255246157498470404753942039553685315432096608*n**18 + 14807875217782990837420280318032055746812128355683882590373673336410370733695629956221432*n**17 + 402855813848345572877666501244647246518417330278951527246613252660957538468522981057784720*n**16 + 9284127206611644335623649629621322071326987621293236539811454890087668110615370761388484992*n**15 + 179543275712103931588590615193980821729234411113499983245039385931559151715685448628205523712*n**14 + 2882926271731523070763803006636496488630052429554969126812082277899063981466128471246818950656*n**13 + 37983994558157188647046553888875959948827106079173299111156662823982280264887841035535512869376*n**12 + 405283839175298474662123522517784047080446529034782091556939572586459502455248894685981265176576*n**11 + 3451056077258948098296870259765006303144669110889681515357741049069694228572358268798091038990336*n**10 + 23073182279490795916564123283011103493592696739501872996105568901916456806289004498842258878658560*n**9 + 118981189882065232856546999610676620179692021046083207916360799930505709111340805020661963264315392*n**8 + 464407646919438442049146188130492361063575099227004929939214840897813859282351507587836457477570560*n**7 + 1345972752448188589015127960279708260891922653833459431404751722530740772883609497059469933625344000*n**6 + 2838285146197680974676718221358446470859764547358929733347116505404900376266034850833978529480704000*n**5 + 4249285831011295028216868055563999582271393040661181520101120605095934081938193782750679920148480000*n**4 + 4362396317441330360342711820911470750174162695631655656944779264328827611137160610317067118182400000*n**3 + 2900420947257687527761349747829480387104072394153471581206670559333531725397021315693816053760000000*n**2 + 1118849189536797259380363769576657976610744489477246261666552263105193362951460352502488104960000000*n + 189221387551455686363029281744275158740229253603772549969324470268643376811149566433820672000000000)/189221387551455686363029281744275158740229253603772549969324470268643376811149566433820672000000000

The diagonal values $G_{m,m}$ for $0\le m\le 10$:

1, 2, 15, 330, 16927, 1725320, 313163337, 93615162116, 43484996560869, 30007547019395772, 29679303387345980127

(They alternate between being odd and even: Is there a proof?)

Answer 1

We can show that for every $m$ there is a polynomial $q_m$ of degree $\binom m2$ such that $G_{m, n} = (m+1)^n q_m(n)$. We will do this by constructing a matrix $A_m$ such that $G_{m, n} = \mathbf{1} A_m^n \begin{pmatrix}1\\0\\ \vdots\\0\end{pmatrix}$, $(A_m - (m+1) I)^{\binom{m}2} \begin{pmatrix}1\\0\\ \vdots\\0\end{pmatrix} \neq 0$, and $(A_m - (m+1) I)^{\binom{m}2 + 1} = 0$, and the result then follows from the theory of linear recurrences.

$A_m$ will be an $m! \times m!$ matrix, indexed by functions $f : \{1, 2, \dots, m\} \to \{1, 2, \dots, m, \infty\}$ such that $i < f(i)$ fo all $i$s. It's convenient to think of this matrix as representing a DFA which accepts valid matrices, over the alphabet of $2^m$ possible rows. A state $f$ represents that for each $i$, the smallest different value which must appear together with it is $f(i)$ ($\infty$ if there is no such value).

The starting state is $f(i) = \infty$. For a given state $f$ and a row $r \subseteq \{1, 2, \dots, m\}$, if $f(i) \notin r \cup \{\infty\}$ for any $i \in r$ then we will not have a transition (that is, this row makes the matrix invalid), otherwise we order the elements of $r$ as $a_1 < a_2 < \cdots < a_{|r|}$, and change $f(a_i) = a_{i+1}$ for all $i < |r|$. This gives a matrix with $G_{m, n} = \mathbf{1} A_m^n \begin{pmatrix}1\\0\\ \vdots\\0\end{pmatrix}$.

Notice that after removing self-loops the automaton is acyclic, as $f$ must decrease lexicographically in every move, and this also shows that a path can have at most $\binom m2$ steps. We will show that each state has exactly $m+1$ self-loops, so $A_m - (m+1) I$ is exactly the automaton without self-loops. Because each path without self-loops has at most $\binom m2$ steps this shows $(A_m - (m+1) I)^{\binom{m}2 + 1} = 0$. Finally, for $(A_m - (m+1) I)^{\binom{m}2} \begin{pmatrix}1\\0\\ \vdots\\0\end{pmatrix} \neq 0$ we need to exhibit a path with $\binom m2$ steps. This is such a path: $$(\infty, \infty, \dots, \infty, \infty, \infty, \infty, \infty), (\infty, \infty, \dots, \infty, \infty, \infty, m, \infty), (\dots, \infty, \infty, m, m, \infty), (\dots, \infty, \infty, m-1, m, \infty), (\dots, \infty, m, m-1, m, \infty), (\dots, \infty, m-1, m-1, m, \infty), (\dots, \infty, m-2, m-1, m, \infty), \dots$$

Which corresponds to a matrix with rows $\{m-1, m\}, \{m-2, m\}, \{m-2, m-1, m\}, \{m-3, m\}, \{m-3, m-1, m\}, \{m-3, m-2, m-1, m\}, \dots$.

Finally, we need to show that each state has exactly $m+1$ self loops. There is the self loop corresponding to the row $\emptyset$, and for each of the $m$ numbers corresponding to starting with it and following $f$. For any other valid row, there must be two elements in it, neither of which can reach the other one. But after reading the row the smaller one can reach the larger one, so the state must have changed.

Using this, we can find a formula for a few more values of $m$:

G_{0, n} = 1
G_{1, n} = 2**n
G_{2, n} = 3**n*(n + 3)/3
G_{3, n} = 4**n*(n**3 + 33*n**2 + 158*n + 192)/192
G_{4, n} = 5**n*(4*n**6 + 510*n**5 + 21265*n**4 + 339300*n**3 + 1862971*n**2 + 3963450*n + 2812500)/2812500
G_{5, n} = 6**n*(5*n**10 + 1656*n**9 + 218757*n**8 + 15070860*n**7 + 579047595*n**6 + 12307090320*n**5 + 139879643143*n**4 + 785515085820*n**3 + 2174816371140*n**2 + 2829503247984*n + 1371372871680)/1371372871680
G_{6, n} = 7**n*(7172*n**15 + 5022010*n**14 + 1516857895*n**13 + 263469636885*n**12 + 29287778089479*n**11 + 2183274807498785*n**10 + 111041477503856185*n**9 + 3840804449137711055*n**8 + 88688615533375058201*n**7 + 1327974755057528002425*n**6 + 12417218090679284102220*n**5 + 68877470860438979753560*n**4 + 220188257628998326857648*n**3 + 392273535466733951303280*n**2 + 358010627702919752131200*n + 129338843688663296688000)/129338843688663296688000
G_{7, n} = 8**n*(4254687*n**21 + 5535462002*n**20 + 3236805075385*n**19 + 1137737037763410*n**18 + 269890043000536182*n**17 + 45868313363013979572*n**16 + 5779961885423967055890*n**15 + 550654038240229787100020*n**14 + 40031085114021359454862507*n**13 + 2223966107987773793305529322*n**12 + 93953073584368156351833321045*n**11 + 2985730317299394710655124899930*n**10 + 70218953609639715079742053386192*n**9 + 1196268095686712452861126712835632*n**8 + 14387061503097492660581697964205200*n**7 + 118452007138432718282353655167585440*n**6 + 643856896398277384129377240034338432*n**5 + 2240856087348558145808907379383593472*n**4 + 4848789119267411781930080716202772480*n**3 + 6229691229266579397970067981904691200*n**2 + 4310149880201857661824841516285952000*n + 1227163456674763699451885550305280000)/1227163456674763699451885550305280000
G_{8, n} = 9**n*(9732839824*n**28 + 21510574745199*n**27 + 21905790920472285*n**26 + 13752768550769415297*n**25 + 5990302268782439939955*n**24 + 1928572726594084442915355*n**23 + 477076331629226261625096300*n**22 + 93008278492164038900365995240*n**21 + 14535507778763830609101662469015*n**20 + 1841686124199050948055535207320840*n**19 + 190505952186817511889570558226095450*n**18 + 16143998148128961808244381910349267695*n**17 + 1121210443838766782651798834281107757785*n**16 + 63660694385180000872701309242603213112735*n**15 + 2939896657954471788548796424085381910955500*n**14 + 109571868162566098284680817016113193374878130*n**13 + 3261813089818956767385873318278486912722620645*n**12 + 76546764960010792286599776182367158889680272095*n**11 + 1393886395672406152749780685646019398245851661025*n**10 + 19333712544356286722935384024039462708130142220710*n**9 + 199963678539305208522049699362136061076304541505576*n**8 + 1504917657203608102346264302744484226540186317383776*n**7 + 8017835851869554535877546809391698276509184342439440*n**6 + 29440740769443471982488291044077721669413794118952928*n**5 + 72598628239494065541217078001835235816640790514867200*n**4 + 116464028266776044789178364713898939297651929000000000*n**3 + 115397575833842174610976252244702073017837928353280000*n**2 + 63638494412318746169559773638195831127703093227520000*n + 14840270971928074950285438360018175178581281792000000)/14840270971928074950285438360018175178581281792000000

Answer 2

Command Master has already answered the question nicely. For my own understanding, this answer works out the details of that answer in the $m=3$ case (excluding the linear algebra at the end). Here's the $3!\times3!$ transition table (read column then row):

	∞ ∞ ∞	∞ 3 ∞	3 ∞ ∞	3 3 ∞	2 ∞ ∞	2 3 ∞
∞ ∞ ∞	0, 1, 2, 3
∞ 3 ∞	23	0, 1, 3, 23
3 ∞ ∞	13		0, 2, 3, 13
3 3 ∞		13	23	0, 3, 13, 23
2 ∞ ∞	12				0, 2, 3, 12
2 3 ∞	123	123	123	123	23, 123	0, 3, 23, 123
Reject		2, 12	1, 12	1, 2, 12	1, 13	1, 2, 12, 13

For example, to go from state (2 ∞ ∞) to (2 3 ∞), you can input either row 23 (011) or 123 (111).

Let's work through an example. (I'll illustrate it with the matrix being input column-by-column instead of row-by-row out of convenience; the ideas are identical.) Let's see how the matrix $$\begin{pmatrix} 0&1&0&1\\ \color{red}{\bf1}&0&1&\color{red}{\bf1}\\ \color{red}{\bf1}&1&1&\color{red}{\bf0}\end{pmatrix}$$ gets rejected (for its offending $\Gamma=\bigl({1\atop1}{1\atop0}\bigr)$ in red). The DFA always starts in state (∞ ∞ ∞), an abbreviation for $f\colon\{1,2,3\}\to\{1,2,3,\infty\}$ with $f(1)=f(2)=f(3)=\infty$, and we input the columns one at a time: $$(\infty\;\infty\;\infty) \underset{23}{\xrightarrow{\bigl({{0\atop1}\atop1}\bigr)}} (\infty\;3\;\infty) \underset{13}{\xrightarrow{\bigl({{1\atop0}\atop1}\bigr)}} (3\;3\;\infty) \underset{23}{\xrightarrow{\bigl({{0\atop1}\atop1}\bigr)}} (3\;3\;\infty) \underset{12}{\xrightarrow{\bigl({{1\atop1}\atop0}\bigr)}} \text{Reject}.$$ The idea is that after the DFA reads the first column, it knows that there cannot be a $1$ in row 2 and a $0$ in row 3 at the same time for any subsequent columns. It encodes this knowledge as the state (∞ 3 ∞). So as it reads a new column from top to bottom, if it sees a $1$ in row 2, it checks its state function $f$ and finds that $f(2)=3$, which means that that the third row of this column must be $1$ (otherwise it will be rejected).

The transition table above then gives rise to the adjacency matrix counting the number of ways to go from one state to another: $$A_3=\left( \begin{array}{cccccc} 4 & & & & & \\ 1 & 4 & & & & \\ 1 & 0 & 4 & & & \\ 0 & 1 & 1 & 4 & & \\ 1 & 0 & 0 & 0 & 4 & \\ 1 & 1 & 1 & 1 & 2 & 4 \\ \end{array} \right).$$ Notice that the sum of entries in the left column is $B_{3,1}=8$, which makes sense as it counts the number of ways to go from the starting state (∞ ∞ ∞) to any other state. We also have $$A_3^2=\left( \begin{array}{cccccc} 16 & & & & & \\ 8 & 16 & & & & \\ 8 & 0 & 16 & & & \\ 2 & 8 & 8 & 16 & & \\ 8 & 0 & 0 & 0 & 16 & \\ 12 & 9 & 9 & 8 & 16 & 16 \\ \end{array} \right),$$ whose left column sums to $B_{3,2}=54$. And so on, with $B_{3,n}$ equal to the sum of entries in the left column of $A_3^n$. This sum is equal to $\mathbf{1}A_3^ne_1$, where $\mathbf{1}$ is the all-$1$ row vector, and $e_1$ is the first unit basis vector. The rest is then some linear algebra, and I found https://scottsha.com/teach/3012spring18/linearrecurrence.pdf to be a helpful reference for learning the theory of linear recurrences.