{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Asymptotics of labeled graphs and labeled tournaments\n", "\n", "\n", "This is a supplementary file for the paper\n", " \n", " \"Asymptotics for graphically divergent series: dense digraphs and 2-SAT formulae\"\n", " by Sergey Dovgal and Khaydar Nurligareev.\n", " \n", "Here, you can find the code for obtaining asymptotic coefficients from Sections A.1-A.4, Tables 1-2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "By the variable t, we mark connected components of a labeled graph or irreducible parts of a labeled tournament" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Preliminary section\n", "" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "N = 30 # Our accuracy\n", "disp = 11 # How many terms we want to display\n", "P. = PolynomialRing(QQ)\n", "PP. = PolynomialRing(P)\n", "R. = PowerSeriesRing(PP,N)" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 1, 2, 8, 64, 1024, 32768, 2097152, 268435456, 68719476736, 35184372088832]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# EGF of labeled graphs/tournaments\n", "g = sum((2**(i*(i-1)/2) / i.factorial()) * z^i for i in srange(N))\n", "G = [g[i] * i.factorial() for i in srange(disp)]\n", "G" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# EGF of connected labeled graphs\n", "cg = log(g)\n", "CG = [cg[i] * i.factorial() for i in srange(disp)]\n", "CG" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 0, 2, 24, 544, 22320, 1677488, 236522496, 64026088576, 33832910196480]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# EGF of irreducible labeled tournaments (Section A.1)\n", "it = 1 - 1/g\n", "IT = [it[i] * i.factorial() for i in srange(disp)]\n", "IT" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Connected graphs, graphs with several connected components\n", "" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,\n", " -2,\n", " 0,\n", " -64/3,\n", " -1024,\n", " -2228224/15,\n", " -65011712,\n", " -28143578513408/315,\n", " -6046764196954112/15,\n", " -17599357217582029471744/2835,\n", " -317437253653597463768989696/945]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Coefficients of the CGF of connected labeled graphs (Section A.1)\n", "cg0 = 1 - it\n", "CG0 = [cg0[i] * 2**(i*(i+1)/2) for i in srange(disp)]\n", "CG0" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,\n", " t,\n", " t^2 + t,\n", " t^3 + 3*t^2 + 4*t,\n", " t^4 + 6*t^3 + 19*t^2 + 38*t,\n", " t^5 + 10*t^4 + 55*t^3 + 230*t^2 + 728*t,\n", " t^6 + 15*t^5 + 125*t^4 + 825*t^3 + 5098*t^2 + 26704*t,\n", " t^7 + 21*t^6 + 245*t^5 + 2275*t^4 + 20818*t^3 + 207536*t^2 + 1866256*t,\n", " t^8 + 28*t^7 + 434*t^6 + 5320*t^5 + 64673*t^4 + 925036*t^3 + 15891372*t^2 + 251548592*t,\n", " t^9 + 36*t^8 + 714*t^7 + 11088*t^6 + 169113*t^5 + 3102204*t^4 + 76321756*t^3 + 2343580752*t^2 + 66296291072*t,\n", " t^10 + 45*t^9 + 1110*t^8 + 21210*t^7 + 391881*t^6 + 8692845*t^5 + 272277040*t^4 + 12143833740*t^3 + 675458276144*t^2 + 34496488594816*t]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# EGF of labeled graphs,\n", "# with the marking variable t for connected components\n", "gt = exp(t*cg)\n", "GT = [gt[i] * i.factorial() for i in srange(disp)]\n", "GT" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[t,\n", " t^2 - t,\n", " t^3 - t^2,\n", " t^4 + t^2 - 2*t,\n", " t^5 + 2*t^4 + 7*t^3 + 14*t^2 - 24*t,\n", " t^6 + 5*t^5 + 25*t^4 + 115*t^3 + 398*t^2 - 544*t,\n", " t^7 + 9*t^6 + 65*t^5 + 455*t^4 + 3238*t^3 + 18552*t^2 - 22320*t,\n", " t^8 + 14*t^7 + 140*t^6 + 1330*t^5 + 13783*t^4 + 156576*t^3 + 1505644*t^2 - 1677488*t,\n", " t^9 + 20*t^8 + 266*t^7 + 3248*t^6 + 43673*t^5 + 711788*t^4 + 13457052*t^3 + 222306448*t^2 - 236522496*t,\n", " t^10 + 27*t^9 + 462*t^8 + 7014*t^7 + 115689*t^6 + 2400363*t^5 + 65405368*t^4 + 2131689876*t^3 + 61826469776*t^2 - 64026088576*t,\n", " t^11 + 35*t^10 + 750*t^9 + 13830*t^8 + 270921*t^7 + 6730227*t^6 + 234020920*t^5 + 11134500260*t^4 + 640578971024*t^3 + 33180955688512*t^2 - 33832910196480*t]" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# CGF of labeled graphs (before substitution z -> 2zw),\n", "# with the marking variable t for connected components\n", "qgt = t * gt * (1 - it)\n", "QGT = [qgt[i] * i.factorial() for i in srange(disp)]\n", "QGT" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[t,\n", " 2*t^2 - 2*t,\n", " 4*t^3 - 4*t^2,\n", " 32/3*t^4 + 32/3*t^2 - 64/3*t,\n", " 128/3*t^5 + 256/3*t^4 + 896/3*t^3 + 1792/3*t^2 - 1024*t,\n", " 4096/15*t^6 + 4096/3*t^5 + 20480/3*t^4 + 94208/3*t^3 + 1630208/15*t^2 - 2228224/15*t,\n", " 131072/45*t^7 + 131072/5*t^6 + 1703936/9*t^5 + 11927552/9*t^4 + 424411136/45*t^3 + 810549248/15*t^2 - 65011712*t,\n", " 16777216/315*t^8 + 33554432/45*t^7 + 67108864/9*t^6 + 637534208/9*t^5 + 33034338304/45*t^4 + 125090922496/15*t^3 + 3608644943872/45*t^2 - 28143578513408/315*t,\n", " 536870912/315*t^9 + 2147483648/63*t^8 + 20401094656/45*t^7 + 249108103168/45*t^6 + 3349537619968/45*t^5 + 54591181815808/45*t^4 + 114677774286848/5*t^3 + 17049980783034368/45*t^2 - 6046764196954112/15*t,\n", " 274877906944/2835*t^10 + 274877906944/105*t^9 + 6047313952768/135*t^8 + 91809220919296/135*t^7 + 1514302389354496/135*t^6 + 10473123132473344/45*t^5 + 2568355808391725056/405*t^4 + 195318150456198299648/945*t^3 + 16994730605763356524544/2835*t^2 - 17599357217582029471744/2835*t,\n", " 140737488355328/14175*t^11 + 140737488355328/405*t^10 + 1407374883553280/189*t^9 + 129759964263612416/945*t^8 + 1815654337272086528/675*t^7 + 15034845143511334912/225*t^6 + 941014757240089870336/405*t^5 + 313408320136829317677056/2835*t^4 + 90153475475158192328015872/14175*t^3 + 4669804364830611960743591936/14175*t^2 - 317437253653597463768989696/945*t]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Coefficients of the CGF of labeled graphs,\n", "# with the marking variable t for connected components\n", "QGTzero = [qgt[i] * 2**(i*(i+1)/2) for i in srange(disp)]\n", "QGTzero" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "# How many terms we want to display\n", "disp = 10" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [t,\n", " -2*t,\n", " 0,\n", " -64/3*t,\n", " -1024*t,\n", " -2228224/15*t,\n", " -65011712*t,\n", " -28143578513408/315*t,\n", " -6046764196954112/15*t,\n", " -17599357217582029471744/2835*t],\n", " [0,\n", " 2*t^2,\n", " -4*t^2,\n", " 32/3*t^2,\n", " 1792/3*t^2,\n", " 1630208/15*t^2,\n", " 810549248/15*t^2,\n", " 3608644943872/45*t^2,\n", " 17049980783034368/45*t^2,\n", " 16994730605763356524544/2835*t^2],\n", " [0,\n", " 0,\n", " 4*t^3,\n", " 0,\n", " 896/3*t^3,\n", " 94208/3*t^3,\n", " 424411136/45*t^3,\n", " 125090922496/15*t^3,\n", " 114677774286848/5*t^3,\n", " 195318150456198299648/945*t^3],\n", " [0,\n", " 0,\n", " 0,\n", " 32/3*t^4,\n", " 256/3*t^4,\n", " 20480/3*t^4,\n", " 11927552/9*t^4,\n", " 33034338304/45*t^4,\n", " 54591181815808/45*t^4,\n", " 2568355808391725056/405*t^4],\n", " [0,\n", " 0,\n", " 0,\n", " 0,\n", " 128/3*t^5,\n", " 4096/3*t^5,\n", " 1703936/9*t^5,\n", " 637534208/9*t^5,\n", " 3349537619968/45*t^5,\n", " 10473123132473344/45*t^5],\n", " [0,\n", " 0,\n", " 0,\n", " 0,\n", " 0,\n", " 4096/15*t^6,\n", " 131072/5*t^6,\n", " 67108864/9*t^6,\n", " 249108103168/45*t^6,\n", " 1514302389354496/135*t^6],\n", " [0,\n", " 0,\n", " 0,\n", " 0,\n", " 0,\n", " 0,\n", " 131072/45*t^7,\n", " 33554432/45*t^7,\n", " 20401094656/45*t^7,\n", " 91809220919296/135*t^7],\n", " [0,\n", " 0,\n", " 0,\n", " 0,\n", " 0,\n", " 0,\n", " 0,\n", " 16777216/315*t^8,\n", " 2147483648/63*t^8,\n", " 6047313952768/135*t^8],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 536870912/315*t^9, 274877906944/105*t^9]]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Coefficients of the CGF of labeled graphs (matrix form with respect to t),\n", "# with the marking variable t for connected components\n", "QGTzeroMatrix = [[qgt[i][0][j] * 2**(i*(i+1)/2) * t^j for i in srange(disp)] for j in srange(disp)]\n", "QGTzeroMatrix" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [1, -1, 0, -2, -24, -544, -22320, -1677488, -236522496, -64026088576],\n", " [0, 1, -1, 1, 14, 398, 18552, 1505644, 222306448, 61826469776],\n", " [0, 0, 1, 0, 7, 115, 3238, 156576, 13457052, 2131689876],\n", " [0, 0, 0, 1, 2, 25, 455, 13783, 711788, 65405368],\n", " [0, 0, 0, 0, 1, 5, 65, 1330, 43673, 2400363],\n", " [0, 0, 0, 0, 0, 1, 9, 140, 3248, 115689],\n", " [0, 0, 0, 0, 0, 0, 1, 14, 266, 7014],\n", " [0, 0, 0, 0, 0, 0, 0, 1, 20, 462],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 1, 27]]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Refined coefficients of the CGF of labeled graphs (Table 1)\n", "QGTmatrixFact = [[qgt[i][0][j] * i.factorial() for i in srange(disp)] for j in srange(disp)]\n", "QGTmatrixFact" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "t + ((2*t^2 - 2*t)*w)*z + ((2*t^3 - 2*t^2)*w^2)*z^2 + ((4/3*t^4 + 4/3*t^2 - 8/3*t)*w^3)*z^3 + ((2/3*t^5 + 4/3*t^4 + 14/3*t^3 + 28/3*t^2 - 16*t)*w^4)*z^4 + ((4/15*t^6 + 4/3*t^5 + 20/3*t^4 + 92/3*t^3 + 1592/15*t^2 - 2176/15*t)*w^5)*z^5 + ((4/45*t^7 + 4/5*t^6 + 52/9*t^5 + 364/9*t^4 + 12952/45*t^3 + 24736/15*t^2 - 1984*t)*w^6)*z^6 + ((8/315*t^8 + 16/45*t^7 + 32/9*t^6 + 304/9*t^5 + 15752/45*t^4 + 59648/15*t^3 + 1720736/45*t^2 - 13419904/315*t)*w^7)*z^7 + ((2/315*t^9 + 8/63*t^8 + 76/45*t^7 + 928/45*t^6 + 12478/45*t^5 + 203368/45*t^4 + 427208/5*t^3 + 63516128/45*t^2 - 22525952/15*t)*w^8)*z^8 + ((4/2835*t^10 + 4/105*t^9 + 88/135*t^8 + 1336/135*t^7 + 22036/135*t^6 + 152404/45*t^5 + 37374496/405*t^4 + 2842253168/945*t^3 + 247305879104/2835*t^2 - 256104354304/2835*t)*w^9)*z^9 + ((4/14175*t^11 + 4/405*t^10 + 40/189*t^9 + 3688/945*t^8 + 51604/675*t^7 + 427316/225*t^6 + 26745248/405*t^5 + 8907600208/2835*t^4 + 2562315884096/14175*t^3 + 132723822754048/14175*t^2 - 9022109385728/945*t)*w^10)*z^10 + ((8/155925*t^12 + 32/14175*t^11 + 8/135*t^10 + 176/135*t^9 + 46792/1575*t^8 + 191744/225*t^7 + 14342504/405*t^6 + 6178841008/2835*t^5 + 2624865852512/14175*t^4 + 270702882737216/14175*t^3 + 279089788612521728/155925*t^2 - 282096739342852096/155925*t)*w^11)*z^11 + ((4/467775*t^13 + 8/17325*t^12 + 124/8505*t^11 + 3208/8505*t^10 + 139708/14175*t^9 + 1507192/4725*t^8 + 92387516/6075*t^7 + 16058453032/14175*t^6 + 1788074299792/14175*t^5 + 274302416452448/14175*t^4 + 1692649159562141696/467775*t^3 + 920652989998396928/1485*t^2 - 2946539924570189824/4725*t)*w^12)*z^12 + ((8/6081075*t^14 + 8/93555*t^13 + 136/42525*t^12 + 584/6075*t^11 + 1496/525*t^10 + 161368/1575*t^9 + 231842584/42525*t^8 + 20037053096/42525*t^7 + 912812681584/14175*t^6 + 326312490784/25*t^5 + 340979769367660736/93555*t^4 + 21608204664993104128/17325*t^3 + 95797674039965274449920/243243*t^2 - 2402548574289278267973632/6081075*t)*w^13)*z^13 + ((8/42567525*t^15 + 8/552825*t^14 + 296/467775*t^13 + 10232/467775*t^12 + 31016/42525*t^11 + 1225688/42525*t^10 + 71393128/42525*t^9 + 48649155272/297675*t^8 + 124240284272/4725*t^7 + 31182245494048/4725*t^6 + 163405298775638848/66825*t^5 + 585712722851886487552/467775*t^4 + 64068168651226087071232/81081*t^3 + 19705758593818353432074156032/42567525*t^2 - 14461133909589193501442048/31185*t)*w^14)*z^14 + ((16/638512875*t^16 + 32/14189175*t^15 + 32/280665*t^14 + 6304/1403325*t^13 + 1174144/7016625*t^12 + 1533536/212625*t^11 + 57843232/127575*t^10 + 2068332512/42525*t^9 + 5707563091952/637875*t^8 + 1702346434966976/637875*t^7 + 1726114698439507456/1403325*t^6 + 130606969770342844672/155925*t^5 + 72229619960684874054669056/91216125*t^4 + 197394660032718751456440614912/212837625*t^3 + 58841546188926623322619337191424/58046625*t^2 - 647849698201253370788046628487168/638512875*t)*w^15)*z^15 + ((2/638512875*t^17 + 16/49116375*t^16 + 344/18243225*t^15 + 15328/18243225*t^14 + 34844/1002375*t^13 + 542912/334125*t^12 + 2783768/25515*t^11 + 3774898784/297675*t^10 + 11656165420318/4465125*t^9 + 4015486167470864/4465125*t^8 + 496078807189963408/1002375*t^7 + 327581560462513148672/779625*t^6 + 48242620708568491032154592/91216125*t^5 + 197619884896486082305043886848/212837625*t^4 + 259139947594237640537611725182464/127702575*t^3 + 2654564737264523230860438401135570944/638512875*t^2 - 885287010066705353119153770626351104/212837625*t)*w^16)*z^16 + ((4/10854718875*t^18 + 4/91216125*t^17 + 368/127702575*t^16 + 18416/127702575*t^15 + 85912/13030875*t^14 + 2335096/7016625*t^13 + 166179344/7016625*t^12 + 4380396368/1488375*t^11 + 2976547297468/4465125*t^10 + 1159797181740772/4465125*t^9 + 8149720940343930368/49116375*t^8 + 236606232206350891168/1403325*t^7 + 4832733436388674711499456/18243225*t^6 + 26375646737991805556142839872/42567525*t^5 + 1296491179689727688092359574779392/638512875*t^4 + 5311722458440017422581337166638302208/638512875*t^3 + 20481064205778474032378548449082880155648/638512875*t^2 - 348268412827106260798525586793706790846464/10854718875*t)*w^17)*z^17 + ((4/97692469875*t^19 + 4/723647925*t^18 + 16/39092625*t^17 + 6256/273648375*t^16 + 200216/174139875*t^15 + 813928/13030875*t^14 + 295815952/63149625*t^13 + 90716888432/147349125*t^12 + 6083228089276/40186125*t^11 + 2638116356835748/40186125*t^10 + 468389226097825024/9823275*t^9 + 307669166926640397152/5457375*t^8 + 87137550652318003046163392/820945125*t^7 + 594011626794020209944193047872/1915538625*t^6 + 7783106603066630741862840732663296/5746615875*t^5 + 9564214027776513713266357480995478528/1149323175*t^4 + 14750191914419597150899743596169586171904/229864635*t^3 + 35806363905260276635558643547690214645399552/76621545*t^2 - 19895156263120268635010914395450159726854144/42567525*t)*w^18)*z^18 + ((8/1856156927625*t^20 + 64/97692469875*t^19 + 8/147349125*t^18 + 496/147349125*t^17 + 71056/383107725*t^16 + 627776/58046625*t^15 + 698727632/820945125*t^14 + 51839597536/442047375*t^13 + 2736397270136/88409475*t^12 + 118541566886912/8037225*t^11 + 1766586108703330984/147349125*t^10 + 113371078095277913648/7016625*t^9 + 203662004677694942434071232/5746615875*t^8 + 713466240648780529188578359424/5746615875*t^7 + 556216594112901099441308742611584/820945125*t^6 + 31889799974274604393305209761640704256/5746615875*t^5 + 368818581374470501110156092859645547368448/5746615875*t^4 + 6087917852718620604151292776910175576135667712/6512831325*t^3 + 23940036822212081422375474899078749597714990876622848/1856156927625*t^2 - 23941771997938809676429555271159203422920064755040256/1856156927625*t)*w^19)*z^19 + ((4/9280784638125*t^21 + 8/109185701625*t^20 + 4/592075575*t^19 + 2152/4652022375*t^18 + 29608/1064188125*t^17 + 5546608/3192564375*t^16 + 821954792/5746615875*t^15 + 117872730256/5746615875*t^14 + 12722547038924/2210236875*t^13 + 134535037396088/45106875*t^12 + 236902940434441156/88409475*t^11 + 1791092981408793195272/442047375*t^10 + 291428920941821373021192704/28733079375*t^9 + 1190179965895943208128350804672/28733079375*t^8 + 7790842663290379013173101687768128/28733079375*t^7 + 11392275649431375089519913094979153792/4104725625*t^6 + 409860454445102734531615307131131986592256/9577693125*t^5 + 50737294008858140418536600257953623556001138688/54273594375*t^4 + 79805906792301438967499659552848255507581012483268608/3093594879375*t^3 + 6276383421487051001921951028991990691310142999163986837504/9280784638125*t^2 - 15730884330536096146101265449015160501234971347343376384/23260111875*t)*w^20)*z^20 + ((8/194896477400625*t^22 + 8/1031198293125*t^21 + 232/293077409625*t^20 + 17464/293077409625*t^19 + 1904384/488462349375*t^18 + 2492176/9577693125*t^17 + 385485904/17239847625*t^16 + 10265779184/3094331625*t^15 + 9403958420008/9577693125*t^14 + 1212028947843544/2210236875*t^13 + 510581020733395768/947244375*t^12 + 665405122114721901272/736745625*t^11 + 218932436937529922017570864/86199238125*t^10 + 2382478321242131309446903877056/201131555625*t^9 + 119916744672525768440988630189568/1326142125*t^8 + 95720064303830721465431508642397453184/86199238125*t^7 + 1844635306470405993163531839393121987694336/86199238125*t^6 + 304448155499413839653972754258149465297900220416/488462349375*t^5 + 55252912985933880426365537966642872556133541876477952/2141719531875*t^4 + 597773604835957311520542456513007622202974095963580628992/441942125625*t^3 + 13163245568892522542160095801645175622230726637689768953485459456/194896477400625*t^2 - 774324070122375985884672977318272715174291171609156350206017536/11464498670625*t)*w^21)*z^21 + ((8/2143861251406875*t^23 + 8/10257709336875*t^22 + 488/5568470782875*t^21 + 3656/506224616625*t^20 + 250304/488462349375*t^19 + 12944/354729375*t^18 + 25606928/7836294375*t^17 + 43030057424/86199238125*t^16 + 4444829746664/28733079375*t^15 + 2655837467973896/28733079375*t^14 + 7189529735153026504/72937816875*t^13 + 58735276297802391992/324168075*t^12 + 48731632913922354857274832/86199238125*t^11 + 119229199447628881199822808448/40226311125*t^10 + 15596589846190446264650804695901824/603394666875*t^9 + 223404019201378249245912765498976167296/603394666875*t^8 + 737956263553860980716500635903116855864576/86199238125*t^7 + 152235578292933263611691766221330344320702241792/488462349375*t^6 + 22803753671435231705699712635547491577615582551947264/1325826376875*t^5 + 201394090219271342930992846242190785303615315456135135232/148889593125*t^4 + 289597202262651648688393712366046881582678071294345076665732661248/2143861251406875*t^3 + 2123547428865830733350958785142978203682774824371205790284830196105216/164912403954375*t^2 - 167311552577927106452220046580823282712510374343594525543338667409408/12993098493375*t)*w^22)*z^22 + ((16/49308808782358125*t^24 + 32/428772250281375*t^23 + 256/27842353914375*t^22 + 23008/27842353914375*t^21 + 252176/3977479130625*t^20 + 1006784/209341006875*t^19 + 656971712/1465387048125*t^18 + 3260102336/46414974375*t^17 + 82817536912/3656937375*t^16 + 2892946195891552/201131555625*t^15 + 89530518479811328/5418237825*t^14 + 2410176246329503370464/72937816875*t^13 + 9762308777789385915030896/86199238125*t^12 + 132593430556793855792281662848/201131555625*t^11 + 3900988163003679803944608801139648/603394666875*t^10 + 12769177082148365882755474156911206144/120678933375*t^9 + 574044027495888610972423327462049309397248/201131555625*t^8 + 60898692769999281488384638269851001960907300864/488462349375*t^7 + 34206994248334271346909218166680469286053849031109632/3977479130625*t^6 + 25107688636346236715878334048394910489539136066574866960384/27842353914375*t^5 + 3182429328188426800520147736227643830929914272995275229348347904/23558914850625*t^4 + 2208512494105979814708105144734792854631296554359859988857232854286336/85754450056275*t^3 + 10068711684519722562859911230099651775983270247726899442133171901373701685248/2143861251406875*t^2 - 17813972203484507610323879843907829348488871210187270675216694064991002689536/3792985290950625*t)*w^23)*z^23 + ((4/147926426347074375*t^25 + 16/2348038513445625*t^24 + 536/584689432201875*t^23 + 52352/584689432201875*t^22 + 1148/154966719375*t^21 + 16642096/27842353914375*t^20 + 254799392/4396161144375*t^19 + 95222009536/10257709336875*t^18 + 5605473709348/1810184000625*t^17 + 3762721820084272/1810184000625*t^16 + 50914559346671755192/19912024006875*t^15 + 134309562841644912256/24312605625*t^14 + 58669756285215143868346124/2844574858125*t^13 + 875884046510328597094218852464/6637341335625*t^12 + 200144643005060256608359345217584/139244923125*t^11 + 47896451119099286157692693375295745984/1810184000625*t^10 + 1476311670428654885050113660874042970919488/1810184000625*t^9 + 426321526131550079627458848431470390200975411968/10257709336875*t^8 + 13683326705525546329726029037305193861024873406825728/3977479130625*t^7 + 597814653659205317219803520305357632936906700937401572352/1325826376875*t^6 + 44554531111230912719652580905760608990997516019816228108559896576/494737211863125*t^5 + 1245410492320736900855764804706779915761058128142394138152113546641408/48357772588125*t^4 + 3553682434488783458756168453191595536439665396764023087629166282283335155712/378328456130625*t^3 + 541430384125159908233739856550072434953615973027420623603248346026578475820777472/164912403954375*t^2 - 138012061396393875196896181275446527395396912682211570779503907824014948791484416/42036495125625*t)*w^24)*z^24 + ((8/3698160658676859375*t^26 + 8/13447856940643125*t^25 + 16/183759535834875*t^24 + 8464/918797679174375*t^23 + 140984/171967480059375*t^22 + 199624/2841056521875*t^21 + 62432/8813660625*t^20 + 35603125696/30773128010625*t^19 + 3595653789736/9050920003125*t^18 + 230729873427688/822810909375*t^17 + 7316147859857585552/19912024006875*t^16 + 145085368268621060816/170188239375*t^15 + 16323815465893524071760488/4740958096875*t^14 + 2390864804434332538114588598744/99560120034375*t^13 + 28634080072215298996145294641029056/99560120034375*t^12 + 53231587535140843328280924524339847968/9050920003125*t^11 + 1845635820687641074055597485548631898381312/9050920003125*t^10 + 609074083438366292130210762790554001293141047936/51288546684375*t^9 + 257887872639203179831548266626470268823253375932910592/224880550846875*t^8 + 75326178981618535475468327155250076523251873326797328731648/417635308715625*t^7 + 7240191057904787691140569411636172584133267987411702040691158059008/160789593855515625*t^6 + 110427072739644577967352925568390996781075504819788928605902556357107712/6431583754220625*t^5 + 302064111203722193987036992272082576114610556094700228707306036024871180271616/32157918771103125*t^4 + 17789906375647619222914927104164959562708228676742907373449064046279539518663032832/2709275207821875*t^3 + 16296214960766117851189186626807820420610302266702303416021302220662828271688828609863090176/3698160658676859375*t^2 - 16296239244023058046473587308348808557128439018866125311470992007136157719474561503564136448/3698160658676859375*t)*w^25)*z^25 + ((8/48076088562799171875*t^27 + 8/160789593855515625*t^26 + 1168/147926426347074375*t^25 + 7024/7785601386688125*t^24 + 2770696/32157918771103125*t^23 + 22900424/2923447161009375*t^22 + 68557024/83527061743125*t^21 + 79779634624/584689432201875*t^20 + 7386802687304/153865640053125*t^19 + 5457764944107032/153865640053125*t^18 + 4906168507809651728/99560120034375*t^17 + 1737469818525536199152/14222874290625*t^16 + 686721443381109282319812488/1294281560446875*t^15 + 5184732730427940736091230834328/1294281560446875*t^14 + 13528901097608147282014911620288/258597714375*t^13 + 117138669312912239745438217150010435936/99560120034375*t^12 + 410195729788130451516735472204941424347136/9050920003125*t^11 + 456837816756766669348451385679560813532337738624/153865640053125*t^10 + 106433911372500919547854470603691232595717600923210752/324827462334375*t^9 + 15978599698353332808138981323953265206382533785720863118848/265767923728125*t^8 + 2896107358047124265305657953971693465620524899883927813296591742976/160789593855515625*t^7 + 1380346373579465810132899255349494369193909072678059830228374445229932544/160789593855515625*t^6 + 815290357485050339371953014854392930265155630470772421554191175487807225856/130194003121875*t^5 + 971330740777438353206914092533497545792688340450905881401626653733553829335712530432/147926426347074375*t^4 + 47078024482766730353398123422506725939550397264368564347006333010367424288943095794034540544/5341787618088796875*t^3 + 546811410086882164440251640440679451110273367332059300450520297443569349643815238374787446676127744/48076088562799171875*t^2 - 400594750028877796434165637413722530087811212628462061808702277244143911548080946131925116911616/35220577701684375*t)*w^26)*z^26 + ((16/1298054391195577640625*t^28 + 64/16025362854266390625*t^27 + 16/23356804160064375*t^26 + 5344/63397039863031875*t^25 + 19125584/2218896395206115625*t^24 + 26699392/32157918771103125*t^23 + 2378492432/26311024449084375*t^22 + 133964479072/8770341483028125*t^21 + 11099475774928/2023924957621875*t^20 + 119366085893056/28261035928125*t^19 + 10487364056151829424/1692522040584375*t^18 + 36147449893225293344/2212447111875*t^17 + 884371474883147070124359248/11648534044021875*t^16 + 68429770884870675466252309504/110938419466875*t^15 + 7816581023069754637767705761969072/896041080309375*t^14 + 558976917955914192472337867300104736/2612364665625*t^13 + 8122949297331082498153246831863125285505344/896041080309375*t^12 + 304579933917529432137939068496773380309462963072/461596920159375*t^11 + 6466101010561446171706868336220432449123646740764792064/78933073347253125*t^10 + 150658345107357382359935778947285156811384483997238495888896/8770341483028125*t^9 + 8688413223428294726148459938419344184892201159352463380401054700544/1447106344699640625*t^8 + 709896392565366373551717215146309131368039479094426943540057124131678208/206729477814234375*t^7 + 53305762673688005968847908129122955442202699372051176946181416806226902048768/17024780525878125*t^6 + 9713323618666878621582111908464892460910214331956030465543434584500780180031230541824/2218896395206115625*t^5 + 11439971313905013741042592304924163628339160075899850665004250493297031437610897825624071995392/1298054391195577640625*t^4 + 9842613008211421575460299068837268571867945527167036866014465190357551223941729203009392242970329088/432684797065192546875*t^3 + 73391867128085134584320213663471058128890101734575838175344992682357058756648795285707119361090916550967296/1298054391195577640625*t^2 - 73391896655935599195581143439331763729210738958470891334960311954433292206784891546518339989942248346222592/1298054391195577640625*t)*w^27)*z^27 + ((8/9086380738369043484375*t^29 + 16/51922175647823105625*t^28 + 632/11094481976030578125*t^27 + 3632/482368781566546875*t^26 + 1825336/2218896395206115625*t^25 + 62017712/739632131735371875*t^24 + 2745389144/289421268939928125*t^23 + 15776417648/9693535323346875*t^22 + 15630368984504/26311024449084375*t^21 + 12500050348732816/26311024449084375*t^20 + 106384949926530872/145073317764375*t^19 + 3467271316968403912144/1692522040584375*t^18 + 118109086777284510037533688/11648534044021875*t^17 + 7191392379673226257071787133168/81539738308153125*t^16 + 15640436525146513393070224419556792/11648534044021875*t^15 + 83103201875976644749408545227338955536/2329706808804375*t^14 + 113622660364576365488312233662549890835808/68926236946875*t^13 + 670122731563270223731576880143402549338597627328/5077566121753125*t^12 + 1436964582234743535323884986416530250574602084925399424/78933073347253125*t^11 + 258967091366431643511867175324884815411372911400337986816/60300285215625*t^10 + 17377006677464466259725115551884499778691848909088895339994048635392/10129744412897484375*t^9 + 2319007625590942574269704694116987358657221060499194892079501243786820608/2025948882579496875*t^8 + 106611837147596845450162171843821320959972811689148845095580813740708353835008/85123902629390625*t^7 + 1815305917483538430866811822306130532487107718521385544246578598464364370301845504/829369961578125*t^6 + 7626654171960937422351596793968355448958658444936721210765615596162581625306168020501393440768/1298054391195577640625*t^5 + 29527854277945449846219372707863181764852357914002150658202313562801052342103831001219264841561407488/1298054391195577640625*t^4 + 1027486553183151775595776315810705434565657542739944312281082522124663737140068513239876818462515065912295424/9086380738369043484375*t^3 + 4925247692088203486419134593560020631482897986690785031505184464009165656796792068042074082294548597059120095297536/9086380738369043484375*t^2 - 1641749573191654454868080802192353108092895210955066131144582412508688817421704657899422094045426203767373922566144/3028793579456347828125*t)*w^28)*z^28 + ((16/263505041412702261046875*t^30 + 16/698952364489926421875*t^29 + 656/144228265688397515625*t^28 + 92912/144228265688397515625*t^27 + 1328/17694548606109375*t^26 + 221488/27393782656865625*t^25 + 486605488/512053014278334375*t^24 + 6841082128/41345895562846875*t^23 + 230013738992/3758717778440625*t^22 + 1332302658679856/26311024449084375*t^21 + 23723329157467818224/289421268939928125*t^20 + 3682586582505718715312/15232698365259375*t^19 + 251392574839435669146492368/198025078748371875*t^18 + 959688227780292475049231409104/81539738308153125*t^17 + 15647706817883667888823579009884592/81539738308153125*t^16 + 447589549769607866011798093048396872784/81539738308153125*t^15 + 355643623706465405833955410251005828626528/1294281560446875*t^14 + 121848995487507954367521017381230215936925240256/5077566121753125*t^13 + 18065364391595109867389089517668012365052608426088064/4961507467541625*t^12 + 6848374404596709397898563678855709554844214735751238573824/7175733940659375*t^11 + 4344296382633752407050966013632737756370852455205596186240448283136/10129744412897484375*t^10 + 3312886034464146877996419948422672255481663315517068578685284848038382592/10129744412897484375*t^9 + 4228948354139672959539395894248704785632271912546603032724476364522101548480512/10129744412897484375*t^8 + 4162865882035618913746497607373573732044511056162424123638647817066865953950779219968/4754777989727390625*t^7 + 108952291750119923822608005619224851606440843697294940502747251512245474505635348364600311808/37087268319873646875*t^6 + 1789567734824555569913662431811657861942005488641752364806223481211586338650363831865827602113101824/118004944654143421875*t^5 + 8491626684104211835665623208550025413463984634479136543585694466861393874445665908722894383351343892922368/75094055689000359375*t^4 + 895499767195460411481615933277674038712386850637392240975141946259790228154507493839173541105602373691311648669696/826034612579003953125*t^3 + 2644223018167508609865864197194066515408347192178275287918851586329161110951600021084972054673405067400444984126057232728064/263505041412702261046875*t^2 - 2644223303831964142339766087034850077832397934690400831952164453947177853115475321902404405740227320958988780229391426781184/263505041412702261046875*t)*w^29)*z^29 + O(z^30)" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# CGF of labeled graphs after substitution z -> 2zw (Section A.2) \n", "# Marking variable t is for connected components\n", "qgt.subs(z=2*z*w)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Irreducible tournaments, tornaments with several irreducible parts\n", "" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "# How many terms we want to display\n", "disp = 11" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 0, 2, 0, 16, 240, 6608, 315840, 27001984, 4268194560, 1281626527232]" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# EGF of labeled tournaments with two irreducible parts (Section A.3)\n", "it2 = it**2\n", "IT2 = [it2[i] * i.factorial() for i in srange(disp)]\n", "IT2" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,\n", " -4,\n", " 8,\n", " -128/3,\n", " -4096/3,\n", " -3473408/15,\n", " -4984930304/45,\n", " -50988241125376/315,\n", " -239467516496183296/315,\n", " -34025482048081491918848/2835,\n", " -9342744711155730849185398784/14175]" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Coefficients of the CGF of irreducible labeled tournaments (Section A.3)\n", "it0 = (1 - it)**2\n", "IT0 = [it0[i] * 2**(i*(i+1)/2) for i in srange(disp)]\n", "IT0" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,\n", " t,\n", " 2*t^2,\n", " 6*t^3 + 2*t,\n", " 24*t^4 + 16*t^2 + 24*t,\n", " 120*t^5 + 120*t^3 + 240*t^2 + 544*t,\n", " 720*t^6 + 960*t^4 + 2160*t^3 + 6608*t^2 + 22320*t,\n", " 5040*t^7 + 8400*t^5 + 20160*t^4 + 70224*t^3 + 315840*t^2 + 1677488*t,\n", " 40320*t^8 + 80640*t^6 + 201600*t^5 + 758016*t^4 + 3830400*t^3 + 27001984*t^2 + 236522496*t,\n", " 362880*t^9 + 846720*t^7 + 2177280*t^6 + 8628480*t^5 + 46448640*t^4 + 366729600*t^3 + 4268194560*t^2 + 64026088576*t,\n", " 3628800*t^10 + 9676800*t^8 + 25401600*t^7 + 104751360*t^6 + 586656000*t^5 + 4919278080*t^4 + 64185972480*t^3 + 1281626527232*t^2 + 33832910196480*t]" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# EGF of labeled tournaments, \n", "# with the marking variable t for irreducible parts\n", "tt = 1/(1-t*it)\n", "TT = [tt[i] * i.factorial() for i in srange(disp)]\n", "TT" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[t,\n", " t^2 - t,\n", " t^3 - t^2,\n", " t^4 + t^2 - 2*t,\n", " t^5 + 2*t^4 + 7*t^3 + 14*t^2 - 24*t,\n", " t^6 + 5*t^5 + 25*t^4 + 115*t^3 + 398*t^2 - 544*t,\n", " t^7 + 9*t^6 + 65*t^5 + 455*t^4 + 3238*t^3 + 18552*t^2 - 22320*t,\n", " t^8 + 14*t^7 + 140*t^6 + 1330*t^5 + 13783*t^4 + 156576*t^3 + 1505644*t^2 - 1677488*t,\n", " t^9 + 20*t^8 + 266*t^7 + 3248*t^6 + 43673*t^5 + 711788*t^4 + 13457052*t^3 + 222306448*t^2 - 236522496*t,\n", " t^10 + 27*t^9 + 462*t^8 + 7014*t^7 + 115689*t^6 + 2400363*t^5 + 65405368*t^4 + 2131689876*t^3 + 61826469776*t^2 - 64026088576*t,\n", " t^11 + 35*t^10 + 750*t^9 + 13830*t^8 + 270921*t^7 + 6730227*t^6 + 234020920*t^5 + 11134500260*t^4 + 640578971024*t^3 + 33180955688512*t^2 - 33832910196480*t]" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# CGF of labeled tournaments (before substitution z -> 2zw),\n", "# with the marking variable t for irreducible parts\n", "qtt = t * tt * tt * (1 - it) * (1 - it)\n", "QTT = [qgt[i] * i.factorial() for i in srange(disp)]\n", "QTT" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "# How many terms we want to display\n", "disp = 10" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [1, -2, 2, -4, -32, -848, -38032, -3039136, -446043008, -123783982592],\n", " [0, 2, -8, 16, -16, 368, 22528, 2232064, 372697856, 111712858112],\n", " [0, 0, 6, -36, 120, 0, 9744, 586656, 60297600, 10743552000],\n", " [0, 0, 0, 24, -192, 960, 960, 153216, 10063872, 1129843200],\n", " [0, 0, 0, 0, 120, -1200, 8400, 16800, 2177280, 156844800],\n", " [0, 0, 0, 0, 0, 720, -8640, 80640, 241920, 30723840],\n", " [0, 0, 0, 0, 0, 0, 5040, -70560, 846720, 3386880],\n", " [0, 0, 0, 0, 0, 0, 0, 40320, -645120, 9676800],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 362880, -6531840]]" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Refined coefficients of the CGF of labeled tournaments (Table 2)\n", "QTTmatrixFact = [[qtt[i][0][j] * i.factorial() for i in srange(disp)] for j in srange(disp)]\n", "QTTmatrixFact" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "t + ((4*t^2 - 4*t)*w)*z + ((12*t^3 - 16*t^2 + 4*t)*w^2)*z^2 + ((32*t^4 - 48*t^3 + 64/3*t^2 - 16/3*t)*w^3)*z^3 + ((80*t^5 - 128*t^4 + 80*t^3 - 32/3*t^2 - 64/3*t)*w^4)*z^4 + ((192*t^6 - 320*t^5 + 256*t^4 + 1472/15*t^2 - 3392/15*t)*w^5)*z^5 + ((448*t^7 - 768*t^6 + 2240/3*t^5 + 256/3*t^4 + 12992/15*t^3 + 90112/45*t^2 - 152128/45*t)*w^6)*z^6 + ((1024*t^8 - 1792*t^7 + 2048*t^6 + 1280/3*t^5 + 19456/5*t^4 + 74496/5*t^3 + 17856512/315*t^2 - 24313088/315*t)*w^7)*z^7 + ((2304*t^9 - 4096*t^8 + 5376*t^7 + 1536*t^6 + 13824*t^5 + 319488/5*t^4 + 8039680/21*t^3 + 745395712/315*t^2 - 892086016/315*t)*w^8)*z^8 + ((5120*t^10 - 9216*t^9 + 40960/3*t^8 + 14336/3*t^7 + 130048/3*t^6 + 1991680/9*t^5 + 301291520/189*t^4 + 954982400/63*t^3 + 446851432448/2835*t^2 - 495135930368/2835*t)*w^9)*z^9 + ((11264*t^11 - 20480*t^10 + 33792*t^9 + 40960/3*t^8 + 1885184/15*t^7 + 3407872/5*t^6 + 1026857984/189*t^5 + 58596343808/945*t^4 + 4632695441408/4725*t^3 + 250670744915968/14175*t^2 - 265536775462912/14175*t)*w^10)*z^10 + ((24576*t^12 - 45056*t^11 + 81920*t^10 + 36864*t^9 + 5177344/15*t^8 + 29216768/15*t^7 + 5213216768/315*t^6 + 39540822016/189*t^5 + 18759377772544/4725*t^4 + 8116956889088/75*t^3 + 540707547912593408/155925*t^2 - 558237335326810112/155925*t)*w^11)*z^11 + ((53248*t^13 - 98304*t^12 + 585728/3*t^11 + 286720/3*t^10 + 4554752/5*t^9 + 237764608/45*t^8 + 6330413056/135*t^7 + 199312400384/315*t^6 + 5394570469376/405*t^5 + 6177522832523264/14175*t^4 + 93700957622853632/4455*t^3 + 569980478259428458496/467775*t^2 - 580029488718632603648/467775*t)*w^12)*z^12 + ((114688*t^14 - 212992*t^13 + 458752*t^12 + 720896/3*t^11 + 6995968/3*t^10 + 68960256/5*t^9 + 3409903616/27*t^8 + 240642031616/135*t^7 + 1083421081600/27*t^6 + 118072847319040/81*t^5 + 125388751434678272/1485*t^4 + 1213422490282164224/165*t^3 + 4744684757293120849199104/6081075*t^2 - 4789928030151541140865024/6081075*t)*w^13)*z^13 + ((245760*t^15 - 458752*t^14 + 1064960*t^13 + 589824*t^12 + 17481728/3*t^11 + 104857600/3*t^10 + 6879690752/21*t^9 + 902893404160/189*t^8 + 5071308013568/45*t^7 + 1380490588258304/315*t^6 + 586228327243988992/2079*t^5 + 306384442194340151296/10395*t^4 + 66637133344223685358403584/14189175*t^3 + 39210445548996793480315142144/42567525*t^2 - 39411623787914121522914902016/42567525*t)*w^14)*z^14 + ((524288*t^16 - 983040*t^15 + 7340032/3*t^14 + 4259840/3*t^13 + 214171648/15*t^12 + 3893559296/45*t^11 + 52010156032/63*t^10 + 431801171968/35*t^9 + 1423354323009536/4725*t^8 + 8295511240278016/675*t^7 + 44017032666807795712/51975*t^6 + 3066886920760757387264/31185*t^5 + 4002475577792485963418304512/212837625*t^4 + 35706887077056476194944385024/6449625*t^3 + 1290967974781967107518017482522624/638512875*t^2 - 1294515027372635938488562670043136/638512875*t)*w^15)*z^15 + ((1114112*t^17 - 2097152*t^16 + 5570560*t^15 + 10092544/3*t^14 + 172097536/5*t^13 + 1050673152/5*t^12 + 640415891456/315*t^11 + 1950581915648/63*t^10 + 407479153917952/525*t^9 + 155027897765593088/4725*t^8 + 17620546217483370496/7425*t^7 + 5114564219140977065984/17325*t^6 + 2669741233041554438593183744/42567525*t^5 + 4716000003260110517578697801728/212837625*t^4 + 516860399380082228218814094573568/42567525*t^3 + 481942142365638991029936929601093632/58046625*t^2 - 5309130660248892420381853469360521216/638512875*t)*w^16)*z^16 + ((2359296*t^18 - 4456448*t^17 + 12582912*t^16 + 7864320*t^15 + 409206784/5*t^14 + 2511601664/5*t^13 + 515950247936/105*t^12 + 23924612005888/315*t^11 + 612267741151232/315*t^10 + 14778203434385408/175*t^9 + 65821353980937109504/10395*t^8 + 6139989414642415304704/7425*t^7 + 2670602400245624490027646976/14189175*t^6 + 628979964358796236587452858368/8513505*t^5 + 82722930537407653828027424964608/1702701*t^4 + 2590453424683075965261090218049536/51975*t^3 + 695814695669012353327034049894959713353728/10854718875*t^2 - 696356227077173977508003536060069431738368/10854718875*t)*w^17)*z^17 + ((4980736*t^19 - 9437184*t^18 + 84672512/3*t^17 + 54525952/3*t^16 + 576978944/3*t^15 + 53317992448/45*t^14 + 2210001584128/189*t^13 + 57608731885568/315*t^12 + 13490509453459456/2835*t^11 + 17113701503991808/81*t^10 + 169331223737633603584/10395*t^9 + 206365195178010157776896/93555*t^8 + 9616255420033714321889165312/18243225*t^7 + 9436325980746333083819491459072/42567525*t^6 + 1772905402599981611763096412749824/10945935*t^5 + 76389367507489750796254436893197860864/383107725*t^4 + 162700184923923937067598394373382521749504/422911125*t^3 + 91268626346479121094047129680022897841424826368/97692469875*t^2 - 91306229584330150731878820476293183031927898112/97692469875*t)*w^18)*z^18 + ((10485760*t^20 - 19922944*t^19 + 62914560*t^18 + 124780544/3*t^17 + 1342177280/3*t^16 + 2762997760*t^15 + 741496324096/27*t^14 + 81955845570560/189*t^13 + 1543926274064384/135*t^12 + 1465148307266338816/2835*t^11 + 36298565504271908864/891*t^10 + 3931665835859193626624/693*t^9 + 25647368273291388376787714048/18243225*t^8 + 1617842747066210034480833363968/2606175*t^7 + 8865342394752313327609835407015936/18243225*t^6 + 7275770720906019022702580487355891712/10945935*t^5 + 113641703681931614273104803696462398488576/73841625*t^4 + 2897814661672719678790278805734680393812017152/516891375*t^3 + 47869664972384704759657376629385921915214063497904128/1856156927625*t^2 - 47880073882680968927870463659556636132619105281769472/1856156927625*t)*w^19)*z^19 + ((22020096*t^21 - 41943040*t^20 + 139460608*t^19 + 94371840*t^18 + 15472787456/15*t^17 + 95697240064/15*t^16 + 574025105408/9*t^15 + 137004178210816/135*t^14 + 18270076603990016/675*t^13 + 93080165021646848/75*t^12 + 201720748812309364736/2025*t^11 + 63199038237046428663808/4455*t^10 + 3331223844599701651523108864/921375*t^9 + 151011192213555084422924170428416/91216125*t^8 + 656732409288868667380496891641856/482625*t^7 + 60634390605321422436547390086104219648/30405375*t^6 + 1136466203301288932517449027217259997691904/221524875*t^5 + 13375141547864828538721282778367482746950909952/596413125*t^4 + 19149253907184262423133087349898850132072848568614912/123743795175*t^3 + 12551330458105009388413167060250304433043771353260701515776/9280784638125*t^2 - 12552766860326256606389257336708510002478435893836726140928/9280784638125*t)*w^20)*z^20 + ((46137344*t^22 - 88080384*t^21 + 922746880/3*t^20 + 637534208/3*t^19 + 11798577152/5*t^18 + 657201299456/45*t^17 + 138627887661056/945*t^16 + 147972763418624/63*t^15 + 128046805689565184/2025*t^14 + 41603591442559664128/14175*t^13 + 3389806256685435584512/14175*t^12 + 1474866135226616178016256/42525*t^11 + 11660379772805621914840072192/1289925*t^10 + 9152767423420204020633922699264/2149875*t^9 + 14042751777486574324000321011974144/3869775*t^8 + 5144904311211542532955156929144946688/921375*t^7 + 5062571854274666832496984675752742607650816/328930875*t^6 + 4917841412362729715543879505643388316252372992/65786175*t^5 + 731170997032821841436698804061868540852471425172242432/1181190772125*t^4 + 187941529182646635205925927861277523435479084605970055168/23160603375*t^3 + 26324909499215216299489745628083108254376952928739464253878042624/194896477400625*t^2 - 26326491147841075256101598731995184807084136113195560442877968384/194896477400625*t)*w^21)*z^21 + ((96468992*t^23 - 184549376*t^22 + 675282944*t^21 + 1426063360/3*t^20 + 80409001984/15*t^19 + 165893111808/5*t^18 + 316156179120128/945*t^17 + 5087749942018048/945*t^16 + 138056968173518848/945*t^15 + 13874638864460546048/2025*t^14 + 1959010675167957352448/3465*t^13 + 1442274444612638303322112/17325*t^12 + 9501776665697431718268502016/429975*t^11 + 6041123562511849416492018827264/567567*t^10 + 4903980789773421030638744590352384/525525*t^9 + 633867034340012961233509262457913212928/42567525*t^8 + 81002553412510379578921796515102512381952/1879605*t^7 + 166452304487414802050163370091018373988089856/742203*t^6 + 487453220840994769438032938254331083168527644348121088/236238154425*t^5 + 421746154442840067437290096727895458702943525691482064289792/12993098493375*t^4 + 579159607886805716151360925064166617239728278461787201119593693184/714620417135625*t^3 + 4246961200607318927654458337881002105637439647170497251012052567195648/164912403954375*t^2 - 55212233156311346078595828455287042442971820977863006344813448796307456/2143861251406875*t)*w^22)*z^22 + ((201326592*t^24 - 385875968*t^23 + 1476395008*t^22 + 1056964608*t^21 + 36305895424/3*t^20 + 1123016507392/15*t^19 + 15903727026176/21*t^18 + 11564281199853568/945*t^17 + 35101252928929792/105*t^16 + 996580282339426304/63*t^15 + 391883683636682162176/297*t^14 + 2045631062870479096250368/10395*t^13 + 50172576050203997312093519872/945945*t^12 + 1342525200474965132627912163328/51597*t^11 + 66205456783776403288859487217123328/2837835*t^10 + 20123116678186013315736161889265123328/525525*t^9 + 83163651919264481807541203982491451618492416/723647925*t^8 + 64916993745005409098859056790348611884052119552/103378275*t^7 + 487456755179422859021593418731578729779005093427806208/78746051475*t^6 + 56233178148757821327871991091872409552448308428365780484096/519723939735*t^5 + 2316653897145962852918091183310955499361320539266727291239912177664/714620417135625*t^4 + 30749693564225533729207322038919551203682091313770478763165188358144/199003179375*t^3 + 463153118213052782490566406777968768954523868017998030175102800774309865324544/49308808782358125*t^2 - 463160737501228887060200799387235981866789804469888726415262943294781743169536/49308808782358125*t)*w^23)*z^23 + ((419430400*t^25 - 805306368*t^24 + 9646899200/3*t^23 + 7012876288/3*t^22 + 81503715328/3*t^21 + 1511291617280/9*t^20 + 11920933388288/7*t^19 + 193264636395520/7*t^18 + 5309918684905472/7*t^17 + 2278869790229528576/63*t^16 + 2110541261457665818624/693*t^15 + 681942342772221886332928/1485*t^14 + 27368340485824524361184313344/218295*t^13 + 11814609399589949752262829015040/189189*t^12 + 679044477880096214724624108224512/11907*t^11 + 23285639813944678975186127936341147648/243243*t^10 + 6480344852653835806857199388728482284437504/21928725*t^9 + 330488678350162361298654179644487341220839817216/197358525*t^8 + 6434460277663108988517283165820663261650738127520661504/371231385525*t^7 + 281166963516581523365269307905472691244244349474749353558016/866206566225*t^6 + 661903322925804823490071072803765492216666674007634428673327628288/61253178611625*t^5 + 1325070428624845853516873315631417095633969115671409426357584685141327872/2143861251406875*t^4 + 79398112797370136844600847169852089665710393921667787059017815076554579902464/1408823108067375*t^3 + 971317772234881114779454205744858681421526887234785506242370378668085941044630257664/147926426347074375*t^2 - 57136829948715076280204762997587250022186116451751439522407239152166437945308348416/8701554491004375*t)*w^24)*z^24 + ((872415232*t^26 - 1677721600*t^25 + 6979321856*t^24 + 15435038720/3*t^23 + 303399174144/5*t^22 + 1872941285376/5*t^21 + 79945313288192/21*t^20 + 6497514035347456/105*t^19 + 298996662745956352/175*t^18 + 6151818910048976896/75*t^17 + 120623259081490894422016/17325*t^16 + 408034433256608894025728/385*t^15 + 228080164486527557490396102656/779625*t^14 + 805563817970016813469230413381632/5457375*t^13 + 106708819037876992024810971855847424/779625*t^12 + 348293312907765052354366271865900498944/1488375*t^11 + 29375402407138806349945535479443644301180928/39760875*t^10 + 665822954531771264865496806476547741239585275904/154625625*t^9 + 6599469235577254541135446533210179627722395096631476224/142781302125*t^8 + 92692641357633720600161509624697884893706003269708909903872/101986644375*t^7 + 1272893555127976114879867153441941710546190411490599058796177260544/39264858084375*t^6 + 48537463203255091488852483379117277922154055281021658316289383350665216/23558914850625*t^5 + 10715014565207989677673239318258005881387866566245548652854198393738901848064/47531143996875*t^4 + 215633378000751638180510088117836430379409717202891022348892645640465837778272256/5473283248125*t^3 + 32592284222685340462558249982218789085991795245239784919275909262705228975278412769427193856/3698160658676859375*t^2 - 32592429921601710447955562407021331451609108603731625618464988307855158877770121669840470016/3698160658676859375*t)*w^25)*z^25 + ((1811939328*t^27 - 3489660928*t^26 + 15099494400*t^25 + 11274289152*t^24 + 674511192064/5*t^23 + 4157528342528/5*t^22 + 42324688109568/5*t^21 + 2895481193627648/21*t^20 + 286727712721076224/75*t^19 + 32309529292440600576/175*t^18 + 39065238869249651376128/2475*t^17 + 41972472248503287200874496/17325*t^16 + 65168430042421214553118343168/96525*t^15 + 45335833336757666265438875549696/131625*t^14 + 50444894162279374701536622776680448/155925*t^13 + 210820711244687178469904411779429040128/375375*t^12 + 16972553241207466094201111755289523151437824/9398025*t^11 + 1112879767390395847699257121850891810417722523648/103378275*t^10 + 24512377829690588734166634335057611716520244853673558016/206239658625*t^9 + 4498691036235965097345964817907896384982877933739238718701568/1856156927625*t^8 + 2206351775166322843534508158907097465507465683292668958038460203008/24306816909375*t^7 + 1051646139349518839566804671697670378007767067463251053211691657151381504/170147718365625*t^6 + 588135781439725770569255489031406134200766861413835485549172009853567501336576/782679504481875*t^5 + 205570683075331299190173269920316955586833882320807976923190212921921515809610399744/1304465840803125*t^4 + 847400652514964949754704032219701497192532828375768487977134552623821782569737206958460502016/16025362854266390625*t^3 + 99420025269532891392352846812748940057175174269668184569732697461515757456872656693009765437014016/4370553505709015625*t^2 - 1093622820174395693862009441258074802682145552695373344159168587250772852602907590975050116910546944/48076088562799171875*t)*w^26)*z^26 + ((3758096384*t^28 - 7247757312*t^27 + 97710505984/3*t^26 + 73819750400/3*t^25 + 4479650889728/15*t^24 + 82688589430784/45*t^23 + 2528822519922688/135*t^22 + 13751669506441216/45*t^21 + 3444195140254564352/405*t^20 + 836014002248861351936/2025*t^19 + 10549201112660556382208/297*t^18 + 366984911785640691167657984/66825*t^17 + 28153784367240902373508063952896/18243225*t^16 + 966719323306540760203746630172672/1216215*t^15 + 5902124882063488930640663427600613376/7818525*t^14 + 508064322717355995984278533362547687424/382725*t^13 + 20163489163970102561287031299407471451215757312/4652022375*t^12 + 33386495285160117933336859851175021785683291275264/1268733375*t^11 + 330917767969057593922827060287379120269336237949398810624/1113694156575*t^10 + 3856026144884246865541285314900094264700477512027890849415168/618718975875*t^9 + 1112002355424755749118987375021709610903045493214812978483333636816896/4593988395871875*t^8 + 11357786248848679509816866522615318149773633908517260663314105761976549376/656284056553125*t^7 + 18322701700309624172701411817698756892734237748091734511540484743430766468268032/8127825623465625*t^6 + 33302466538174543609182802686435262834080552031457212781845990689681228513062894436352/63397039863031875*t^5 + 91519315929808178732725621926808167029867244458563616207077756208010886738764124641200804200448/432684797065192546875*t^4 + 855877402462273573577854695001840507635494576495838444184028412671784210167328008882968427833065472/6270794160365109375*t^3 + 6381893786491142643086007030966798770027364355898823757267464020968536642837185685212975492568842567155712/56437147443285984375*t^2 - 146783734256193149111268245483019951568661095309068896081772498243896793002836830561705155778190280935604224/1298054391195577640625*t)*w^27)*z^27 + ((7784628224*t^29 - 15032385536*t^28 + 70061654016*t^27 + 160524402688/3*t^26 + 1975684956160/3*t^25 + 20220706029568/5*t^24 + 7800269689585664/189*t^23 + 636993478596755456/945*t^22 + 2540340489949806592/135*t^21 + 520373159236577787904/567*t^20 + 2476310721745127003389952/31185*t^19 + 42817647420989836248481792/3465*t^18 + 446721257093701735583394335555584/127702575*t^17 + 232016824878607979512635343845195776/127702575*t^16 + 8898682336024791536655291724486148096/5108103*t^15 + 169525214750859410375558470690253073022976/54729675*t^14 + 8554241493096208477864232014554664740577083392/834978375*t^13 + 76170861780897637539815005872115404183026656083968/1206079875*t^12 + 2573809015580771709495010131385672149061920458400126205952/3543572316375*t^11 + 121464952377439754332572222368555353300987873504979885485981696/7795859096025*t^10 + 2224006302102497391892322980128646136388042090598133816304295422722048/3573102085678125*t^9 + 1484084811307484302982744715252389461510852058763601120030741012707259973632/32157918771103125*t^8 + 666946585721280806814932246483920927524573940032686602115669375096319719361216512/105661733105053125*t^7 + 388528887439311861881691624796077825952621254574734083278494663922993782267871397675008/246544043911790625*t^6 + 427090247075189550034412337742489737826114061525300253694368753333905544649306234507687974928384/605758715891269565625*t^5 + 1653555568648950653329593901557749061322530819143202299066678050503526076831503370549485368319890423808/3028793579456347828125*t^4 + 7472620458288049196924027910079527077102768246917345766635712143717281714295812962704456655654492148072448/11013794834386719375*t^3 + 9850489219259981602045258123493652228449206702962029904372230106963025431402649312145936109882186996738103497981952/9086380738369043484375*t^2 - 9850495384176820362798160463194011143098914456265256577669945618874728586874366588880396806995692187522548719681536/9086380738369043484375*t)*w^28)*z^28 + ((16106127360*t^30 - 31138512896*t^29 + 150323855360*t^28 + 115964116992*t^27 + 4341138194432/3*t^26 + 26601953689600/3*t^25 + 5705851167834112/63*t^24 + 279791564278988800/189*t^23 + 39159446072761253888/945*t^22 + 10147259107191554048/5*t^21 + 1100730686667878310084608/6237*t^20 + 861441378515904809425436672/31185*t^19 + 111683604695849050268473946537984/14189175*t^18 + 525913226955663603257210944379420672/127702575*t^17 + 169500275568901781097297440247396696064/42567525*t^16 + 60855540664212383527725016784296914976768/8513505*t^15 + 1123288018096649171753415916200862738213240832/46990125*t^14 + 41547829715557191596158564020210803209829768757248/278326125*t^13 + 22649549256688921745371141766966414258726879763545756532736/12993098493375*t^12 + 134961172722997793780112995288251095633680255876797365546385408/3543572316375*t^11 + 3336011309804352750959283018157760231793549256474769724595301508972544/2143861251406875*t^10 + 141341463564467631997847533762391943293322296255498981047823942223036153856/1191034028559375*t^9 + 2489934570253117770499053055647582861745637749114427437137966111104234249567338496/147926426347074375*t^8 + 466234753856474057869698270394312208936995621618069647808912747571171203535147236327424/105661733105053125*t^7 + 427090310717083152598249702434160611695162693227893829811489117835362986417632443585869257900032/201919571963756521875*t^6 + 220474104292691722156315867419567317103619048017644781950139823625802206042598254474764428601358024704/121151743178253913125*t^5 + 328795344259580441494254669374545327221767242380037950512318814248774357757236374216700602570073705788997632/121151743178253913125*t^4 + 962196949863984056862234354453380902249904741453461399372104021268009291053611375916517106427537249588947714048/147926426347074375*t^3 + 5288444322348879967153101027524523639564176926126518699039432752145720103971595017758217507597723340947130473947055163179008/263505041412702261046875*t^2 - 5288446036335076813967797439295007797929796121221234722572809689999404897073211593146312365150158187000217670424427891785728/263505041412702261046875*t)*w^29)*z^29 + O(z^30)" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# CGF of labeled tournaments after substitution z -> 2zw (Section A.4) \n", "# Marking variable t is for irreducible parts\n", "qtt.subs(z=2*w*z)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.0", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.10" } }, "nbformat": 4, "nbformat_minor": 4 }