Number \(a_n(FS_r)\) of index n subsemigroups of the free semigroup of rank r
The following values were computed using
this C++ code. For a summary of the orbit data for each support size and the subsequent polynomials see
here.
| r \ n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|
| 1 |
1 | 2 | 4 | 7 | 12 | 23 | 39 | 67 | 118 |
|---|
| 2 |
2 | 11 | 62 | 382 | 2562 | 18413 | 140968 | 1142004 | 9745298 |
|---|
| 3 |
3 | 27 | 250 | 2568 | 28746 | 347691 | 4495983 | 61714968 | 894242997 |
|---|
| 4 |
4 | 50 | 644 | 9209 | 143416 | 2415078 | 43532832 | 833734416 | 16863679508 |
|---|
| 5 |
5 | 80 | 1320 | 24150 | 480736 | 10340800 | 238120365 | 5826981430 | 150609007570 |
|---|
| 6 |
6 | 117 | 2354 | 52437 | 1269738 | 33192442 | 928558122 | 27600653310 | 866466783828 |
|---|
| 7 |
7 | 161 | 3822 | 100317 | 2859878 | 87935351 | 2892046165 | 101031525714 | 3726895105059 |
|---|
| 8 |
8 | 212 | 5800 | 175238 | 5746592 | 203079088 | 7672012360 | 307755240801 | 13032655134280 |
|---|
| 9 |
9 | 270 | 8364 | 285849 | 10596852 | 423019929 | 18042714315 | 816825050010 | 39027404931886 |
|---|
| 10 |
10 | 335 | 11590 | 442000 | 18274722 | 813079415 | 38632533180 | 1947580054285 | 103592924112830 |
|---|
| 11 |
11 | 407 | 15554 | 654742 | 29866914 | 1465238951 | 76729376515 | 4261622698733 | 249671899238553 |
|---|
| 12 |
12 | 486 | 20332 | 936327 | 46708344 | 2504570454 | 143291607432 | 8692072992879 | 556011110821900 |
|---|
| 13 |
13 | 572 | 26000 | 1300208 | 70407688 | 4096363050 | 254187917217 | 16718094641859 | 1159218973374618 |
|---|
| 14 |
14 | 665 | 32634 | 1761039 | 102872938 | 6453945820 | 431689558638 | 30595875988069 | 2285577690060224 |
|---|
| 15 |
15 | 765 | 40310 | 2334675 | 146336958 | 9847206595 | 706238357145 | 53655396376965 | 4295541793230055 |
|---|
| 16 |
16 | 872 | 49104 | 3038172 | 203383040 | 14611806800 | 1118513917168 | 90675496274886 | 7744391551417168 |
|---|
| 17 |
17 | 986 | 59092 | 3889787 | 276970460 | 21159092347 | 1721823440719 | 148349597180949 | 13463091632241446 |
|---|
| 18 |
18 | 1107 | 70350 | 4908978 | 370460034 | 29986700577 | 2584837575504 | 235855685089242 | 22664032519139786 |
|---|
| 19 |
19 | 1235 | 82954 | 6116404 | 487639674 | 41689863251 | 3794695709751 | 365545078971718 | 37077004487877597 |
|---|
| 20 |
20 | 1370 | 96980 | 7533925 | 632749944 | 56973405590 | 5460504130960 | 553765453466370 | 59121471456422020 |
|---|
\begin{align}
a_n(FS_1)&=\href{https://oeis.org/A007323}{A007323}(n) \\[1em]
a_1(FS_r)&=r \\[1em]
a_2(FS_r)&=\frac{7}{2}r^2-\frac{3}{2}r \\[1em]
a_3(FS_r)&=\frac{38}{3}r^3-\frac{11}r^2+\frac{7}{3}r \\[1em]
a_4(FS_r)&=\frac{1201}{24}r^4-\frac{239}{4}r^3+\frac{311}{24}r^2+\frac{15}{4}r \\[1em]
a_5(FS_r)&=\frac{6389}{30}r^5-\frac{613}{2}r^4+\frac{185}{6}r^3+\frac{255}{2}r^2-\frac{264}{5} \\[1em]
a_6(FS_r)&=\frac{696049}{720}r^6-\frac{72727}{48}r^5-\frac{58627}{144}r^4+\frac{33101}{16}r^3-\frac{509257}{360}r^2+\frac{973}{3} \\[1em]
a_7(FS_r)&=\frac{11708603}{2520}r^7-\frac{87143}{12}r^6-\frac{146903}{18}r^5+\frac{54431}{2}r^4-\frac{9126049}{360}r^3+\frac{129725}{12}r^2-\frac{13019}{7}r \\[1em]
a_8(FS_r)&=\frac{947714177}{40320}r^8-\frac{5336487}{160}r^7-\frac{55786441}{576}r^6+\frac{7419257}{24}r^5-\frac{2105526961}{5760}r^4+\frac{110385341}{480}r^3-\frac{52875299}{672}r^2+\frac{95103}{8}r \\[1em]
a_9(FS_r)&=\frac{5649947729}{45360}r^9-\frac{78967849}{560}r^8-\frac{1039050691}{1080}r^7+\frac{142822454}{45}r^6-\frac{9770306269}{2160}r^5+\frac{2708660903}{720}r^4-\frac{44177206909}{22680}r^3+\frac{378138079}{630}r^2-\frac{776555}{9}r
\end{align}
Number \(a^I_n(FS_r)\) of index n ideals of the free semigroup of rank r
The following values were computed using
this C++ code. For a summary of the orbit data for each support size and the subsequent polynomials see
here.
| r \ n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|
| 1 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
|---|
| 2 |
2 | 3 | 6 | 10 | 20 | 35 | 68 | 126 | 242 | 458 | 886 | 1696 |
|---|
| 3 |
3 | 6 | 16 | 36 | 96 | 237 | 624 | 1608 | 4221 | 11043 | 29109 | 76768 |
|---|
| 4 |
4 | 10 | 32 | 89 | 284 | 866 | 2776 | 8860 | 28744 | 93464 | 305608 | 1000982 |
|---|
| 5 |
5 | 15 | 55 | 180 | 656 | 2330 | 8620 | 32020 | 120900 | 459660 | 1761230 | 6779350 |
|---|
| 6 |
6 | 21 | 86 | 321 | 1302 | 5212 | 21582 | 90132 | 382602 | 1639917 | 7096674 | 30926564 |
|---|
| 7 |
7 | 28 | 126 | 525 | 2331 | 10297 | 46796 | 215012 | 1003877 | 4740008 | 22622985 | 108914792 |
|---|
| 8 |
8 | 36 | 176 | 806 | 3872 | 18600 | 91520 | 455849 | 2306152 | 11808484 | 61161312 | 319883860 |
|---|
| 9 |
9 | 45 | 237 | 1179 | 6075 | 31395 | 165591 | 884592 | 4796848 | 26337348 | 146326572 | 821478540 |
|---|
| 10 |
10 | 55 | 310 | 1660 | 9112 | 50245 | 281920 | 1602175 | 9236660 | 53921531 | 318568940 | 1902539090 |
|---|
| 11 |
11 | 66 | 396 | 2266 | 13178 | 77033 | 457028 | 2745633 | 16720968 | 103104859 | 643399813 | 4059329428 |
|---|
| 12 |
12 | 78 | 496 | 3015 | 18492 | 113994 | 711624 | 4496163 | 28776892 | 186442554 | 1222285176 | 8102047571 |
|---|
| 13 |
13 | 91 | 611 | 3926 | 25298 | 163748 | 1071226 | 7088185 | 47477573 | 321812751 | 2206749233 | 15299530558 |
|---|
| 14 |
14 | 105 | 742 | 5019 | 33866 | 229334 | 1566826 | 10819459 | 75575332 | 534012038 | 3816294860 | 27571346453 |
|---|
| 15 |
15 | 120 | 890 | 6315 | 44493 | 314245 | 2235600 | 16062315 | 116655430 | 856672638 | 6360814995 | 47737864765 |
|---|
| 16 |
16 | 136 | 1056 | 7836 | 57504 | 422464 | 3121664 | 23276054 | 175312224 | 1334541552 | 10268240608 | 79840419428 |
|---|
| 17 |
17 | 153 | 1241 | 9605 | 73253 | 558501 | 4276877 | 33020579 | 257349587 | 2026164771 | 16118246499 | 129545331183 |
|---|
| 18 |
18 | 171 | 1446 | 11646 | 92124 | 727431 | 5761692 | 45971316 | 370007534 | 3007022544 | 24682915962 | 204647344752 |
|---|
| 19 |
19 | 190 | 1672 | 13984 | 114532 | 934933 | 7646056 | 62935486 | 522217071 | 4373164659 | 36975349437 | 315689966676 |
|---|
| 20 |
20 | 210 | 1920 | 16645 | 140924 | 1187330 | 10010360 | 84869790 | 724885360 | 6245397756 | 54307290760 | 476722268320 |
|---|
\begin{align*}
a^I_n(FS_1)&=1 \\[1em]
a^I_n(FS_2)& \sim \href{http://oeis.org/A001405}{A001405}(n+1) ? \\[1em]
a^I_1(FS_r)&=r \\[1em]
a^I_2(FS_r)&=\frac{1}{2}r^2+\frac{1}{2}r \\[1em]
a^I_3(FS_r)&=\frac{1}{6}r^3+\frac{3}{2}r^2-\frac{2}{3}r \\[1em]
a^I_4(FS_r)&=\frac{1}{24}r^4+\frac{5}{4}r^3-\frac{1}{24}r^2-\frac{1}{4}r \\[1em]
a^I_5(FS_r)&=\frac{1}{120}r^5+\frac{7}{12}r^4+\frac{67}{24}r^3-\frac{43}{12}r^2+\frac{6}{5}r \\[1em]
a^I_6(FS_r)&=\frac{1}{720}r^6+\frac{3}{16}r^5+\frac{461}{144}r^4-\frac{73}{48}r^3-\frac{1513}{360}r^2+\frac{10}{3}r \\[1em]
a^I_7(FS_r)&=\frac{1}{5040}r^7+\frac{11}{240}r^6+\frac{263}{144}r^5+\frac{115}{16}r^4-\frac{8089}{360}r^3+\frac{319}{15}r^2-\frac{48}{7}r \\[1em]
a^I_8(FS_r)&=\frac{1}{40320}r^8+\frac{13}{1440}r^7+\frac{1979}{2880}r^6+\frac{173}{18}r^5-\frac{66113}{5760}r^4-\frac{43913}{1440}r^3+\frac{227777}{3360}r^2-\frac{281}{8}r \\[1em]
a^I_9(FS_r)&=\frac{1}{362880}r^9+\frac{1}{672}r^8+\frac{1657}{8640}r^7+\frac{547}{90}r^6+\frac{377749}{17280}r^5-\frac{37105}{288}r^4+\frac{18446699}{90720}r^3-\frac{294191}{2520}r^2+\frac{136}{9}r \\[1em]
a^I_{10}(FS_r)&=\frac{1}{3628800}r^{10}+\frac{17}{80640}r^9+\frac{5129}{120960}r^8+\frac{14423}{5760}r^7+\frac{5648053}{172800}r^6-\frac{789689}{11520}r^5-\frac{20055283}{90720}r^4+\frac{18449327}{20160}r^3-\frac{28177631}{25200}r^2+\frac{2292}{5}r \\[1em]
a^I_{11}(FS_r)&=\frac{1}{39916800}r^{11}+\frac{19}{725760}r^{10}+\frac{937}{120960}r^9+\frac{91897}{120960}r^8+\frac{3771383}{172800}r^7+\frac{2583703}{34560}r^6-\frac{133247833}{181440}r^5+\frac{289546877}{181440}r^4-\frac{5427659}{6300}r^3-\frac{1158377}{1260}r^2+\frac{9054}{11}r \\[1em]
a^I_{12}(FS_r)&=\frac{1}{479001600}r^{12}+\frac{1}{345600}r^{11}+\frac{10487}{8709120}r^{10}+\frac{17567}{96768}r^9+\frac{137379751}{14515200}r^8+\frac{1567309}{12800}r^7-\frac{664752743}{1741824}r^6-\frac{22482445}{13824}r^5+\frac{108858294689}{10886400}r^4-\frac{11855920577}{604800}r^3+\frac{5629166951}{332640}r^2-\frac{21769}{4}r
\end{align*}
Number \(a^C_n(FS_r)\) of n-class congruences on the free semigroup of rank r
The following table was computed using the \(T(n,k)\) values below and
this GAP code.
| r \ n | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|
| 1 |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|
| 2 |
1 | 10 | 40 | 149 | 457 | 1380 | 3940 |
|---|
| 3 |
1 | 26 | 227 | 1696 | 10381 | 64954 | 367829 |
|---|
| 4 |
1 | 58 | 940 | 12053 | 124683 | 1312774 | 32656398 |
|---|
| 5 |
1 | 122 | 3383 | 68524 | 1089957 | 17321988 | 780465754 |
|---|
| 6 |
1 | 250 | 11320 | 344609 | 7962407 | 179542398 | 12045020929 |
|---|
| 7 |
1 | 506 | 36347 | 1609696 | 52053881 | 1600876052 | 147519031977 |
|---|
| 8 |
1 | 1018 | 113860 | 7172573 | 316326523 | 12911778902 | 1565476753784 |
|---|
| 9 |
1 | 2042 | 351263 | 30972244 | 1828173277 | 97095768316 | 15081546028136 |
|---|
| 10 |
1 | 4090 | 1073200 | 130896569 | 10196063247 | 694127660206 | 135628506406503 |
|---|
| 11 |
1 | 8186 | 3258467 | 544933096 | 55412413281 | 4779497152260 | 1159259144898895 |
|---|
| 12 |
1 | 16378 | 9853180 | 2244421493 | 295432808963 | 31988435265990 | 9533744204879710 |
|---|
| 13 |
1 | 32762 | 29715143 | 9173051164 | 1552590940997 | 209469188672204 | 76099049497779198 |
|---|
| 14 |
1 | 65530 | 89456680 | 37280896529 | 8070527804887 | 1348524331804574 | 593323024246963037 |
|---|
| 15 |
1 | 131066 | 268992587 | 150894854896 | 41600595455881 | 8566031734908628 | 4540142135847262133 |
|---|
| 16 |
1 | 262138 | 808222900 | 608903612813 | 213047930085003 | 53836804230621238 | 34221197250091626276 |
|---|
| 17 |
1 | 524282 | 2427159023 | 2451607805284 | 1085579112867117 | 335491118566317852 | 254797914798557657140 |
|---|
| 18 |
1 | 1048570 | 7286457760 | 9854452832489 | 5509732907735326 | 2076374535267426702 | 1878179549788810530931 |
|---|
| 19 |
1 | 2097146 | 21869334707 | 39561959263096 | 27877453473125681 | 12779714168984616356 | 13730528967947333170491 |
|---|
| 20 |
1 | 4194298 | 65627927020 | 158680447050533 | 140706743945898643 | 78302998414071527846 | 99692765346386868067082 |
|---|
\begin{align*}
a^C_n(FS_1)&=n &\text{where:}\qquad{r \brace k}&=\href{http://oeis.org/A008277}{A008277}(r,k)&& \\[1em]
a^C_1(FS_r)&={r \brace 1}T(1,1) &s(n,k)&=\href{http://oeis.org/A008275}{A008275}(n,k)&& \\[1em]
&=-s(2,1)\cdot 1 &\text{and}\qquad T(n,k)&=\text{ [ see below ]}&& \\[1em]
&=1 \\[1em]
a^C_2(FS_r)&={r \brace 1}T(2,1)+{r \brace 2}T(2,2) \\[1em]
&=-s(3,1)\cdot a^C_2(FS_{r-2})-s(3,2)\cdot a^C_2(FS_{r-1}) \\[1em]
&=4\cdot 2^r-6=\href{http://oeis.org/A131130}{A131130}(r) \\[1em]
a^C_3(FS_r)&={r \brace 1}T(3,1)+{r \brace 2}T(3,2)+{r \brace 3}T(3,3) \\[1em]
&=-s(4,1)\cdot a^C_3(FS_{r-3})-s(4,2)\cdot a^C_3(FS_{r-2})-s(4,3)\cdot a^C_3(FS_{r-1}) \\[1em]
&= \frac{113}{6}\cdot 3^r-38\cdot 2^r+\frac{45}{2} \\[1em]
a^C_4(FS_r)&={r \brace 1}T(4,1)+{r \brace 2}T(4,2)+{r \brace 3}T(4,3)+{r \brace 4}T(4,4) \\[1em]
&=-s(5,1)\cdot a^C_4(FS_{r-4})-s(5,2)\cdot a^C_4(FS_{r-3})-s(5,3)\cdot a^C_4(FS_{r-2})-s(5,4)\cdot a^C_4(FS_{r-1}) \\[1em]
&=\frac{291}{2}\cdot 4^r-\frac{745}{2}\cdot 3^r+317\cdot 2^r-\frac{189}{2} \\[1em]
a^C_5(FS_r)&={r \brace 1}T(5,1)+{r \brace 2}T(5,2)+{r \brace 3}T(5,3)+{r \brace 4}T(5,4)+{r \brace 5}T(5,5) \\[1em]
&=-s(6,1)\cdot a^C_5(FS_{r-5})-s(6,2)\cdot a^C_5(FS_{r-4})-s(6,3)\cdot a^C_5(FS_{r-3})-s(6,4)\cdot a^C_5(FS_{r-2})-s(6,5)\cdot a^C_5(FS_{r-1}) \\[1em]
&=\frac{15311}{10}\cdot 5^r-\frac{58169}{12}\cdot 4^r+5582\cdot 3^r-\frac{5493}{2}\cdot 2^r+\frac{2917}{6} \\[1em]
a^C_6(FS_r)&={r \brace 1}T(6,1)+{r \brace 2}T(6,2)+{r \brace 3}T(6,3)+{r \brace 4}T(6,4)+{r \brace 5}T(6,5)+{r \brace 6}T(6,6) \\[1em]
&=-s(7,1)\cdot a^C_6(FS_{r-6})-s(7,2)\cdot a^C_6(FS_{r-5})-s(7,3)\cdot a^C_6(FS_{r-4})-s(7,4)\cdot a^C_6(FS_{r-3})-s(7,5)\cdot a^C_6(FS_{r-2})-s(7,6)\cdot a^C_6(FS_{r-1}) \\[1em]
&=\frac{8530559}{360}\cdot 6^r-\frac{444264}{5}\cdot 5^r+\frac{3069971}{24}\cdot 4^r-\frac{782245}{9}\cdot 3^r+\frac{216245}{8}\cdot 2^r-\frac{43211}{15} \\[1em]
a^C_7(FS_r)&={r \brace 1}T(7,1)+{r \brace 2}T(7,2)+{r \brace 3}T(7,3)+{r \brace 4}T(7,4)+{r \brace 5}T(7,5)+{r \brace 6}T(7,6)+{r \brace 7}T(7,7) \\[1em]
&=-s(8,1)\cdot a^C_7(FS_{r-7})-s(8,2)\cdot a^C_7(FS_{r-6})-s(8,3)\cdot a^C_7(FS_{r-5})-s(8,4)\cdot a^C_7(FS_{r-4})-s(8,5)\cdot a^C_7(FS_{r-3})-s(8,6)\cdot a^C_7(FS_{r-2})-s(8,7)\cdot a^C_7(FS_{r-1}) \\[1em]
&=\frac{161313668}{105}\cdot 7^r-\frac{235545521}{36}\cdot 6^r+\frac{261192269}{24}\cdot 5^r-\frac{210522757}{24}\cdot 4^r+\frac{122535049}{36}\cdot 3^r-\frac{7912154}{15}\cdot 2^r+\frac{458861}{24}
\end{align*}
Number \(T(n,k)\) of order n Cayley tables ascendingly generated by k elements
The following values were computed using
this GAP code which relies on the \({\sf \href{http://tinyurl.com/jdmitchell/smallsemi/}{Smallsemi}}\) data library.
| k \ n | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|
| 2 | | 8 | 37 | 145 | 452 | 1374 | 3933 |
|---|
| 3 | | | 113 | 1257 | 9020 | 60826 | 356023 |
|---|
| 4 | | | | 3492 | 67394 | 938194 | 30492722 |
|---|
| 5 | | | | | 183732 | 6398792 | 466578957 |
|---|
| 6 | | | | | | 17061118 | 3032145644 |
|---|
| 7 | | | | | | | 77430560647 |
|---|
\begin{align*}
T(n,1)&=n \\[1em]
T(n,n)&=\href{http://oeis.org/A023814}{A023814}(n) \\[1em]
\end{align*}