Linear Recurrences For the Sums of The Characters of the Symmetric Group on n elements over shapes with n cells and , 5, rows, where mu is mostly 1's, where the non-one part of mu is a partition with at most , 5, cells. By Shalosh B. Ekhad ----------------------------------------------------- Theorem number, 1, : Let , A[2](n), be the sum of the, 1, powers of the values of the symmetric group characters over all shapes with , n + 1, cells and at most , 5, rows with mu equal to, [2], followed by , n - 1, ones. A[2](n), satisfies the following homogeneous linear recurrence of order, 3, with polynomial coefficients. 15 (n + 1) n (n + 2) A[2](n) (n + 1) (13 n + 35) (n + 2) A[2](n + 1) ---------------------------- - --------------------------------------- (n + 10) (n - 2) (n + 8) (n + 10) (n - 2) (n + 8) 2 (n + 2) (3 (n - 4) + 53 n - 19) A[2](n + 2) - -------------------------------------------- + A[2](3 + n) = 0 (n + 10) (n - 2) (n + 8) and in Maple format: 15*(n+1)*n*(n+2)/(n+10)/(n-2)/(n+8)*A[2](n)-(n+1)*(13*n+35)*(n+2)/(n+10)/(n-2)/ (n+8)*A[2](n+1)-(n+2)*(3*(n-4)^2+53*n-19)/(n+10)/(n-2)/(n+8)*A[2](n+2)+A[2](3+n ) = 0 Sketch of (semi-rigorous) proof: By using the constant term expression for the character with shape, [a[1], a[2], a[3], a[4], a[5]], and mu being, [2] with as many as needed ones appended to make it a partition of, a[1] + a[2] + a[3] + a[4] + a[5] It is (fully rigorously!) derived that that number is given by a certain c\ losed-form expression that we spare you. It follows by the fundamental theorem of WZ theory that the sum of the, 1, power of these over all shapes, [a[1], a[2], a[3], a[4], a[5]], that sum to , n + 1, satisfies SOME linear recurrence with polynomial coefficients whose order can be easily bound. This justifies looking for such a recurrenc\ e by guessing, that nevertheless, can be easily justified, if desired. For the sake of the OEIS, here are the first, 31, terms, starting with , n = 2 `` [0, 0, 0, 0, 1, 5, 25, 105, 440, 1776, 7185, 28875, 116600, 471900, 1920919, 7857785, 32334900, 133795780, 556797090, 2329737630, 9800151075, 41434617175, 176043376245, 751451351585, 3221956145584, 13873435692600, 59980471840250, 260324055921150, 1134018086435325, 4957386826917681, 21744190633748055] `` ----------------------------------------------------- Theorem number, 2, : Let , A[3](n), be the sum of the, 1, powers of the values of the symmetric group characters over all shapes with , n + 2, cells and at most , 5, rows with mu equal to, [3], followed by , n - 1, ones. A[3](n), satisfies the following homogeneous linear recurrence of order, 4, with polynomial coefficients. 3 2 - 15 n (n + 1) (61513123 n - 1648708539 n + 3033405497 n + 30805602324) 4 3 A[3](n)/((n + 10) (n + 12) %1) + (n + 1) (799670599 n - 19137562252 n 2 - 62032211914 n + 607020916222 n + 2249475470760) A[3](n + 1)/((n + 10) 5 4 3 (n + 12) %1) + (184539369 n - 3285909240 n - 28676996996 n 2 + 171770237913 n + 628456227692 n - 554304682848) A[3](n + 2)/((n + 10) 5 4 3 (n + 12) %1) - (61513123 n - 758986927 n - 28894063419 n 2 - 41572068121 n + 1325649000768 n + 2401463753136) A[3](3 + n)/((n + 10) (n + 12) %1) + A[3](n + 4) = 0 2 %1 := 9512630 n - 1701771091 n + 8632657551 and in Maple format: -15*n*(n+1)*(61513123*n^3-1648708539*n^2+3033405497*n+30805602324)/(n+10)/(n+12 )/(9512630*n^2-1701771091*n+8632657551)*A[3](n)+(n+1)*(799670599*n^4-\ 19137562252*n^3-62032211914*n^2+607020916222*n+2249475470760)/(n+10)/(n+12)/( 9512630*n^2-1701771091*n+8632657551)*A[3](n+1)+(184539369*n^5-3285909240*n^4-\ 28676996996*n^3+171770237913*n^2+628456227692*n-554304682848)/(n+10)/(n+12)/( 9512630*n^2-1701771091*n+8632657551)*A[3](n+2)-(61513123*n^5-758986927*n^4-\ 28894063419*n^3-41572068121*n^2+1325649000768*n+2401463753136)/(n+10)/(n+12)/( 9512630*n^2-1701771091*n+8632657551)*A[3](3+n)+A[3](n+4) = 0 Sketch of (semi-rigorous) proof: By using the constant term expression for the character with shape, [a[1], a[2], a[3], a[4], a[5]], and mu being, [3] with as many as needed ones appended to make it a partition of, a[1] + a[2] + a[3] + a[4] + a[5] It is (fully rigorously!) derived that that number is given by a certain c\ losed-form expression that we spare you. It follows by the fundamental theorem of WZ theory that the sum of the, 1, power of these over all shapes, [a[1], a[2], a[3], a[4], a[5]], that sum to , n + 2, satisfies SOME linear recurrence with polynomial coefficients whose order can be easily bound. This justifies looking for such a recurrenc\ e by guessing, that nevertheless, can be easily justified, if desired. For the sake of the OEIS, here are the first, 31, terms, starting with , n = 3 `` [1, 1, 2, 3, 6, 10, 19, 28, 35, -20, -272, -1187, -3189, -3210, 35192, 354161, 2345645, 13354555, 70446386, 355008503, 1737304616, 8333759862, 39422604369, 184635436342, 858532133887, 3971275701001, 18300687210746, 84108487619317, 385837659240628, 1767810347344706, 8093661288860775] `` ----------------------------------------------------- Theorem number, 3, : Let , A[4](n), be the sum of the, 1, powers of the values of the symmetric group characters over all shapes with , n + 3, cells and at most , 5, rows with mu equal to, [4], followed by , n - 1, ones. A[4](n), satisfies the following homogeneous linear recurrence of order, 5, with polynomial coefficients. 2 140 (n + 1) n (4596807 (n - 2) + 132461324 n + 170614056) A[4](n) - ------------------------------------------------------------------ + 1/3 (n + 14) (n + 12) %1 (n + 1) 3 2 (306723183 (n - 2) + 68929768877 (n - 2) + 433360582818 n - 446272231244) 4 A[4](n + 1)/((n + 14) (n + 12) %1) + 2/3 (901331858 (n - 2) 3 2 + 5758515527 (n - 2) + 76776077653 (n - 2) + 1027037988082 n 4 + 1340780335636) A[4](n + 2)/((n + 14) (n + 12) %1) - (18888138 (n - 2) 3 2 + 1844934386 (n - 2) + 59473390401 (n - 2) + 435245686067 n - 204929043596) A[4](n + 3)/((n + 14) (n + 12) %1) - 1/3 ( 4 3 2 137544832 (n - 2) + 906463770 (n - 2) - 15299564116 (n - 2) + 340733864409 n + 4105851510552) A[4](n + 4)/((n + 14) (n + 12) %1) + A[4](n + 5) = 0 2 %1 := 5160429 (n - 2) - 98412314 n + 2663293148 and in Maple format: -140*(n+1)*n*(4596807*(n-2)^2+132461324*n+170614056)/(n+14)/(n+12)/(5160429*(n-\ 2)^2-98412314*n+2663293148)*A[4](n)+1/3*(n+1)*(306723183*(n-2)^3+68929768877*(n -2)^2+433360582818*n-446272231244)/(n+14)/(n+12)/(5160429*(n-2)^2-98412314*n+ 2663293148)*A[4](n+1)+2/3*(901331858*(n-2)^4+5758515527*(n-2)^3+76776077653*(n-\ 2)^2+1027037988082*n+1340780335636)/(n+14)/(n+12)/(5160429*(n-2)^2-98412314*n+ 2663293148)*A[4](n+2)-(18888138*(n-2)^4+1844934386*(n-2)^3+59473390401*(n-2)^2+ 435245686067*n-204929043596)/(n+14)/(n+12)/(5160429*(n-2)^2-98412314*n+ 2663293148)*A[4](n+3)-1/3*(137544832*(n-2)^4+906463770*(n-2)^3-15299564116*(n-2 )^2+340733864409*n+4105851510552)/(n+14)/(n+12)/(5160429*(n-2)^2-98412314*n+ 2663293148)*A[4](n+4)+A[4](n+5) = 0 Sketch of (semi-rigorous) proof: By using the constant term expression for the character with shape, [a[1], a[2], a[3], a[4], a[5]], and mu being, [4] with as many as needed ones appended to make it a partition of, a[1] + a[2] + a[3] + a[4] + a[5] It is (fully rigorously!) derived that that number is given by a certain c\ losed-form expression that we spare you. It follows by the fundamental theorem of WZ theory that the sum of the, 1, power of these over all shapes, [a[1], a[2], a[3], a[4], a[5]], that sum to , n + 3, satisfies SOME linear recurrence with polynomial coefficients whose order can be easily bound. This justifies looking for such a recurrenc\ e by guessing, that nevertheless, can be easily justified, if desired. For the sake of the OEIS, here are the first, 31, terms, starting with , n = 4 `` [0, 0, 1, 3, 9, 25, 70, 196, 553, 1569, 4460, 12650, 35519, 97747, 258986, 639380, 1357970, 1796050, -3784965, -47739875, -284561195, -1388145395, -\ 6111329686, -25046164088, -96224616494, -343163977550, -1096068488775, -\ 2798846265969, -2708082995457, 32898543510679, 351692642359350] `` ----------------------------------------------------- Theorem number, 4, : Let , A[2, 2](n), be the sum of the, 1, powers of the values of the symmetric group characters over all shapes with , n + 3, cells and at most , 5, rows with mu equal to, [2, 2], followed by , n - 1, ones. A[2, 2](n), satisfies the following homogeneous linear recurrence of order, 5, with polynomial coefficients. 2 n (n + 1) (1665652437 n + 14380716089 n + 41825673630) A[2, 2](n) 15/4 ------------------------------------------------------------------ - 1/2 (n + 14) (n + 12) %1 3 2 (n + 1) (12599184588 n + 118165502671 n + 390175534535 n + 517966559250) 4 3 A[2, 2](n + 1)/((n + 14) (n + 12) %1) + 1/4 (2810136458 n - 54160485338 n 2 - 863000171729 n - 3825081620077 n - 6114496071750) A[2, 2](n + 2)/( 4 3 (n + 14) (n + 12) %1) - 1/4 (1728913612 n - 2542040726 n 2 - 139634293690 n - 557741526505 n - 451098861663) A[2, 2](n + 3)/( 4 3 (n + 14) (n + 12) %1) - 1/4 (1183297421 n + 17655092320 n 2 - 13324066442 n - 734242647028 n - 1579093717131) A[2, 2](n + 4)/( (n + 14) (n + 12) %1) + A[2, 2](n + 5) = 0 2 %1 := 78914299 n - 464731484 n + 683454168 and in Maple format: 15/4*n*(n+1)*(1665652437*n^2+14380716089*n+41825673630)/(n+14)/(n+12)/(78914299 *n^2-464731484*n+683454168)*A[2,2](n)-1/2*(n+1)*(12599184588*n^3+118165502671*n ^2+390175534535*n+517966559250)/(n+14)/(n+12)/(78914299*n^2-464731484*n+ 683454168)*A[2,2](n+1)+1/4*(2810136458*n^4-54160485338*n^3-863000171729*n^2-\ 3825081620077*n-6114496071750)/(n+14)/(n+12)/(78914299*n^2-464731484*n+ 683454168)*A[2,2](n+2)-1/4*(1728913612*n^4-2542040726*n^3-139634293690*n^2-\ 557741526505*n-451098861663)/(n+14)/(n+12)/(78914299*n^2-464731484*n+683454168) *A[2,2](n+3)-1/4*(1183297421*n^4+17655092320*n^3-13324066442*n^2-734242647028*n -1579093717131)/(n+14)/(n+12)/(78914299*n^2-464731484*n+683454168)*A[2,2](n+4)+ A[2,2](n+5) = 0 Sketch of (semi-rigorous) proof: By using the constant term expression for the character with shape, [a[1], a[2], a[3], a[4], a[5]], and mu being, [2, 2] with as many as needed ones appended to make it a partition of, a[1] + a[2] + a[3] + a[4] + a[5] It is (fully rigorously!) derived that that number is given by a certain c\ losed-form expression that we spare you. It follows by the fundamental theorem of WZ theory that the sum of the, 1, power of these over all shapes, [a[1], a[2], a[3], a[4], a[5]], that sum to , n + 3, satisfies SOME linear recurrence with polynomial coefficients whose order can be easily bound. This justifies looking for such a recurrenc\ e by guessing, that nevertheless, can be easily justified, if desired. For the sake of the OEIS, here are the first, 31, terms, starting with , n = 4 `` [2, 2, 3, 5, 11, 27, 82, 268, 975, 3671, 14446, 57796, 235765, 971193, 4042482, 16943384, 71505764, 303441604, 1294526389, 5548488359, 23887420295, 103262464415, 448133268714, 1951919703612, 8531615646976, 37414342665712, 164595199147987, 726281749386593, 3213994260729605, 14262081438708141, 63455391521132822] `` ----------------------------------------------------- Theorem number, 5, : Let , A[5](n), be the sum of the, 1, powers of the values of the symmetric group characters over all shapes with , n + 4, cells and at most , 5, rows with mu equal to, [5], followed by , n - 1, ones. A[5](n), satisfies the following homogeneous linear recurrence of order, 5, with polynomial coefficients. 3 45/2 n (n + 1) (12498339512087722915449535305 n 2 - 945588555570486247694409378968 n - 22555248656003949684143915852323 n - 21435348327584917630630001650934) A[5](n)/((n + 15) (n + 13) %1) + 3/2 3 (n + 1) (4547537034469009493637465755489 n 2 + 354458804231958206768312541508589 n + 2013066691398186466641526267694022 n + 1702777523767086022630713773928000) A[5](n + 1)/((n + 15) (n + 13) %1) 4 - 3/2 (n + 1) (85045862015384368646607121078 n 3 - 1910479452109766764245843374523 n 2 - 215759776658204589066574156540485 n - 1627524867619856510215221058088570 n - 2735992734405416620763118203969832) A[5](n + 2)/((n + 15) (n + 13) %1) 5 - 1/2 (302477862053062313523387350908 n 4 - 17279436497120086246152071851135 n 3 + 255769328347158498080811596292762 n 2 + 6979249917426657955824600869397799 n + 34196705502464627304819806821649714 n + 28095492364056081451385078748876744) A[5](n + 3)/((n + 15) (n + 13) %1) 5 - 1/2 (23462586282812207388114957771 n 4 3 - 2385792615295877748647575916104 n + 38761995174688500114749679829097 n 2 + 1476525483204894587848136913028360 n + 7289729645805676605209984177887444 n + 14366917172926624581261576004811952) A[5](n + 4)/((n + 15) (n + 13) %1) + A[5](n + 5) = 0 3 2 %1 := 9326378169040047828047291594 n - 786122203010736618496292120739 n + 18571983848391992270063499328378 n - 6549144322181100087041206822800 and in Maple format: 45/2*n*(n+1)*(12498339512087722915449535305*n^3-945588555570486247694409378968* n^2-22555248656003949684143915852323*n-21435348327584917630630001650934)/(n+15) /(n+13)/(9326378169040047828047291594*n^3-786122203010736618496292120739*n^2+ 18571983848391992270063499328378*n-6549144322181100087041206822800)*A[5](n)+3/2 *(n+1)*(4547537034469009493637465755489*n^3+354458804231958206768312541508589*n ^2+2013066691398186466641526267694022*n+1702777523767086022630713773928000)/(n+ 15)/(n+13)/(9326378169040047828047291594*n^3-786122203010736618496292120739*n^2 +18571983848391992270063499328378*n-6549144322181100087041206822800)*A[5](n+1)-\ 3/2*(n+1)*(85045862015384368646607121078*n^4-1910479452109766764245843374523*n^ 3-215759776658204589066574156540485*n^2-1627524867619856510215221058088570*n-\ 2735992734405416620763118203969832)/(n+15)/(n+13)/(9326378169040047828047291594 *n^3-786122203010736618496292120739*n^2+18571983848391992270063499328378*n-\ 6549144322181100087041206822800)*A[5](n+2)-1/2*(302477862053062313523387350908* n^5-17279436497120086246152071851135*n^4+255769328347158498080811596292762*n^3+ 6979249917426657955824600869397799*n^2+34196705502464627304819806821649714*n+ 28095492364056081451385078748876744)/(n+15)/(n+13)/( 9326378169040047828047291594*n^3-786122203010736618496292120739*n^2+ 18571983848391992270063499328378*n-6549144322181100087041206822800)*A[5](n+3)-1 /2*(23462586282812207388114957771*n^5-2385792615295877748647575916104*n^4+ 38761995174688500114749679829097*n^3+1476525483204894587848136913028360*n^2+ 7289729645805676605209984177887444*n+14366917172926624581261576004811952)/(n+15 )/(n+13)/(9326378169040047828047291594*n^3-786122203010736618496292120739*n^2+ 18571983848391992270063499328378*n-6549144322181100087041206822800)*A[5](n+4)+A [5](n+5) = 0 Sketch of (semi-rigorous) proof: By using the constant term expression for the character with shape, [a[1], a[2], a[3], a[4], a[5]], and mu being, [5] with as many as needed ones appended to make it a partition of, a[1] + a[2] + a[3] + a[4] + a[5] It is (fully rigorously!) derived that that number is given by a certain c\ losed-form expression that we spare you. It follows by the fundamental theorem of WZ theory that the sum of the, 1, power of these over all shapes, [a[1], a[2], a[3], a[4], a[5]], that sum to , n + 4, satisfies SOME linear recurrence with polynomial coefficients whose order can be easily bound. This justifies looking for such a recurrenc\ e by guessing, that nevertheless, can be easily justified, if desired. For the sake of the OEIS, here are the first, 31, terms, starting with , n = 5 `` [1, 0, 0, 0, 2, 10, 43, 161, 587, 2070, 7268, 25301, 88187, 307009, 1071122, 3738761, 13065741, 45643352, 159287484, 554279458, 1919773756, 6599629366, 22439538137, 75068478034, 245182506655, 771856723126, 2287648139340, 6059950219180, 12202304674560, 1619442792942, -179396238142425] `` ----------------------------------------------------- Theorem number, 6, : Let , A[3, 2](n), be the sum of the, 1, powers of the values of the symmetric group characters over all shapes with , n + 4, cells and at most , 5, rows with mu equal to, [3, 2], followed by , n - 1, ones. A[3, 2](n), satisfies the following homogeneous linear recurrence of order, 5, with polynomial coefficients. 3 - 15 (n + 1) n (2241358464636696306286592 (n - 1) 2 - 32112443298676855968334563 (n - 1) - 304272352828163671953553169 n + 187674094972284356342560313) A[3, 2](n)/((n + 15) (n + 13) %1) + (n + 1) 4 3 (35517986344709301115202366 (n - 1) - 389142691132031878315291413 (n - 1) 2 - 6674743471193428417170666176 (n - 1) - 17413925616255775323578126145 n + 29214942097301530277427532257) A[3, 2](n + 1)/((n + 15) (n + 13) %1) + 2 5 4 (597229631701069834923331 (n - 1) + 35767500949221103623926780 (n - 1) 3 - 780516757562940662536028902 (n - 1) 2 - 10801955352063391003110685205 (n - 1) - 40213346335820901293839828704 n + 1072338169320994040400283776) A[3, 2](n + 2)/((n + 15) (n + 13) %1) - 2 5 4 (1758711862761573066490963 (n - 1) + 20979170001610784460737661 (n - 1) 3 - 632569958187325675366343154 (n - 1) 2 - 6921184669242946132697452262 (n - 1) - 412252743687121518937048732 n + 91277322498525632201644332876) A[3, 2](n + 3)/((n + 15) (n + 13) %1) + ( 5 4 425355086962149942231778 (n - 1) - 8238908510752282549255153 (n - 1) 3 - 239763139609629915001008992 (n - 1) 2 + 1010788270672841565630716333 (n - 1) + 21235593328569405850874627074 n - 15998130378348976942562680514) A[3, 2](n + 4)/((n + 15) (n + 13) %1) + A[3, 2](n + 5) = 0 2 %1 := 3111608615021640040272863 (n - 1) - 53013061398177484065799542 n + 234429443360372203796359837 and in Maple format: -15*(n+1)*n*(2241358464636696306286592*(n-1)^3-32112443298676855968334563*(n-1) ^2-304272352828163671953553169*n+187674094972284356342560313)/(n+15)/(n+13)/( 3111608615021640040272863*(n-1)^2-53013061398177484065799542*n+ 234429443360372203796359837)*A[3,2](n)+(n+1)*(35517986344709301115202366*(n-1)^ 4-389142691132031878315291413*(n-1)^3-6674743471193428417170666176*(n-1)^2-\ 17413925616255775323578126145*n+29214942097301530277427532257)/(n+15)/(n+13)/( 3111608615021640040272863*(n-1)^2-53013061398177484065799542*n+ 234429443360372203796359837)*A[3,2](n+1)+2*(597229631701069834923331*(n-1)^5+ 35767500949221103623926780*(n-1)^4-780516757562940662536028902*(n-1)^3-\ 10801955352063391003110685205*(n-1)^2-40213346335820901293839828704*n+ 1072338169320994040400283776)/(n+15)/(n+13)/(3111608615021640040272863*(n-1)^2-\ 53013061398177484065799542*n+234429443360372203796359837)*A[3,2](n+2)-2*( 1758711862761573066490963*(n-1)^5+20979170001610784460737661*(n-1)^4-\ 632569958187325675366343154*(n-1)^3-6921184669242946132697452262*(n-1)^2-\ 412252743687121518937048732*n+91277322498525632201644332876)/(n+15)/(n+13)/( 3111608615021640040272863*(n-1)^2-53013061398177484065799542*n+ 234429443360372203796359837)*A[3,2](n+3)+(425355086962149942231778*(n-1)^5-\ 8238908510752282549255153*(n-1)^4-239763139609629915001008992*(n-1)^3+ 1010788270672841565630716333*(n-1)^2+21235593328569405850874627074*n-\ 15998130378348976942562680514)/(n+15)/(n+13)/(3111608615021640040272863*(n-1)^2 -53013061398177484065799542*n+234429443360372203796359837)*A[3,2](n+4)+A[3,2](n +5) = 0 Sketch of (semi-rigorous) proof: By using the constant term expression for the character with shape, [a[1], a[2], a[3], a[4], a[5]], and mu being, [3, 2] with as many as needed ones appended to make it a partition of, a[1] + a[2] + a[3] + a[4] + a[5] It is (fully rigorously!) derived that that number is given by a certain c\ losed-form expression that we spare you. It follows by the fundamental theorem of WZ theory that the sum of the, 1, power of these over all shapes, [a[1], a[2], a[3], a[4], a[5]], that sum to , n + 4, satisfies SOME linear recurrence with polynomial coefficients whose order can be easily bound. This justifies looking for such a recurrenc\ e by guessing, that nevertheless, can be easily justified, if desired. For the sake of the OEIS, here are the first, 31, terms, starting with , n = 5 `` [0, 1, 2, 4, 9, 20, 51, 132, 384, 1175, 3975, 14344, 55628, 226161, 955813, 4138695, 18230580, 81158085, 363860980, 1638635544, 7401954755, 33505161034, 151896024423, 689461533821, 3132770327904, 14248325387475, 64863541552056, 295553690517012, 1347954163190749, 6153527662513394, 28118468789335045] `` ----------------------------------------------------- This concludes this article, that took, 54046.518, seconds. to generate.