(*********************************************************************** Mathematica-Compatible Notebook This notebook can be used on any computer system with Mathematica 4.0, MathReader 4.0, or any compatible application. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. ***********************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 282896, 6457]*) (*NotebookOutlinePosition[ 283669, 6484]*) (* CellTagsIndexPosition[ 283625, 6480]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell["On Relations ", "Title"], Cell["Jaime Rangel-Mondrag\[OAcute]n", "Author", TextAlignment->Left, TextJustification->0], Cell["\<\ Universidad Aut\[OAcute]noma de Quer\[EAcute]taro, Mexico jrangel@sunserver.uaq.mx May, 2002\ \>", "Address", TextAlignment->Left, TextJustification->0], Cell[TextData[StyleBox["Permission is hereby granted to reproduce part or all \ of this file for any purpose other than direct profit providing that the \ source is acknowledged.", FontColor->RGBColor[0, 0, 1]]], "Reference", TextAlignment->Left, TextJustification->0], Cell["\<\ Given a set A, the set of all possible relations defined on it has found a \ prominent place as a natural framework both in applied and theoretical \ research. A relation on A is any subset of A \[Times] A. This notebook \ includes the generation and enumeration of important families of relations. \ The enumeration of these families is accomplished under conjugacy \ equivalence by means of Burnside\[CloseCurlyQuote]s lemma following the ideas \ of Davis. The families include relations in general, symmetric relations, \ reflexive relations, graphs, partial and total orders, lattices and \ functions. File onRelations.pdf containing all figures refered to in the text \ complements this notebook.\ \>", "Abstract"], Cell["\<\ \tRelation seems to be the principle of order. At least it can be said that the various conceptions of order which appear in \ the greats books involve the idea of relation and of different kinds of \ relationship. \tThe order of the universe or of nature, for example, seems to be \ differently conceived according as things are causally related to one \ another, related as lower and higher species in a hierarchy of grades of \ being, or as the parts of one all-embracing whole. \tIn each case, it makes a difference, as we have already observed, whether \ the relations involved are thought to be real or logical, and internal or \ external to the things related. \tRelations similarly enter into conceptions of psychological, political, and \ moral order - the order of the parts of the soul, the order of classes or \ functions in the state, the order of goods, of means and ends, of duties, of \ loves. \t \tRELATION \tThe Syntopicon Vol. II \tGreat Books \tEncyclopaedia Britannica, Inc. \tSixth Printing, 1996 \t\ \>", "Caption", TextAlignment->Right], Cell[CellGroupData[{ Cell["References", "Section"], Cell[GraphicsData["Bitmap", "\<\ CF5dJ6E]HGAYHf4PAg9QL6QYHgIVIWo ooooool01?ooo`04R8R800000000A4A42oooo`04^k^k0000000000002?oo o`<000000k^k^oooooooo`05oooo00>k^k/00000000020000003A4A4oooo oooo00Coool016IVIP00000008R8R0Koool015EEE@00000008R8R0Koool0 16IVIP00000008R8R0Coool016IVIP00000004A4A0Woool3000000>IVIWo ooooool01?ooo`04R8R800000000A4A42oooo`04^k^k0000000000002ooo o`03VIVI0000000000L000000hR8R?ooooooo`04oooo00>8R8P000000000 20000003IVIVoooooooo01Koool0017oool018R8R000000006IVIPKoool0 13oooo00Bk^k/000000014A4@6oooo 0`0000038R8Roooooooo00Coool013ZZZ[oooooool01Oooo`04IVIV00000000EEEE1oooo`04R8R800000000 A4A42oooo`04^k^k0000000000002?ooo`<000000k^k^oooooooo`05oooo 00Bk^k/000000000000>oooo00Ck^k_oooooool01Oooo`04R8R80000 0000A4A42oooo`04^k^k0000000000002?ooo`04ZZZZ000000004A4A6ooo o`04k^k_oooooool01Oooo`04 ^k^k0000000000003oooo`04R8R800000000R8R81?ooo`068R8R0000R8R8 R8R800008R8R1?ooo`04VIVI00000000R8R81_ooo`05k^k^000000000000 8R8Soooooool01Oooo`048R8R0000 0000VIVI1Oooo`04IVIV00000000MgMg2?ooo`04R8R800000000A4A42ooo o`04^k^k0000000000002?ooo`<000000k^k^oooooooo`05oooo00Bk^k/0 00000000000?oooo00BZZZX00000001gMgL4oooo0P0000:k^k/2000000G^ k^kooooooooooon8R8P00P000003R8R8oooooooo00Goool0128R8P000000 09VIV@Goool016IVIP00000007MgM`Soool018R8R000000004A4A0_oool0 1;^k^`000000000000Soool0114A4@0000000;^k^a[oool01MgMg@000000 00000:ZZZP0Eoooo000Boooo00Ck^k/00000 00000^k^kP8000001K^k^oooooooooooogMgM`02000000>k^k_oooooool0 1Oooo`04IVIV00000000R8R81Oooo`04k ^k/0000000000^k^kP8000001K^k^oooooooooooogMgM`02000000>k^k_o ooooool01Oooo`04IVIV00000000R8R81Oooo`04k^k_oooooool01Oooo`04^k^k00000000 00004?ooo`04A4A400000000ck ^k_oooooool01Oooo`04^k^k0000000000001hR8R003^k^koooooooo00Ko ool018R8R00000000;^k^`;oool00b8R8P0009VIV@02oooo00>ZZZX00000 00000oooo`8000000dA4A?ooooooo`07oooo00A4A4@00000002k^k/3oooo 00AVIVH000000028R8P9oooo00B8R8P000000014A4@;oooo00Bk^k/00000 00000007oooo00Bk^k/000000000000Eoooo00?^k^j8R8P000000`000003 8R8Rck^k_ooook^k_oooooool0 1Oooo`03^k^k0000000000P000000hR8R?ooooooo`06oooo00BIVIT00000 0028R8P2oooo0P000004^k^koooooooogMgM0P000003^k^koooock^k/R8R8000000`000003MgMgk^k^oooo 01Soool001?oool01[^k^`00000008R8R?oook^k^`800004oooo00DA4A40 0028R8Sooonk^k/00P000003R8R8oooooooo00Ooool01;^k^`00000007Mg M`?oool300002_ooo`04R8R800000000A4A42oooo`03^k^k0000000000`0 00000k^k^oooooooo`05oooo00>k^k/00000000020000003R8R8oooooooo 00Koool01[^k^`00000008R8R?oook^k^`800004oooo00DA4A400028R8So oonk^k/00P000003R8R8oooooooo00Ooool01;^k^`00000007MgM`?oool3 00002_ooo`04R8R800000000A4A42oooo`04^k^k0000000000001oooo`04 ^k^k0000000000004oooo`03VIVI00000000008000000ck^k_oooooool01oooo`04k^k^00000000A4A40_oo o`04^k^k00000000A4A42_ooo`04R8R800000000A4A42oooo`03^k^k0000 000000`000000k^k^oooooooo`05oooo00Bk^k/000000000000Aoooo0P00 0005A4A4ooooVIVI00008R8R00Coool01DA4A00006IVI_oooiVIV@020000 00>k^k_oooooool01oooo`04k^k^00000000A4A40_ooo`04^k^k00000000 A4A42_ooo`04R8R800000000A4A42oooo`04^k^k0000000000001oooo`04 coooo00Jk^k/000000000000A4A7k ^k_oooooool02?ooo`04R8R800000000A4A42oooo`04^k^k000000000000 2?ooo`<000000k^k^oooooooo`05oooo00Bk^k/000000000000Aoooo00M4 A4@00000003ooom4A4@00028R8P01?ooo`05VIVI00000000ooooMgMg0080 000;oooo00IVIVH00000003MgMgooomVIVH2000000>k^k_oooooool02?oo o`04R8R800000000A4A42oooo`04^k^k0000000000002?ooo`<000000k^k ^oooooooo`0>oooo00E4A4@00000000A4A7k^k_oooooool01Oooo`04 ^k^k0000000000004Oooo`04R8R800000000gMgM0P000003ck^ kP0Poooo000Doooo00Bk^k/000000028R8P200001_ooo`06A4A40000R8R8 4A4A0000R8R83?ooo`044A4A0000MgMggMgM0P000003MgMgoooooooo00Wo ool018R8R000000004A4A0_oool01;^k^`000000000000Soool3000000>k ^k_oooooool01Oooo`04^k^k0000000000004Oooo`04^k^k00000000R8R8 0P0000Koool01TA4A00008R8R14A4@0008R8R0coool0114A4@0007MgMmgM g@8000000gMgMoooooooo`09oooo00B8R8P000000014A4@;oooo00Bk^k/0 000000000008oooo00B8R8P00000001EEED?oooo00B8R8P000000014A4@Q oooo000Doooo00K^k^h00000001VIVH0000c8R8Soooooool0 2_ooo`04A4A40000A4A4^k^k0P000003VIVIoooooooo00Woool018R8R000 000004A4A0_oool01;^k^`000000000000Soool01IVIT0001EEED00P000003^k^koooooooo00[oool018R8R000028R 8XR8R08000000mgMgOooooooo`09oooo00B8R8P000000014A4@;oooo00Bk ^k/0000000000008oooo0`000003^k^koooooooo00Goool01;^k^`000000 000001;oool01A4A4@0004A4A00005EEE@06oooo00>IVIT0001EEED00P00 0003^k^koooooooo00[oool018R8R000028R8XR8R08000000mgMgOoooooo o`09oooo00B8R8P000000014A4@;oooo00Bk^k/0000000000009oooo00@R 8R800000002ZZZX>oooo00BZZZX00000000R8R8Qoooo000Eoooo00E4A4@0 000000000028R8P01_ooo`03ck^k/3oooo00C^k^j8R8PA4A54A4@Goooo000Eoooo00Bk^k/0 000000000008oooo00AVIVH000000014A4@>oooo00EgMgL000000000002k ^k/01oooo`03A4A40000000000/00006oooo00Bk^k/0000000000008oooo 0`000003^k^koooooooo00Goool00k^k^`0000000008000000=4A4Cooooo ool02?ooo`04^k^k0000000000002?ooo`04IVIV00000000A4A43_ooo`05 MgMg000000000000^k^k00Ooool00dA4A0000000000;00001_ooo`04^k^k 0000000000002oooo`03VIVI00000000008000000c8R8Soooooool01Oooo`03ZZZZ4A4A0000008000000b8R8TA4A4A4A003 000000=4A4Coooooool05Oooo`005Oooo`04k^k^00000000A4A42?ooo`04 R8R800000000MgMg3_ooo`04VIVI0000000000002?ooo`03A4A400000000 00/00006oooo00Bk^k/0000000000008oooo0`000003^k^koooooooo00Go ool00k^k^`0000000008000000=4A4Coooooool02?ooo`04k^k^00000000 A4A42?ooo`04R8R800000000MgMg3_ooo`04VIVI0000000000002?ooo`03 A4A40000000000/00006oooo00Bk^k/000000000000k^k/R8R80 00001P000003R8R8oooooooo00Koool00lcoooo00C^k^jk^k^k^k_k^k[^k^k^k^k^k^`Soool3^k^k00?^k^koooooool01Oooo`03k^k^ ^k^k^k^k00Rk^k/00lck^k[^k^k^k^mgMg@koool01>k^k[^k^k^k^lc8R8RZZZ[oool06?oo o`00ooooo`?oool00?ooool3oooo003ooooo0oooo`00ooooo`?oool00?oo ool3oooo003ooooo0oooo`00ooooo`?oool000;ooonQM5ZT00IeFjEoIj^X VN;EeFjD0EGAJY0;oool000;ooonRM5ZT00N0J:c;`]gUh>kZi_7o oooEcNB6Kk00EGAJY0;oool000;ooom?M5ZT00=lI:V0J:alI:T01GAJY003 NF2WPVZ]OFBZ00UdFZ@01GMMYX1X[8=[[WiVZgEKY@07M5ZT00=gGJIhGjIg GJH02GAJY003NF2WPFZ]O6>Y00IdFZ@017aSZH1X[81X[7MMYP=dFZ@00gQO YWmWZgEKY@0>M5ZT00AkHZR3Jjj1JZekHZP4M5ZT00J5KZn@O;OLe^Sooonk [m=kHZQDM5ZT0_ooo`000_ooodidFZ@01XQb/K^_dlk5gkjbeI=n^7QOYP9d FZ@01X5Z[K2QbmChf9Z8_GeTZPIdFZ@028=[[ZJEaL>hfhf9n= `89Z[GEKY@AdFZ@01GILYHih]J^Kb:JEaG]RZ007M5ZT00IlHjV[VlSBbN6j [M::MK=eFjD3M5ZT00b6Kk2k[m?;`]g>aMnVULF0J:adFZAoIj^]W/W:`=bM R[mlHjT;M5ZT00QkHZR@O;NhZm7;`]g7_=Zi[=68L[5lHjT4M5ZT00AoIj__ k?Gmo?jIQKaDM5ZT0_ooo`000_ooodidFZ@02MkHjOooooooooooooGcnJJE aGMMYWEKYKjbe@03oooo00?lnog1]MIiH:L017AJY00:Nf:XfmCWoooof=7V ^ZgBhM_[oooofmCWTgjhMefV0gAJY006MefVZi_8ooooooooXY32MUbU1WAJ Y006VHFlm_Cioooooooom?;hT7bg0WAJY009MUbUfmCWoooooooon_WloOcn c/GOT7bgakcJ00;oool00o[io;JXcgMMYP09M5ZT00YgGJJ[VlSjnOcmo?k; `]g7_=[lnoghmo^hZm5lHjT4M5ZT00CNf>Woooo3^=QmI:YCM5ZT0_ooo`00 0_ooodidFZ@04?Gcn?ooooknon?NkOKenOCan9V5_8E^[mkHjOooooCanScf=7VZ9S6fmCWoooog]SYOfN[P6R/g=KXn?Ok T7bg0gAJY004j>C`ooooeC`UH6i00=d FZ@01WMMY/RnfockoOooojnPbgQOYPEdFZ@049V5_?GcnOooomSAiYn=`?oo okNYd7AJY;BVc_Sgnooool[0g8=[[WAJY8Ye/mcFj0;oool01=cFj:JEaNo/ mNKRk`UdFZ@01:fNbOSgnocloJfNb@=dFZ@01If:_ooooocloLRnfgMMYP02 M5ZT00FIQKc^joCooonj[M9gGJH0DWAJY0;oool000;ooom>M5ZT00O>aMom o?kmo?j>N;EeFjF]W/WbkoH00]kHj@07ooood/WQM5ZTME^UT7bgo?cmhmk] 00=dFZ@01>STl?ooonSTl91l]`9dFZ@01WEKYJ:@`_SgnoknomSAiWEKY@9d FZ@01WEKYIN4^oSgnooooo[io8ih]@EdFZ@05hYe/m_DioooonOSkhQb/L6e e_ooohI_/;JXcoSgnoooom37h8E^[gAJY7EKYJRHa_GcnOoooo;_mZRHaYF1 ^O[io<6eeP08M5ZT00BdY/kjnOcooonn/]D3M5ZT00b2JZg>aMooooojnObM R[mgGJIdFZAfG:GSg^gooooUh>jCO[QBM5ZT0_ooo`000_ooodidFZ@05k2Q boKenOoooj^Kb7ILYGUPYlNlf_glo_Whnoooom_DigUPYgAJY7UPYk6Rc?oo oin=`7ILYGAJY>[VlOoooogloYV5_003M5ZT00F3Jjk>aMooooodl_R]W/T0 0gAJY006MefVj^Kaoooooooo`kSHOVJ[17AJY00=N5nV^joCoooolNkfWHZo Nf:XYYG5MefVUhBkm_CiooooiN3^RgJc009dFZ@027QOY[jbeOooooknol>h f7EKYI1l]geTZPQdFZ@01;JXco[io?oool[0g0=dFZ@01WEKYIF1^Ooooooo oo;_mWUPY`9dFZ@01=37h?oooogloZRHaU9dFZ@2oooo0002ooooCWAJY008 Nf:Xl^ofoooof=7VQg2`M5ZTT7bghmg/0_ooo`0=hM_[QVn`M5ZTM5ZTQFj_ l^ofg]SYMefVM5ZTd/WQoOcnoooo[j3;00=dFZ@01WEKYJJEaOooooknonGP kWMMYP=dFZ@01K^_doSgnoooooWhniN4^`05M5ZT00bRT<;oooojnOc5^]Ud FZAgGZIdFZAkHZS_k?Goooolo?fMR[l3M5ZT00JJR;gZi_7ooooLe^QgGZIe FjD9M5ZT00FJR;gWhnoooooNf>V;M[<00gAJY00j^KaVXRmM5ZTM5ZTNf:XaK[Io?_m RWFcM5ZTY9?3m?7hooooeLgTR7:a0gAJY005T7bgin?_oooom?7hWHZo00=d FZ@01XM`/?Cbn?ooooooomcFj8Qb/@AdFZ@019=n^>cXloooonOSk`AdFZ@0 1Lk5gockoOoool>hf7iVZ`02M5ZT00EiH:O3^=Soooo[io:GQ;/02WAJY005 NF2WeLgToooonOSk/J;<00=dFZ@037UPYkBVc_ooooooomG=i7eTZWAJY7]R Z>7KjoooomkHjHih]E5dFZ@2oooo0002ooooCGAJY00=OFBZM5ZTX8k1mO?h oooo^joCO6BYM5ZTT7bgiN3^oooom_Gi]:K>009dFZ@02WMMYYf:_ooookZ] dWUPYg]RZ>_Xl_ooooSgniZ8_@=dFZ@03giVZl>hf?ooooGcnJfNbGAJY9=n ^8Ye/gAJY=_Dioooonk[m?oookjbeGMMYP03M5ZT00F1JZg:`=coooodlOR@ O;L00gAJY005RgJcl^ofoooomO?hSWRe00=dFZ@01:JEaOoooockoKjbe@]d FZ@01;2QboKenOooom37h0=dFZ@01WEKYHQb/Oooooooon_WlWmWZ`9dFZ@0 1=;9hOooooSgnj:@`U5dFZ@2oooo0002ooooCGAJY00=g=KXb/3LN5nVin?_ oooohM_[SWReM5ZTN5nV_[;Eooooo_kod/WQ00=dFZ@02XI_/?ooomcFj7iV ZgAJY;6Rc?SgnooookjbeG]RZ09dFZ@03gEKYJBC`oooooGcnJfNbGAJY;R[ dNOSkgmWZj^Kb?GcnOOfn^?Mk>[VlKNYd003M5ZT00EfG:FXVm_Gioooo/ZC=DGAJY0;oool000;ooom=M5ZT00Nn/]Gooonn/]GD c>?hmo_jnObJR;d00WAJY00AWHZoknceoooohmk]P6R/M5ZTNF2W/J;>N;D02gAJY004WHZok^_dooood/WQ0gAJY005Nf:Xg]SYoooom_GiPVZ] 009dFZ@01H=[[]kHjOoool[0g7ILY@1@M5ZT0_ooo`000_ooodedFZ@04GQO Y/[0g?ooon_Xl_[io?oookBVcWQOYWAJY7eTZ/[0g?ooonk[m9n=`7AJY85Z [OGcn002oooo00R3JjidFZAdFZB:MK?EcNCooooUh>j>N;D2M5ZT00BPS/7o ooohmo^EPKT2M5ZT016VULGooooDc>?dlOSooonn/]FVULG[io;oooogm_[H dNJRT<9mI:[Le^SoooofmOV1JZd017AJY00;RgJceLgTooooi^7_WHZoM5ZT OVJ[f=7VoooomO?i/ZC=00]dFZ@01GQOYZJEaNk[m?cloK6Rc003M5ZT00kZ i_7oooo>aMmkHZQmI:ZRT<:]W/WVhNoooooZi_6i[=6XVN;E=M5ZT 0_ooo`000_ooodidFZ@00h=[[/_2gOooo`02oooo00G5^]UiH:MdFZAdFZBV ULD00_ooo`07akcJM5ZTPFZ]mO?ioooon_WlPVZ]00=dFZ@02H]f/l_2gOoo on[VlK:TcJfNbN?NkOknolFjf@04M5ZT00Rj[M;ooooooooooooLe^R3JjjR T<;bkoH2oooo00KBbN5dFZBaX/coooojnObXV<2oooo00?mo?kHdNIdFZ@02gAJY00=ME^UXY32i^;_oooo`kSH YYG5_[;Eooooj^KaTgjhME^UO6BYj^Ka00Ooool00m;9hGAJY7AJY01;M5ZT 0_ooo`000_ooodmdFZ@01X5Z[K^_dn?Mk>?Mk::@`WEKY@9dFZ@02XQb/LFj fMSAi[V/dGAJY7QOYZJEaNOSkk^_dg]RZ0AdFZ@027iVZk2QbmSAi^?Mk>7K jn?Mk;BVcX5Z[@EdFZ@03kNYd=kHjNOSkk6Rc7UPYgMMYZRHa]_DimkHjIf: _gAJY9=n^?ooooglo];9h@06M5ZT00Z3JjjaX/cHdNKbkoKVh^oBbN7Uh>ko oooak_InIZ/=M5ZT00NEPKW;`]gWhnoKe>OZi_7@an2MR[l00gAJY009]:K> akcJd/WQm?;hooooj^KaaK[IakcJ]:K>04edFZ@2oooo0002ooooDGAJY003 TgjhT7bgMefV00AdFZ@00gUPYh5Z[H1X[003M5ZT00>JR;egGZIdFZ@01WAJ Y004Nf:XVHFlWhg0Qg2`27AJY003RgJcVXRmMejV00=dFZ@02HQb/Hih]GAJ Y7AJY8M`/>o/mOoooo7^mWMNYP07M5ZT00QmI:ZEPKV8L[5fG:F_X<_ooood lORTTlN;FPS/6IQKagGZH6M5ZT00AgGZKBbN7ooooBbN5@M5ZT 0_ooo`000_ooogedFZ@01WiVZl>hf?oooooooi=n^7EKY@YdFZ@019Z8_O[i o?ckoM37h1YdFZ@01:JEaOKdnOGcn:^Kb4mdFZ@2oooo0002ooooOGAJY006 ME^UVXRmoooooOcn_[;EMejV2WAJY005R7:ag]SYoooolNkfNF2W01UdFZ@0 1GUPYl[0g?ooom37h7]RZ002M5ZT00=hGjIdFZAdFZ@0BGAJY0;oool000;o oomlM5ZT00=eFjEgGZJ8L[400_kno`03g]SYN5nVM5ZT00MdFZ@01gEKYGMM YXE^[lNlf_ooooKenIZ8_@0JM5ZT00VGQ;_/j??fmOV]W/V3Jjj@O;NXVhO`L0 0lJI>NcM_Oooo`0Aoooo00?N`h^hO`O6VCT01_ooo`:hO`L00nOD[?oooooo o`08oooo1kQo1`03bj59oooooooo00Goool2^7l700?/gKgoooooool01?oo o`03n_K^e;9Z_HPH00BhO`L00m2ZF^cM_Oooo`06oooo00?jm^kD/VZmR1P0 1;Qo1`03d:YJk=fmoooo00[oool00l^QBKQo1mk3R`08oooo1kQo1`03bj59 oooooooo00Goool2^7l700?/gKgoooooool01Oooo`:hO`L6oooo00?@ZUZh O`ON`h/04Oooo`03n_K^e;9Z_HPH00BhO`L00m2ZF^cM_Oooo`0>oooo000C oooo0[Qo1`03aYTibj59bj5900;;XDT00mVkNoooooooo`05oooo0[Qo1`08 k=fmoooooooooooon_K^_HPH^7l7g/>;1_ooo`:hO`L00ncM_Oooooooo`06 oooo00WSc9bhO`NhO`O1T2SI^g_N`h_@ZUZmR1SN`h/04_ooo`04bj59^7l7 ^7l7n_K^1?ooo`04k=fm^7l7^7l7fK]k2_ooo`:hO`L00lJI>L^QBL^QB@02 bj5900?I^g_oooooool01Oooo`:hO`L00ncM_Oooooooo`04oooo00C/gKfh O`NhO`O@ZUX2g/>;00C6VCVhO`NhO`ON`h/6oooo00C/gKfhO`NhO`O@ZUX2 g/>;00C6VCVhO`NhO`ON`h/:oooo00?;XDVhO`ON`h/02?ooo`:hO`L00lJI >L^QBL^QB@02bj5900?I^g_oooooool01Oooo`:hO`L00ncM_Oooooooo`05 oooo0[Qo1`Goool01?K^g[Qo1kQo1mk3Ra7oool01>cM_KQo1kQo1m2ZFP;N `h/01KQo1kQo1mk3R`koool001?oool2^7l700?/gKgoooooool02_oo o`:hO`L01ncM_OooooooooooomVkNkQo1l6@:007oooo0[Qo1`03k=fmoooo oooo00Goool01?K^g[f86;Qo1mBbJPCoool00o[fk_7UcOooo`0Aoooo00Bm R1RhO`NhO`O/gKd4oooo00CSc9bhO`NhO`O;XDT:oooo0[Qo1`03k=fmoooo oooo00[oool2^7l700?/gKgoooooool01?ooo`03k=fmfK]kn_K^00Coool0 1>?;4Oooo`03 k=fmfK]kn_K^00Coool01>?cM_OooooooooK^gP:hO`L00nOD[?oooooo o`05oooo0[Qo1`03k=fmoooooooo00Goool00mBbJ[Qo1l6@:00Hoooo00Gf k]jhO`NmR1RhO`ON`h/01?ooo`04fK]k^7l7_HPH^7l72_ooo`:hO`L00ncM _Oooooooo`0:oooo0[Qo1`03k=fmoooooooo00Coool00o[fk_ooooooo`05 oooo00?D/VZhO`O1T2P01Oooo`03n_K^oooooooo00Goool00mBbJ[Qo1l6@ :009oooo00?;XDVhO`ON`h/02?ooo`:hO`L00ncM_Oooooooo`0:oooo0[Qo 1`03k=fmoooooooo00Goool2^7l71?ooo`05n_K^_HPH^7l7^7l7g/>;017o ool00o[fk_ooooooo`05oooo00?D/VZhO`O1T2P03Oooo`004oooo`:hO`L0 0ncM_Oooooooo`0:oooo0[Qo1`06k=fmooooooooe;9Z^7l7bj592?ooo`:h O`L00ncM_Oooooooo`04oooo00Cjm^jmR1RhO`ON`h/Hoooo00GWe:bhO`OD /VZhO`O;XDT01?ooo`05bj59^7l7e;9Z^7l7k=fm00Woool2^7l700?/gKgo ooooool02_ooo`:hO`L00ncM_Oooooooo`0;01Woool01>cM_KQo1kQo1oK^gPcoool001?oool2^7l7 00?/gKgoooooool02_ooo`:hO`L00ncM_OoooncM_@02^7l700?aiLgooooo ool01_ooo`:hO`L00ncM_Oooooooo`04oooo00C/gKfhO`NhO`Ofk]hHoooo 00GN`h^hO`OSc9bhO`NmR1P01?ooo`05^7l7aYTig/>;^7l7g/>;00Woool2 ^7l700?/gKgoooooool02_ooo`:hO`L00ncM_Oooooooo`0;01Woool01>cM_KQo1kQo1ncM_@coool0 01?oool2^7l700?/gKgoooooool02_ooo`:hO`L01NcM_Ooool^QBKQo1mBb JP09oooo0[Qo1`03k=fmoooooooo00Coool00mk3RkQo1kQo1`0Ioooo00K; XDVhO`O/gKg;XDVhO`Ofk]h2oooo00Kfk]jhO`O@ZU[We:bhO`O@ZUX9oooo 0[Qo1`03k=fmoooooooo00[oool2^7l700?/gKgoooooool03?ooo`04fK]k ^7l7^7l7n_K^3?ooo`04fK]k^7l7^7l7n_K^2?ooo`03bj59^7l7g/>;00So ool2^7l700?/gKgoooooool02_ooo`:hO`L00ncM_Oooooooo`05oooo0[Qo 1`?oool01^cM_KQo1l^QBMk3RkQo1mk3RaWoool01=VkNkQo1kQo1o[fkPco ool001?oool2^7l700?/gKgoooooool02_ooo`:hO`L01NcM_NOD[;Qo1kf8 6?[fkP09oooo0[Qo1`03k=fmoooooooo00Coool00mBbJ[Qo1l^QB@0Ioooo 00JmR1RhO`Ojm^kD/VZhO`OSc9`2oooo00KWe:bhO`ON`h_aiLfhO`O1T2P9 oooo0[Qo1`03k=fmoooooooo00[oool2^7l700?/gKgoooooool02oooo`04 lNG=^7l7^7l7bj593?ooo`04lNG=^7l7^7l7bj592Oooo`03bj59^7l7g/>; 00Soool2^7l700?/gKgoooooool02_ooo`:hO`L00ncM_Oooooooo`05oooo 0[Qo1`?oool01]BbJ[Qo1nOD[=k3RkQo1mk3RaSoool01?7UcKQo1kQo1l^Q B@goool001?oool2^7l700?/gKgoooooool02_ooo`:hO`L01>cM_L6@:;Qo 1mk3R`[oool2^7l700?/gKgoooooool01?ooo`03bj59^7l7bj5901Soool0 1oK^g[Qo1kf86?ooon?;00Soool2^7l700?/gKgoooooool02_oo o`:hO`L00ncM_Oooooooo`05oooo0[Qo1`;oool01oK^g[Qo1l6@:?ooomk3 RkQo1mk3R`0Goooo00GN`h^hO`NhO`NmR1Sfk]h03Oooo`004oooo`:hO`L0 0mk3RncM_NcM_@02k=fm00?aiLgoooooool01Oooo`:hO`L00mBbJ[Qo1l6@ :00;oooo0[Qo1`03k=fmoooooooo00Coool00l^QBKQo1l^QB@0Hoooo00OW e:bhO`O;XDWooooaiLfhO`O6VCT00_ooo`07bj59^7l7m^kNoooobj59^7l7 imB/00Soool2^7l700?N`h_/gKg/gKd00^cM_@03lNG=oooooooo00Goool2 ^7l700?/gKgoooooool02?ooo`06imB/`I0X^7l7^7l7aYTim^kN2_ooo`06 imB/`I0X^7l7^7l7aYTim^kN2_ooo`03bj59^7l7g/>;00Soool2^7l700?N `h_/gKg/gKd00^cM_@03lNG=oooooooo00Goool2^7l700?/gKgoooooool0 1Oooo`:hO`L2oooo00ON`h^hO`ON`h_ooooN`h^hO`ON`h/05Oooo`06imB/ `I0X^7l7^7l7aYTim^kN3_ooo`004oooo`NhO`L00l^QBOooooooo`05oooo 1KQo1`03_HPHd:YJk=fm00Soool2^7l700?/gKgoooooool01?ooo`03bj59 ^7l7bj5901Soool00mk3RkQo1mVkN`02oooo00JmR1RhO`Ooooooooo1T2Rm R1P2oooo00?I^g^hO`OI^g/02?ooo`NhO`L00l^QBOooooooo`05oooo0[Qo 1`03k=fmoooooooo00Koool01_K^g/^QBKQo1kQo1kf86>??;00?Sc9coooooool01Oooo`:h O`L01=BbJ]k3RmVkNlJI>@:hO`L00n?;n_K^2_ooo`06imB/_HPH^7l7^7l7g/>; n_K^3Oooo`03bj59^7l7g/>;00Soool2^7l700?D/V[N`h_N`h/00]k3R`03 hlbLoooooooo00Goool2^7l700?/gKgoooooool01Oooo`:hO`L01?ooon?< W;Qo1mBbJP;oool00mk3RkQo1mk3R`0Boooo00KWe:bmR1RhO`NhO`ON`h_j m^hAoooo000Coooo0[Qo1`03k=fmoooooooo00[oool2^7l700S/gKgooooo oooooooN`h^hO`NmR1Sjm^h6oooo0[Qo1`03k=fmoooooooo00Coool00mk3 RkQo1l^QB@0Hoooo00>mR1RhO`O/gKd00_ooo`06g/>;^7l7g/>;k=fm^7l7 fK]k0_ooo`03lNG=^7l7^7l700Soool2^7l700?/gKgoooooool02_ooo`:h O`L00ncM_Oooooooo`04oooo00Gfk]jmR1RhO`NmR1SaiLd02oooo`05m^kN _HPH^7l7_HPHlNG=00ooool00l^QBKQo1mk3R`08oooo0[Qo1`03k=fmoooo oooo00[oool2^7l700?/gKgoooooool01Oooo`:hO`L01?ooolJI>KQo1ncM _@;oool00mk3RkQo1mk3R`0Aoooo00Gfk]jmR1RhO`NmR1SaiLd04oooo`00 4oooo`:hO`L00ncM_Oooooooo`0:oooo0[Qo1`05k=fmoooooooooooon_K^ 00:hO`L00nOD[?ooooooo`04oooo0[Qo1`03k=fmoooooooo00Coool00mk3 RkQo1kf8600Goooo00Cfk]jhO`NhO`Ojm^h2oooo00KWe:bhO`O@ZU[N`h^h O`ON`h/3oooo0[Qo1`03k=fmoooooooo00Goool2^7l700?/gKgoooooool0 2_ooo`:hO`L00ncM_Oooooooo`04oooo00CD/VZhO`NmR1SaiLd;^7l7g/>;00Ooool00o[fk^cM_Oooo`07oooo00CD/VZhO`NmR1Sa iLdDoooo000Coooo0[Qo1`03k=fmoooooooo00[oool2^7l700?/gKgooooo ool00_ooo`:hO`L00mk3Roooooooo`04oooo0[Qo1`03k=fmoooooooo00Co ool01>cM_KQo1kQo1oK^gQKoool00nOD[;Qo1kf86003oooo00Kjm^jhO`O; XDWI^g^hO`O/gKd3oooo00?;XDVhO`ON`h/01oooo`:hO`L00ncM_Ooooooo o`0:oooo0[Qo1`03k=fmoooooooo00Coool00kf86;Qo1mBbJP0=oooo00>m R1RhO`OD/VX04Oooo`03bj59^7l7g/>;00Soool2^7l700?/gKgoooooool0 2_ooo`:hO`L00ncM_Oooooooo`05oooo00FhO`O1T2SD/VZhO`OSc9`00ooo o`03g/>;^7l7g/>;00Koool01=k3RkQo1kf86?[fkPOoool00kf86;Qo1mBb JP0Eoooo000Coooo0[Qo1`03k=fmoooooooo00[oool2^7l700?/gKgooooo ool00_ooo`:hO`L00mk3Roooooooo`04oooo0[Qo1`03k=fmoooooooo00Go ool2^7l700?Sc9coooooool05?ooo`03g/>;^7l7bj5900Coool01<6@:;Qo 1l^QBKQo1`Coool00mVkNkQo1m2ZFP07oooo0[Qo1`03k=fmoooooooo00[o ool2^7l700?/gKgoooooool01?ooo`:hO`L00mk3Roooooooo`0;oooo0[Qo 1`03g/>;oooooooo00ooool00l^QBKQo1mk3R`08oooo0[Qo1`03k=fmoooo oooo00[oool2^7l700?/gKgoooooool01Oooo`04^7l7bj59_HPH_HPH1?oo o`03g/>;^7l7g/>;00Koool01?K^g[Qo1kQo1mk3R`Ooool2^7l700?N`h_o ooooool04oooo`004oooo`:hO`L00ncM_Oooooooo`0:oooo0[Qo1`05k=fm oooooooooooom^kN00:hO`L00nOD[?ooooooo`04oooo0[Qo1`03k=fmoooo oooo00Goool00mBbJ[Qo1l6@:00Foooo00?;XDVhO`OI^g/01?ooo`04e;9Z ^7l7bj59`I0X1?ooo`03hlbL^7l7`I0X00Ooool2^7l700?/gKgoooooool0 2_ooo`:hO`L00ncM_Oooooooo`04oooo00?6VCVhO`OD/VX03Oooo`03aYTi ^7l7e;9Z017oool00l^QBKQo1mk3R`08oooo0[Qo1`03k=fmoooooooo00[o ool2^7l700?/gKgoooooool01Oooo`04^7l7_HPH^7l7fK]k1?ooo`03g/>; ^7l7g/>;00Ooool00mVkNkQo1l6@:007oooo00?6VCVhO`OD/VX05Oooo`00 4oooo`:hO`L00ncM_Oooooooo`0:oooo0[Qo1`05k=fmooooooooooooe;9Z 00:hO`L00oK^g_ooooooo`04oooo0[Qo1`03k=fmoooooooo00Goool01?K^ g[Qo1kQo1mVkN`Goool00o[fk_ooooooo`0=oooo00>mR1RhO`ON`h/01?oo o`04g/>;^7l7^7l7d:YJ1?ooo`04k=fm^7l7^7l7m^kN1_ooo`:hO`L00ncM _Oooooooo`0:oooo0[Qo1`03k=fmoooooooo00Coool01>?;00Soool2^7l700?/gKgoooooool02_oo o`:hO`L00ncM_Oooooooo`05oooo0kQo1`03m^kNoooooooo00;oool00mk3 RkQo1mk3R`07oooo00Cjm^jmR1RhO`O/gKd6oooo00CSc9bhO`NhO`OaiLd5 oooo00?I^g_oooooool03?ooo`004oooo`:hO`L00mBbJ]k3Rmk3R`02g/>; 00?Sc9coooooool01Oooo`:hO`L01=BbJ]k3RmVkNlJI>@:hO`L00mk3Rooo ooooo`05oooo0[Qo1`03k=fmoooooooo00Koool02N?cM_N?oooo00Cfk]jhO`NhO`O/gKd4oooo00C/gKfhO`Nh O`ON`h/5oooo0[Qo1`03imB/oooooooo00Coool2^7l700?D/V[N`h_N`h/0 0]k3R`03hlbLoooooooo00Goool2^7l700?/gKgoooooool01Oooo`04bj59 ^7l7^7l7fK]k0^cM_@03g/>;`I0X^7l700Ooool01<^QBKQo1kQo1mVkN`;/ gKd00mk3Rl6@:;Qo1`06oooo00O/gKgN`h_N`h_N`h_1T2RhO`O;XDT00mk3 R`03m^kNoooooooo00;oool2^7l700?D/V[N`h_N`h/00]k3R`03hlbLoooo oooo00Goool2^7l700?/gKgoooooool01Oooo`:hO`L00m2ZF_ooooooo`03 oooo00?N`h^hO`ON`h/02?ooo`03g/>;^7l7d:YJ00Ooool01<^QBKQo1kQo 1mVkN`;/gKd00mk3Rl6@:;Qo1`0>oooo000Coooo1kQo1`03bj59oooooooo 00Goool6^7l700?6VCWWe:coool01oooo`:hO`L00ncM_Oooooooo`07oooo 00?We:c1T2RhO`L01;Qo1`03g/>;oooooooo00coool01>OD[;Qo1kQo1o[f kPGoool2^7l700?We:coooooool00oooo`03aYTi^7l7fK]k00Koool7^7l7 00?;XDWoooooool01Oooo`:hO`L00ncM_Oooooooo`06oooo00?I^g^hO`Nh O`L01;Qo1`03d:YJoooooooo00Koool00mVkNkQo1kQo1`04^7l700?@ZU[o ooooool01?ooo`03g/>;^7l7^7l700NhO`L00ncM_Oooooooo`02oooo1kQo 1`03bj59oooooooo00Goool2^7l700?/gKgoooooool01Oooo`:hO`L00nOD [?ooooooo`03oooo00?N`h^hO`ON`h/02Oooo`03`I0X^7l7m^kN00Ooool0 0mVkNkQo1kQo1`04^7l700?@ZU[oooooool03?ooo`004oooo`O/gKd00o7U cOooooooo`05oooo1NcM_@_oool2k=fm00?jm^koooooool02Oooo`05k=fm g/>;g/>;g/>;lNG=00ooool00oK^g^cM_NcM_@06oooo00?aiLg/gKgjm^h0 1Oooo`03lNG=k=fmlNG=00Koool7k=fm00?aiLgoooooool01Oooo`;/gKd0 0o[fk_ooooooo`07oooo00Kjm^kWe:cN`h_N`h_We:cjm^h:oooo00Kjm^kW e:cN`h_N`h_We:cjm^h7oooo00?fk]k/gKg/gKd01ncM_@03n_K^oooooooo 00;oool7k=fm00?aiLgoooooool01Oooo`;/gKd00o[fk_ooooooo`05oooo 0^cM_@Koool00oK^g^cM_OK^gP09oooo00?aiLgfk]koool02?ooo`06n_K^ imB/g/>;g/>;imB/n_K^3oooo`00ooooo`?oool00?ooool3oooo0000\ \>"], "Graphics", ImageSize->{258, 93}, ImageMargins->{{0, 0}, {0, 0}}, ImageRegion->{{0, 1}, {0, 1}}], Cell["\<\ [1] http://mathworld.wolfram.com/ [2] The number of structures of Finite Relations R. L. Davis, Proc. Amer. Math. Soc., 4 (1953) 483-495 [3] Concrete Mathematics R. L. Graham, D. E. Knuth and O. Patashnik, Addison-Wesley, 1994 [4] Applied Combinatorics A. Tucker, John-Wiley, 1984 [5] Discrete Mathematical Structures with Applications to Computer Science J. P. Tremblay and R. Manohar, Mc. Graw-Hill, 1988 [6] Finite Groups Acting on sets with Applications L. W. Shapiro, Mathematics Magazine, May-June, 1973 p. 136-147 [7] Fundamental Algorithms D. E. Knuth, Third Edition. Addison-Wesley, 1998 [8] Discrete and Combinatorial Mathematics R. P. Grimaldi, Fourth Edition. Addison-Wesley, 2000 [9] The On-line Encyclopedia of Integer Sequences http://www.research.att.com/~njas/sequences/index.html\ \>", "Reference"] }, Open ]], Cell[CellGroupData[{ Cell["Introduction", "SectionFirst"], Cell["\<\ \tIn dealing with a problem of high complexity, a first attempt at its \ solution is often made through dividing the problem into cases. In \ mathematics this division arises naturally by imposing a relation on the \ elements of the set under study. Supporting this point of view, prominent \ categories of relations have found a plethora of applications; among those \ categories we can consider those of functions, equivalence relations, \ partial orders, lattices, Boolean algebras, etc., which are defined according \ to their compliance to a handful of very general and primitive structural \ characteristics such as transitivity. Their relevance to Computer Science is \ commonplace as they offer a natural framework for the setting and analysis of \ problems in the areas of pattern classification and enumeration of classes \ [3]. Even in dealing with finite structures, however, once a relation has been \ specified, it is often the case that further distinction is needed among the \ classes due to their abundance. This simplification is achieved through \ setting up an isomorphism. The idea behind it resides in specifying when can \ two configurations be regarded as equal, leading to a significant reduction \ of complexity and hence providing insight into the fine structure of the \ problem at hand. We divide our work in two main parts. The first one addresses the problem of \ generation of all relations and prominent families and their enumeration. By \ their prolific nature we consider only a limited range of relations. The \ second part distinguishes among non-isomorphic structures following \ David\.b4s ideas to consider the action of a group of symmetries in \ accordance to Polya\.b4s theory. \ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["PART I GENERATION", "Section"], Cell[TextData[{ "\tLet \[GothicCapitalR]", Cell[BoxData[ \(TraditionalForm\`\_n\)]], " be the set of all relations on the set ", StyleBox["Range[n]", "Input"], ", that is all possible subsets of ", StyleBox["Range[n]", "Input"], "x ", StyleBox["Range[n]", "Input"], ". The members of ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalR]\_n\)]], " are often conveniently represented as binary matrices of size n x n. " }], "Text"], Cell[BoxData[ \(\[GothicCapitalR]\_n_ := \(\[GothicCapitalR]\_n = Map[Partition[IntegerDigits[#, 2, n\^2], n] &, Range[0, 2\^\(n\^2\) - 1]]\)\)], "Input", CellLabel->"In[22]:=", InitializationCell->True], Cell[CellGroupData[{ Cell[BoxData[ \(\(\(\ \)\(MatrixForm\ /@ \ \[GothicCapitalR]\_2\)\)\)], "Input", CellLabel->"In[23]:="], Cell[BoxData[ RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0"}, {"0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0"}, {"0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0"}, {"1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0"}, {"1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1"}, {"0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1"}, {"0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1"}, {"1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1"}, {"1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0"}, {"0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0"}, {"0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0"}, {"1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0"}, {"1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1"}, {"0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1"}, {"0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1"}, {"1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1"}, {"1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}]], "Output", CellLabel->"Out[23]="] }, Open ]], Cell[TextData[{ "The first and last members of the above list are refered to as the ", StyleBox["empty", FontSlant->"Italic"], " and ", StyleBox["universal", FontSlant->"Italic"], " relations respectively. The number of relations grows exponentially:" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[\[GothicCapitalR]\_#] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({2, 16, 512, 65536}\)], "Output"] }, Open ]], Cell["The above numbers start as (seq A002416 in [8]):", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(2\^\(Range[7]\^2\)\)], "Input"], Cell[BoxData[ \({2, 16, 512, 65536, 33554432, 68719476736, 562949953421312}\)], "Output"] }, Open ]], Cell[TextData[{ "Even when trying to compute ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalR]\_5\)]], ", ", StyleBox["Mathematica", FontSlant->"Italic"], " disconnects the kernel for lack of memory (in a 160Mb environment), \ rendering the generation of all relations for n\[GreaterEqual]6 unfeasible. \ In the following we process the ones already generated in order to select \ prominent subfamilies." }], "Text"], Cell[CellGroupData[{ Cell["Testing Relations", "Subsection"], Cell["\<\ We consider the families of reflexive, symmetric, transitive, equivalence, \ graph, anti-symmetric, partial order, total order and lattice and design \ predicates to test a given relation for its inclusion to these classes.\ \>", "Text"], Cell[BoxData[{ \(leq[m1_, m2_] := Apply[And, NonPositive\ /@ \ Flatten[m1 - m2]]\), "\n", \(square[ m_] := \((m . m\ /. \ {x_\ /; \ x > 0\ \[Rule] 1})\)\[IndentingNewLine]\), "\n", \(reflexiveQ[m_] := leq[IdentityMatrix[Length[m]], m]\[IndentingNewLine]\), "\n", \(symmetricQ[{x_Integer}] := True\), "\n", \(symmetricQ[m_] := \((Transpose[m] == m)\)\[IndentingNewLine]\), "\n", \(transitiveQ[m_] := leq[square[m], m]\[IndentingNewLine]\), "\n", \(equivalenceQ[ m_] := \(\(reflexiveQ[m]\)\(&&\)\(symmetricQ[m]\)\(&&\)\(transitiveQ[ m]\)\(\[IndentingNewLine]\)\)\), "\n", \(graphQ[ m_] := \(\(reflexiveQ[m]\)\(&&\)\(symmetricQ[ m]\)\(\[IndentingNewLine]\)\)\), "\n", \(antiSymmetricQ[m_] := leq[Partition[Flatten[m]\ Flatten[Transpose[m]], Length[m]], IdentityMatrix[Length[m]]]\[IndentingNewLine]\), "\n", \(partialOrderQ[ m_] := \(\(reflexiveQ[m]\)\(\ \)\(&&\)\(\ \)\(antiSymmetricQ[ m]\)\(\ \)\(&&\)\(\ \)\(transitiveQ[ m]\)\(\[IndentingNewLine]\)\)\), "\n", \(totalOrderQ[ m_] := \(\(partialOrderQ[ m]\)\(&&\)\((Length[Cases[Flatten[m] + Flatten[Transpose[m]], 0]] == 0)\)\(\[IndentingNewLine]\)\)\), "\n", \(lubGlbQ[m_] := Module[{n = Range[Length[m]], i, j, t}, \[IndentingNewLine]t = Flatten[Outer[List, n, n], 1]; \[IndentingNewLine]And\ @@ Map[\(({i, j} = #; \((m\[LeftDoubleBracket]i, j\[RightDoubleBracket] == 1)\) || \((\((Length[ Select[n, m\[LeftDoubleBracket]i, #\[RightDoubleBracket] == m\[LeftDoubleBracket] j, #\[RightDoubleBracket] == 1 &, 1]] > 0)\) && \((Length[ Select[n, m\[LeftDoubleBracket]#, i\[RightDoubleBracket] == m\[LeftDoubleBracket]#, j\[RightDoubleBracket] == 1 &, 1]] > 0)\))\))\) &, t]]\[IndentingNewLine]\), "\n", \(latticeQ[m_] := partialOrderQ[m] && \ lubGlbQ[m]\)}], "Input", CellLabel->"In[2]:=", InitializationCell->True], Cell[CellGroupData[{ Cell["1.- Reflexive Relations", "Subsubsection"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, reflexiveQ]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({1, 4, 64, 4096}\)], "Output"] }, Open ]], Cell["\<\ Those numbers start off as (see sequences A053763 and A053773 in [8]):\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(2\^\(Range[7] \((Range[7] - 1)\)\)\)], "Input"], Cell[BoxData[ \({1, 4, 64, 4096, 1048576, 1073741824, 4398046511104}\)], "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell["2.- Symmetric Relations", "Subsubsection"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, symmetricQ]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({2, 8, 64, 1024}\)], "Output"] }, Open ]], Cell["Those numbers start as (see sequence A006125 in [8]):", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(2\^\(\(Range[7] \((Range[7] + 1)\)\)\/2\)\)], "Input"], Cell[BoxData[ \({2, 8, 64, 1024, 32768, 2097152, 268435456}\)], "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell["3.- Transitive Relations", "Subsubsection"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, transitiveQ]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({2, 13, 171, 3994}\)], "Output"] }, Open ]], Cell["(Sequence A006905 in [8])", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["4.- Equivalence Relations", "Subsubsection"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, equivalenceQ]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({1, 2, 5, 15}\)], "Output"] }, Open ]], Cell["(Sequence A000110 in [8])", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["5.- Graphs", "Subsubsection"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, graphQ]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({1, 2, 8, 64}\)], "Output"] }, Open ]], Cell["numbers that start as (sequence A006125 in [8]):", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(2\^\(\(Range[7] \((Range[7] - 1)\)\)\/2\)\)], "Input"], Cell[BoxData[ \({1, 2, 8, 64, 1024, 32768, 2097152}\)], "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell["6.- Anti-symmetric Relations", "Subsubsection"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[ Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, antiSymmetricQ]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({2, 12, 216, 11664}\)], "Output"] }, Open ]], Cell["\<\ A different and quite illustrative way of testing for anti-symmetry is the \ following:\ \>", "Text"], Cell[BoxData[ \(antiQ[ m_] := \((Length[ Cases[Flatten[m - 2\ IdentityMatrix[Length[m]]] + Flatten[Transpose[m]], 2]] == 0)\)\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, antiQ]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({2, 12, 216, 11664}\)], "Output"] }, Open ]], Cell["Those numbers start off as:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(2\^Range[7]\) 3\^\(\(Range[7] \((Range[7] - 1)\)\)\/2\)\)], "Input"], Cell[BoxData[ \({2, 12, 216, 11664, 1889568, 918330048, 1338925209984}\)], "Output"] }, Open ]], Cell["Note they are not the same as:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[ Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, Not[symmetricQ[#]] &]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({0, 8, 448, 64512}\)], "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell["7.- Partial Orders", "Subsubsection"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[ Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, partialOrderQ]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({1, 3, 19, 219}\)], "Output"] }, Open ]], Cell["(Sequence A001035 in [8])", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["8.- Total Orders", "Subsubsection"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, totalOrderQ]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({1, 2, 6, 24}\)], "Output"] }, Open ]], Cell["They start off as:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Range[7]!\)\)], "Input"], Cell[BoxData[ \({1, 2, 6, 24, 120, 720, 5040}\)], "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell["9.- Lattices", "Subsubsection"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, latticeQ]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({1, 2, 6, 36}\)], "Output"] }, Open ]], Cell["(Sequence A055512 in [8])", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["10.- Other types", "Subsubsection"], Cell["\<\ Further computations can also be performed. For instance, to find the number \ of symmetric-antisymmetric relations:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[ Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, symmetricQ[#] && antiSymmetricQ[#] &]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({2, 4, 8, 16}\)], "Output"] }, Open ]], Cell["numbers that start as:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(2\^Range[7]\)], "Input"], Cell[BoxData[ \({2, 4, 8, 16, 32, 64, 128}\)], "Output"] }, Open ]], Cell["or also a unique occurrence:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[ Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_#, reflexiveQ[#] && symmetricQ[#] && antiSymmetricQ[#] &]] &\) /@ Range[4]\)], "Input"], Cell[BoxData[ \({1, 1, 1, 1}\)], "Output"] }, Open ]], Cell["\<\ We can also consider further classifications. Take for instance the relations \ mod m on Range[n]:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(m = 3;\)\), "\[IndentingNewLine]", \(\(n = 10;\)\), "\[IndentingNewLine]", \(Table[If[Mod[i - j, m] \[Equal] 0, 1, 0], {i, n}, {j, n}] // MatrixForm\)}], "Input", CellLabel->"In[46]:="], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0", "1", "0", "0", "1", "0", "0", "1"}, {"0", "1", "0", "0", "1", "0", "0", "1", "0", "0"}, {"0", "0", "1", "0", "0", "1", "0", "0", "1", "0"}, {"1", "0", "0", "1", "0", "0", "1", "0", "0", "1"}, {"0", "1", "0", "0", "1", "0", "0", "1", "0", "0"}, {"0", "0", "1", "0", "0", "1", "0", "0", "1", "0"}, {"1", "0", "0", "1", "0", "0", "1", "0", "0", "1"}, {"0", "1", "0", "0", "1", "0", "0", "1", "0", "0"}, {"0", "0", "1", "0", "0", "1", "0", "0", "1", "0"}, {"1", "0", "0", "1", "0", "0", "1", "0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]], "Output", CellLabel->"Out[48]//MatrixForm="] }, Open ]], Cell["which can also be considered more generally:", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(m = 11;\)\), "\[IndentingNewLine]", \(\(n = 20;\)\), "\[IndentingNewLine]", \(\(ListDensityPlot[Table[Mod[i\ \ j, m], {i, n}, {j, n}]];\)\)}], "Input",\ CellLabel->"In[77]:="], Cell[GraphicsData["PostScript", "\<\ %! %%Creator: Mathematica %%AspectRatio: 1 MathPictureStart /Mabs { Mgmatrix idtransform Mtmatrix dtransform } bind def /Mabsadd { Mabs 3 -1 roll add 3 1 roll add exch } bind def %% DensityGraphics %%IncludeResource: font Courier %%IncludeFont: Courier /Courier findfont 10 scalefont setfont % Scaling calculations 0.0192308 0.0480769 0.0192308 0.0480769 [ [.01923 -0.0125 -3 -9 ] [.01923 -0.0125 3 0 ] [.25962 -0.0125 -3 -9 ] [.25962 -0.0125 3 0 ] [.5 -0.0125 -6 -9 ] [.5 -0.0125 6 0 ] [.74038 -0.0125 -6 -9 ] [.74038 -0.0125 6 0 ] [.98077 -0.0125 -6 -9 ] [.98077 -0.0125 6 0 ] [ 0 0 -0.125 0 ] [-0.0125 .01923 -6 -4.5 ] [-0.0125 .01923 0 4.5 ] [-0.0125 .25962 -6 -4.5 ] [-0.0125 .25962 0 4.5 ] [-0.0125 .5 -12 -4.5 ] [-0.0125 .5 0 4.5 ] [-0.0125 .74038 -12 -4.5 ] [-0.0125 .74038 0 4.5 ] [-0.0125 .98077 -12 -4.5 ] [-0.0125 .98077 0 4.5 ] [ 0 0 -0.125 0 ] [ 0 1 .125 0 ] [ 1 0 .125 0 ] [ 0 0 0 0 ] [ 1 1 0 0 ] ] MathScale % Start of Graphics 1 setlinecap 1 setlinejoin newpath 0 g .25 Mabswid [ ] 0 setdash .01923 0 m .01923 .00625 L s [(0)] .01923 -0.0125 0 1 Mshowa .25962 0 m .25962 .00625 L s [(5)] .25962 -0.0125 0 1 Mshowa .5 0 m .5 .00625 L s [(10)] .5 -0.0125 0 1 Mshowa .74038 0 m .74038 .00625 L s [(15)] .74038 -0.0125 0 1 Mshowa .98077 0 m .98077 .00625 L s [(20)] .98077 -0.0125 0 1 Mshowa .125 Mabswid .06731 0 m .06731 .00375 L s .11538 0 m .11538 .00375 L s .16346 0 m .16346 .00375 L s .21154 0 m .21154 .00375 L s .30769 0 m .30769 .00375 L s .35577 0 m .35577 .00375 L s .40385 0 m .40385 .00375 L s .45192 0 m .45192 .00375 L s .54808 0 m .54808 .00375 L s .59615 0 m .59615 .00375 L s .64423 0 m .64423 .00375 L s .69231 0 m .69231 .00375 L s .78846 0 m .78846 .00375 L s .83654 0 m .83654 .00375 L s .88462 0 m .88462 .00375 L s .93269 0 m .93269 .00375 L s .25 Mabswid 0 0 m 1 0 L s 0 .01923 m .00625 .01923 L s [(0)] -0.0125 .01923 1 0 Mshowa 0 .25962 m .00625 .25962 L s [(5)] -0.0125 .25962 1 0 Mshowa 0 .5 m .00625 .5 L s [(10)] -0.0125 .5 1 0 Mshowa 0 .74038 m .00625 .74038 L s [(15)] -0.0125 .74038 1 0 Mshowa 0 .98077 m .00625 .98077 L s [(20)] -0.0125 .98077 1 0 Mshowa .125 Mabswid 0 .06731 m .00375 .06731 L s 0 .11538 m .00375 .11538 L s 0 .16346 m .00375 .16346 L s 0 .21154 m .00375 .21154 L s 0 .30769 m .00375 .30769 L s 0 .35577 m .00375 .35577 L s 0 .40385 m .00375 .40385 L s 0 .45192 m .00375 .45192 L s 0 .54808 m .00375 .54808 L s 0 .59615 m .00375 .59615 L s 0 .64423 m .00375 .64423 L s 0 .69231 m .00375 .69231 L s 0 .78846 m .00375 .78846 L s 0 .83654 m .00375 .83654 L s 0 .88462 m .00375 .88462 L s 0 .93269 m .00375 .93269 L s .25 Mabswid 0 0 m 0 1 L s .01923 .99375 m .01923 1 L s .25962 .99375 m .25962 1 L s .5 .99375 m .5 1 L s .74038 .99375 m .74038 1 L s .98077 .99375 m .98077 1 L s .125 Mabswid .06731 .99625 m .06731 1 L s .11538 .99625 m .11538 1 L s .16346 .99625 m .16346 1 L s .21154 .99625 m .21154 1 L s .30769 .99625 m .30769 1 L s .35577 .99625 m .35577 1 L s .40385 .99625 m .40385 1 L s .45192 .99625 m .45192 1 L s .54808 .99625 m .54808 1 L s .59615 .99625 m .59615 1 L s .64423 .99625 m .64423 1 L s .69231 .99625 m .69231 1 L s .78846 .99625 m .78846 1 L s .83654 .99625 m .83654 1 L s .88462 .99625 m .88462 1 L s .93269 .99625 m .93269 1 L s .25 Mabswid 0 1 m 1 1 L s .99375 .01923 m 1 .01923 L s .99375 .25962 m 1 .25962 L s .99375 .5 m 1 .5 L s .99375 .74038 m 1 .74038 L s .99375 .98077 m 1 .98077 L s .125 Mabswid .99625 .06731 m 1 .06731 L s .99625 .11538 m 1 .11538 L s .99625 .16346 m 1 .16346 L s .99625 .21154 m 1 .21154 L s .99625 .30769 m 1 .30769 L s .99625 .35577 m 1 .35577 L s .99625 .40385 m 1 .40385 L s .99625 .45192 m 1 .45192 L s .99625 .54808 m 1 .54808 L s .99625 .59615 m 1 .59615 L s .99625 .64423 m 1 .64423 L s .99625 .69231 m 1 .69231 L s .99625 .78846 m 1 .78846 L s .99625 .83654 m 1 .83654 L s .99625 .88462 m 1 .88462 L s .99625 .93269 m 1 .93269 L s .25 Mabswid 1 0 m 1 1 L s 0 0 m 1 0 L 1 1 L 0 1 L closepath clip newpath % Start of gray image p .01923 .01923 translate .96154 .96154 scale 20 string 20 20 8 [20 0 0 20 0 0] { \tcurrentfile \t1 index \treadhexstring \tpop } Mimage 19334C668099B3CCE6FF0019334C668099B3CCE6 336699CCFF194C80B3E600336699CCFF194C80B3 4C99E61966B3FF3380CC004C99E61966B3FF3380 66CC1980E63399FF4CB30066CC1980E63399FF4C 80FF66E64CCC33B319990080FF66E64CCC33B319 9919B333CC4CE666FF80009919B333CC4CE666FF B34CFF9933E68019CC6600B34CFF9933E68019CC CC8033FFB36619E6994C00CC8033FFB36619E699 E6B3804C19FFCC99663300E6B3804C19FFCC9966 FFE6CCB39980664C331900FFE6CCB39980664C33 0000000000000000000000000000000000000000 19334C668099B3CCE6FF0019334C668099B3CCE6 336699CCFF194C80B3E600336699CCFF194C80B3 4C99E61966B3FF3380CC004C99E61966B3FF3380 66CC1980E63399FF4CB30066CC1980E63399FF4C 80FF66E64CCC33B319990080FF66E64CCC33B319 9919B333CC4CE666FF80009919B333CC4CE666FF B34CFF9933E68019CC6600B34CFF9933E68019CC CC8033FFB36619E6994C00CC8033FFB36619E699 E6B3804C19FFCC99663300E6B3804C19FFCC9966 pop P % End of image .01923 .01923 m .01923 .98077 L s .06731 .01923 m .06731 .98077 L s .11538 .01923 m .11538 .98077 L s .16346 .01923 m .16346 .98077 L s .21154 .01923 m .21154 .98077 L s .25962 .01923 m .25962 .98077 L s .30769 .01923 m .30769 .98077 L s .35577 .01923 m .35577 .98077 L s .40385 .01923 m .40385 .98077 L s .45192 .01923 m .45192 .98077 L s .5 .01923 m .5 .98077 L s .54808 .01923 m .54808 .98077 L s .59615 .01923 m .59615 .98077 L s .64423 .01923 m .64423 .98077 L s .69231 .01923 m .69231 .98077 L s .74038 .01923 m .74038 .98077 L s .78846 .01923 m .78846 .98077 L s .83654 .01923 m .83654 .98077 L s .88462 .01923 m .88462 .98077 L s .93269 .01923 m .93269 .98077 L s .98077 .01923 m .98077 .98077 L s .01923 .01923 m .98077 .01923 L s .01923 .06731 m .98077 .06731 L s .01923 .11538 m .98077 .11538 L s .01923 .16346 m .98077 .16346 L s .01923 .21154 m .98077 .21154 L s .01923 .25962 m .98077 .25962 L s .01923 .30769 m .98077 .30769 L s .01923 .35577 m .98077 .35577 L s .01923 .40385 m .98077 .40385 L s .01923 .45192 m .98077 .45192 L s .01923 .5 m .98077 .5 L s .01923 .54808 m .98077 .54808 L s .01923 .59615 m .98077 .59615 L s .01923 .64423 m .98077 .64423 L s .01923 .69231 m .98077 .69231 L s .01923 .74038 m .98077 .74038 L s .01923 .78846 m .98077 .78846 L s .01923 .83654 m .98077 .83654 L s .01923 .88462 m .98077 .88462 L s .01923 .93269 m .98077 .93269 L s .01923 .98077 m .98077 .98077 L s % End of Graphics MathPictureEnd \ \>"], "Graphics", CellLabel->"From In[77]:=", ImageSize->{288, 288}, ImageMargins->{{0, 0}, {0, 0}}, ImageRegion->{{0, 1}, {0, 1}}, ImageCache->GraphicsData["Bitmap", "\<\ CF5dJ6E]HGAYHf4PAg9QL6QYHgOooo`@00003oooo0P0000?oool001;oool010000?ooooooo`0003goool010000?oo ooooo`0003coool01@000?ooooooooooo`000002oooo00<0003oooooool0=oooo`050000oooooooo oooo000000;oool00`000?ooooooo`0foooo00<0003oooooool00oooo`040000oooooooo00000_oo o`004_ooo`040000oooooooo0000@?ooo`030000oooooooo03[oool01@000?ooooooooooo`000002 oooo00<0003oooooool0=oooo`030000oooooooo00Coool00`000?ooooooo`0goooo00<0003ooooo ool00_ooo`040000oooooooo00000_ooo`004_ooo`040000oooooooo0000?_ooo`80000moooo00D0 003oooooooooool000000_ooo`030000oooooooo03Ooool00`000?ooooooo`02oooo0P0003_oool0 1@000?ooooooooooo`000002oooo0@00007oool1oooo000Boooo00@0003oooooool0000noooo00<0 003oooooool0??ooo`050000oooooooooooo000000;oool00`000?ooooooo`0goooo00<0003ooooo ool00_ooo`030000oooooooo03Soool010000?ooooooo`0000;oool010000?ooooooo`0000;oool0 01?oool20000?oooo`<0000koooo0P0000Coool20000>Oooo`800004oooo0`0003Woool200001?oo o`800003oooo003ooooo8Oooo`00ooooob7oool00?oooolQoooo003ooooo8Oooo`00ooooob7oool0 0?oooolQoooo000?ooooo`0001400001oooo000?oooo00<0003oooooool00_ooo`030000oooooooo 00[oool00`000?ooooooo`0:oooo00<0003oooooool02_ooo`030000oooooooo00[oool00`000?oo ooooo`0:oooo00<0003oooooool02_ooo`030000oooooooo00[oool00`000?ooooooo`0:oooo00<0 003oooooool02_ooo`030000oooooooo00[oool00`000?ooooooo`0:oooo00<0003oooooool02_oo o`030000oooooooo00[oool00`000?ooooooo`0:oooo00<0003oooooool02_ooo`030000oooooooo 00[oool00`000?ooooooo`0:oooo00<0003oooooool02_ooo`030000oooooooo00[oool00`000?oo ooooo`0;oooo00<0003oooooool00_ooo`400001oooo000?oooo00<0003oooooool0ooooo`goool1 00000Oooo`002?ooo`800005oooo00<0003oooooool0ooooo`goool100000Oooo`001oooo`040000 oooooooo00001?ooo`030000oooooooo0?ooool=oooo0@00007oool000Ooool010000?ooooooo`00 00Coool300000_ooool0000700000_ooo`<00001oooo0007oooo00@0003oooooool00004oooo00<0 003oooooool00_ooo`0300006ATI6ATI00XI6AT00`0003c/k>c 00Zc/k<00`000000031TI 6@030000c/k<02[>c/`030000cKV i^KViP0;i^KV00<0003oooooool00_ooo`400001oooo0007oooo00@0003oooooool00004oooo00<0 003oooooool00_ooo`0300006ATI6ATI00XI6AT00`0003c/k>c 00Zc/k<00`000000031TI 6@030000c/k<02[>c/`030000cKV i^KViP0;i^KV00<0003oooooool00_ooo`400001oooo0008oooo0P0000Goool00`000?ooooooo`02 oooo00<0000I6ATI6AT02QTI6@030000c/k<02[>c/`030000 cKVi^KViP0:i^KV00<0003oooooool02_ooo`h0000<6ATI00<0000cc/k>c/`0:/k>c00<0003c/k<02[>c/`030000cKV i^KViP0:i^KV00<0003oooooool02_ooo`h0000<6ATI00<0000cc /k>c/`0:/k>c00<0003c/k<02[>c/`030000cKVi^KViP0:i^KV00<0003ooooo ool02_ooo`h0000<6ATI00<0000cc/k>c/`0:/k>c00<0003c/k<02[>c /`030000cKVi^KViP0:i^KV00<0003oooooool02_ooo`h0000<6ATI00<0 000cc/k>c/`0:/k>c00<0003c/k<02[>c/`030000cKVi^KViP0:i^KV00<0003oooooool02_ooo`h0000<6ATI00<0000cc/k>c/`0:/k>c00<0003c/k<02[>c/`030000cKVi^KViP0:i^KV00<0 003oooooool02_ooo`h0000<6ATI00<0000cc/k>c/`0:/k>c00<0 003c /k<02[>c/`030000cKVi^KViP0:i^KV00<0003oooooool02_ooo`h0000< 6ATI00<0000cc/k>c/`0:/k>c00<0003c/k<02[>c/`030000cKVi^KViP0:i^KV00<0003oooooool02_ooo`h0000<6ATI00<0000cc/k>c/`0:/k>c00<0003c/k<02[>c/`030000cKVi^KViP0: i^KV00<0003oooooool02_ooo`h0000<6ATI00<0000cc/k>c/`0: /k>c00<0003c/k<02[>c/`030000cKVi^KViP0:i^KV00<0003oooooool02_oo o`h0000<6ATI00<0000cc/k>c/`0:/k>c00<0003c/k<02[>c /`030000i^KVi^KV00[Vi^H>000033c/k>c/`0;/k>c00<0003oooooool00_ooo`400001oooo000? oooo00<0003oooooool00_ooo`030000c/k<02[>c/`030000i^KVi^KV00[Vi^H> 000033c/k>c/`0;/k>c00<0003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_oo o`030000c/k<02[>c/`030000i^KVi^KV00[Vi^H>000033c/k>c/`0;/k>c00<0 003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`030000c /k<02[>c/`030000i^KVi^KV00[Vi^H>000033c/k>c/`0;/k>c00<0003oooooool00_ooo`400001 oooo000?oooo00<0003oooooool00_ooo`030000c/k<02[>c/`030000i^KVi^KV 00[Vi^H>000033c/k>c/`0;/k>c00<0003oooooool00_ooo`400001oooo000?oooo00<0003ooooo ool00_ooo`030000c/k<02[>c/`030000i^KVi^KV00[Vi^H>000033c/k>c/`0; /k>c00<0003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`030000c/k<02[>c/`030000i^KVi^KV00[Vi^H>000033c/k>c/`0;/k>c00<0003oooooool00_oo o`400001oooo000?oooo00<0003oooooool00_ooo`030000c/k<02[>c/`030000 i^KVi^KV00[Vi^H>000033c/k>c/`0;/k>c00<0003oooooool00_ooo`400001oooo000?oooo00<0 003oooooool00_ooo`030000c/k<02[>c/`030000i^KVi^KV00[Vi^H>000033c /k>c/`0;/k>c00<0003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`030000 c/k<02[>c/`030000i^KVi^KV00[Vi^H>000033c/k>c/`0;/k>c00<0003ooooo ool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`030000c/k<02[>c /`030000i^KVi^KV00[Vi^H>000033c/k>c/`0;/k>c00<0003oooooool00_ooo`400001oooo000? oooo00<0003oooooool00_ooo`030000c/k<02[>c/`030000i^KVi^KV00[Vi^H> 000033c/k>c/`0;/k>c00<0003oooooool00_ooo`400001oooo000?oooo0P0000?ooooo00001`00 00?oool200000Oooo`003oooo`030000oooooooo00;oool00`0004ac/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cc/k<02[>c/`030000oooooooo00[oool0 0`0003c/k>c00Zc/k<00`000?oo ooooo`0:oooo00<0000cc/k<02[>c/`030000oooooooo00[oool00`0003c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cc /k<02[>c/`030000oooooooo00[oool00`0003c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cc/k<02[>c/`030000oooooooo 00[oool00`0003c/k>c00Zc/k<0 0`000?ooooooo`0:oooo00<0000cc/k<02[>c/`030000oooooooo00[oool00`0003c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0 000cc/k<02[>c/`030000oooooooo00[oool00`0003c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cc/k<02[>c/`030000 oooooooo00[oool00`0003c/k>c 00Zc/k<00`000?ooooooo`0:oooo00<0000cc/k<02[>c/`030000oooooooo00[oool00`0003c/k>c00Zc/k<00`000?ooooooo`0: oooo00<0000cc/k<02[>c/`030000oooooooo00[oool00`0003c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cc/k<02[>c /`030000oooooooo00[oool00`0003c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cc/k<02[>c/`030000oooooooo00[oool0 0`0003c/k>c00Zc/k<00`000?oo ooooo`0:oooo00<0000cc/k<02[>c/`030000oooooooo00[oool00`0003c/k<02[>c/`h0000c/k<02[>c/`h0000< IVIV00<0003c/k<02[>c/`h0000c/k<02[>c/`h0000c/k<02[>c /`h0000c/k<02[>c/`h0000c/k<02[>c/`h0000c /k<02[>c/`h0000c/k<02[>c/`h0000c/k<02[>c/`h0000c/k<02[>c/`h0000c/k<02[>c/`h0000< IVIV00<0003c/k>c/`0:/k>c00<0000I6ATI6AT02QTI6@030000 VIVIVIVI00ZIVIT>00003820P0030000oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KV i^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0;6ATI00<0003oooooool00_ooo`400001oooo000?oooo00<0 003oooooool00_ooo`030000P820P82000Z0P8000`000?ooooooo`0:oooo00<0001VIVIVIVH02VIV IP030000i^KVi^KV00[Vi^H00`0004ac/k>c/`0:/k>c00<0000I6ATI6AT02QTI6@030000VIVIVIVI00ZIVIT>00003820 P0030000oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI 6ATI6@0;6ATI00<0003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`030000 P820P82000Z0P8000`000?ooooooo`0:oooo00<0001VIVIVIVH02VIVIP030000i^KVi^KV00[Vi^H0 0`0004ac/k>c/`0: /k>c00<0000I6ATI6AT02QTI6@030000VIVIVIVI00ZIVIT>00003820P0030000oooooooo00[oool0 0`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0;6ATI00<0003ooooo ool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`030000P820P82000Z0P8000`000?oo ooooo`0:oooo00<0001VIVIVIVH02VIVIP030000i^KVi^KV00[Vi^H00`0004ac/k>c/`0:/k>c00<0000I6ATI6AT02QTI 6@030000VIVIVIVI00ZIVIT>00003820P0030000oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0 003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0;6ATI00<0003oooooool00_ooo`400001oooo000? oooo00<0003oooooool00_ooo`030000P820P82000Z0P8000`000?ooooooo`0:oooo00<0001VIVIV IVH02VIVIP030000i^KVi^KV00[Vi^H00`0004ac/k>c/`0:/k>c00<0000I6ATI6AT02QTI6@030000VIVIVIVI00ZIVIT> 00003820P0030000oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000 C4ac/k>c00Zc/k<0 0`0001TI6ATI6@0;6ATI00<0003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_oo o`030000P820P82000Z0P8000`000?ooooooo`0:oooo00<0001VIVIVIVH02VIVIP030000i^KVi^KV 00[Vi^H00`0004ac /k>c/`0:/k>c00<0000I6ATI6AT02QTI6@030000VIVIVIVI00ZIVIT>00003820P0030000oooooooo 00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0;6ATI00<0 003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`030000P820P82000Z0P800 0`000?ooooooo`0:oooo00<0001VIVIVIVH02VIVIP030000i^KVi^KV00[Vi^H00`0004ac/k>c/`0:/k>c00<0000I6ATI 6AT02QTI6@030000VIVIVIVI00ZIVIT>00003820P0030000oooooooo00[oool00`0006IVIVIVIP0: IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0;6ATI00<0003oooooool00_ooo`400001 oooo000?oooo00<0003oooooool00_ooo`030000P820P82000Z0P8000`000?ooooooo`0:oooo00<0 001VIVIVIVH02VIVIP030000i^KVi^KV00[Vi^H00`0004ac/k>c/`0:/k>c00<0000I6ATI6AT02QTI6@030000VIVIVIVI 00ZIVIT>00003820P0030000oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KV iP030000C4ac/k>c 00Zc/k<00`0001TI6ATI6@0;6ATI00<0003oooooool00_ooo`400001oooo000?oooo00<0003ooooo ool00_ooo`030000P820P82000Z0P8000`000?ooooooo`0:oooo00<0001VIVIVIVH02VIVIP030000 i^KVi^KV00[Vi^H00`0004ac/k>c/`0:/k>c00<0000I6ATI6AT02QTI6@030000VIVIVIVI00ZIVIT>00003820P0030000 oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0; 6ATI00<0003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`030000P820P820 00Z0P8000`000?ooooooo`0:oooo00<0001VIVIVIVH02VIVIP030000i^KVi^KV00[Vi^H00`0004a< C4ac/k>c/`0:/k>c00<0 000I6ATI6AT02QTI6@030000VIVIVIVI00ZIVIT>00003820P0030000oooooooo00[oool00`0006IV IVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0;6ATI00<0003oooooool00_oo o`400001oooo0008oooo0P0000Goool00`000?ooooooo`02oooo00<00020P820P8002X20P0030000 oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0: 6ATI00<0002IVIVIVIT02YVIV@h0000KVi^KViP0:i^KV00<0001c/k<02[>c/`0300006ATI6ATI00/I6AT00`000?ooooooo`02oooo0@00007oool0 00Ooool010000?ooooooo`0000Coool00`000?ooooooo`02oooo00<00020P820P8002X20P0030000 oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0: 6ATI00<0002IVIVIVIT02YVIV@h0000KVi^KViP0:i^KV00<0001c/k<02[>c/`0300006ATI6ATI00/I6AT00`000?ooooooo`02oooo0@00007oool0 00[oool00`000?ooooooo`02oooo0`0000;ooooo00001`0000;oool300000Oooo`002?ooo`800005 oooo00<0003oooooool00_ooo`030000VIVIVIVI00ZIVIT00`0001TI6ATI6@0:6ATI00<0002c/k>c /k<02[>c/`030000 000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k>c 00Zc/k<00`0003KV i^KViP0:i^KV00<0001VIVIVIVH02VIVIP030000oooooooo00[oool00`000820P820P00:P8203P00 00bIVIT00`0001TI6ATI6@0:6ATI00<0002c/k>c/k<02[>c/`030000c/k<02[>c/`030000 000039VIV@030000 6ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT00`000;>c /k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c /`030000000039VI V@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT0 0`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0 000cc /k<02[>c/`030000 000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI 00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0: /k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k>c/`0:/k>c00<0 001c/k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0001c/k>c/`0: /k>c00<0001c/k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0001c /k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0 001c/k>c/`0:/k>c00<0001c/k>c00Zc/k<0 0`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0: VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0: 6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool0 00ooool00`000?ooooooo`02oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0 000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KV iP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02 oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000 i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000 IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT0 0`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0003c/k>c 00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VI VIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI 6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00 007oool000ooool00`000?ooooooo`02oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0: IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KV i^H02^KViP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool00`000?oo ooooo`02oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI 6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c /`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI 00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H0 0`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH0 0`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?ooooooo`02 oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0003c/k>c00Zc/k<00`0006IV IVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0 001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0 003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool0 0`000?ooooooo`02oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI 6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c /k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000 VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0 003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV 00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV 00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?oo ooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0003c/k>c00Zc/k<0 0`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0: VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0: 6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool0 00ooool00`000?ooooooo`02oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0 000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KV iP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool200000oooool00007 00000oooo`800001oooo000?oooo00<0003oooooool00_ooo`030000i^KVi^KV00[Vi^H00`000;>c /k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0 001c/k>c/`0:/k>c00<00020P820 P8002X20P0030000C4a 00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c 00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00: P82000<0001c/k>c/`0:/k>c00<0 0020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<00020P820P8002X20P0030000 C4a00003>KViP030000 /k>c/k>c00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820 P820P00:P82000<0001c/k>c/`0: /k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<00020P820P8002X20 P0030000C4a00003>KV iP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<0 0`000820P820P00:P82000<0001c /k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0 001c/k>c/`0:/k>c00<00020P820 P8002X20P0030000C4a 00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<0002IVIVIVIT02YVIV@030000 P820P82000Z0P8000`0006IVIVIVIP0:IVIV00<0001KVi^KViP0:i^KV00<0003c/k>c00Zc/k<00`0009VIVIVIV@0:VIVI00<00020P820P8002X20P0030000IVIVIVIV00YVIVH0 0`0004ac/k>c/`0:/k>c00<0002IVIVIVIT02YVIV@030000P820P82000Z0P8000`0006IV IVIVIP0:IVIV00<0001KVi^KViP0:i^KV00<0003c/k>c00Zc/k<00`0009VI VIVIV@0:VIVI00<00020P820P8002X20P0030000IVIVIVIV00YVIVH00`0004ac/k>c/`0: /k>c00<0002IVIVIVIT02YVIV@030000P820P82000Z0P8000`0006IVIVIVIP0:IVIV00<0001KVi^KViP0: i^KV00<0003c/k>c00Zc/k<00`0009VIVIVIV@0:VIVI00<00020P820 P8002X20P0030000IVIVIVIV00YVIVH00`0004ac/k>c/`0:/k>c00<0002IVIVIVIT02YVI V@030000P820P82000Z0P8000`0006IVIVIVIP0:IVIV00<0001KVi^KViP0:i^KV00<0003c/k>c00Zc/k<00`0009VIVIVIV@0:VIVI00<00020P820P8002X20P0030000IVIVIVIV 00YVIVH00`0004ac/k>c/`0:/k>c00<0002IVIVIVIT02YVIV@030000P820P82000Z0P800 0`0006IVIVIVIP0:IVIV00<0001KVi^KViP0:i^KV00<0003c/k>c00Zc/k<0 0`0009VIVIVIV@0:VIVI00<00020P820P8002X20P0030000IVIVIVIV00YVIVH00`0004ac /k>c/`0:/k>c00<0002IVIVIVIT02YVIV@030000P820P82000Z0P8000`0006IVIVIVIP0:IVIV00<0 001KV i^KViP0:i^KV00<0003c/k>c00Zc/k<00`0009VIVIVIV@0:VIVI00<0 0020P820P8002X20P0030000IVIVIVIV00YVIVH00`0004ac/k>c/`0:/k>c00<0002IVIVI VIT02YVIV@030000P820P82000Z0P8000`0006IVIVIVIP0:IVIV00<0001KVi^KViP0:i^KV00<0003c/k>c00Zc/k<00`0009VIVIVIV@0:VIVI00<00020P820P8002X20P0030000 IVIVIVIV00YVIVH00`0004ac/k>c/`0:/k>c00<0002IVIVIVIT02YVIV@030000P820P820 00Z0P8000`0006IVIVIVIP0:IVIV00<0001KVi^KViP0:i^KV00<0003c/k>c 00Zc/k<00`0009VIVIVIV@0:VIVI00<00020P820P8002X20P0030000IVIVIVIV00YVIVH00`0004a< C4ac/k>c/`0:/k>c00<0002IVIVIVIT02YVIV@030000P820P82000Z0P8000`0006IVIVIVIP0: IVIV00<0001KVi^KViP0:i^KV00<0003c/k>c00Zc/k<00`0009VIVIVIV@0: VIVI00<00020P820P8002X20P0030000IVIVIVIV00YVIVH00`0004ac/k>c/`0:/k>c00<0 002IVIVIVIT02YVIV@030000P820P82000Z0P8000`0006IVIVIVIP0:IVIV00<0001KVi^KViP0:i^KV00<0 003c/k>c00Zc/k<00`0009VIVIVIV@0:VIVI00<00020P820P8002X20 P0030000IVIVIVIV00YVIVH00`0004ac/k>c/`0: /k>c00<0002IVIVIVIT02YVIV@030000P820P82000Z0P8000`0006IVIVIVIP0:IVIV00<0001KVi^KViP0: i^KV00<0003c/k>c00Zc/k<00`0009VIVIVIV@0:VIVI00<00020P820 P8002X20P0030000IVIVIVIV00YVIVH00`0004aKVi^KViP0:i^KV00<0003c/k>c00Zc/k<00`0009VIVIVIV@0:VIVI00<00020P820P8002X20P0030000 IVIVIVIV00YVIVH00`0004a 00003?ooo`030000i^KVi^KV00[Vi^H00`000c/k<02[>c/`030000 VIVIVIVI00ZIVIT00`000820P820P00:P82000<0001VIVIVIVH02VIVIP030000C4ac/k>c00Zc/k<00`000000031TI6@030000c /k<02[>c/`030000cKVi^KViP0;i^KV00<0003oooooool00_ooo`400001 oooo000?oooo00<0003oooooool00_ooo`0300006ATI6ATI00XI6AT00`0003c/k>c00Zc/k<00`000000031TI6@030000c/k<02[>c/`030000cKVi^KViP0;i^KV00<0003oooooool00_ooo`400001oooo000?oooo00<0003ooooo ool00_ooo`0300006ATI6ATI00XI6AT00`0003c/k>c00Zc/k<0 0`000000031TI6@030000 c/k<02[>c/`030000cKVi^KViP0; i^KV00<0003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`0300006ATI6ATI 00XI6AT00`0003c/k>c00Zc/k<00`000000031TI6@030000c/k<02[>c/`030000cKVi^KViP0;i^KV00<0003oooooool00_oo o`400001oooo000?oooo00<0003oooooool00_ooo`0300006ATI6ATI00XI6AT00`0003c/k>c00Zc/k<00`000000031TI6@030000c/k<02[>c/`030000 cKVi^KViP0;i^KV00<0003oooooool00_ooo`400001oooo000?oooo00<0 003oooooool00_ooo`0300006ATI6ATI00XI6AT00`0003c/k>c 00Zc/k<00`000000031TI 6@030000c/k<02[>c/`030000cKV i^KViP0;i^KV00<0003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`030000 6ATI6ATI00XI6AT00`0003c/k>c00Zc/k<00`000000031TI6@030000c/k<02[>c/`030000cKVi^KViP0;i^KV00<0003ooooo ool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`0300006ATI6ATI00XI6AT00`0003c/k>c00Zc/k<00`000000031TI6@030000c/k<02[>c /`030000cKVi^KViP0;i^KV00<0003oooooool00_ooo`400001oooo000? oooo00<0003oooooool00_ooo`0300006ATI6ATI00XI6AT00`0003c/k>c00Zc/k<00`000 000031TI6@030000c/k<02[>c/`030000cKVi^KViP0;i^KV00<0003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_oo o`0300006ATI6ATI00XI6AT00`0003c/k>c00Zc/k<00`000000031TI6@030000c/k<02[>c/`030000cKVi^KViP0;i^KV00<0 003oooooool00_ooo`400001oooo000?oooo00<0003oooooool00_ooo`0300006ATI6ATI00XI6AT0 0`0003c/k>c00Zc/k<00`000000031TI6@030000c /k<02[>c/`030000cKVi^KViP0;i^KV00<0003oooooool00_ooo`400001 oooo000?oooo00<0003oooooool00_ooo`0300006ATI6ATI00XI6AT00`0003c/k>c00Zc/k<00`000000031TI6@030000c/k<02[>c/`030000cKVi^KViP0;i^KV00<0003oooooool00_ooo`400001oooo000?oooo0P0000?ooooo 00001`0000?oool200000Oooo`003oooo`030000oooooooo00;oool00`0003c/k>c 00Zc/k<00`000>KVi^KViP0:i^KV3P0000`cc/k<02k>c/`030000oooooooo00;oool100000Ooo o`003oooo`030000oooooooo00;oool00`0003c/k>c00Zc/k<00`000>KVi^KViP0: i^KV3P0000`cc/k<02k>c/`030000oooooooo00;oool100000Oooo`003oooo`030000oooooooo 00;oool00`0003c/k>c00Zc/k<00`000>KVi^KViP0:i^KV3P0000`cc/k<02k>c /`030000oooooooo00;oool100000Oooo`003oooo`030000oooooooo00;oool00`0003c/k>c00Zc/k<00`000>KVi^KViP0:i^KV3P0000`cc/k<02k>c/`030000oooooooo00;oool1 00000Oooo`003oooo`030000oooooooo00;oool00`0003c/k>c00Zc/k<00`000>KV i^KViP0:i^KV3P0000`cc/k<02k>c/`030000oooooooo00;oool100000Oooo`003oooo`030000 oooooooo00;oool00`0003c/k>c00Zc/k<00`000>KVi^KViP0:i^KV3P0000`cc /k<02k>c/`030000oooooooo00;oool100000Oooo`003oooo`030000oooooooo00;oool00`0003c/k>c00Zc/k<00`000>KVi^KViP0:i^KV3P0000`cc/k<02k>c/`030000oooooooo 00;oool100000Oooo`003oooo`030000oooooooo00;oool00`0003c/k>c00Zc/k<0 0`000>KVi^KViP0:i^KV3P0000`cc/k<02k>c/`030000oooooooo00;oool100000Oooo`003ooo o`030000oooooooo00;oool00`0003c/k>c00Zc/k<00`000>KVi^KViP0:i^KV3P00 00`cc/k<02k>c/`030000oooooooo00;oool100000Oooo`003oooo`030000oooooooo00;oool0 0`0003c/k>c00Zc/k<00`000>KVi^KViP0:i^KV3P0000`cc/k<02k>c/`030000 oooooooo00;oool100000Oooo`003oooo`030000oooooooo00;oool00`0003c/k>c 00Zc/k<00`000>KVi^KViP0:i^KV3P0000`cc/k<02k>c/`030000oooooooo00;oool100000Ooo o`003oooo`030000oooooooo00;oool00`0003c/k>c00Zc/k<00`000>KVi^KViP0: i^KV3P0000`cc/k<02k>c/`030000oooooooo00;oool100000Oooo`003oooo`800003ooooo`00 00L00003oooo0P00007oool000ooool00`000?ooooooo`02oooo00<0001KVi^KViP0:i^KV00<0000I6ATI6AT02QTI6@030000IVIVIVIV00YVIVH0 0`000;>c/k>c/`0:/k>c00<0003oooooool02_ooo`030000c/k>c00Zc/k<00`000?ooooooo`0: oooo00<0000cKV i^KViP0:i^KV00<0000I6ATI6AT02QTI6@030000IVIVIVIV00YVIVH00`000;>c/k>c/`0:/k>c00<0 003oooooool02_ooo`030000c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cKVi^KViP0:i^KV00<0000I6ATI 6AT02QTI6@030000IVIVIVIV00YVIVH00`000;>c/k>c/`0:/k>c00<0003oooooool02_ooo`030000 c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cKVi^KViP0:i^KV00<0000I6ATI6AT02QTI6@030000IVIVIVIV 00YVIVH00`000;>c/k>c/`0:/k>c00<0003oooooool02_ooo`030000c/k>c00Zc/k<00`000?oo ooooo`0:oooo00<0000cKVi^KViP0:i^KV00<0000I6ATI6AT02QTI6@030000IVIVIVIV00YVIVH00`000;>c/k>c/`0: /k>c00<0003oooooool02_ooo`030000c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cKVi^KViP0:i^KV00<0 000I6ATI6AT02QTI6@030000IVIVIVIV00YVIVH00`000;>c/k>c/`0:/k>c00<0003oooooool02_oo o`030000c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cKVi^KViP0:i^KV00<0000I6ATI6AT02QTI6@030000 IVIVIVIV00YVIVH00`000;>c/k>c/`0:/k>c00<0003oooooool02_ooo`030000c/k>c00Zc/k<0 0`000?ooooooo`0:oooo00<0000cKVi^KViP0:i^KV00<0000I6ATI6AT02QTI6@030000IVIVIVIV00YVIVH00`000;>c /k>c/`0:/k>c00<0003oooooool02_ooo`030000c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0 000cKVi^KViP0: i^KV00<0000I6ATI6AT02QTI6@030000IVIVIVIV00YVIVH00`000;>c/k>c/`0:/k>c00<0003ooooo ool02_ooo`030000c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cKVi^KViP0:i^KV00<0000I6ATI6AT02QTI 6@030000IVIVIVIV00YVIVH00`000;>c/k>c/`0:/k>c00<0003oooooool02_ooo`030000c/k>c 00Zc/k<00`000?ooooooo`0:oooo00<0000cKVi^KViP0:i^KV00<0000I6ATI6AT02QTI6@030000IVIVIVIV00YVIVH0 0`000;>c/k>c/`0:/k>c00<0003oooooool02_ooo`030000c/k>c00Zc/k<00`000?ooooooo`0: oooo00<0000cKV i^KViP0:i^KV00<0000I6ATI6AT02QTI6@030000IVIVIVIV00YVIVH00`000;>c/k>c/`0:/k>c00<0 003oooooool02_ooo`030000c/k>c00Zc/k<00`000?ooooooo`0:oooo00<0000cKVi^KViP0:i^KV00<0 000cc/k>c00Zc/k<>000036IVIP030000cKVi^KViP0:i^KV00<0000cc/k>c00Zc/k<> 000036IVIP030000cKVi^KViP0:i^KV00<0000cc/k>c00Zc/k<>000036IVIP030000cKVi^KViP0: i^KV00<0000cc/k>c00Zc/k<>000036IVIP030000cKVi^KViP0:i^KV00<0000cc/k>c 00Zc/k<>000036IVIP030000cKVi^KViP0:i^KV00<0000cc/k>c00Zc/k<>000036IVIP030000 cKV i^KViP0:i^KV00<0000cc/k>c00Zc/k<>000036IVIP030000cKVi^KViP0:i^KV00<0000cc/k>c00Zc/k<>000036IVIP030000cKVi^KViP0:i^KV00<0000cc/k>c00Zc/k<>000036IV IP030000cKVi^KViP0:i^KV00<0000cc/k>c00Zc/k<>000036IVIP030000cKVi^KViP0:i^KV00<0000cc/k>c00Zc/k<>000036IVIP030000cc/k<02[>c /`h0000c/k>c00Zc/k<00`0001TI6ATI6@0:6ATI00<0 002IVIVIVIT02YVIV@h0000KV i^KViP0:i^KV00<0001c/k<02[>c/`0300006ATI6ATI00/I6AT00`000?ooooooo`02oooo0@00007oool000?oool0 0`000?ooooooo`02oooo00<0003oooooool01?ooo`030000oooooooo00;oool00`000820P820P00: P82000<0003oooooool02_ooo`030000IVIVIVIV00YVIVH00`000>KVi^KViP0:i^KV00<0001c/k<02[>c/`030000 6ATI6ATI00XI6AT00`0009VIVIVIV@0:VIVI3P0000b0P8000`000?ooooooo`0:oooo00<0001VIVIV IVH02VIVIP030000i^KVi^KV00[Vi^H00`0004ac/k>c/`0:/k>c00<0000I6ATI6AT02aTI6@030000oooooooo00;oool1 00000Oooo`000_ooo`800004oooo0`0000Coool00`000?ooooooo`02oooo00<00020P820P8002X20 P0030000oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI 6ATI6@0:6ATI00<0002IVIVIVIT02YVIV@h0000KVi^KViP0:i^KV00<0001c/k<02[>c/`0300006ATI6ATI00/I6AT00`000?ooooooo`02oooo0@00 007oool000ooool00`000?ooooooo`02oooo00<00020P820P8002X20P0030000oooooooo00[oool0 0`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0:6ATI00<0002IVIVI VIT02YVIV@h0000KVi^KViP0: i^KV00<0001c /k<02[>c/`0300006ATI6ATI00/I6AT00`000?ooooooo`02oooo0@00007oool000ooool00`000?oo ooooo`02oooo00<00020P820P8002X20P0030000oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0 003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0:6ATI00<0002IVIVIVIT02YVIV@h0000KVi^KViP0:i^KV00<0001c/k<02[>c/`0300006ATI6ATI 00/I6AT00`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<00020P820 P8002X20P0030000oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000 C4ac/k>c00Zc/k<0 0`0001TI6ATI6@0:6ATI00<0002IVIVIVIT02YVIV@h0000KVi^KViP0:i^KV00<0001c/k<02[>c/`0300006ATI6ATI00/I6AT00`000?ooooooo`02 oooo0@00007oool000ooool00`000?ooooooo`02oooo00<00020P820P8002X20P0030000oooooooo 00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0:6ATI00<0 002IVIVIVIT02YVIV@h0000KV i^KViP0:i^KV00<0001c/k<02[>c/`0300006ATI6ATI00/I6AT00`000?ooooooo`02oooo0@00007oool000ooool0 0`000?ooooooo`02oooo00<00020P820P8002X20P0030000oooooooo00[oool00`0006IVIVIVIP0: IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0:6ATI00<0002IVIVIVIT02YVIV@h0000< P82000<0003oooooool02_ooo`030000IVIVIVIV00YVIVH00`000>KVi^KViP0:i^KV00<0001c/k<02[>c/`030000 6ATI6ATI00/I6AT00`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0 0020P820P8002X20P0030000oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KV iP030000C4ac/k>c 00Zc/k<00`0001TI6ATI6@0:6ATI00<0002IVIVIVIT02YVIV@h0000KVi^KViP0:i^KV00<0001c/k<02[>c/`0300006ATI6ATI00/I6AT00`000?oo ooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<00020P820P8002X20P0030000 oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0: 6ATI00<0002IVIVIVIT02YVIV@h0000KVi^KViP0:i^KV00<0001c/k<02[>c/`0300006ATI6ATI00/I6AT00`000?ooooooo`02oooo0@00007oool0 00ooool00`000?ooooooo`02oooo00<00020P820P8002X20P0030000oooooooo00[oool00`0006IV IVIVIP0:IVIV00<0003Vi^KVi^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0:6ATI00<0002IVIVIVIT02YVI V@h0000KVi^KViP0:i^KV00<0 001c/k<02[>c /`0300006ATI6ATI00/I6AT00`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02 oooo00<00020P820P8002X20P0030000oooooooo00[oool00`0006IVIVIVIP0:IVIV00<0003Vi^KV i^H02^KViP030000C4ac/k>c00Zc/k<00`0001TI6ATI6@0:6ATI00<0002IVIVIVIT02YVIV@h0000KVi^KViP0:i^KV00<0001c/k<02[>c/`0300006ATI6ATI00/I6AT0 0`000?ooooooo`02oooo0@00007oool000ooool200000oooool0000700000oooo`800001oooo000? oooo00<0003oooooool00_ooo`030000VIVIVIVI00ZIVIT00`0001TI6ATI6@0:6ATI00<0002c/k>c /k<02[>c/`030000 000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI 00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0: /k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000 000039VIV@030000 6ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT00`000;>c /k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c /`030000000039VI V@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT0 0`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0 000cc /k<02[>c/`030000 000039VIV@0300006ATI6ATI00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k<02[>c/`030000000039VIV@0300006ATI6ATI 00XI6AT00`000;>c/k>c/`0:/k>c00<0000cc/k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0 001c/k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0001c/k>c/`0: /k>c00<0001c/k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0001c /k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0001c/k>c/`0:/k>c00<0001c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI 6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c /k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000 VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0 003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV 00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV 00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?oo ooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0003c/k>c00Zc/k<0 0`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0: VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0: 6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool0 00ooool00`000?ooooooo`02oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0 000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KV iP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02 oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000 i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000 IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT0 0`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0003c/k>c 00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VI VIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI 6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00 007oool000ooool00`000?ooooooo`02oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0: IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KV i^H02^KViP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool00`000?oo ooooo`02oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI 6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c /`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI 00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H0 0`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV00YVIVH0 0`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?ooooooo`02 oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0003c/k>c00Zc/k<00`0006IV IVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0 001c/k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0 003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool0 0`000?ooooooo`02oooo00<0003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI 6AT02QTI6@030000i^KVi^KV00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c /k<02[>c/`030000IVIVIVIV00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000 VIVIVIVI00^IVIT00`000?ooooooo`02oooo0@00007oool000ooool00`000?ooooooo`02oooo00<0 003c/k>c00Zc/k<00`0006IVIVIVIP0:IVIV00<0000I6ATI6AT02QTI6@030000i^KVi^KV 00[Vi^H00`0009VIVIVIV@0:VIVI00<0001c/k<02[>c/`030000IVIVIVIV 00YVIVH00`0001TI6ATI6@0:6ATI00<0003Vi^KVi^H02^KViP030000VIVIVIVI00^IVIT00`000?oo ooooo`02oooo0@00007oool000ooool200000oooool0000700000oooo`800001oooo000?oooo00<0 003oooooool00_ooo`030000i^KVi^KV00[Vi^H00`000;>c/k>c/`0:/k>c00<00020P820P8002X20 P0030000C4a00003>KV iP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<0 0`000820P820P00:P82000<0001c /k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0 001c/k>c/`0:/k>c00<00020P820 P8002X20P0030000C4a 00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c 00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00: P82000<0001c/k>c/`0:/k>c00<0 0020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<00020P820P8002X20P0030000 C4a00003>KViP030000 /k>c/k>c00Zc/k<00`000820P820P00:P82000<0001c/k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820 P820P00:P82000<0001c/k>c/`0: /k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0001c /k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820P820P00:P82000<0 001c/k>c/`0:/k>c00<00020P820P8002X20P0030000C4a00003>KViP030000/k>c/k>c00Zc/k<00`000820 P820P00:P82000<0001"], ImageRangeCache->{{{0, 287}, {287, 0}} -> {-1.58175, -1.49696, 0.0768038, \ 0.0768038}}] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell["Summary", "Subsubsection"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(n = 4;\)\), "\[IndentingNewLine]", \(\(Print["\", Length[\[GothicCapitalR]\_n], "\< relations on a set of \>", n, "\< elements, there are:\>"];\)\), "\[IndentingNewLine]", \(Print[ v = Length[ u = Select[\[GothicCapitalR]\_n, reflexiveQ]], "\< reflexive relations like \>", MatrixForm[ u\[LeftDoubleBracket]Random[ Integer, {1, v}]\[RightDoubleBracket]]]\), "\[IndentingNewLine]", \(Print[ v = Length[ u = Select[\[GothicCapitalR]\_n, symmetricQ]], "\< symmetric relations like \>", MatrixForm[ u\[LeftDoubleBracket]Random[ Integer, {1, v}]\[RightDoubleBracket]]]\), "\[IndentingNewLine]", \(Print[ v = Length[ u = Select[\[GothicCapitalR]\_n, transitiveQ]], "\< transitive relations like \>", MatrixForm[ u\[LeftDoubleBracket]Random[ Integer, {1, v}]\[RightDoubleBracket]]]\), "\[IndentingNewLine]", \(Print[ v = Length[ u = Select[\[GothicCapitalR]\_n, equivalenceQ]], "\< equivalence relations like \>", MatrixForm[ u\[LeftDoubleBracket]Random[ Integer, {1, v}]\[RightDoubleBracket]]]\), "\[IndentingNewLine]", \(Print[ v = Length[ u = Select[\[GothicCapitalR]\_n, graphQ]], "\< graph relations like \>", MatrixForm[ u\[LeftDoubleBracket]Random[ Integer, {1, v}]\[RightDoubleBracket]]]\), "\[IndentingNewLine]", \(Print[ v = Length[ u = Select[\[GothicCapitalR]\_n, antiSymmetricQ]], "\< antiSymmetric relations like \>", MatrixForm[ u\[LeftDoubleBracket]Random[ Integer, {1, v}]\[RightDoubleBracket]]]\), "\[IndentingNewLine]", \(Print[ v = Length[ u = Select[\[GothicCapitalR]\_n, partialOrderQ]], "\< partial order relations like \>", MatrixForm[ u\[LeftDoubleBracket]Random[ Integer, {1, v}]\[RightDoubleBracket]]]\), "\[IndentingNewLine]", \(Print[ v = Length[ u = Select[\[GothicCapitalR]\_n, totalOrderQ]], "\< total order relations like \>", MatrixForm[ u\[LeftDoubleBracket]Random[ Integer, {1, v}]\[RightDoubleBracket]]]\), "\[IndentingNewLine]", \(Print[ v = Length[ u = Select[\[GothicCapitalR]\_n, latticeQ]], "\< lattice relations like \>", MatrixForm[ u\[LeftDoubleBracket]Random[ Integer, {1, v}]\[RightDoubleBracket]]]\)}], "Input", CellLabel->"In[24]:="], Cell[BoxData[ InterpretationBox[\("Of the "\[InvisibleSpace]65536\[InvisibleSpace]" \ relations on a set of "\[InvisibleSpace]4\[InvisibleSpace]" elements, there \ are:"\), SequenceForm[ "Of the ", 65536, " relations on a set of ", 4, " elements, there are:"], Editable->False]], "Print", CellLabel->"From In[24]:="], Cell[BoxData[ InterpretationBox[ RowBox[{ "4096", "\[InvisibleSpace]", "\<\" reflexive relations like \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1", "0"}, {"1", "1", "1", "1"}, {"1", "1", "1", "0"}, {"1", "0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], SequenceForm[ 4096, " reflexive relations like ", MatrixForm[ {{1, 1, 1, 0}, {1, 1, 1, 1}, {1, 1, 1, 0}, {1, 0, 0, 1}}]], Editable->False]], "Print", CellLabel->"From In[24]:="], Cell[BoxData[ InterpretationBox[ RowBox[{ "1024", "\[InvisibleSpace]", "\<\" symmetric relations like \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0", "0"}, {"0", "0", "1", "1"}, {"0", "1", "0", "1"}, {"0", "1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], SequenceForm[ 1024, " symmetric relations like ", MatrixForm[ {{1, 0, 0, 0}, {0, 0, 1, 1}, {0, 1, 0, 1}, {0, 1, 1, 1}}]], Editable->False]], "Print", CellLabel->"From In[24]:="], Cell[BoxData[ InterpretationBox[ RowBox[{ "3994", "\[InvisibleSpace]", "\<\" transitive relations like \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0", "0"}, {"0", "0", "0", "0"}, {"0", "1", "1", "1"}, {"0", "1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], SequenceForm[ 3994, " transitive relations like ", MatrixForm[ {{1, 1, 0, 0}, {0, 0, 0, 0}, {0, 1, 1, 1}, {0, 1, 0, 0}}]], Editable->False]], "Print", CellLabel->"From In[24]:="], Cell[BoxData[ InterpretationBox[ RowBox[{ "15", "\[InvisibleSpace]", "\<\" equivalence relations like \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1", "1"}, {"1", "1", "1", "1"}, {"1", "1", "1", "1"}, {"1", "1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], SequenceForm[ 15, " equivalence relations like ", MatrixForm[ {{1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}}]], Editable->False]], "Print", CellLabel->"From In[24]:="], Cell[BoxData[ InterpretationBox[ RowBox[{ "64", "\[InvisibleSpace]", "\<\" graph relations like \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0", "0"}, {"0", "1", "0", "1"}, {"0", "0", "1", "1"}, {"0", "1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], SequenceForm[ 64, " graph relations like ", MatrixForm[ {{1, 0, 0, 0}, {0, 1, 0, 1}, {0, 0, 1, 1}, {0, 1, 1, 1}}]], Editable->False]], "Print", CellLabel->"From In[24]:="], Cell[BoxData[ InterpretationBox[ RowBox[{ "11664", "\[InvisibleSpace]", "\<\" antiSymmetric relations like \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0", "1"}, {"0", "1", "1", "0"}, {"0", "0", "1", "1"}, {"0", "0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], SequenceForm[ 11664, " antiSymmetric relations like ", MatrixForm[ {{0, 1, 0, 1}, {0, 1, 1, 0}, {0, 0, 1, 1}, {0, 0, 0, 1}}]], Editable->False]], "Print", CellLabel->"From In[24]:="], Cell[BoxData[ InterpretationBox[ RowBox[{ "219", "\[InvisibleSpace]", "\<\" partial order relations like \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0", "1"}, {"0", "1", "0", "0"}, {"0", "0", "1", "0"}, {"0", "0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], SequenceForm[ 219, " partial order relations like ", MatrixForm[ {{1, 1, 0, 1}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}]], Editable->False]], "Print", CellLabel->"From In[24]:="], Cell[BoxData[ InterpretationBox[ RowBox[{ "24", "\[InvisibleSpace]", "\<\" total order relations like \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1", "1"}, {"0", "1", "1", "1"}, {"0", "0", "1", "0"}, {"0", "0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], SequenceForm[ 24, " total order relations like ", MatrixForm[ {{1, 1, 1, 1}, {0, 1, 1, 1}, {0, 0, 1, 0}, {0, 0, 1, 1}}]], Editable->False]], "Print", CellLabel->"From In[24]:="], Cell[BoxData[ InterpretationBox[ RowBox[{ "36", "\[InvisibleSpace]", "\<\" lattice relations like \"\>", "\[InvisibleSpace]", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0", "0"}, {"1", "1", "1", "1"}, {"1", "0", "1", "1"}, {"1", "0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], SequenceForm[ 36, " lattice relations like ", MatrixForm[ {{1, 0, 0, 0}, {1, 1, 1, 1}, {1, 0, 1, 1}, {1, 0, 0, 1}}]], Editable->False]], "Print", CellLabel->"From In[24]:="] }, Open ]], Cell[TextData[{ "Now, to each relation M let us associate a binary vector v of size 9 with \ entries corresponding to each of the above classes, wherein v[i]=True iff M \ is of type i. There are ", Cell[BoxData[ \(TraditionalForm\`2\^9\)]], "=512 such, coded by the corresponding decimal digits. For a given n, let \ us compute a vector of length 512 whose i-th entry includes the number of \ relations in ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalR]\_n\)]], " obeying the properties described by the binary number i." }], "Text"], Cell[BoxData[ \(data[n_] := Map[{reflexiveQ[#], symmetricQ[#], transitiveQ[#], equivalenceQ[#], graphQ[#], antiSymmetricQ[#], partialOrderQ[#], totalOrderQ[#], latticeQ[#]} &, \[GothicCapitalR]\_n]\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(v = Table[0, {512}];\)\), "\[IndentingNewLine]", \(\(Map[\(v\[LeftDoubleBracket]# + 1\[RightDoubleBracket]++\) &, \(FromDigits[#, 2] &\) /@ \ \((\ data[4]\ /. \ {True \[Rule] 1, False \[Rule] 0})\)];\)\), "\[IndentingNewLine]", \(v\)}], "Input"], Cell[BoxData[ \({49228, 0, 0, 0, 0, 0, 0, 0, 7650, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 332, 0, 0, 0, 0, 0, 0, 0, 3270, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 923, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 22, 0, 0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3182, 0, 0, 0, 0, 0, 0, 0, 510, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 122, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 182, 12, 0, 24, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 49, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}\)], "Output"] }, Open ]], Cell[TextData[{ "So, there are 49228 relations not enjoying any property, 7650 being only \ antisymmetric (because the number 7650 occupies position ", Cell[BoxData[ \(TraditionalForm\`000001000\_2\)]], "=8, counting the first as the \"zero-th\" one), 332 being only transitive, \ etc. In order to find out the number of antisymmetric relations we have to \ add the numbers at positions " }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(FromDigits[#, 2] &\) /@ Select[IntegerDigits[Range[0, 2\^9 - 1], 2, 9], #\[LeftDoubleBracket]\(-4\)\[RightDoubleBracket] == 1 &] + 1\)], "Input"], Cell[BoxData[ \({9, 10, 11, 12, 13, 14, 15, 16, 25, 26, 27, 28, 29, 30, 31, 32, 41, 42, 43, 44, 45, 46, 47, 48, 57, 58, 59, 60, 61, 62, 63, 64, 73, 74, 75, 76, 77, 78, 79, 80, 89, 90, 91, 92, 93, 94, 95, 96, 105, 106, 107, 108, 109, 110, 111, 112, 121, 122, 123, 124, 125, 126, 127, 128, 137, 138, 139, 140, 141, 142, 143, 144, 153, 154, 155, 156, 157, 158, 159, 160, 169, 170, 171, 172, 173, 174, 175, 176, 185, 186, 187, 188, 189, 190, 191, 192, 201, 202, 203, 204, 205, 206, 207, 208, 217, 218, 219, 220, 221, 222, 223, 224, 233, 234, 235, 236, 237, 238, 239, 240, 249, 250, 251, 252, 253, 254, 255, 256, 265, 266, 267, 268, 269, 270, 271, 272, 281, 282, 283, 284, 285, 286, 287, 288, 297, 298, 299, 300, 301, 302, 303, 304, 313, 314, 315, 316, 317, 318, 319, 320, 329, 330, 331, 332, 333, 334, 335, 336, 345, 346, 347, 348, 349, 350, 351, 352, 361, 362, 363, 364, 365, 366, 367, 368, 377, 378, 379, 380, 381, 382, 383, 384, 393, 394, 395, 396, 397, 398, 399, 400, 409, 410, 411, 412, 413, 414, 415, 416, 425, 426, 427, 428, 429, 430, 431, 432, 441, 442, 443, 444, 445, 446, 447, 448, 457, 458, 459, 460, 461, 462, 463, 464, 473, 474, 475, 476, 477, 478, 479, 480, 489, 490, 491, 492, 493, 494, 495, 496, 505, 506, 507, 508, 509, 510, 511, 512}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Plus @@ \ v\[LeftDoubleBracket]%\[RightDoubleBracket]\)], "Input"], Cell[BoxData[ \(11664\)], "Output"] }, Open ]], Cell["\<\ The inmense majority of relations avoid our classification and there is only \ one enjoying all of them.\ \>", "Text"] }, Closed]] }, Open ]], Cell[CellGroupData[{ Cell["Equivalence Relations and Partial Orders", "Subsection"], Cell["\<\ \tIt seems that equivalence relations and partial orders are scarse and worth \ of being generated differently. They are both reflexive and transitive so \ first we generate such relations. We observe that the inclusion of the \ elements of the diagonal has no effect on the transitity law. Given an \ already transitive matrix, we add one element to it and add those elements \ implied by its presence in order to preserve transitivity. \ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ Length[u\[LeftDoubleBracket]n\[RightDoubleBracket] = Select[\(\(\[GothicCapitalR]\)\(\ \)\)\_n, reflexiveQ[#] && transitiveQ[#] &]], {n, 4}]\)], "Input"], Cell[BoxData[ \({1, 4, 29, 355}\)], "Output"] }, Open ]], Cell["(Sequence A000798 in [8])", "Text"], Cell[TextData[{ "The following function ", StyleBox["extend", "Input"], " takes a pair of elements forming a relation and extends it so that it \ becomes transitive (transitive closure)" }], "Text"], Cell[BoxData[ \(extend[p_] := Module[{t}, \[IndentingNewLine]t[ u : {___, {a_, b_\ }, ___, {b_, c_\ }, ___}] := Append[u, {a, c}\ ]\ /; \((c \[NotEqual] a)\) && Not[MemberQ[u, {a, c}]]; \[IndentingNewLine]t[ u : {___, {b_, c_\ }, ___, {a_, b_}, ___}] := Append[u, {a, c}\ ]\ /; \((c \[NotEqual] a)\) && Not[MemberQ[u, {a, c}]]; \[IndentingNewLine]t[x_] := x; \[IndentingNewLine]\[IndentingNewLine]FixedPoint[t, p]]\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(extend[{{1, 3}, {1, 2}, {2, 1}, {7, 1}}]\)], "Input"], Cell[BoxData[ \({{1, 3}, {1, 2}, {2, 1}, {7, 1}, {2, 3}, {7, 3}, {7, 2}}\)], "Output"] }, Open ]], Cell[TextData[{ "Function ", StyleBox["trans", "Input"], " below works by extending (in the ", StyleBox["Do", "Input"], " loop) throughout all possible elements, one at a time." }], "Text"], Cell[BoxData[ \(trans[n_] := \(trans[n] = Module[{\[CapitalOmega], tr = {{}}, j, m, ans = {}, b}, \[IndentingNewLine]\[CapitalOmega] = Select[Flatten[Table[{i, j}, {i, n}, {j, n}], 1], First[#] \[NotEqual] Last[#] &]; \[IndentingNewLine]\[IndentingNewLine]Do[\ \[IndentingNewLine]tr = Union[Flatten[ Map[\((m = #; \[IndentingNewLine]b = Complement[\[CapitalOmega], m]; \[IndentingNewLine]\(Sort[ extend[Join[{#}, m]]] &\) /@ b)\) &, tr], 1]]; \[IndentingNewLine]ans = Join[ans, tr], {n \((n - 1)\)}]; \[IndentingNewLine]\[IndentingNewLine]ans = Union[ans]; \[IndentingNewLine]\(\((j = IdentityMatrix[ n]; \[IndentingNewLine]m = #; \[IndentingNewLine]\(\((j\ \[LeftDoubleBracket]First[#], Last[#]\[RightDoubleBracket] = 1)\) &\) /@ m; \[IndentingNewLine]j)\) &\) /@ ans]\)\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(MatrixForm /@ trans[3]\)], "Input"], Cell[BoxData[ RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"1", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "1"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0"}, {"1", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0"}, {"0", "1", "0"}, {"0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1"}, {"0", "1", "1"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1"}, {"0", "1", "0"}, {"1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"1", "1", "1"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"1", "1", "0"}, {"1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "1"}, {"0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1"}, {"0", "1", "1"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1"}, {"0", "1", "0"}, {"0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0"}, {"0", "1", "0"}, {"1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1"}, {"1", "1", "1"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"1", "1", "1"}, {"1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"1", "1", "0"}, {"1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1"}, {"1", "1", "1"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1"}, {"0", "1", "1"}, {"0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1"}, {"0", "1", "0"}, {"1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0"}, {"1", "1", "0"}, {"1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1"}, {"1", "1", "1"}, {"1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"1", "1", "1"}, {"1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1"}, {"1", "1", "1"}, {"1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Timing[Table[Length[trans[n]] + 1, {n, 5}]]\)], "Input"], Cell[BoxData[ \({784.6600000000003`\ Second, {1, 4, 29, 355, 6942}}\)], "Output"] }, Open ]], Cell["(+1 to include the identity. Timing taken on a 700 Mhz PC)", "Text"], Cell["So, the number of equivalence relations is:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[Length[Select[trans[n], symmetricQ]] + 1, {n, 5}]\)], "Input"], Cell[BoxData[ \({1, 2, 5, 15, 52}\)], "Output"] }, Open ]], Cell["and the number of partial orders is:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[Length[Select[trans[n], antiSymmetricQ]] + 1, {n, 5}]\)], "Input"], Cell[BoxData[ \({1, 3, 19, 219, 4231}\)], "Output"] }, Open ]], Cell["\<\ and the number of relations that are both equivalence and partial orders \ is:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ Length[Select[trans[n], \((symmetricQ[#] && antiSymmetricQ[#])\) &]] + 1, {n, 5}]\)], "Input"], Cell[BoxData[ \({1, 1, 1, 1, 1}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell["Set Partitions", "Subsubsection"], Cell[TextData[{ "\tIf we are interested only in the enumeration of equivalence relations, \ Bell and Stirling numbers arise. The relation between set partitions and \ equivalence relations allow us to further simplify their enumeration and \ generation. For a positive integer m, let \[ScriptCapitalP](m) denote the set \ of all partitions of ", StyleBox["Range[m]", "Input"], " into non-empty subsets. For positive integers m and n with \ n\[LessEqual]m, let \[ScriptCapitalP](m, n) denote the set of all partitions \ of ", StyleBox["Range[m]", "Input"], " into exactly n non-empty subsets. The Bell numbers \[ScriptCapitalB](m) = \ | \[ScriptCapitalP](m) | and the Stirling numbers of the second kind \ \[ScriptCapitalS](m, n) = | \[ScriptCapitalP](n, m) | are such that \ \[ScriptCapitalB](m) = ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\+\(n = 1\)\%m S(n, \ m)\)]], ". Moreover, they satisfy the following recursive definitions:" }], "Text"], Cell[BoxData[{ \(\[ScriptCapitalB][0] := 1\), "\[IndentingNewLine]", \(\[ScriptCapitalB][ m_] := \[Sum]\+\(i = 0\)\%\(m - 1\)Binomial[m - 1, i] \[ScriptCapitalB][ i]\[IndentingNewLine]\), "\[IndentingNewLine]", \(\[ScriptCapitalS][0, 0] := 1\), "\[IndentingNewLine]", \(\[ScriptCapitalS][_, 0] := 0\ \), "\[IndentingNewLine]", \(\[ScriptCapitalS][m_, n_] := 0\ /; \ n == m + 1\), "\[IndentingNewLine]", \(\[ScriptCapitalS][m_, n_] := 0\ /; \ n > m\), "\[IndentingNewLine]", \(\[ScriptCapitalS][m_, n_] := n\ \ \[ScriptCapitalS][m - 1, n] + \[ScriptCapitalS][m - 1, n - 1]\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[\[ScriptCapitalB][n], {n, 10}]\)], "Input"], Cell[BoxData[ \({1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Table[\[ScriptCapitalS][n, m], {n, 10}, {m, 10}]\ // \ MatrixForm\)], "Input"], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0", "0", "0", "0", "0", "0", "0", "0"}, {"1", "1", "0", "0", "0", "0", "0", "0", "0", "0"}, {"1", "3", "1", "0", "0", "0", "0", "0", "0", "0"}, {"1", "7", "6", "1", "0", "0", "0", "0", "0", "0"}, {"1", "15", "25", "10", "1", "0", "0", "0", "0", "0"}, {"1", "31", "90", "65", "15", "1", "0", "0", "0", "0"}, {"1", "63", "301", "350", "140", "21", "1", "0", "0", "0"}, {"1", "127", "966", "1701", "1050", "266", "28", "1", "0", "0"}, {"1", "255", "3025", "7770", "6951", "2646", "462", "36", "1", "0"}, {"1", "511", "9330", "34105", "42525", "22827", "5880", "750", "45", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]], "Output"] }, Open ]], Cell["\<\ The sum of the last row must be equal to \[ScriptCapitalB][10]. The numbers \ below or to the right of the 1\.b4s form familiar sequences. The following provides a function to generate set partitions in lexicographic \ order. \ \>", "Text"], Cell[BoxData[{ \(part[n_Integer] := part[Range[n]]\), "\[IndentingNewLine]", \(part[{x_}] := {{{x}}}\), "\[IndentingNewLine]", \(part[{x_, y___}] := Module[{p = part[{y}], u}, \[IndentingNewLine]Flatten[ Map[\((u = #; \[IndentingNewLine]Join[{Join[{{x}}, u]}, MapIndexed[ReplacePart[u, Join[{x}, #1], #2] &, \ u]])\) &, p], 1]]\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(part[4]\)], "Input"], Cell[BoxData[ \({{{1}, {2}, {3}, {4}}, {{1, 2}, {3}, {4}}, {{2}, {1, 3}, {4}}, {{2}, {3}, {1, 4}}, {{1}, {2, 3}, {4}}, {{1, 2, 3}, {4}}, {{2, 3}, {1, 4}}, {{1}, {3}, {2, 4}}, {{1, 3}, {2, 4}}, {{3}, {1, 2, 4}}, {{1}, {2}, {3, 4}}, {{1, 2}, {3, 4}}, {{2}, {1, 3, 4}}, {{1}, {2, 3, 4}}, {{1, 2, 3, 4}}}\)], "Output"] }, Open ]], Cell["Visually more appealing:", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(t[{p__}] := \(StringJoin[ToString /@ {p}]\)\&_\), "\n", \(\(\((t /@ #)\) &\) /@ part[4]\)}], "Input"], Cell[BoxData[ \({{"1"\&_, "2"\&_, "3"\&_, "4"\&_}, {"12"\&_, "3"\&_, "4"\&_}, {"2"\&_, "13"\&_, "4"\&_}, {"2"\&_, "3"\&_, "14"\&_}, {"1"\&_, "23"\&_, "4"\&_}, {"123"\&_, "4"\&_}, {"23"\&_, "14"\&_}, {"1"\&_, "3"\&_, "24"\&_}, {"13"\&_, "24"\&_}, {"3"\&_, "124"\&_}, {"1"\&_, "2"\&_, "34"\&_}, {"12"\&_, "34"\&_}, {"2"\&_, "134"\&_}, {"1"\&_, "234"\&_}, {"1234"\&_}}\)], "Output"] }, Open ]], Cell["\<\ Or, if it is required the number 1 to appear in the first partition:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Sort[ Map[\((t /@ #)\) &, \(Sort[#, First[#1] < First[#2] &] &\)\ /@ \ part[4]]]\)], "Input"], Cell[BoxData[ \({{"1234"\&_}, {"1"\&_, "234"\&_}, {"12"\&_, "34"\&_}, {"123"\&_, "4"\&_}, {"124"\&_, "3"\&_}, {"13"\&_, "24"\&_}, {"134"\&_, "2"\&_}, {"14"\&_, "23"\&_}, {"1"\&_, "2"\&_, "34"\&_}, {"1"\&_, "23"\&_, "4"\&_}, {"1"\&_, "24"\&_, "3"\&_}, {"12"\&_, "3"\&_, "4"\&_}, {"13"\&_, "2"\&_, "4"\&_}, {"14"\&_, "2"\&_, "3"\&_}, {"1"\&_, "2"\&_, "3"\&_, "4"\&_}}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Table[Length[part[n]], {n, 6}]\)], "Input"], Cell[BoxData[ \({1, 2, 5, 15, 52, 203}\)], "Output"] }, Open ]], Cell["\<\ From the list of partitions we can recover all matrices corresponding to \ equivalence relations.\ \>", "Text"], Cell[TextData[{ "Conversely, an equivalence relation induces a partition of the base set. \ The identification of partitions and equivalence relations allows us to \ easily visualize the truth of non-trivial results such as the following:\n\n\ If | A | = n, then, for any n \[LessEqual] h \[LessEqual] ", Cell[BoxData[ \(TraditionalForm\`n\^2\)]], ", there is an equivalence relation H on A, with | H | = h, if and only if \ there exists a sequence of positive integers ", Cell[BoxData[ \(TraditionalForm\`n\_1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`n\_2\)]], ", ..., ", Cell[BoxData[ \(TraditionalForm\`n\_k\)]], " such that\t\t" }], "Text"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`\[Sum]\+\(i = 1\)\%k n\_i = n\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\+\(i = 1\)\%k n\_i\^2 = h\)]], "\t" }], "Text", TextAlignment->Center], Cell[TextData[{ "To see the correctness of this assertion, we only have to interpret k as \ the number of classes, ", Cell[BoxData[ \(TraditionalForm\`n\_i\)]], " as the number of elements belonging to class i and recall the fact that \ an equivalence relation has associated a binary matrix in which the rows and \ columns can be relabeled in such a way that the matrix consists of diagonal \ blocks of ", Cell[BoxData[ \(TraditionalForm\`n\_i\^2\)]], " 1\.b4s each [4]." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Functions", "Subsection"], Cell[TextData[{ "\tFunctions are a special kind of relations, namely, those matrices having \ just a 1 in each row, hence there are ", Cell[BoxData[ \(TraditionalForm\`n\^n\)]], "of them, instead of ", Cell[BoxData[ \(TraditionalForm\`2\^\(n\^2\)\)]], ", (for n = 4 there are 256 functions out of 65536 relations). It is easy \ to see that there is only one reflexive function, which also happens to be \ the only symmetric one, the only partial order, and the only equivalence \ relation. " }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(#\^# &\) /@ Range[7]\)], "Input", CellLabel->"In[80]:="], Cell[BoxData[ \({1, 4, 27, 256, 3125, 46656, 823543}\)], "Output", CellLabel->"Out[80]="] }, Open ]], Cell["(Sequence A000312 in [8])", "Text"], Cell[TextData[{ "Instead of filtering all relations to obtain those corresponding to \ functions, we directly generate them. We generate all type of rows first (n \ types with all zeroes except a single 1). Then we generate all numbers from 1 \ to ", Cell[BoxData[ \(TraditionalForm\`n\^n\)]], " in a number system of base n, which provides us with a way to actually \ enumerate the functions. Each number in base n describes which type of \ corresponds to the associated function." }], "Text"], Cell[BoxData[{ \(functions[1] := {{1}}\), "\n", \(functions[n_] := \(functions[n] = Module[{z, f, i}, \[IndentingNewLine]z = Table[0, {n}]; \[IndentingNewLine]f = 1 + IntegerDigits[Range[0, n\^n - 1], n, n]; \[IndentingNewLine]r = Table[ReplacePart[z, 1, i], {i, n, 1, \(-1\)}]; \[IndentingNewLine]Map[ r\[LeftDoubleBracket]#\[RightDoubleBracket] &, f]]\)\)}], "Input",\ CellLabel->"In[186]:="], Cell[CellGroupData[{ Cell[BoxData[ \(MatrixForm\ /@ \ functions[3]\)], "Input"], Cell[BoxData[ RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"0", "0", "1"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"0", "0", "1"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"0", "0", "1"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"0", "1", "0"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"0", "1", "0"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"1", "0", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"1", "0", "0"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"1", "0", "0"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"0", "0", "1"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"0", "0", "1"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"0", "0", "1"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"0", "1", "0"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"0", "1", "0"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"1", "0", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"1", "0", "0"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"1", "0", "0"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "0", "1"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "0", "1"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "0", "1"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"1", "0", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"1", "0", "0"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"1", "0", "0"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}]], "Output"] }, Open ]], Cell["Let us now find out which of those are transitive", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MatrixForm\ /@ \ Select[functions[3], transitiveQ]\)], "Input"], Cell[BoxData[ RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"0", "0", "1"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"0", "1", "0"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "0", "1"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"1", "0", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"1", "0", "0"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}]], "Output"] }, Open ]], Cell["and symmetric:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MatrixForm\ /@ \ Select[functions[3], symmetricQ]\)], "Input"], Cell[BoxData[ RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"0", "1", "0"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"1", "0", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "0", "1"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Table[Length[Select[functions[n], transitiveQ]], {n, 6}]\)], "Input"], Cell[BoxData[ \({1, 3, 10, 41, 196, 1057}\)], "Output"] }, Open ]], Cell["(See sequence A000248 in [8])", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[Length[Select[functions[n], symmetricQ]], {n, 6}]\)], "Input"], Cell[BoxData[ \({1, 2, 4, 10, 26, 76}\)], "Output"] }, Open ]], Cell["(See sequence A000085 in[8])", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ Length[Select[functions[n], transitiveQ[#] && symmetricQ[#] &]], {n, 6}]\)], "Input"], Cell[BoxData[ \({1, 1, 1, 1, 1, 1}\)], "Output"] }, Open ]], Cell["\<\ To check for surjectivity we only have to check the transpose being also a \ function. Automatically we are checking for injectivity as all surjective \ functions are also injective ones.\ \>", "Text"], Cell[BoxData[ \(surjectiveQ[m_] := Positive[\ Times\ @@ Map[Plus\ @@ # &, \ Transpose[m]]]\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(MatrixForm\ /@ \ Select[functions[3], surjectiveQ]\)], "Input"], Cell[BoxData[ RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"0", "1", "0"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"1", "0", "0"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"0", "0", "1"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"1", "0", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "0", "1"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Table[Length[Select[functions[n], surjectiveQ]], {n, 2, 6}]\)], "Input"], Cell[BoxData[ \({2, 6, 24, 120, 720}\)], "Output"] }, Open ]], Cell["\<\ The above counts the number of permutations.They can be readily generated as:\ \ \>", "Text"], Cell[BoxData[ \(permutations[n_] := Module[{z = Table[0, {n}], f = Permutations[Range[n]], i}, \n\t\tr = Table[ReplacePart[z, 1, i], {i, n, 1, \(-1\)}]; \n\t\tMap[ r\[LeftDoubleBracket]#\[RightDoubleBracket] &, f]]\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(MatrixForm\ /@ \ permutations[3]\)], "Input"], Cell[BoxData[ RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"0", "1", "0"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"1", "0", "0"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"0", "0", "1"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"1", "0", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "0", "1"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0"}, {"0", "1", "0"}, {"0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}]], "Output"] }, Open ]], Cell["Conjecture: Symmetry implies surjectivity.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ Length[\ Select[functions[n], symmetricQ[#] && Not[surjectiveQ[#]] &]], {n, 2, 6}]\)], "Input"], Cell[BoxData[ \({0, 0, 0, 0, 0}\)], "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell["Connected Relations and Trees", "Subsection"], Cell["\<\ \tAny relation can be depicted as a multigraph. In order to find out quickly \ whether the matrix of a relation corresponds to a connected multigraph we \ examine its power:\ \>", "Text"], Cell[BoxData[ \(connectedQ[m_] := Module[{n = Length[m], r}, \[IndentingNewLine]r = m + IdentityMatrix[n]; \[IndentingNewLine]Position[ MatrixPower[r, n], 0] \[Equal] {}]\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(MatrixForm /@ \ Select[\[GothicCapitalR]\_2, connectedQ]\)], "Input"], Cell[BoxData[ RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1"}, {"1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1"}, {"1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1"}, {"1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1"}, {"1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[Select[\[GothicCapitalR]\_#, connectedQ]] &\) /@ \ Range[4]\)], "Input"], Cell[BoxData[ \({2, 4, 144, 25696}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(MatrixForm\ /@ \ Select[functions[3], connectedQ]\)], "Input"], Cell[BoxData[ RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1"}, {"1", "0", "0"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1", "0"}, {"0", "0", "1"}, {"1", "0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(\(Length[Select[functions[#], connectedQ]] &\) /@ \ Range[6]\)], "Input"], Cell[BoxData[ \({1, 1, 2, 6, 24, 120}\)], "Output"] }, Open ]], Cell["\<\ Trees are connected acyclic graphs; equivalently, graphs having 3 |m| -2 \ 1\.b4s\ \>", "Text"], Cell[BoxData[ \(treeQ[ m_] := \((\((Plus @@ \ Flatten[m])\) \[Equal] 3 Length[m] - 2)\) && graphQ[m]\)], "Input", CellLabel->"In[109]:="], Cell[CellGroupData[{ Cell[BoxData[ \(\(MatrixForm /@ Select[\[GothicCapitalR]\_#, treeQ] &\) /@ \ Range[4]\)], "Input", CellLabel->"In[112]:="], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"{", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], "}"}], ",", RowBox[{"{", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1"}, {"1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], "}"}], ",", RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1"}, {"0", "1", "1"}, {"1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0"}, {"1", "1", "1"}, {"0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1"}, {"1", "1", "0"}, {"1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}], ",", RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0", "0"}, {"0", "1", "1", "1"}, {"0", "1", "1", "1"}, {"0", "1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0", "1"}, {"0", "1", "0", "1"}, {"0", "0", "1", "1"}, {"1", "1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0", "1"}, {"0", "1", "1", "0"}, {"0", "1", "1", "1"}, {"1", "0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0", "1"}, {"0", "1", "1", "1"}, {"0", "1", "1", "0"}, {"1", "1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1", "0"}, {"0", "1", "0", "1"}, {"1", "0", "1", "1"}, {"0", "1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1", "0"}, {"0", "1", "1", "0"}, {"1", "1", "1", "1"}, {"0", "0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1", "0"}, {"0", "1", "1", "1"}, {"1", "1", "1", "0"}, {"0", "1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1", "1"}, {"0", "1", "0", "0"}, {"1", "0", "1", "1"}, {"1", "0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1", "1"}, {"0", "1", "0", "1"}, {"1", "0", "1", "0"}, {"1", "1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "1", "1"}, {"0", "1", "1", "0"}, {"1", "1", "1", "0"}, {"1", "0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0", "0"}, {"1", "1", "0", "1"}, {"0", "0", "1", "1"}, {"0", "1", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0", "0"}, {"1", "1", "1", "0"}, {"0", "1", "1", "1"}, {"0", "0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0", "0"}, {"1", "1", "1", "1"}, {"0", "1", "1", "0"}, {"0", "1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0", "1"}, {"1", "1", "0", "0"}, {"0", "0", "1", "1"}, {"1", "0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0", "1"}, {"1", "1", "0", "1"}, {"0", "0", "1", "0"}, {"1", "1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "0", "1"}, {"1", "1", "1", "0"}, {"0", "1", "1", "0"}, {"1", "0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1", "0"}, {"1", "1", "0", "0"}, {"1", "0", "1", "1"}, {"0", "0", "1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1", "0"}, {"1", "1", "0", "1"}, {"1", "0", "1", "0"}, {"0", "1", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1", "0"}, {"1", "1", "1", "0"}, {"1", "1", "1", "0"}, {"0", "0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1", "1"}, {"1", "1", "0", "0"}, {"1", "0", "1", "0"}, {"1", "0", "0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}]}], "}"}]], "Output", CellLabel->"Out[112]="] }, Open ]], Cell["(See sequences A003150 and A006963 in [8]) ", "Text"] }, Closed]] }, Open ]], Cell[CellGroupData[{ Cell["PART II SELECTIVE ENUMERATION", "Section"], Cell[TextData[{ "\tOf the 16 relations forming the set ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalR]\_2\)]], ", only 10 are different under relabeling. By renaming the elements {1,2,3} \ as, say, {3,1,2} respectively, matrix m below gets transformed into a \ structurally equivalent (isomorphic) one:" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"m", "=", RowBox[{"(", GridBox[{ {"0", "1", "1"}, {"1", "0", "0"}, {"1", "1", "1"} }], ")"}]}], ";"}], "\[IndentingNewLine]", \(Plus\ @@ \ m\), "\[IndentingNewLine]", \(Transpose[\(Transpose[ m\[LeftDoubleBracket]{3, 1, 2}\[RightDoubleBracket]]\)\[LeftDoubleBracket]{3, 1, 2}\[RightDoubleBracket]]\ // MatrixForm\)}], "Input", CellLabel->"In[90]:="], Cell[BoxData[ \({2, 2, 2}\)], "Output", CellLabel->"Out[91]="], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1", "1"}, {"1", "0", "1"}, {"0", "1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]], "Output", CellLabel->"Out[92]//MatrixForm="] }, Open ]], Cell["\<\ The 10 non-isomorphic relations we mentioned previously are obtained through \ the following:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(n = 2;\)\), "\[IndentingNewLine]", \(\(ans = {};\)\), "\[IndentingNewLine]", \(\(u = \[GothicCapitalR]\_n;\)\), "\[IndentingNewLine]", \(\(p = Permutations[Range[n]];\)\), "\[IndentingNewLine]", \(\(While[u \[NotEqual] {}, AppendTo[ans, First[u]]; \[IndentingNewLine]t = \ \((\(Transpose[\(Transpose[\(First[ u]\)\[LeftDoubleBracket]#\[RightDoubleBracket]]\)\ \[LeftDoubleBracket]#\[RightDoubleBracket]] &\) /@ p)\); \[IndentingNewLine]u = Complement[u, t]\[IndentingNewLine]];\)\), "\[IndentingNewLine]", \(MatrixForm /@ \ ans\)}], "Input", CellLabel->"In[57]:="], Cell[BoxData[ RowBox[{"{", RowBox[{ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0"}, {"0", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0"}, {"0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0"}, {"1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0"}, {"1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1"}, {"0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1"}, {"1", "0"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "1"}, {"1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0"}, {"0", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0"}, {"1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)], ",", TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "1"}, {"1", "1"} }], "\[NoBreak]", ")"}], (MatrixForm[ #]&)]}], "}"}]], "Output", CellLabel->"Out[62]="] }, Open ]], Cell[TextData[{ "Note that the identity relation and the one obtained by swapping its rows \ are non-isomorphic. Similarly, from the relations on ", StyleBox["Range[3]", "Input"], ", only 104 are non-isomorphic." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(n = 3;\)\), "\[IndentingNewLine]", \(\(ans = {};\)\), "\[IndentingNewLine]", \(\(u = \[GothicCapitalR]\_n;\)\), "\[IndentingNewLine]", \(\(p = Permutations[Range[n]];\)\), "\[IndentingNewLine]", \(\(While[u \[NotEqual] {}, AppendTo[ans, First[u]]; \[IndentingNewLine]t = \ \((\(Transpose[\(Transpose[\(First[ u]\)\[LeftDoubleBracket]#\[RightDoubleBracket]]\)\ \[LeftDoubleBracket]#\[RightDoubleBracket]] &\) /@ p)\); \[IndentingNewLine]u = Complement[u, t]\[IndentingNewLine]];\)\), "\[IndentingNewLine]", \(Length[ans]\)}], "Input", CellLabel->"In[20]:="], Cell[BoxData[ \(104\)], "Output", CellLabel->"Out[25]="] }, Open ]], Cell[TextData[{ "However, if we want to find out how large is the set of non-isomorphic \ relations by exhaustive enumeration on ", StyleBox["Range[4]", "Input"], " we find it intolerably time-consuming (on a 700 MHz PC) when using this \ procedure.\n\nThis section will aim at solving the problem of counting how \ many distinct relations, taken from a number of important categories, can be \ defined on a finite set, the distinction being made upon non-isomorphic \ structures. We accomplish this by using a tool from computational group \ theory called Burnside\.b4s Lemma, which applies whenever the criteria to \ distinguish two configurations depends heavily on symmetry properties of the \ underlying set; this symmetry is described by the action of a group on the \ set [3, 5].\n\nIn the following, we will obtain a formula for the number of \ non-isomorphic relations by exploiting symmetry properties of the set of \ permutations that give rise to isomorphic versions of each of the possible \ relations.\n\n\tLet ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalS]\_n\)]], " be the symmetric group, that is, the group of all permutations on ", StyleBox["Range[n]", "Input"], ". For every relation A \[Epsilon] ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalR]\_n\)]], " and permutation \[Pi] \[Epsilon] ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalS]\_n\)]], ", we define a transformation ", Cell[BoxData[ \(TraditionalForm\`\[GothicT]\_\[Pi]\)]], " : ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalR]\_n\)]], " \[Rule]", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalR]\_n\)]], " by the rule" }], "Text"], Cell[BoxData[ \(\(\[GothicT]\_\[Pi]\) \((A)\) = \(\(\[GothicT]\_\[Pi]\) \((\([a\_\(i, j\ \)]\))\) = \([a\_\(\(\[Pi]\^\(-1\)\) \((i)\), \(\[Pi]\^\(-1\)\) \ \((j)\)\)]\)\)\)], "NumberedEquation", TextAlignment->Center], Cell[TextData[{ "For example, if A=", Cell[BoxData[ RowBox[{"(", GridBox[{ {"0", "1", "1", "1"}, {"1", "0", "0", "1"}, {"0", "1", "1", "0"}, {"0", "0", "1", "0"} }], ")"}]]], " \[Epsilon]", Cell[BoxData[ \(TraditionalForm\`\(\(\ \ \)\(\[GothicCapitalR]\_4\)\)\)]], " and \[Pi]=", Cell[BoxData[ RowBox[{"(", GridBox[{ {"1", "2", "3", "4"}, {"4", "1", "2", "3"} }], ")"}]]], "\[Epsilon] ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalS]\_4\)]], ", then ", Cell[BoxData[ \(TraditionalForm\`\(\(\[Pi]\^\(-1\)\)\(=\)\)\)]], Cell[BoxData[ RowBox[{"(", GridBox[{ {"1", "2", "3", "4"}, {"2", "3", "4", "1"} }], ")"}]]], " and ", Cell[BoxData[ \(TraditionalForm\`\[GothicT]\_\[Pi]\)]], "(A)=", Cell[BoxData[ RowBox[{"(", GridBox[{ {"0", "0", "1", "1"}, {"1", "1", "0", "0"}, {"0", "1", "0", "0"}, {"1", "1", "1", "0"} }], ")"}]]], ". These results can be obtained by using definition (1) or, alternatively, \ by interpreting it as the result of rows and columns swapping, that is, first \ we move the rows of A according to \[Pi] to obtain ", Cell[BoxData[ RowBox[{"(", GridBox[{ {"1", "0", "0", "1"}, {"0", "1", "1", "0"}, {"0", "0", "1", "0"}, {"0", "1", "1", "1"} }], ")"}]]], "and then the columns to obtain the final result." }], "Text"], Cell[TextData[{ "Now, let A, B \[Element] ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalR]\_n\)]], ". We say that A and B are isomorphic if there is a \[Pi] \[Epsilon] ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalS]\_n\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\[GothicT]\_\[Pi]\)]], "(A)=B. \n\nAs the algebraic structure of the set { ", Cell[BoxData[ \(TraditionalForm\`\[GothicT]\_\[Pi]\)]], " | \[Pi] \[Epsilon] ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalS]\_n\)]], "} is identical with that of ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalS]\_n\)]], " itself, the concept of isomorphism as equivalence can be seen as an \ action of ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalS]\_n\)]], " onto ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalR]\_n\)]], " [5]. So, the question of counting the number of non-isomorphic relations \ on ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalR]\_n\)]], " is the same as aking how many orbits does this action induce on ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalR]\_n\)]], ". By Burnside\.b4s Lemma [1, 5], this number, denoted by struct(n), is \ given by" }], "Text"], Cell[BoxData[ \(struct \((n)\) = \(1\/\(n!\)\) \(\[Sum]\+\(\[Pi]\ \[Epsilon]\ \ \[GothicCapitalS]\_n\)Fix \((\[GothicT]\_\[Pi])\)\)\)], "Text", TextAlignment->Center], Cell[TextData[{ "where Fix(", Cell[BoxData[ \(TraditionalForm\`t\_\[Pi]\)]], ") is the number of relations fixed by ", Cell[BoxData[ \(TraditionalForm\`t\_\[Pi]\)]], ". Equivalently, by just counting over representatives of conjugation \ classes:" }], "Text"], Cell[BoxData[ \(struct \((n)\) = \[Sum]\+\([\[Pi]]\)n \((\[Pi])\) Fix \((\[GothicT]\_\[Pi])\)\)], "Text", TextAlignment->Center], Cell[TextData[{ "Wherein, if the cycle structure of \[Pi], or any representative of its \ class is ", Cell[BoxData[ \(TraditionalForm\`\(\(x\_1!\)\ \(1\^x\_1\) \(x\_2!\)\ 2\^x\_2 ... \) \ \(x\_n!\)\ n\^x\_n\)]], ", then" }], "Text"], Cell[BoxData[ RowBox[{\(n \((\[Pi])\)\), "=", FractionBox["1", FormBox[\(\(\(x\_1!\)\ \(1\^x\_1\) \(x\_2!\)\ 2\^x\_2 ... \) \ \(x\_n!\)\ n\^x\_n\), "TraditionalForm"]]}]], "Text", TextAlignment->Center], Cell[TextData[{ "Our problem can then be stated as follows: given a conjugate class of ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalS]\_n\)]], ", how many relations are fixed by any of its representatives (hence by all \ members of the class)?\n\nLet \[Pi] \[Epsilon] ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalS]\_n\)]], ". If \[Pi] is an n-cycle [6], then there are only two relations fixed by \ ", Cell[BoxData[ \(TraditionalForm\`\[GothicT]\_\[Pi]\)]], ", namely those in which the elements of their matrices are all zero or all \ unity. Let us then assume that this is not the case and that ", Cell[BoxData[ \(TraditionalForm\`\[GothicT]\_\[Pi]\)]], "(A)=A for some relation A and that \[Pi] contains the cycles (", Cell[BoxData[ \(TraditionalForm\`x\_1\)]], " ", Cell[BoxData[ \(TraditionalForm\`x\_2\)]], " ... ", Cell[BoxData[ \(TraditionalForm\`x\_h\)]], ") and (", Cell[BoxData[ \(TraditionalForm\`y\_1\)]], " ", Cell[BoxData[ \(TraditionalForm\`y\_2\)]], " ... ", Cell[BoxData[ \(TraditionalForm\`y\_k\)]], "). Let ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], " be the submatrix of A consisting exclusively of the rows ", Cell[BoxData[ \(TraditionalForm\`x\_1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`x\_2\)]], ", ..., ", Cell[BoxData[ \(TraditionalForm\`x\_h\)]], " and columns ", Cell[BoxData[ \(TraditionalForm\`y\_1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`y\_2\)]], ", ..., ", Cell[BoxData[ \(TraditionalForm\`y\_k\)]], " of A. ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], " is, in general, build up from disconnected parts of A.\n\nThe effect of \ \[Pi] on A completely resides on ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], "; the cycles of \[Pi] are disjoint, so, in computing \[GothicT](A) row \ movements are not followed by column movements and viceversa as was the case \ previously. Further, the requirement ", Cell[BoxData[ \(TraditionalForm\`\(\[GothicT]\_\[Pi]\)(A) = A\)]], " forces the following hk equations to hold:" }], "Text"], Cell[TextData[{ "Let ", Cell[BoxData[ \(TraditionalForm\`a\_\(x\_i, y\_j\)\)]], " be a typical entry of ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], "; then" }], "Text"], Cell[BoxData[ RowBox[{\(a\_\(x\_i, y\_j\)\), "=", RowBox[{ FormBox[\(a\_\(x\_\(i + 1\), y\_\(j + 1\)\)\), "TraditionalForm"], "=", RowBox[{ FormBox[\(a\_\(x\_\(i + 2\), y\_\(j + 2\)\)\), "TraditionalForm"], "=", " ", RowBox[{"...", " ", "=", " ", FormBox[\(a\_\(x\_\(i + hk\), y\_\(j + hk\)\)\), "TraditionalForm"]}]}]}]}]], "NumberedEquation", TextAlignment->Center], Cell[TextData[{ "where the row and column indices are computed mod h and mod k respectively \ (mod operations will be taken over positive representatives 1, 2, ..., n. For \ instance, if n=6, then 5+5=4 and 4+2=6). This corresponds to a path traversed \ by a bishop over a toroidal chessboard, which may possibly lead to a complete \ traversal of ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], " (see Figure 1), reminding of the well-known fact [3, 4] that, if n and m \ are co-prime and Cn denotes the set of all residual classes mod n, then, \ regarded as group structures, the sets Cn \[Times] Cm and Cnm are \ isomorphic." }], "Text"], Cell[CellGroupData[{ Cell["Example 1", "Subsubsection"], Cell[TextData[{ "\tLet \[Pi]=(1 4 2)(3)(5 6) and let A=", Cell[BoxData[ RowBox[{"(", GridBox[{ {"1", "0", "0", "0", "0", "1"}, {"0", "1", "0", "0", "1", "0"}, {"0", "0", "1", "1", "0", "0"}, {"0", "0", "1", "1", "0", "0"}, {"0", "1", "0", "0", "1", "0"}, {"1", "0", "0", "0", "0", "1"} }], ")"}]], TextJustification->0], " be a candidate to be tested as fixed by ", Cell[BoxData[ \(\[GothicT]\_\[Pi]\)], TextJustification->0], ". Let us, for instance, consider the cycles (1 4 2) and (5 6). Then ", Cell[BoxData[ RowBox[{\(A\_0\), "=", RowBox[{"(", GridBox[{ {"0", "1"}, {"1", "0"}, {"0", "0"} }], ")"}]}]], TextJustification->0], "(note that the internal order of the cycles does not matter). Also, the \ equation ", Cell[BoxData[ \(\(\[GothicT]\_\[Pi]\) \((A)\) = A\)], TextJustification->0], " implies that ", Cell[BoxData[ \(a\_\(1, 5\) = \(a\_\(4, 6\) = \(a\_\(2, 5\) = \(a\_\(1, 6\) = \ \(a\_\(4, 5\) = a\_\(2, 6\)\)\)\)\)\)], TextJustification->0], " . This amounts to say that all elements of ", Cell[BoxData[ \(A\_\(\(0\)\(\ \)\(\[IndentingNewLine]\)\)\)], TextJustification->0], "should be equal. Hence, A is not fixed by ", Cell[BoxData[ \(\[GothicT]\_\[Pi]\)], TextJustification->0], ". Let us note that, if h and k are co-prime, only the first LCM(h, k) \ equations are different, while the other merely repeat them. For instance, if \ \[Pi] = (1 2)(3 4 5 6), then ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], "=", Cell[BoxData[ RowBox[{"(", GridBox[{ {"0", "0", "0", "1"}, {"0", "0", "1", "0"} }], ")"}]]], "and" }], "Text"], Cell[BoxData[ \(\(\[GothicT]\_\[Pi]\) \((A)\) = \(A\ \ \ \ \ \[DoubleLongRightArrow]\ \ \ \ \ a\_\(1, 3\) = \(a\_\(2, 4\) = \(a\_\(1, 5\) = \(a\_\(2, 6\) = \(a\_\(1, 3\ \) = \(a\_\(2, 4\) = \(a\_\(1, 5\) = a\_\(2, 6\)\)\)\)\)\)\)\)\)], "NumberedEquation"], Cell[TextData[{ "Therefore, instead of eight equations, we will have four (the last four \ were written following the indices combinations and to point out that \ redundant information can arise this way). To span the complete set of \ possibilities, that is, encompass all elements of ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], " as indicated, we have to choose a new entry and repeat the procedure, \ that is, " }], "Text"], Cell[TextData[{ Cell[BoxData[ \(a\_\(1, 4\) = \(a\_\(2, 5\) = \(a\_\(1, 6\) = \(a\_\(2, 3\) = \ \(a\_\(1, 4\) = \(a\_\(2, 5\) = \(a\_\(1, 6\) = a\_\(2, 3\)\)\)\)\)\)\)\)]], "." }], "Text", TextAlignment->Center], Cell[TextData[{ "In this case, as we needed to iterate the process twice, we will say that \ ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], " has 2 degrees of freedom. In other words, there are two families that \ arise in this manner and can independently be assigned local equal values. In \ general, the degree of freedom of ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], " under \[Pi] is equal to GCD(h, k).\n\nExtending the concept of degrees of \ freedom to the original matrix A we note that, by disjointness, the degrees \ of freedom of each block of \[Pi] are unaffected by those in any other block. \ So, the degree of freedom of A, denoted by d(\[Pi]), can be taken as the sum \ of the degrees of every pair of cycles of A. As an illustration of this \ consider the following example. Let us compute d(\[Pi]) for \[Pi]=(1 4 \ 2)(3)(5 6) for an arbitrary matrix R of size 6x6. All possible pairings of \ cycles follow the pattern described in Figure 2. The results are given in \ Table 1.\n" }], "Text"], Cell[BoxData[GridBox[{ {\(Identification\[IndentingNewLine] Tag\), \(Cycle\[IndentingNewLine] Pair\), \(Equalities\[IndentingNewLine] Implied\ by\ \((2)\)\), \(Degree\[IndentingNewLine] of\ Freedom\)}, {"A", \(\((1\ 4\ 2)\) \((1\ 4\ 2)\)\), \(x\_\(1, 1\) = \(x\_\(4, 1\) \ = x\_\(2, 2\)\)\[IndentingNewLine] x\_\(1, 4\) = \(x\_\(4, 2\) = x\_\(2, 1\)\)\[IndentingNewLine] x\_\(1, 2\) = \(x\_\(4, 1\) = x\_\(2, 4\)\)\), "3"}, {"B", \(\((1\ 4\ 2)\) \((3)\)\), \(x\_\(1, 3\) = \(x\_\(4, 3\) = x\_\(2, 3\)\)\), "1"}, {"C", \(\((1\ 4\ 2)\) \((5\ 6)\)\), \(x\_\(1, 5\) = \(x\_\(4, 6\) = \ \(x\_\(2, 5\) = \[IndentingNewLine]\(x\_\(1, 6\) = \(x\_\(4, 5\) = x\_\(2, 6\)\)\)\)\)\), "1"}, {"D", \(\((3)\) \((1\ 4\ 2)\)\), \(x\_\(3, 1\) = \(x\_\(3, 4\) = x\_\(3, 2\)\)\), "1"}, {"E", \(\((3)\) \((3)\)\), \(x\_\(3, 3\)\), "1"}, {"F", \(\((3)\) \((5\ 6)\)\), \(x\_\(3, 5\) = x\_\(3, 6\)\), "1"}, {"G", \(\((5\ 6)\) \((1\ 4\ 2)\)\), \(x\_\(5, 1\) = \(x\_\(6, 4\) = \ \(x\_\(5, 2\) = \[IndentingNewLine]\(x\_\(6, 1\) = \(x\_\(5, 4\) = x\_\(6, 2\)\)\)\)\)\), "1"}, {"H", \(\((5\ 6)\) \((3)\)\), \(x\_\(5, 3\) = x\_\(6, 3\)\), "1"}, {"I", \(\((5\ 6)\) \((5\ 6)\)\), \(x\_\(5, 5\) = x\_\(6, 6\)\[IndentingNewLine] x\_\(5, 6\) = x\_\(6, 5\)\), "2"} }]], "NumberedTable", TextAlignment->Center], Cell["\<\ Hence, the degree of freedom of R is d(\[Pi])=12. Consequently, \[Pi] induces \ the following subdivision of R, where elements of the same tag must coincide; \ the subindices correspond to several choices made locally to span all \ elements of the corresponding blocks, these choices amount to the respective \ degrees of freedom of their blocks (see Figure 3)\ \>", "Text"], Cell[BoxData[ RowBox[{"(", GridBox[{ {\(A\_1\), \(A\_3\), "B", \(A\_2\), "C"}, {\(A\_2\), \(A\_1\), "B", \(A\_3\), "C"}, {"D", "D", "E", "D", "F"}, {\(A\_3\), \(A\_2\), "B", \(A\_1\), "C"}, {"G", "G", "H", "G", \(I\_1\)}, {"G", "G", "H", "G", \(I\_2\)} }], ")"}]], "Text", TextAlignment->Center], Cell[TextData[{ "Therefore, there are ", Cell[BoxData[ \(TraditionalForm\`2\^12\)]], " relations fixed by (1 4 2)(3)(5 6). We can conclude that, in general, \ Fix(", Cell[BoxData[ \(TraditionalForm\`\[GothicT]\_\[Pi]\)]], ")=", Cell[BoxData[ \(TraditionalForm\`2\^\(d(\[Pi])\)\)]], ".\n\nTo get an explicit expression for d(\[Pi]) for any permutation \[Pi] \ we only need to count how many pairs of cycles are considered. It is easy to \ see that, if \[Pi] is of type ", Cell[BoxData[ \(TraditionalForm\`\(\(1\^x\_1\) 2\^x\_2\ ... \)\ n\^x\_n\)]], ", there are ", Cell[BoxData[ FormBox[ SuperscriptBox[ RowBox[{"(", RowBox[{"\[CapitalSigma]", FormBox[\(x\_i\), "TraditionalForm"]}], ")"}], "2"], TraditionalForm]]], " different pairings. A pairing of a cycle of length h with one of length k \ will contribute to d(\[Pi]) with an amount of GCD(h, k); as there are ", Cell[BoxData[ \(TraditionalForm\`x\_h\)]], " of type h and ", Cell[BoxData[ \(TraditionalForm\`x\_k\)]], " of type k, its local contribution to the grand total will be ", Cell[BoxData[ \(TraditionalForm\`x\_h\)]], Cell[BoxData[ \(TraditionalForm\`x\_k\)]], " GCD(h, k) (Note: as d( (1 2 ... n) ) = n and d( (1)(2) ...(n) ) = ", Cell[BoxData[ \(TraditionalForm\`n\^2\)]], ", we know that n \[LessEqual] d(\[Pi]) \[LessEqual] ", Cell[BoxData[ \(TraditionalForm\`n\^2\)]], " . More generally, if \[Pi] is of type ", Cell[BoxData[ \(TraditionalForm\`i\^a\)]], Cell[BoxData[ \(TraditionalForm\`j\^b\)]], " where ai + bj = n, then d(\[Pi])=", Cell[BoxData[ \(TraditionalForm\`a\^2\)]], " i +2ab GCD(i, j) + ", Cell[BoxData[ \(TraditionalForm\`b\^2\)]], " j). We thus arrive at the following result." }], "Text"], Cell["\<\ Theorem 1. \tThe number of non-isomorphic relations on a set of n elements is \ given by\ \>", "Text", FontWeight->"Bold"], Cell[BoxData[ \(\[Sum]\+\([\[Pi]]\)n \((\[Pi])\) 2\^\(d \((\[Pi])\)\)\)], "Text", TextAlignment->Center, FontWeight->"Bold"], Cell[TextData[{ "where the sum is taken over representatives \[Pi] of the conjugacy classes \ of ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalS]\_n\)]], " having type ", Cell[BoxData[ \(TraditionalForm\`\(\(1\^x\_1\) 2\^x\_2 ... \) n\^x\_n\)]], " and " }], "Text", FontWeight->"Bold"], Cell[BoxData[{ \(d \((\[Pi])\) = \[Sum]\+\(h, k = 1\)\%n\( x\_h\) \(x\_k\) GCD \((h, k)\)\), "\[IndentingNewLine]", \(n \((\[Pi])\) = 1\/\(\(\(x\_1!\) \(1\^x\_1\) \(x\_2!\) 2\^x\_2 ... \)\ \(x\_n!\) \ n\^x\_n\)\)}], "Text", TextAlignment->Center, FontWeight->"Bold"], Cell[TextData[{ "\nThe latter result can be readily implemented. Given a permutation ", StyleBox["per", "Input"], ", functions ", StyleBox["getType", "Input"], ", ", StyleBox["d", "Input"], " and ", StyleBox["n", "Input"], " below compute its type as a weighted vector, ", StyleBox["d[per]", "Input"], " and ", StyleBox["n[per]", "Input"], " from Theorem 1:" }], "Text"], Cell[BoxData[ \(<< DiscreteMath`Combinatorica`\)], "Input", CellLabel->"In[15]:=", InitializationCell->True], Cell[BoxData[{ \(getType[per_] := Module[{t = Table[0, {Length[per]}], c = Map[Length[#] &, ToCycles[ per]]}, \[IndentingNewLine]Map[\(t\[LeftDoubleBracket]#\ \[RightDoubleBracket]++\) &, c]; \[IndentingNewLine]t]\[IndentingNewLine]\), \ "\[IndentingNewLine]", \(d[per_] := Module[{t = getType[per], h, k, n = Length[per]}, \[IndentingNewLine]Sum[ t\[LeftDoubleBracket]h\[RightDoubleBracket]\ t\[LeftDoubleBracket] k\[RightDoubleBracket]\ GCD[h, k], {h, n}, {k, n}]]\[IndentingNewLine]\), "\[IndentingNewLine]", \(n[per_] := Module[{t = getType[per]}, \[IndentingNewLine]1/ Apply[Times, \(t!\)\ \((Range[Length[t]])\)\^t]]\)}], "Input", CellLabel->"In[110]:="], Cell[TextData[{ "For example, to obtain the type of all the permutations comprising ", Cell[BoxData[ \(TraditionalForm\`\[GothicCapitalS]\_3\)]], ": " }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(s3 = Permutations[Range[3]]\), "\[IndentingNewLine]", \(\(getType[#] &\) /@ \ s3\)}], "Input", CellLabel->"In[114]:="], Cell[BoxData[ \({{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}\)], "Output", CellLabel->"Out[114]="], Cell[BoxData[ \({{3, 0, 0}, {1, 1, 0}, {1, 1, 0}, {0, 0, 1}, {0, 0, 1}, {1, 1, 0}}\)], "Output", CellLabel->"Out[115]="] }, Open ]], Cell["\<\ That is, permutation {1, 2, 3} is the product of 3 cycles of length 1, \ permutation {3, 2, 1} is the product of a cycle of length 1 and a cycle of \ length 2, etc. Similarly, we obtain their respective d and n values and \ calculate their contribution to the final sum in theorem 1 as follows:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(n /@ s3\), "\[IndentingNewLine]", \(d /@ s3\), "\[IndentingNewLine]", \(\(n[#]\ 2\^d[#] &\) /@ s3\)}], "Input", CellLabel->"In[116]:="], Cell[BoxData[ \({1\/6, 1\/2, 1\/2, 1\/3, 1\/3, 1\/2}\)], "Output", CellLabel->"Out[116]="], Cell[BoxData[ \({9, 5, 5, 3, 3, 5}\)], "Output", CellLabel->"Out[117]="], Cell[BoxData[ \({256\/3, 16, 16, 8\/3, 8\/3, 16}\)], "Output", CellLabel->"Out[118]="] }, Open ]], Cell[TextData[{ "Finally, to implement the full expression we need to add only those values \ in the last of the vectors above corresponding to class representatives, \ which in this case occupy the first, second and fourth positions, providing \ the answer 104 to the question of how many non-isomorphic relations on a set \ of 3 elements do exist in the latter example. In general, this value can be \ computed by just adding those corresponding to permutations of different \ types. In the code below, this mechanism is implemented in the Do block, \ which relies on the Mathematica function ", StyleBox["Union", "Input"], " to remove repeated elements thereafter." }], "Text"], Cell[BoxData[ \(numRelations[m_] := Module[{p = Permutations[Range[m]], t, i, q}, \[IndentingNewLine]t = \(getType[#] &\) /@ p; \[IndentingNewLine]Do[\[IndentingNewLine]If[ MemberQ[Take[t, i - 1], t\[LeftDoubleBracket]i\[RightDoubleBracket]], p\[LeftDoubleBracket]i\[RightDoubleBracket] = First[p]], {i, 2, \(m!\)}]; \[IndentingNewLine]p = Union[p]; \[IndentingNewLine]Plus\ @@ \ Map[n[#]\ 2\^d[#] &, p]]\)], "Input", CellLabel->"In[119]:="], Cell[CellGroupData[{ Cell[BoxData[ \(numRelations[3]\)], "Input", CellLabel->"In[120]:="], Cell[BoxData[ \(104\)], "Output", CellLabel->"Out[120]="] }, Open ]], Cell["\<\ Although this implementation of theorem 1 is adequate, it is time-consuming. \ We can produce a more satisfactory design by removing the overhead caused by \ generating all permutations in order to select representatives of conjugacy \ classes. This optimization arises from first solving the following problem:\ \>", "Text"], Cell["\<\ To obtain all the solutions in non-negative integers of the equation:\ \>", "Text", TextAlignment->Center], Cell[BoxData[ \(\(x\_1 + 2 x\_2 + \ ... \)\ + \ n\ x\_n = m\)], "Text", TextAlignment->Center], Cell["where n and m are two given non-negative integers.", "Text", TextAlignment->Center], Cell["The function that computationally solves this problem is:", "Text"], Cell[BoxData[{ \(generate[1, m_] := {{m}}\), "\[IndentingNewLine]", \(generate[n_, m_] := Module[{i, s = {}}, Do[s = Join[s, Map[Append[#, i] &, generate[n - 1, m - n\ i]]], {i, 0, \[LeftFloor]m/ n\[RightFloor]}]; \[IndentingNewLine]s]\)}], "Input", CellLabel->"In[33]:="], Cell[TextData[{ "For instance, to find out the solutions to the Diophantine equation ", Cell[BoxData[ \(TraditionalForm\`x\_1\)]], "+2", Cell[BoxData[ \(TraditionalForm\`x\_2\)]], "+3", Cell[BoxData[ \(TraditionalForm\`x\_3\)]], "+4", Cell[BoxData[ \(TraditionalForm\`x\_4\)]], "+5", Cell[BoxData[ \(TraditionalForm\`x\_5\)]], "=5:" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(generate[5, 5]\)], "Input", CellLabel->"In[35]:="], Cell[BoxData[ \({{5, 0, 0, 0, 0}, {3, 1, 0, 0, 0}, {1, 2, 0, 0, 0}, {2, 0, 1, 0, 0}, {0, 1, 1, 0, 0}, {1, 0, 0, 1, 0}, {0, 0, 0, 0, 1}}\)], "Output", CellLabel->"Out[35]="] }, Open ]], Cell["\<\ Note: we could also have used the following non-recursive method for the case \ n=m:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(f[d_, m_] := Module[{s = Table[0, {m}]}, Map[\(s\[LeftDoubleBracket]#\[RightDoubleBracket]++\) &, d]; s]\[IndentingNewLine]\), "\[IndentingNewLine]", \(buildTypes[m_] := \(\(\(f[#, m] &\)\ /@ \ Partitions[m]\)\(\[IndentingNewLine]\)\)\), "\[IndentingNewLine]", \(buildTypes[5]\)}], "Input", CellLabel->"In[16]:=", InitializationCell->True], Cell[BoxData[ \({{0, 0, 0, 0, 1}, {1, 0, 0, 1, 0}, {0, 1, 1, 0, 0}, {2, 0, 1, 0, 0}, {1, 2, 0, 0, 0}, {3, 1, 0, 0, 0}, {5, 0, 0, 0, 0}}\)], "Output", CellLabel->"Out[18]="] }, Open ]], Cell[TextData[{ "Function ", StyleBox["numRel", "Input"], " below makes use of such vectors as descriptions of the types of \ representatives of conjugate classes and improves substantially on the \ straighforward approach adopted in our previous design of function ", StyleBox["numRelations.", "Input"] }], "Text"], Cell[BoxData[{ \(d[t_] := Module[{h, k, n = Length[t]}, \[IndentingNewLine]Sum[ t\[LeftDoubleBracket]h\[RightDoubleBracket]\ t\[LeftDoubleBracket] k\[RightDoubleBracket]\ GCD[h, k], {h, n}, {k, n}]]\[IndentingNewLine]\), "\[IndentingNewLine]", \(n[t_] := \(\(1/ Apply[Times, \(t!\)\ \ \((Range[Length[t]])\)\^t]\)\(\[IndentingNewLine]\)\)\), \ "\[IndentingNewLine]", \(numRel[m_] := Module[{g = buildTypes[ m]}, \[IndentingNewLine]Plus\ @@ \ \((\((n /@ \ g)\)\ 2\^\((d\ /@ \ g)\))\)]\)}], "Input", CellLabel->"In[19]:=", InitializationCell->True], Cell["\<\ Finally, a table comparing the first ten values of the total number of \ relations and the total number of non-isomorphic relations can be obtained \ through the following:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[{i, 2\^\(i\^2\), numRel[i]}, {i, 8}] // TableForm\)], "Input", CellLabel->"In[163]:="], Cell[BoxData[ TagBox[GridBox[{ {"1", "2", "2"}, {"2", "16", "10"}, {"3", "512", "104"}, {"4", "65536", "3044"}, {"5", "33554432", "291968"}, {"6", "68719476736", "96928992"}, {"7", "562949953421312", "112282908928"}, {"8", "18446744073709551616", "458297100061728"} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], (TableForm[ #]&)]], "Output", CellLabel->"Out[163]//TableForm="] }, Open ]], Cell["(See sequence A000595 in [8])", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Reflexive and Symmetric Relations", "Subsection"], Cell[TextData[{ "\tLet us now specialise Burnside\[CloseCurlyQuote]s theorem firstly to the \ counting of non-isomorphic reflexive relations and subsequently to \ non-isomorphic symmetric relations. The result is contained in the following \ theorem.\n\n", StyleBox["Theorem 2\tThe number of non-isomorphic reflexive relations on an \ n-set is given by ", FontWeight->"Bold"] }], "Text"], Cell[BoxData[ \(\[Sum]\+\([\[Pi]]\)n \((\[Pi])\) 2\^\(d\.b4 \((\[Pi])\)\)\)], "Text", TextAlignment->Center, FontWeight->"Bold"], Cell[TextData[{ StyleBox["where d\.b4(\[Pi])=d(\[Pi])-", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`\[Sum]\+\(k = 1\)\%n x\_k\)], FontWeight->"Bold"], StyleBox[", with n(\[Pi]) and d(\[Pi]) as in theorem 1.", FontWeight->"Bold"], "\n \nProof:\tIn a reflexive relation, all diagonal elements ", Cell[BoxData[ \(TraditionalForm\`a\_\(i, \ i\)\)]], " are equal to unity. Also, the diagonal elements are always permuted among \ themselves by every ", Cell[BoxData[ \(TraditionalForm\`\[GothicT]\_\[Pi]\)]], ". Hence, the number of degrees of freedom is equal to the number of cycles \ in \[Pi], that is, \[CapitalSigma]", Cell[BoxData[ \(TraditionalForm\`x\_k\)]], ". \[Square]\t\t" }], "Text"], Cell[BoxData[ \(numRelReflexive[m_] := Module[{g = buildTypes[ m]}, \[IndentingNewLine]Plus\ @@ \((\((n /@ g)\)\ 2\^\(\((d /@ g)\) - \((\(\((Plus\ @@ #)\) &\) /@ \ g)\)\))\)]\)], "Input", CellLabel->"In[171]:="], Cell[CellGroupData[{ Cell[BoxData[ \(Table[{i, 2\^\(i \((i - 1)\)\), numRelReflexive[i]}, {i, 8}] // TableForm\)], "Input", CellLabel->"In[173]:="], Cell[BoxData[ TagBox[GridBox[{ {"1", "1", "1"}, {"2", "4", "3"}, {"3", "64", "16"}, {"4", "4096", "218"}, {"5", "1048576", "9608"}, {"6", "1073741824", "1540944"}, {"7", "4398046511104", "882033440"}, {"8", "72057594037927936", "1793359192848"} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], (TableForm[ #]&)]], "Output", CellLabel->"Out[173]//TableForm="] }, Open ]], Cell["(See sequence A000273 in[8])", "Text"], Cell[TextData[{ "Note that the number of non-isomorphic reflexive relations coincide with \ that for irreflexive relations, i.e., those for which all diagonal elements \ of the associated matrix are null.\n\nLet us now approach the problem of \ finding out how many non-isomorphic symmetric relations can be defined on an \ n-set. Concerning example 1, our new condition implies a reduction in the \ degrees of freedom of the matrix A because symmetry implies ", Cell[BoxData[ \(TraditionalForm\`A\_2\)]], "= ", Cell[BoxData[ \(TraditionalForm\`A\_3\)]], ", B = D, C = G and F = H, and hence, its degrees of freedom reduce to 12-4 \ = 8 and Fix(", Cell[BoxData[ \(TraditionalForm\`\[GothicT]\_\(\((1\ 2\ 4)\) \((3)\) \((5\ \ 6)\)\)\)]], ") = ", Cell[BoxData[ \(TraditionalForm\`2\^8\)]], "." }], "Text"], Cell[CellGroupData[{ Cell["Example 2", "Subsubsection"], Cell[TextData[{ "\tLet us compute d(\[Pi]) for \[Pi]=(1)(2 3)(4 5)(6) for an arbitrary \ matrix 6 \[Times] 6. All possible pairings of cycles follow the pattern \ described in Figure 4, inducing the subdivision of A shown therein, where \ elements of the same tag must coincide. The results are summarised in Table \ 2. Then, the degree of freedom of A is d(\[Pi])=20. If symmetry is \ considered, we will have: B = E, C = I, D =M, ", Cell[BoxData[ \(TraditionalForm\`J\_1\)]], " = ", Cell[BoxData[ \(TraditionalForm\`G\_1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`J\_2\)]], " = ", Cell[BoxData[ \(TraditionalForm\`G\_2\)]], ", H = N and L =O." }], "Text"], Cell[BoxData[GridBox[{ {\(Identification\[IndentingNewLine] Tag\), \(Cycle\ Pair\), \(Equalities\ \[IndentingNewLine] implied\ by\ \((2)\)\), \(Degree\ \[IndentingNewLine] of\ Freedom\)}, {"A", \(\((1)\) \((1)\)\), \(x\_\(1, 1\)\), "1"}, {"B", \(\((1)\) \((2\ 3)\)\), \(x\_\(1, 2\) = x\_\(1, 3\)\), "1"}, {"C", \(\((1)\) \((4\ 5)\)\), \(x\_\(1, 4\) = x\_\(1, 5\)\), "1"}, {"D", \(\((1)\) \((6)\)\), \(x\_\(1, 6\)\), "1"}, {"E", \(\((2\ 3)\) \((1)\)\), \(x\_\(2, 1\) = x\_\(3, 1\)\), "1"}, {"F", \(\((2\ 3)\) \((2\ 3)\)\), \(x\_\(2, 2\) = x\_\(3, 3\)\[IndentingNewLine] x\_\(2, 3\) = x\_\(3, 2\)\), "2"}, {"G", \(\((2\ 3)\) \((4\ 5)\)\), \(x\_\(5, 4\) = x\_\(3, 5\)\[IndentingNewLine] x\_\(2, 5\) = x\_\(3, 4\)\), "2"}, {"H", \(\((2\ 3)\) \((6)\)\), \(x\_\(2, 6\) = x\_\(3, 6\)\), "1"}, {"I", \(\((4\ 5)\) \((1)\)\), \(x\_\(4, 1\) = x\_\(5, 1\)\), "1"}, {"J", \(\((4\ 5)\) \((2\ 3)\)\), \(x\_\(4, 2\) = x\_\(5, 3\)\[IndentingNewLine] x\_\(4, 3\) = x\_\(5, 2\)\), "2"}, {"K", \(\((4\ 5)\) \((4\ 5)\)\), \(x\_\(4, 4\) = x\_\(5, 5\)\[IndentingNewLine] x\_\(4, 5\) = x\_\(5, 4\)\), "2"}, {"L", \(\((4\ 5)\) \((6)\)\), \(x\_\(4, 6\) = x\_\(5, 6\)\), "1"}, {"M", \(\((6)\) \((1)\)\), \(x\_\(6, 1\)\), "1"}, {"N", \(\((6)\) \((2\ 3)\)\), \(x\_\(6, 2\) = x\_\(6, 3\)\), "1"}, {"O", \(\((6)\) \((4\ 5)\)\), \(x\_\(6, 4\) = x\_\(6, 5\)\), "1"}, {"P", \(\((6)\) \((6)\)\), \(x\_\(6, 6\)\), "1"} }]], "NumberedTable", TextAlignment->Center], Cell[TextData[{ "We sum up our results in the following theorem.\n\n", StyleBox["Theorem 3\tThe number of non-isomorphic symmetric relations on an \ n-set is given by", FontWeight->"Bold"] }], "Text"], Cell[TextData[{ StyleBox["sym(n)=", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`\[Sum]\+\([\[Pi]]\)\(n(\[Pi])\) 2\^\(dsym(\[Pi])\)\)], FontWeight->"Bold"] }], "Text", TextAlignment->Center], Cell[TextData[StyleBox["where ", FontWeight->"Bold"]], "Text"], Cell[BoxData[ \(dsym \((\[Pi])\) = \[Sum]\+\(h = 1\)\%n\( x\_h\) \((\[LeftFloor]h\/2\[RightFloor] + 1)\) + \[Sum]\+\(h = 1\)\%n\( x\_h\) \(h \((x\_h - 1)\)\)\/2 + \[Sum]\+\(h < k\)\(x\_h\) x\_k\ GCD \((h, k)\)\)], "Text", TextAlignment->Center, FontWeight->"Bold"], Cell[TextData[{ StyleBox["and n(\[Pi]) is as in theorem 1.", FontWeight->"Bold"], "\n\nLet us classify the blocks ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], " induced by the pairing of the cycles as diagonal or non-diagonal \ according to whether they contain elements of the main diagonal of A or not. \ (In example 2, F is a diagonal block whereas G and B are not; in example 1, \ blocks A and E are diagonal (the fact that A is disconnected makes no \ difference) while B and C are not.\n\nNon-diagonal blocks subdivide further \ into squares and non-square ones. In example 2, block G is square and H is \ not; in example 1, block C is square while F is not.\n\nNon-diagonal blocks \ fall into transpose pairs; symmetry thus makes no change in d(\[Pi]) within \ each block but since every one determines its reflection, the d(\[Pi]) for \ all of these can be determined from half of them, say those below the \ diagonal. The third sum counts the non-square ones below the diagonal.\n\nA \ diagonal block has its rows and columns permuted by the same h-cycle and will \ have h degrees of freedom. " }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Example 3", "Subsubsection"], Cell["\<\ For the permutation (1 2 3 4 5)(1 2 3 4 5) the block has the form\ \>", "Text"], Cell[BoxData[ RowBox[{"(", GridBox[{ {\(A\_1\), \(A\_2\), \(A\_3\), \(A\_4\), \(A\_5\)}, {\(A\_5\), \(A\_1\), \(A\_2\), \(A\_3\), \(A\_4\)}, {\(A\_4\), \(A\_5\), \(A\_1\), \(A\_2\), \(A\_3\)}, {\(A\_3\), \(A\_4\), \(A\_5\), \(A\_1\), \(A\_2\)}, {\(A\_2\), \(A\_3\), \(A\_4\), \(A\_5\), \(A\_1\)} }], ")"}]], "Text", TextAlignment->Center], Cell[TextData[{ "and symmetry implies that ", Cell[BoxData[ \(TraditionalForm\`A\_2\)]], "=", Cell[BoxData[ \(TraditionalForm\`A\_5\)]], " and ", Cell[BoxData[ \(TraditionalForm\`A\_3\)]], "=", Cell[BoxData[ \(TraditionalForm\`A\_4\)]], ". \n\nIn general, the symmetry property will reduce their h degrees of \ freedom to d(\[Pi]) = \[LeftFloor]h/2\[RightFloor] + 1. There are ", Cell[BoxData[ \(TraditionalForm\`x\_h\)]], " of them, hence the first sum in theorem 3. Since, for each value of h the \ non-diagonal square blocks have h degrees of freedom and there are ", Cell[BoxData[ \(TraditionalForm\`\(\(x\_h\)(x\_h - 1)\)/2\)]], " of them, the second sum accounts for it. For instance, we dissect \ example 2 at Figure 4. Note that the same result is obtained by applying the \ induced symmetry conditions B=E, C=I, D=M, ", Cell[BoxData[ \(TraditionalForm\`J\_1\)]], "=", Cell[BoxData[ \(TraditionalForm\`G\_1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`J\_2\)]], "=", Cell[BoxData[ \(TraditionalForm\`G\_2\)]], ", H=N and L=O.\n\nAlso, in example 1:" }], "Text"], Cell[BoxData[ \(dsym \((\((1\ 4\ 2)\) \((3)\) \((5\ 6)\))\) = \(\([\(x\_1\) \((1)\) + \ \(x\_2\) \((2)\) + \(x\_3\) \((2)\)]\) + \[IndentingNewLine]\([\(\(x\_1\) \ \((x\_1 - 1)\)\)\/2 + \(x\_2\) \((x\_2 - 1)\) + \(x\_3\) \(3 \((x\_3 - 1)\)\)\/2]\) + \ \[IndentingNewLine]\([\(x\_1\) \(x\_2\) GCD \((1, 2)\) + \(x\_1\) \(x\_3\) GCD \((1, 3)\) + \(x\_2\) \(x\_3\) GCD \((2, 3)\)]\) = \(5 + 0 + 3 = 8\)\)\)], "Text", TextAlignment->Left], Cell[TextData[{ "Finally, the following code implements function ", StyleBox["dSym", "Input"], " referred to in theorem 3." }], "Text"], Cell[BoxData[{ \(dSym[per_] := Module[{h, k, n = Length[per]}, Sum[per\[LeftDoubleBracket]h\[RightDoubleBracket]\ \((\[LeftFloor]h/ 2\[RightFloor] + 1)\), {h, n}] + Sum[per\[LeftDoubleBracket] h\[RightDoubleBracket]\ h\ \((per\[LeftDoubleBracket] h\[RightDoubleBracket] - 1)\)/2, {h, n}] + Sum[per\[LeftDoubleBracket] h\[RightDoubleBracket]\ per\[LeftDoubleBracket] k\[RightDoubleBracket]\ GCD[h, k], {h, n}, {k, h + 1, n}]]\[IndentingNewLine]\), "\n", \(numRelSym[m_] := Module[{g = buildTypes[ m]}, \[IndentingNewLine]Plus\ @@ \((\((n /@ g)\)\ 2\^dSym /@ g)\)]\)}], "Input", CellLabel->"In[175]:="], Cell[CellGroupData[{ Cell[BoxData[ \(Table[{i, 2\^\(\(i \((i + 1)\)\)\/2\), numRelSym[i]}, {i, 8}] // TableForm\)], "Input", CellLabel->"In[178]:="], Cell[BoxData[ TagBox[GridBox[{ {"1", "2", "2"}, {"2", "8", "6"}, {"3", "64", "20"}, {"4", "1024", "90"}, {"5", "32768", "544"}, {"6", "2097152", "5096"}, {"7", "268435456", "79264"}, {"8", "68719476736", "2208612"} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], (TableForm[ #]&)]], "Output", CellLabel->"Out[178]//TableForm="] }, Open ]], Cell["(See sequence A000666 in[8])", "Text"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell["Functions", "Subsection"], Cell[TextData[{ "\tAs our final case study, we will proceed with the counting of \ non-isomorphic functions. Let A be the matrix of a given function, i.e., \ having only one digit 1 in each row. We want to find out how many of the ", Cell[BoxData[ \(TraditionalForm\`n\^n\)]], " functions mapping the set {1, ..., n} to itself are non-isomorphic." }], "Text"], Cell[TextData[{ StyleBox["Lemma\t\tIf ", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`A\_0\)], FontWeight->"Bold"], StyleBox[" is a d \[Times] k block under of the functional matrix A then\n\ \n1) If k is not a factor of d, ", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`A\_0\)], FontWeight->"Bold"], StyleBox[" consists entirely of zeroes\n\n2) If k is a factor of d, ", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`A\_0\)], FontWeight->"Bold"], StyleBox[" has d 1's or none. Moreover, there are k different ways in which \ d 1's can be chosen in ", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`A\_0\)], FontWeight->"Bold"], StyleBox[".", FontWeight->"Bold"] }], "Text"], Cell[TextData[{ "Proof:\tCASE 1. If k is not a factor of d, then LCM(d, k)>d so that, if ", Cell[BoxData[ \(TraditionalForm\`a\_\(i, j\)\)]], "=1 then there is a distinct entry in the i-th row, namely ", Cell[BoxData[ \(TraditionalForm\`a\_\(i + d, \ j + d\)\)]], " which is also 1, contradicting the assumption that A is a function.\nFor \ instance, if \[Pi]=(1 4 2)(3)(5 6) and ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], " is the block corresponding to the cycles (1 4 2) and (5 6), ", Cell[BoxData[ \(TraditionalForm\`t\_\[Pi]\)]], "(A)=A , which means that all elements of ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], " must be the same.\nCASE 2. If k is a factor of d, any one of the k \ elements of the d-th row can be chosen to take the value 1 and this choice \ determines all k 1's of the block.\t\[EmptySquare]" }], "Text"], Cell[TextData[{ "For instance, if \[Pi]=(1 2 3 4)(5 6), ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], "=", Cell[BoxData[ RowBox[{"(", GridBox[{ {"x", "y"}, {"y", "x"}, {"x", "y"}, {"y", "x"} }], ")"}]]], " and, if \[Pi]=(1 2 3 4 5 6)(7 8 9), ", Cell[BoxData[ \(TraditionalForm\`A\_0\)]], "=", Cell[BoxData[ RowBox[{"(", GridBox[{ {"x", "y", "z"}, {"z", "x", "y"}, {"y", "z", "x"}, {"x", "y", "z"}, {"z", "x", "y"}, {"y", "z", "x"} }], ")"}]]] }], "Text"], Cell[TextData[{ StyleBox["Theorem 4", FontWeight->"Bold"], "\tThe number of non-isomorphic functions from a set of n elements to \ itself is given by:\n\t" }], "Text", FontWeight->"Bold"], Cell[BoxData[ \(fun \((n)\) = \[Sum]\+\([\[Pi]]\)n \((\[Pi])\) Fix \((\[GothicT]\_\[Pi])\)\)], "Text", TextAlignment->Center, FontWeight->"Bold"], Cell[TextData[{ "where Fix(", Cell[BoxData[ \(TraditionalForm\`t\_\[Pi]\)]], ")=", Cell[BoxData[ \(TraditionalForm\`\[Product]\+\(k = 1\)\%n\((\[Sum]\+\(h | k\)h\ x\_h)\ \)\^x\_k\)]], " and n(\[Pi]) is as in theorem 1." }], "Text", TextAlignment->Left, FontWeight->"Bold"], Cell["\<\ Proof:\tThe different possible ways of choosing the 1's in the matrix A can \ be counted in terms of horizontal bands across A corresponding to the cycles \ of as shown in Figure 6. \[EmptySquare]\ \>", "Text"], Cell[TextData[{ "The previous theorem establishes that, for each k-cycle of the ", Cell[BoxData[ \(TraditionalForm\`x\_k\)]], " present, there will be ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\+\(h | k\)h\ x\_h\)]], " ways of choosing the 1's. For instance, in example 1, blocks A and B have \ together 4 ways of choosing the 1's as k=3 and 1", Cell[BoxData[ \(TraditionalForm\`x\_1\)]], "+3", Cell[BoxData[ \(TraditionalForm\`x\_3\)]], " = 4.\nIndependence of the choices in different bands determines the \ result. \n\nExample 4.\tIn example 1, the function property forces the matrix \ A to be of the form " }], "Text"], Cell[BoxData[ RowBox[{"(", GridBox[{ {\(A\_1\), \(A\_3\), "B", \(A\_2\), "0", "0"}, {\(A\_2\), \(A\_1\), "B", \(A\_3\), "0", "0"}, {"0", "0", "1", "0", "0", "0"}, {\(A\_3\), \(A\_2\), "B", \(A\_1\), "0", "0"}, {"0", "0", "H", "0", \(I\_1\), \(I\_2\)}, {"0", "0", "H", "0", \(I\_2\), \(I\_1\)} }], ")"}]], "Input", TextAlignment->Center], Cell[BoxData[ \(and\ Fix \((t\_\[Pi])\) = 12\ as\ shown\ in\ Figure\ 7. \)], "Text"], Cell[BoxData[{ \(fix[per_] := Module[{p = 1, s, h, k}, \[IndentingNewLine]Do[ s = 0; \[IndentingNewLine]Do[ If[Mod[k, h] \[Equal] 0, s = s + h*per\[LeftDoubleBracket]h\[RightDoubleBracket]], {h, k}]; \[IndentingNewLine]If[ per\[LeftDoubleBracket]k\[RightDoubleBracket] \[Equal] 0, , p = p\ s\^per\[LeftDoubleBracket]k\[RightDoubleBracket]], {k, Length[per]}]; \ \[IndentingNewLine]p]\[IndentingNewLine]\), "\ \[IndentingNewLine]", \(numFun[m_] := Module[{g = buildTypes[ m]}, \[IndentingNewLine]Plus\ @@ \((\((n /@ g)\)\ \((fix /@ g)\))\)]\)}], "Input", CellLabel->"In[182]:="], Cell[CellGroupData[{ Cell[BoxData[ \(Table[{i, i\^i, numFun[i]}, {i, 8}] // TableForm\)], "Input", CellLabel->"In[185]:="], Cell[BoxData[ TagBox[GridBox[{ {"1", "1", "1"}, {"2", "4", "3"}, {"3", "27", "7"}, {"4", "256", "19"}, {"5", "3125", "47"}, {"6", "46656", "130"}, {"7", "823543", "343"}, {"8", "16777216", "951"} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], (TableForm[ #]&)]], "Output", CellLabel->"Out[185]//TableForm="] }, Open ]], Cell["(See sequence A001372 in[8])", "Text"] }, Closed]] }, Open ]] }, Open ]] }, FrontEndVersion->"4.0 for Microsoft Windows", ScreenRectangle->{{0, 1152}, {0, 817}}, AutoGeneratedPackage->Automatic, WindowToolbars->"EditBar", WindowSize->{747, 742}, WindowMargins->{{80, Automatic}, {Automatic, 6}}, Magnification->1, StyleDefinitions -> "ArticleClassic.nb" ] (*********************************************************************** Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. ***********************************************************************) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1739, 51, 30, 0, 72, "Title"], Cell[1772, 53, 95, 2, 41, "Author"], Cell[1870, 57, 167, 7, 72, "Address"], Cell[2040, 66, 274, 5, 34, "Reference"], Cell[2317, 73, 732, 11, 124, "Abstract"], Cell[3052, 86, 1075, 24, 234, "Caption"], Cell[CellGroupData[{ Cell[4152, 114, 29, 0, 56, "Section"], Cell[4184, 116, 32407, 533, 101, 32316, 530, "GraphicsData", "Bitmap", \ "Graphics"], Cell[36594, 651, 840, 33, 484, "Reference"] }, Open ]], Cell[CellGroupData[{ Cell[37471, 689, 36, 0, 62, "SectionFirst"], Cell[37510, 691, 1752, 28, 265, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[39299, 724, 36, 0, 56, "Section"], Cell[39338, 726, 466, 14, 45, "Text"], Cell[39807, 742, 231, 5, 35, "Input", InitializationCell->True], Cell[CellGroupData[{ Cell[40063, 751, 110, 2, 31, "Input"], Cell[40176, 755, 3205, 99, 75, "Output"] }, Open ]], Cell[43396, 857, 281, 8, 44, "Text"], Cell[CellGroupData[{ Cell[43702, 869, 79, 1, 31, "Input"], Cell[43784, 872, 53, 1, 30, "Output"] }, Open ]], Cell[43852, 876, 64, 0, 27, "Text"], Cell[CellGroupData[{ Cell[43941, 880, 51, 1, 34, "Input"], Cell[43995, 883, 93, 1, 30, "Output"] }, Open ]], Cell[44103, 887, 440, 11, 44, "Text"], Cell[CellGroupData[{ Cell[44568, 902, 39, 0, 43, "Subsection"], Cell[44610, 904, 247, 4, 44, "Text"], Cell[44860, 910, 2408, 48, 631, "Input", InitializationCell->True], Cell[CellGroupData[{ Cell[47293, 962, 48, 0, 33, "Subsubsection"], Cell[CellGroupData[{ Cell[47366, 966, 120, 2, 31, "Input"], Cell[47489, 970, 50, 1, 30, "Output"] }, Open ]], Cell[47554, 974, 95, 2, 27, "Text"], Cell[CellGroupData[{ Cell[47674, 980, 67, 1, 31, "Input"], Cell[47744, 983, 86, 1, 30, "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell[47879, 990, 48, 0, 25, "Subsubsection"], Cell[CellGroupData[{ Cell[47952, 994, 120, 2, 31, "Input"], Cell[48075, 998, 50, 1, 30, "Output"] }, Open ]], Cell[48140, 1002, 69, 0, 27, "Text"], Cell[CellGroupData[{ Cell[48234, 1006, 74, 1, 38, "Input"], Cell[48311, 1009, 77, 1, 30, "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell[48437, 1016, 49, 0, 25, "Subsubsection"], Cell[CellGroupData[{ Cell[48511, 1020, 121, 2, 31, "Input"], Cell[48635, 1024, 52, 1, 30, "Output"] }, Open ]], Cell[48702, 1028, 41, 0, 27, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[48780, 1033, 50, 0, 25, "Subsubsection"], Cell[CellGroupData[{ Cell[48855, 1037, 122, 2, 31, "Input"], Cell[48980, 1041, 47, 1, 30, "Output"] }, Open ]], Cell[49042, 1045, 41, 0, 27, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[49120, 1050, 35, 0, 25, "Subsubsection"], Cell[CellGroupData[{ Cell[49180, 1054, 116, 2, 31, "Input"], Cell[49299, 1058, 47, 1, 30, "Output"] }, Open ]], Cell[49361, 1062, 64, 0, 27, "Text"], Cell[CellGroupData[{ Cell[49450, 1066, 74, 1, 38, "Input"], Cell[49527, 1069, 69, 1, 30, "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell[49645, 1076, 53, 0, 25, "Subsubsection"], Cell[CellGroupData[{ Cell[49723, 1080, 135, 3, 31, "Input"], Cell[49861, 1085, 53, 1, 30, "Output"] }, Open ]], Cell[49929, 1089, 111, 3, 27, "Text"], Cell[50043, 1094, 179, 4, 51, "Input"], Cell[CellGroupData[{ Cell[50247, 1102, 115, 2, 31, "Input"], Cell[50365, 1106, 53, 1, 30, "Output"] }, Open ]], Cell[50433, 1110, 43, 0, 27, "Text"], Cell[CellGroupData[{ Cell[50501, 1114, 90, 1, 38, "Input"], Cell[50594, 1117, 88, 1, 30, "Output"] }, Open ]], Cell[50697, 1121, 46, 0, 27, "Text"], Cell[CellGroupData[{ Cell[50768, 1125, 147, 3, 31, "Input"], Cell[50918, 1130, 52, 1, 30, "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell[51019, 1137, 43, 0, 25, "Subsubsection"], Cell[CellGroupData[{ Cell[51087, 1141, 134, 3, 31, "Input"], Cell[51224, 1146, 49, 1, 30, "Output"] }, Open ]], Cell[51288, 1150, 41, 0, 27, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[51366, 1155, 41, 0, 25, "Subsubsection"], Cell[CellGroupData[{ Cell[51432, 1159, 121, 2, 31, "Input"], Cell[51556, 1163, 47, 1, 30, "Output"] }, Open ]], Cell[51618, 1167, 34, 0, 27, "Text"], Cell[CellGroupData[{ Cell[51677, 1171, 46, 1, 31, "Input"], Cell[51726, 1174, 63, 1, 30, "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell[51838, 1181, 37, 0, 25, "Subsubsection"], Cell[CellGroupData[{ Cell[51900, 1185, 118, 2, 31, "Input"], Cell[52021, 1189, 47, 1, 30, "Output"] }, Open ]], Cell[52083, 1193, 41, 0, 27, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[52161, 1198, 41, 0, 25, "Subsubsection"], Cell[52205, 1200, 140, 3, 27, "Text"], Cell[CellGroupData[{ Cell[52370, 1207, 163, 3, 31, "Input"], Cell[52536, 1212, 47, 1, 30, "Output"] }, Open ]], Cell[52598, 1216, 38, 0, 27, "Text"], Cell[CellGroupData[{ Cell[52661, 1220, 44, 1, 31, "Input"], Cell[52708, 1223, 60, 1, 30, "Output"] }, Open ]], Cell[52783, 1227, 44, 0, 27, "Text"], Cell[CellGroupData[{ Cell[52852, 1231, 187, 4, 51, "Input"], Cell[53042, 1237, 46, 1, 30, "Output"] }, Open ]], Cell[53103, 1241, 122, 3, 27, "Text"], Cell[CellGroupData[{ Cell[53250, 1248, 227, 5, 71, "Input"], Cell[53480, 1255, 818, 15, 170, "Output"] }, Open ]], Cell[54313, 1273, 60, 0, 27, "Text"], Cell[CellGroupData[{ Cell[54398, 1277, 211, 5, 71, "Input"], Cell[54612, 1284, 117181, 1877, 296, 6439, 505, "GraphicsData", "PostScript", \ "Graphics"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell[171842, 3167, 32, 0, 25, "Subsubsection"], Cell[CellGroupData[{ Cell[171899, 3171, 2820, 76, 411, "Input"], Cell[174722, 3249, 350, 8, 25, "Print"], Cell[175075, 3259, 654, 17, 69, "Print"], Cell[175732, 3278, 654, 17, 69, "Print"], Cell[176389, 3297, 656, 17, 69, "Print"], Cell[177048, 3316, 654, 17, 69, "Print"], Cell[177705, 3335, 642, 17, 69, "Print"], Cell[178350, 3354, 664, 17, 69, "Print"], Cell[179017, 3373, 660, 17, 69, "Print"], Cell[179680, 3392, 654, 17, 69, "Print"], Cell[180337, 3411, 646, 17, 69, "Print"] }, Open ]], Cell[180998, 3431, 561, 12, 61, "Text"], Cell[181562, 3445, 247, 4, 71, "Input"], Cell[CellGroupData[{ Cell[181834, 3453, 341, 7, 71, "Input"], Cell[182178, 3462, 1753, 23, 334, "Output"] }, Open ]], Cell[183946, 3488, 413, 8, 61, "Text"], Cell[CellGroupData[{ Cell[184384, 3500, 196, 4, 52, "Input"], Cell[184583, 3506, 1384, 18, 277, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[186004, 3529, 86, 1, 31, "Input"], Cell[186093, 3532, 39, 1, 30, "Output"] }, Open ]], Cell[186147, 3536, 128, 3, 27, "Text"] }, Closed]] }, Open ]], Cell[CellGroupData[{ Cell[186324, 3545, 62, 0, 43, "Subsection"], Cell[186389, 3547, 462, 7, 78, "Text"], Cell[CellGroupData[{ Cell[186876, 3558, 210, 4, 31, "Input"], Cell[187089, 3564, 49, 1, 30, "Output"] }, Open ]], Cell[187153, 3568, 41, 0, 27, "Text"], Cell[187197, 3570, 204, 5, 28, "Text"], Cell[187404, 3577, 538, 10, 171, "Input"], Cell[CellGroupData[{ Cell[187967, 3591, 73, 1, 31, "Input"], Cell[188043, 3594, 90, 1, 30, "Output"] }, Open ]], Cell[188148, 3598, 199, 6, 28, "Text"], Cell[188350, 3606, 1119, 21, 291, "Input"], Cell[CellGroupData[{ Cell[189494, 3631, 55, 1, 31, "Input"], Cell[189552, 3634, 6724, 198, 217, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[196313, 3837, 76, 1, 31, "Input"], Cell[196392, 3840, 85, 1, 30, "Output"] }, Open ]], Cell[196492, 3844, 74, 0, 27, "Text"], Cell[196569, 3846, 59, 0, 27, "Text"], Cell[CellGroupData[{ Cell[196653, 3850, 88, 1, 31, "Input"], Cell[196744, 3853, 51, 1, 30, "Output"] }, Open ]], Cell[196810, 3857, 52, 0, 27, "Text"], Cell[CellGroupData[{ Cell[196887, 3861, 92, 1, 31, "Input"], Cell[196982, 3864, 55, 1, 30, "Output"] }, Open ]], Cell[197052, 3868, 102, 3, 27, "Text"], Cell[CellGroupData[{ Cell[197179, 3875, 136, 3, 31, "Input"], Cell[197318, 3880, 49, 1, 30, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[197404, 3886, 39, 0, 33, "Subsubsection"], Cell[197446, 3888, 965, 18, 97, "Text"], Cell[198414, 3908, 679, 13, 196, "Input"], Cell[CellGroupData[{ Cell[199118, 3925, 69, 1, 31, "Input"], Cell[199190, 3928, 82, 1, 30, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[199309, 3934, 106, 2, 31, "Input"], Cell[199418, 3938, 879, 16, 170, "Output"] }, Open ]], Cell[200312, 3957, 251, 6, 61, "Text"], Cell[200566, 3965, 404, 7, 111, "Input"], Cell[CellGroupData[{ Cell[200995, 3976, 40, 1, 31, "Input"], Cell[201038, 3979, 373, 6, 87, "Output"] }, Open ]], Cell[201426, 3988, 40, 0, 27, "Text"], Cell[CellGroupData[{ Cell[201491, 3992, 127, 2, 51, "Input"], Cell[201621, 3996, 428, 6, 49, "Output"] }, Open ]], Cell[202064, 4005, 93, 2, 27, "Text"], Cell[CellGroupData[{ Cell[202182, 4011, 131, 3, 31, "Input"], Cell[202316, 4016, 428, 6, 49, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[202781, 4027, 63, 1, 31, "Input"], Cell[202847, 4030, 56, 1, 30, "Output"] }, Open ]], Cell[202918, 4034, 121, 3, 27, "Text"], Cell[203042, 4039, 690, 18, 95, "Text"], Cell[203735, 4059, 231, 8, 27, "Text"], Cell[203969, 4069, 506, 12, 61, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[204524, 4087, 31, 0, 27, "Subsection"], Cell[204558, 4089, 526, 12, 67, "Text"], Cell[CellGroupData[{ Cell[205109, 4105, 80, 2, 31, "Input"], Cell[205192, 4109, 95, 2, 30, "Output"] }, Open ]], Cell[205302, 4114, 41, 0, 27, "Text"], Cell[205346, 4116, 506, 10, 61, "Text"], Cell[205855, 4128, 500, 11, 131, "Input"], Cell[CellGroupData[{ Cell[206380, 4143, 63, 1, 31, "Input"], Cell[206446, 4146, 6486, 191, 217, "Output"] }, Open ]], Cell[212947, 4340, 65, 0, 27, "Text"], Cell[CellGroupData[{ Cell[213037, 4344, 84, 1, 31, "Input"], Cell[213124, 4347, 2440, 72, 111, "Output"] }, Open ]], Cell[215579, 4422, 30, 0, 27, "Text"], Cell[CellGroupData[{ Cell[215634, 4426, 83, 1, 31, "Input"], Cell[215720, 4429, 1012, 30, 58, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[216769, 4464, 89, 1, 31, "Input"], Cell[216861, 4467, 59, 1, 30, "Output"] }, Open ]], Cell[216935, 4471, 45, 0, 27, "Text"], Cell[CellGroupData[{ Cell[217005, 4475, 88, 1, 31, "Input"], Cell[217096, 4478, 55, 1, 30, "Output"] }, Open ]], Cell[217166, 4482, 44, 0, 27, "Text"], Cell[CellGroupData[{ Cell[217235, 4486, 127, 3, 31, "Input"], Cell[217365, 4491, 52, 1, 30, "Output"] }, Open ]], Cell[217432, 4495, 211, 4, 44, "Text"], Cell[217646, 4501, 116, 2, 31, "Input"], Cell[CellGroupData[{ Cell[217787, 4507, 84, 1, 31, "Input"], Cell[217874, 4510, 1488, 44, 58, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[219399, 4559, 92, 1, 31, "Input"], Cell[219494, 4562, 54, 1, 30, "Output"] }, Open ]], Cell[219563, 4566, 103, 3, 27, "Text"], Cell[219669, 4571, 259, 4, 71, "Input"], Cell[CellGroupData[{ Cell[219953, 4579, 66, 1, 31, "Input"], Cell[220022, 4582, 1488, 44, 58, "Output"] }, Open ]], Cell[221525, 4629, 58, 0, 27, "Text"], Cell[CellGroupData[{ Cell[221608, 4633, 139, 3, 51, "Input"], Cell[221750, 4638, 49, 1, 30, "Output"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell[221848, 4645, 51, 0, 27, "Subsection"], Cell[221902, 4647, 197, 4, 44, "Text"], Cell[222102, 4653, 217, 4, 71, "Input"], Cell[CellGroupData[{ Cell[222344, 4661, 89, 1, 31, "Input"], Cell[222436, 4664, 840, 26, 42, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[223313, 4695, 108, 2, 31, "Input"], Cell[223424, 4699, 52, 1, 30, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[223513, 4705, 83, 1, 31, "Input"], Cell[223599, 4708, 536, 16, 58, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[224172, 4729, 93, 1, 31, "Input"], Cell[224268, 4732, 55, 1, 30, "Output"] }, Open ]], Cell[224338, 4736, 105, 3, 27, "Text"], Cell[224446, 4741, 161, 4, 31, "Input"], Cell[CellGroupData[{ Cell[224632, 4749, 135, 3, 31, "Input"], Cell[224770, 4754, 7881, 201, 348, "Output"] }, Open ]], Cell[232666, 4958, 59, 0, 27, "Text"] }, Closed]] }, Open ]], Cell[CellGroupData[{ Cell[232774, 4964, 48, 0, 56, "Section"], Cell[232825, 4966, 334, 7, 44, "Text"], Cell[CellGroupData[{ Cell[233184, 4977, 509, 12, 101, "Input"], Cell[233696, 4991, 68, 2, 30, "Output"], Cell[233767, 4995, 265, 8, 58, "Output"] }, Open ]], Cell[234047, 5006, 117, 3, 27, "Text"], Cell[CellGroupData[{ Cell[234189, 5013, 686, 14, 191, "Input"], Cell[234878, 5029, 2035, 63, 42, "Output"] }, Open ]], Cell[236928, 5095, 230, 5, 45, "Text"], Cell[CellGroupData[{ Cell[237183, 5104, 678, 14, 191, "Input"], Cell[237864, 5120, 62, 2, 30, "Output"] }, Open ]], Cell[237941, 5125, 1706, 36, 233, "Text"], Cell[239650, 5163, 222, 4, 31, "NumberedEquation"], Cell[239875, 5169, 1579, 51, 145, "Text"], Cell[241457, 5222, 1272, 35, 95, "Text"], Cell[242732, 5259, 172, 3, 47, "Text"], Cell[242907, 5264, 281, 9, 27, "Text"], Cell[243191, 5275, 145, 3, 42, "Text"], Cell[243339, 5280, 244, 7, 27, "Text"], Cell[243586, 5289, 234, 6, 42, "Text"], Cell[243823, 5297, 2189, 68, 180, "Text"], Cell[246015, 5367, 192, 8, 31, "Text"], Cell[246210, 5377, 467, 11, 31, "NumberedEquation"], Cell[246680, 5390, 649, 12, 78, "Text"], Cell[CellGroupData[{ Cell[247354, 5406, 34, 0, 33, "Subsubsection"], Cell[247391, 5408, 1847, 55, 224, "Text"], Cell[249241, 5465, 280, 4, 27, "NumberedEquation"], Cell[249524, 5471, 440, 9, 61, "Text"], Cell[249967, 5482, 223, 6, 27, "Text"], Cell[250193, 5490, 1033, 19, 163, "Text"], Cell[251229, 5511, 1519, 27, 339, "NumberedTable"], Cell[252751, 5540, 384, 6, 61, "Text"], Cell[253138, 5548, 371, 9, 103, "Text"], Cell[253512, 5559, 1884, 54, 129, "Text"], Cell[255399, 5615, 134, 4, 27, "Text"], Cell[255536, 5621, 132, 3, 42, "Text"], Cell[255671, 5626, 314, 10, 27, "Text"], Cell[255988, 5638, 297, 7, 86, "Text"], Cell[256288, 5647, 396, 14, 63, "Text"], Cell[256687, 5663, 116, 3, 31, "Input", InitializationCell->True], Cell[256806, 5668, 808, 18, 191, "Input"], Cell[257617, 5688, 174, 5, 27, "Text"], Cell[CellGroupData[{ Cell[257816, 5697, 146, 3, 51, "Input"], Cell[257965, 5702, 135, 3, 30, "Output"], Cell[258103, 5707, 135, 3, 30, "Output"] }, Open ]], Cell[258253, 5713, 318, 5, 44, "Text"], Cell[CellGroupData[{ Cell[258596, 5722, 168, 4, 71, "Input"], Cell[258767, 5728, 96, 2, 43, "Output"], Cell[258866, 5732, 78, 2, 30, "Output"], Cell[258947, 5736, 92, 2, 43, "Output"] }, Open ]], Cell[259054, 5741, 686, 11, 96, "Text"], Cell[259743, 5754, 554, 11, 133, "Input"], Cell[CellGroupData[{ Cell[260322, 5769, 74, 2, 31, "Input"], Cell[260399, 5773, 63, 2, 30, "Output"] }, Open ]], Cell[260477, 5778, 335, 5, 61, "Text"], Cell[260815, 5785, 118, 3, 27, "Text"], Cell[260936, 5790, 103, 2, 27, "Text"], Cell[261042, 5794, 91, 1, 27, "Text"], Cell[261136, 5797, 73, 0, 27, "Text"], Cell[261212, 5799, 328, 7, 111, "Input"], Cell[261543, 5808, 397, 17, 27, "Text"], Cell[CellGroupData[{ Cell[261965, 5829, 72, 2, 31, "Input"], Cell[262040, 5833, 187, 3, 49, "Output"] }, Open ]], Cell[262242, 5839, 108, 3, 27, "Text"], Cell[CellGroupData[{ Cell[262375, 5846, 409, 9, 111, "Input", InitializationCell->True], Cell[262787, 5857, 187, 3, 49, "Output"] }, Open ]], Cell[262989, 5863, 323, 7, 46, "Text"], Cell[263315, 5872, 671, 16, 153, "Input", InitializationCell->True], Cell[263989, 5890, 196, 4, 44, "Text"], Cell[CellGroupData[{ Cell[264210, 5898, 114, 2, 35, "Input"], Cell[264327, 5902, 554, 16, 138, "Output"] }, Open ]], Cell[264896, 5921, 45, 0, 27, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[264978, 5926, 55, 0, 43, "Subsection"], Cell[265036, 5928, 395, 8, 78, "Text"], Cell[265434, 5938, 136, 3, 43, "Text"], Cell[265573, 5943, 758, 20, 78, "Text"], Cell[266334, 5965, 272, 7, 53, "Input"], Cell[CellGroupData[{ Cell[266631, 5976, 139, 3, 32, "Input"], Cell[266773, 5981, 533, 16, 138, "Output"] }, Open ]], Cell[267321, 6000, 44, 0, 27, "Text"], Cell[267368, 6002, 845, 21, 113, "Text"], Cell[CellGroupData[{ Cell[268238, 6027, 34, 0, 33, "Subsubsection"], Cell[268275, 6029, 700, 19, 78, "Text"], Cell[268978, 6050, 1695, 30, 439, "NumberedTable"], Cell[270676, 6082, 208, 5, 61, "Text"], Cell[270887, 6089, 230, 8, 27, "Text"], Cell[271120, 6099, 64, 1, 27, "Text"], Cell[271187, 6102, 336, 7, 48, "Text"], Cell[271526, 6111, 1134, 19, 248, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[272697, 6135, 34, 0, 33, "Subsubsection"], Cell[272734, 6137, 89, 2, 27, "Text"], Cell[272826, 6141, 404, 8, 87, "Text"], Cell[273233, 6151, 1172, 36, 146, "Text"], Cell[274408, 6189, 491, 8, 80, "Text"], Cell[274902, 6199, 141, 4, 28, "Text"], Cell[275046, 6205, 810, 17, 133, "Input"], Cell[CellGroupData[{ Cell[275881, 6226, 140, 3, 39, "Input"], Cell[276024, 6231, 503, 16, 138, "Output"] }, Open ]], Cell[276542, 6250, 44, 0, 27, "Text"] }, Open ]] }, Closed]], Cell[CellGroupData[{ Cell[276635, 6256, 31, 0, 27, "Subsection"], Cell[276669, 6258, 371, 7, 61, "Text"], Cell[277043, 6267, 789, 25, 95, "Text"], Cell[277835, 6294, 890, 20, 113, "Text"], Cell[278728, 6316, 641, 25, 101, "Text"], Cell[279372, 6343, 197, 6, 44, "Text"], Cell[279572, 6351, 164, 4, 42, "Text"], Cell[279739, 6357, 299, 11, 27, "Text"], Cell[280041, 6370, 221, 4, 44, "Text"], Cell[280265, 6376, 665, 17, 95, "Text"], Cell[280933, 6395, 412, 9, 106, "Input"], Cell[281348, 6406, 88, 1, 27, "Text"], Cell[281439, 6409, 739, 16, 175, "Input"], Cell[CellGroupData[{ Cell[282203, 6429, 107, 2, 32, "Input"], Cell[282313, 6433, 484, 16, 138, "Output"] }, Open ]], Cell[282812, 6452, 44, 0, 27, "Text"] }, Closed]] }, Open ]] }, Open ]] } ] *) (*********************************************************************** End of Mathematica Notebook file. ***********************************************************************)