From mmishna@sfu.ca Mon Jan 1 18:00:04 2007 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.7 (2006-10-05) on demeter.uwaterloo.ca X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.7 Received: from defout.telus.net (defout.telus.net [199.185.220.240]) by graceland.math.uwaterloo.ca (8.13.8/8.13.8) with ESMTP id l01N01Aq022359 for ; Mon, 1 Jan 2007 18:00:04 -0500 (EST) Received: from priv-edtnaa05.telusplanet.net ([209.121.14.164]) by priv-edtnes87.telusplanet.net (InterMail vM.7.05.01.01 201-2174-106-103-20060222) with ESMTP id <20070101215912.KYUC28003.priv-edtnes87.telusplanet.net@priv-edtnaa05.telusplanet.net> for ; Mon, 1 Jan 2007 14:59:12 -0700 Received: from [10.0.1.4] (unknown [209.121.14.164]) by priv-edtnaa05.telusplanet.net (BorderWare MXtreme Infinity Mail Firewall) with ESMTP id 4BGGELHCJR for ; Mon, 1 Jan 2007 14:59:10 -0700 (MST) Mime-Version: 1.0 (Apple Message framework v749.3) In-Reply-To: <200612302055.kBUKtYJi000280@graceland.math.uwaterloo.ca> References: <200612302055.kBUKtYJi000280@graceland.math.uwaterloo.ca> Content-Type: multipart/mixed; boundary=Apple-Mail-3-402985348 Message-Id: <7A94AA03-4ACD-4D46-A6DC-936D352C6B46@sfu.ca> From: Marni Mishna Subject: Re: Submission to the Journal of Integer Sequences Date: Mon, 1 Jan 2007 13:59:06 -0800 To: Jeffrey Shallit X-Mailer: Apple Mail (2.749.3) X-Greylist: Delayed for 01:00:48 by milter-greylist-2.0 (graceland.math.uwaterloo.ca [129.97.75.152]); Mon, 01 Jan 2007 18:00:04 -0500 (EST) X-UUID: 0d7899aa-8977-4aab-8b7f-4e7d85d7a7da Status: RO --Apple-Mail-3-402985348 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed On 30-Dec-06, at 12:55 PM, Jeffrey Shallit wrote: > Yes, I think I would prefer the .ps or .eps files. Jeffrey Shallit > > P. S. Thanks for not yelling at me about the delay! It was a rough > fall, but I promise to be more prompt now that teaching is over. Hello again, Here are the required .eps files, and a modified .tex file that will use them. If I thought yelling might have made a difference, I might have considered it, but I didn't really think that was the case. I am hoping instead that the energy will go into a speedy review process! ;) Marni --Apple-Mail-3-402985348 Content-Transfer-Encoding: 7bit Content-Type: application/postscript; x-unix-mode=0700; name="multi1.eps" Content-Disposition: inline; filename=multi1.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: multi1.fig %%Creator: fig2dev Version 3.2 Patchlevel 4 %%CreationDate: Wed Jul 6 16:43:10 2005 %%For: marni@Edna.local (Marni Mishna) %%BoundingBox: 0 0 288 253 %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save newpath 0 253 moveto 0 0 lineto 288 0 lineto 288 253 lineto closepath clip newpath 1.3 299.2 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /DrawEllipse { /endangle exch def /startangle exch def /yrad exch def /xrad exch def /y exch def /x exch def /savematrix mtrx currentmatrix def x y tr xrad yrad sc 0 0 1 startangle endangle arc closepath savematrix setmatrix } def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin 10 setmiterlimit 0 slj 0 slc 0.06000 0.06000 sc % % Fig objects follow % % % here starts figure with depth 50 % Arc 15.000 slw gs clippath 3763 3531 m 3882 3548 l 3912 3331 l 3828 3502 l 3793 3315 l cp eoclip n 2383.9 3187.5 1480.1 -51.8 13.2 arc gs col0 s gr gr % arrowhead n 3793 3315 m 3828 3502 l 3912 3331 l 3860 3264 l 3793 3315 l cp gs col7 1.00 shd ef gr col0 s % Arc gs clippath 1694 2132 m 1590 2191 l 1699 2382 l 1662 2196 l 1803 2322 l cp eoclip n 4722.8 573.5 3465.1 110.2 152.5 arc gs col0 s gr gr % arrowhead n 1803 2322 m 1662 2196 l 1699 2382 l 1781 2404 l 1803 2322 l cp gs col7 1.00 shd ef gr col0 s % Polyline 30.000 slw [120] 0 sd n 1800 4200 m 2700 1200 l 3300 1200 l 4500 4200 l 4200 4500 l 2100 4500 l 1800 4200 l cp gs col0 s gr [] 0 sd % Polyline [15 30] 30 sd n 300 4200 m 1200 1200 l 1800 1200 l 3000 4200 l 2700 4500 l 600 4500 l 300 4200 l cp gs col0 s gr [] 0 sd % here ends figure; % % here starts figure with depth 48 % Ellipse 15.000 slw n 900 3900 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr % Ellipse n 3000 1800 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr % Ellipse n 1500 1800 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr % Ellipse n 3900 3900 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr % Ellipse n 2400 3900 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr /Helvetica-Bold ff 360.00 scf sf 2925 1935 m gs 1 -1 sc (2) col0 sh gr % Polyline 2 slj gs clippath 2858 1486 m 2871 1366 l 2653 1344 l 2826 1423 l 2640 1464 l cp eoclip n 1800 1575 m 1803 1573 l 1809 1570 l 1820 1564 l 1837 1555 l 1858 1543 l 1884 1530 l 1912 1515 l 1942 1500 l 1972 1486 l 2002 1472 l 2030 1459 l 2057 1447 l 2083 1437 l 2108 1428 l 2132 1420 l 2155 1414 l 2178 1408 l 2201 1404 l 2225 1400 l 2245 1397 l 2266 1395 l 2288 1394 l 2311 1392 l 2336 1392 l 2362 1392 l 2390 1392 l 2420 1393 l 2453 1394 l 2488 1396 l 2525 1398 l 2564 1401 l 2605 1404 l 2645 1407 l 2685 1410 l 2723 1413 l 2757 1416 l 2787 1419 l 2811 1421 l 2850 1425 l gs col0 s gr gr % arrowhead 0 slj n 2640 1464 m 2826 1423 l 2653 1344 l 2587 1398 l 2640 1464 l cp gs col7 1.00 shd ef gr col0 s /Helvetica-Bold ff 360.00 scf sf 1395 1965 m gs 1 -1 sc (1) col0 sh gr % Polyline n 105 795 m 0 795 0 4860 105 arcto 4 {pop} repeat 0 4965 4635 4965 105 arcto 4 {pop} repeat 4740 4965 4740 900 105 arcto 4 {pop} repeat 4740 795 105 795 105 arcto 4 {pop} repeat cp gs col0 s gr /Helvetica-Bold ff 360.00 scf sf 825 4050 m gs 1 -1 sc (3) col0 sh gr /Helvetica-Bold ff 360.00 scf sf 2295 4035 m gs 1 -1 sc (4) col0 sh gr /Helvetica-Bold ff 360.00 scf sf 3825 4065 m gs 1 -1 sc (5) col0 sh gr % here ends figure; $F2psEnd rs showpage --Apple-Mail-3-402985348 Content-Transfer-Encoding: 7bit Content-Type: application/postscript; x-unix-mode=0700; name="graph1.eps" Content-Disposition: inline; filename=graph1.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: graph1.fig %%Creator: fig2dev Version 3.2 Patchlevel 4 %%CreationDate: Wed Jul 6 16:48:43 2005 %%For: marni@Edna.local (Marni Mishna) %%BoundingBox: 0 0 669 291 %%Magnification: 1.0000 %%EndComments /MyAppDict 100 dict dup begin def /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save newpath 0 291 moveto 0 0 lineto 669 0 lineto 669 291 lineto closepath clip newpath -16.7 325.3 translate 1 -1 scale % This junk string is used by the show operators /PATsstr 1 string def /PATawidthshow { % cx cy cchar rx ry string % Loop over each character in the string { % cx cy cchar rx ry char % Show the character dup % cx cy cchar rx ry char char PATsstr dup 0 4 -1 roll put % cx cy cchar rx ry char (char) false charpath % cx cy cchar rx ry char /clip load PATdraw % Move past the character (charpath modified the % current point) currentpoint % cx cy cchar rx ry char x y newpath moveto % cx cy cchar rx ry char % Reposition by cx,cy if the character in the string is cchar 3 index eq { % cx cy cchar rx ry 4 index 4 index rmoveto } if % Reposition all characters by rx ry 2 copy rmoveto % cx cy cchar rx ry } forall pop pop pop pop pop % - currentpoint newpath moveto } bind def /PATcg { 7 dict dup begin /lw currentlinewidth def /lc currentlinecap def /lj currentlinejoin def /ml currentmiterlimit def /ds [ currentdash ] def /cc [ currentrgbcolor ] def /cm matrix currentmatrix def end } bind def % PATdraw - calculates the boundaries of the object and % fills it with the current pattern /PATdraw { % proc save exch PATpcalc % proc nw nh px py 5 -1 roll exec % nw nh px py newpath PATfill % - restore } bind def % PATfill - performs the tiling for the shape /PATfill { % nw nh px py PATfill - PATDict /CurrentPattern get dup begin setfont % Set the coordinate system to Pattern Space PatternGState PATsg % Set the color for uncolored pattezns PaintType 2 eq { PATDict /PColor get PATsc } if % Create the string for showing 3 index string % nw nh px py str % Loop for each of the pattern sources 0 1 Multi 1 sub { % nw nh px py str source % Move to the starting location 3 index 3 index % nw nh px py str source px py moveto % nw nh px py str source % For multiple sources, set the appropriate color Multi 1 ne { dup PC exch get PATsc } if % Set the appropriate string for the source 0 1 7 index 1 sub { 2 index exch 2 index put } for pop % Loop over the number of vertical cells 3 index % nw nh px py str nh { % nw nh px py str currentpoint % nw nh px py str cx cy 2 index oldshow % nw nh px py str cx cy YStep add moveto % nw nh px py str } repeat % nw nh px py str } for 5 { pop } repeat end } bind def % PATkshow - kshow with the current pattezn /PATkshow { % proc string exch bind % string proc 1 index 0 get % string proc char % Loop over all but the last character in the string 0 1 4 index length 2 sub { % string proc char idx % Find the n+1th character in the string 3 index exch 1 add get % string proc char char+1 exch 2 copy % strinq proc char+1 char char+1 char % Now show the nth character PATsstr dup 0 4 -1 roll put % string proc chr+1 chr chr+1 (chr) false charpath % string proc char+1 char char+1 /clip load PATdraw % Move past the character (charpath modified the current point) currentpoint newpath moveto % Execute the user proc (should consume char and char+1) mark 3 1 roll % string proc char+1 mark char char+1 4 index exec % string proc char+1 mark... cleartomark % string proc char+1 } for % Now display the last character PATsstr dup 0 4 -1 roll put % string proc (char+1) false charpath % string proc /clip load PATdraw neewath pop pop % - } bind def % PATmp - the makepattern equivalent /PATmp { % patdict patmtx PATmp patinstance exch dup length 7 add % We will add 6 new entries plus 1 FID dict copy % Create a new dictionary begin % Matrix to install when painting the pattern TilingType PATtcalc /PatternGState PATcg def PatternGState /cm 3 -1 roll put % Check for multi pattern sources (Level 1 fast color patterns) currentdict /Multi known not { /Multi 1 def } if % Font dictionary definitions /FontType 3 def % Create a dummy encoding vector /Encoding 256 array def 3 string 0 1 255 { Encoding exch dup 3 index cvs cvn put } for pop /FontMatrix matrix def /FontBBox BBox def /BuildChar { mark 3 1 roll % mark dict char exch begin Multi 1 ne {PaintData exch get}{pop} ifelse % mark [paintdata] PaintType 2 eq Multi 1 ne or { XStep 0 FontBBox aload pop setcachedevice } { XStep 0 setcharwidth } ifelse currentdict % mark [paintdata] dict /PaintProc load % mark [paintdata] dict paintproc end gsave false PATredef exec true PATredef grestore cleartomark % - } bind def currentdict end % newdict /foo exch % /foo newlict definefont % newfont } bind def % PATpcalc - calculates the starting point and width/height % of the tile fill for the shape /PATpcalc { % - PATpcalc nw nh px py PATDict /CurrentPattern get begin gsave % Set up the coordinate system to Pattern Space % and lock down pattern PatternGState /cm get setmatrix BBox aload pop pop pop translate % Determine the bounding box of the shape pathbbox % llx lly urx ury grestore % Determine (nw, nh) the # of cells to paint width and height PatHeight div ceiling % llx lly urx qh 4 1 roll % qh llx lly urx PatWidth div ceiling % qh llx lly qw 4 1 roll % qw qh llx lly PatHeight div floor % qw qh llx ph 4 1 roll % ph qw qh llx PatWidth div floor % ph qw qh pw 4 1 roll % pw ph qw qh 2 index sub cvi abs % pw ph qs qh-ph exch 3 index sub cvi abs exch % pw ph nw=qw-pw nh=qh-ph % Determine the starting point of the pattern fill %(px, py) 4 2 roll % nw nh pw ph PatHeight mul % nw nh pw py exch % nw nh py pw PatWidth mul exch % nw nh px py end } bind def % Save the original routines so that we can use them later on /oldfill /fill load def /oldeofill /eofill load def /oldstroke /stroke load def /oldshow /show load def /oldashow /ashow load def /oldwidthshow /widthshow load def /oldawidthshow /awidthshow load def /oldkshow /kshow load def % These defs are necessary so that subsequent procs don't bind in % the originals /fill { oldfill } bind def /eofill { oldeofill } bind def /stroke { oldstroke } bind def /show { oldshow } bind def /ashow { oldashow } bind def /widthshow { oldwidthshow } bind def /awidthshow { oldawidthshow } bind def /kshow { oldkshow } bind def /PATredef { MyAppDict begin { /fill { /clip load PATdraw newpath } bind def /eofill { /eoclip load PATdraw newpath } bind def /stroke { PATstroke } bind def /show { 0 0 null 0 0 6 -1 roll PATawidthshow } bind def /ashow { 0 0 null 6 3 roll PATawidthshow } bind def /widthshow { 0 0 3 -1 roll PATawidthshow } bind def /awidthshow { PATawidthshow } bind def /kshow { PATkshow } bind def } { /fill { oldfill } bind def /eofill { oldeofill } bind def /stroke { oldstroke } bind def /show { oldshow } bind def /ashow { oldashow } bind def /widthshow { oldwidthshow } bind def /awidthshow { oldawidthshow } bind def /kshow { oldkshow } bind def } ifelse end } bind def false PATredef % Conditionally define setcmykcolor if not available /setcmykcolor where { pop } { /setcmykcolor { 1 sub 4 1 roll 3 { 3 index add neg dup 0 lt { pop 0 } if 3 1 roll } repeat setrgbcolor - pop } bind def } ifelse /PATsc { % colorarray aload length % c1 ... cn length dup 1 eq { pop setgray } { 3 eq { setrgbcolor } { setcmykcolor } ifelse } ifelse } bind def /PATsg { % dict begin lw setlinewidth lc setlinecap lj setlinejoin ml setmiterlimit ds aload pop setdash cc aload pop setrgbcolor cm setmatrix end } bind def /PATDict 3 dict def /PATsp { true PATredef PATDict begin /CurrentPattern exch def % If it's an uncolored pattern, save the color CurrentPattern /PaintType get 2 eq { /PColor exch def } if /CColor [ currentrgbcolor ] def end } bind def % PATstroke - stroke with the current pattern /PATstroke { countdictstack save mark { currentpoint strokepath moveto PATpcalc % proc nw nh px py clip newpath PATfill } stopped { (*** PATstroke Warning: Path is too complex, stroking with gray) = cleartomark restore countdictstack exch sub dup 0 gt { { end } repeat } { pop } ifelse gsave 0.5 setgray oldstroke grestore } { pop restore pop } ifelse newpath } bind def /PATtcalc { % modmtx tilingtype PATtcalc tilematrix % Note: tiling types 2 and 3 are not supported gsave exch concat % tilingtype matrix currentmatrix exch % cmtx tilingtype % Tiling type 1 and 3: constant spacing 2 ne { % Distort the pattern so that it occupies % an integral number of device pixels dup 4 get exch dup 5 get exch % tx ty cmtx XStep 0 dtransform round exch round exch % tx ty cmtx dx.x dx.y XStep div exch XStep div exch % tx ty cmtx a b 0 YStep dtransform round exch round exch % tx ty cmtx a b dy.x dy.y YStep div exch YStep div exch % tx ty cmtx a b c d 7 -3 roll astore % { a b c d tx ty } } if grestore } bind def /PATusp { false PATredef PATDict begin CColor PATsc end } bind def % crosshatch lines 11 dict begin /PaintType 1 def /PatternType 1 def /TilingType 1 def /BBox [0 0 1 1] def /XStep 1 def /YStep 1 def /PatWidth 1 def /PatHeight 1 def /Multi 2 def /PaintData [ { clippath } bind { 16 16 true [ 16 0 0 -16 0 16 ] {} imagemask } bind ] def /PaintProc { pop exec fill } def currentdict end /P11 exch def /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /DrawEllipse { /endangle exch def /startangle exch def /yrad exch def /xrad exch def /y exch def /x exch def /savematrix mtrx currentmatrix def x y tr xrad yrad sc 0 0 1 startangle endangle arc closepath savematrix setmatrix } def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin 10 setmiterlimit 0 slj 0 slc 0.06000 0.06000 sc % % Fig objects follow % % % here starts figure with depth 52 % Polyline 45.000 slw n 6615 3915 m 6615 2115 l gs 0.00 setgray ef gr gs col0 s gr % Polyline n 4815 3915 m 6615 2115 l gs 0.00 setgray ef gr gs col0 s gr % Polyline n 9015 2130 m 10515 2130 l 10515 3930 l 9015 3930 l 10515 2130 l gs col0 s gr % here ends figure; % % here starts figure with depth 50 % Ellipse 15.000 slw n 10515 3915 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr % Ellipse n 10530 2115 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr % Ellipse n 915 2430 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr % Ellipse n 2115 1230 300 300 0 360 DrawEllipse gs /PC [[1.00 1.00 1.00] [0.00 0.00 0.00]] def 15.00 15.00 sc P11 [16 0 0 -16 121.00 62.00] PATmp PATsp ef gr PATusp gs col0 s gr % Ellipse n 2115 2430 300 300 0 360 DrawEllipse gs /PC [[1.00 1.00 1.00] [0.00 0.00 0.00]] def 15.00 15.00 sc P11 [16 0 0 -16 121.00 142.00] PATmp PATsp ef gr PATusp gs col0 s gr % Ellipse n 2115 4830 300 300 0 360 DrawEllipse gs /PC [[1.00 1.00 1.00] [0.00 0.00 0.00]] def 15.00 15.00 sc P11 [16 0 0 -16 121.00 302.00] PATmp PATsp ef gr PATusp gs col0 s gr % Ellipse 7.500 slw n 4815 2115 300 300 0 360 DrawEllipse gs col7 0.00 shd ef gr gs col0 s gr % Ellipse 15.000 slw n 4815 3915 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr % Ellipse n 6615 3915 300 300 0 360 DrawEllipse gs col7 0.90 shd ef gr gs col0 s gr % Ellipse n 6615 2115 300 300 0 360 DrawEllipse gs /PC [[1.00 1.00 1.00] [0.00 0.00 0.00]] def 15.00 15.00 sc P11 [16 0 0 -16 421.00 121.00] PATmp PATsp ef gr PATusp gs col0 s gr % Ellipse n 2115 3630 300 300 0 360 DrawEllipse gs col7 0.90 shd ef gr gs col0 s gr % Polyline 45.000 slw n 1215 1230 m 1815 1230 l gs 0.00 setgray ef gr gs col0 s gr % Polyline n 1215 2430 m 1815 2430 l gs 0.00 setgray ef gr gs col0 s gr % Polyline n 1215 3630 m 1815 3630 l gs 0.00 setgray ef gr gs col0 s gr % Polyline n 1215 4830 m 1815 4830 l gs 0.00 setgray ef gr gs col0 s gr % Polyline n 5115 2115 m 6315 2115 l gs 0.00 setgray ef gr gs col0 s gr % Polyline n 5115 3915 m 6315 3915 l gs 0.00 setgray ef gr gs col0 s gr % Ellipse 15.000 slw n 9015 2115 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr % Ellipse n 9015 3915 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr % Ellipse 7.500 slw n 915 1230 300 300 0 360 DrawEllipse gs col7 0.00 shd ef gr gs col0 s gr % Ellipse 15.000 slw n 915 3630 300 300 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col0 s gr % Ellipse n 915 4830 300 300 0 360 DrawEllipse gs col7 0.90 shd ef gr gs col0 s gr % here ends figure; % % here starts figure with depth 48 /Helvetica-Bold ff 360.00 scf sf 825 2565 m gs 1 -1 sc (1) col0 sh gr /Helvetica-Bold ff 360.00 scf sf 10410 4035 m gs 1 -1 sc (4) col0 sh gr /Helvetica-Bold ff 360.00 scf sf 2025 4950 m gs 1 -1 sc (2) col0 sh gr % Polyline 30.000 slw gs clippath 4215 3090 m 4215 2910 l 3883 2910 l 4153 3000 l 3883 3090 l cp eoclip n 2700 3000 m 4200 3000 l gs col0 s gr gr % arrowhead n 3883 3090 m 4153 3000 l 3883 2910 l 3793 3000 l 3883 3090 l cp gs col7 1.00 shd ef gr col0 s % Polyline 15.000 slw n 405 600 m 300 600 300 5295 105 arcto 4 {pop} repeat 300 5400 11295 5400 105 arcto 4 {pop} repeat 11400 5400 11400 705 105 arcto 4 {pop} repeat 11400 600 405 600 105 arcto 4 {pop} repeat cp gs col0 s gr % Polyline 30.000 slw gs clippath 8655 3075 m 8655 2895 l 8323 2895 l 8593 2985 l 8323 3075 l cp eoclip n 7140 2985 m 8640 2985 l gs col0 s gr gr % arrowhead n 8323 3075 m 8593 2985 l 8323 2895 l 8233 2985 l 8323 3075 l cp gs col7 1.00 shd ef gr col0 s /Helvetica-Bold ff 360.00 scf sf 2025 3735 m gs 1 -1 sc (3) col0 sh gr /Helvetica-Bold ff 360.00 scf sf 2010 2550 m gs 1 -1 sc (4) col0 sh gr /Helvetica-Bold ff 360.00 scf sf 810 4980 m gs 1 -1 sc (6) col0 sh gr /Helvetica-Bold ff 360.00 scf sf 825 3765 m gs 1 -1 sc (7) col0 sh gr /Helvetica-Bold ff 360.00 scf sf 840 1365 m gs 1 -1 sc (8) col7 sh gr /Helvetica-Bold ff 360.00 scf sf 2025 1380 m gs 1 -1 sc (5) col0 sh gr /Helvetica-Bold ff 360.00 scf sf 10440 2250 m gs 1 -1 sc (2) col0 sh gr /Helvetica-Bold ff 360.00 scf sf 8925 2265 m gs 1 -1 sc (1) col0 sh gr /Helvetica-Bold ff 360.00 scf sf 8955 4065 m gs 1 -1 sc (3) col0 sh gr % here ends figure; $F2psEnd rs end showpage --Apple-Mail-3-402985348 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed --Apple-Mail-3-402985348 Content-Transfer-Encoding: quoted-printable Content-Type: application/octet-stream; x-unix-mode=0600; x-mac-creator=454D4178; name="regular.tex" Content-Disposition: attachment; filename=regular.tex %=20Automatic=20enumeration=20of=20regular=20objects=0A%=20Marni=20= Mishna,=20Simon=20Fraser=20University,=20Canada=0A%=20Latest=20major=20= update:=20October=2023,=202006.=20=0A=0A\documentclass{amsart}=0A= \usepackage{amsmath,=20amssymb}=0A\usepackage{fullpage}=0A= \usepackage{graphicx}=0A=0A=20=0A%%=20example=20environment=0A= \newenvironment{example}{=0A\begin{quotation}\noindent{\bfseries=20= Example.\/}=20}{\end{quotation}}=0A=0A=0A%%=20symmetric=20functions=0A=0A= \def\gadj{{\#}}=0A\def\uadj{\star}=20=20=20=20%=20usual=20adjunction=0A= \def\sadj{\perp}=20=20%=20symmetric=20adjunction=0A= \newcommand{\pleth}[2]{#1\left[#2\right]}=20%=20symmetric=20plethysm=0A= \newcommand{\Hk}{{\mathcal{H}_k}}=20%=20Hammond=20series=0A\def\iprod{*}=20= %=20=20tensor/=20inner/=20..=20product=0A\def\HH{\ensuremath{H}}=0A= \def\EE{\ensuremath{=20E}}=0A\def\SS{\ensuremath{\mathcal=20S}}=0A= \def\Hk{{\mathcal{H}_k}}=20%=20Hammond=20series=0A= \newcommand{\rsc}[2]{\left\langle#1,=20#2\right\rangle}=20%=20symm.=20= scalar=20product=0A\newcommand{\rsp}[2]{\left\langle#1|=20= #2\right\rangle}=20%=20usual=20scalar=20product=0A= \def\sgn{\operatorname{sgn}}=20%=20sign=20of=20a=20permutation=0A= \def\field{K}=0A\def\Lambdap{\field[\boldp]}=20%=20SFs=20viewed=20as=20a=20= ring=20in=20p=0A\def\Lambdapt{\field[t][\boldp]}=0A= \def\lser{\field[\![\boldp]\!]}=20%=20power=20series=0A= \def\bm{{\mathbf{m}}}=0A=0A=0A=0A%%=20q=20stuff=0A= \newcommand\exq[1]{\ifthenelse{\equal{#1}{}}{\operatorname{ex}_q}{\operato= rname{=0Aex}_q\left(#1\right)}}=0A=0A=0A%%=20font=20definitions=0A= \newcommand\cA{\mathcal=20A}=0A\newcommand\bP{\mathbb=20P}=0A= \newcommand\bA{\mathbb=20A}=0A\newcommand\bN{\mathbb=20N}=0A= \newcommand\bR{\mathbb=20R}=0A\newcommand\bZ{\mathbb=20Z}=0A= \newcommand\bS{\mathbb=20S}=0A\newcommand\bC{\mathbb=20C}=0A=0A=0A= \newcommand{\cF}{{\mathcal=20F}}=0A\newcommand{\cB}{{\mathcal=20B}}=0A= \newcommand{\cS}{{\mathcal=20S}}=0A\newcommand{\cG}{{\mathcal=20G}}=0A= \newcommand{\cH}{{\mathcal=20H}}=0A\newcommand{\cI}{{\mathcal=20I}}=0A= \newcommand{\cJ}{{\mathcal=20J}}=0A\newcommand{\cL}{{\mathcal=20L}}=0A= \newcommand{\cX}{{\mathcal=20X}}=0A\newcommand{\cR}{{\mathcal=20R}}=0A= \newcommand{\cU}{{\mathcal=20U}}=0A\newcommand{\cV}{{\mathcal=20V}}=0A=0A= \def\sF{\ensuremath{\mathsf{F}}=20}=20%=20species=20font=0A= \def\sP{\ensuremath{\mathsf{P}}=20}=20=0A\def\sE{\ensuremath{\mathsf{E}}=20= }=0A\def\sG{\ensuremath{\mathsf{G}}=20}=0A= \def\sS{\ensuremath{\mathsf{S}}=20}=0A\def\sR{\ensuremath{\mathsf{R}}=20= }=0A\def\sX{\ensuremath{\mathsf{X}}=20}=0A= \def\sL{\ensuremath{\mathsf{L}}=20}=0A\def\sC{\ensuremath{\mathsf{C}}=20= }=0A=0A\def\C{\ensuremath{\mathbb=20C}}=0A\def\R{\ensuremath{\mathbb=20= R}}=0A\def\Z{\ensuremath{\mathbb=20Z}}=0A\def\Q{\ensuremath{\mathbb=20= Q}}=0A\def\N{\ensuremath{\mathbb=20N}}=0A\def\A{\ensuremath{\mathbb=20= A}}=0A=0A=0A%%%%%%%%%%%=20algorithm=20names=0A\def\spa{{\sf=20= scalar\_de}}=0A\def\ham{{\sf=20hammond}}=0A=0A=0A=0A%\begin{document}=0A= %\begin{frontmatter}=0A=0A%----------------=0A= \usepackage{amssymb,amsmath,=20amsthm}=0A= \newtheorem{thm}{Theorem}[section]=0A\newtheorem{cor}[thm]{Corollary}=0A= \newtheorem{prop}[thm]{Proposition}=0A\newtheorem{conj}{Conjecture}=0A= \newtheorem{defn}{Definition=20}=0A= \newenvironment{pf}{\begin{proof}}{\end{proof}}=0A%----------------=0A=0A= =0A\title{Automatic=20enumeration=20of=20regular=20objects}=0A= \author{Marni=20Mishna}=0A\email{mmishna@sfu.ca}=0A\address{Deptartment=20= of=20Mathematics\\=20Simon=20Fraser=20University\\8888=20University=20= Drive\\=20Burnaby,=0A=20=20Canada\\V5A=201S6}=20=0A\thanks{The=20author=20= thanks=20the=20Canadian=20Natural=20Science=20and=0A=20=20Engineering=20= Research=20Council=20for=20funding=20this=20work=20through=20the=20PDF=20= program.}=0A\thanks{This=20work=20was=20completed=20while=20at=20=20= LaBRI,=20Universit\'e=20=0A=20=20Bordeaux=20I,=20and=20at=20the=20Fields=20= Institute,=20Toronto,=20Canada.}=0A\thanks{{\bf=20keywords:}=20= Asymptotic=20enumeration,=20automatic=20combinatorics,=20generating=0A=20= =20functions,=20symmetric=20functions}=0A\thanks{{\bf=20Mathematics=20= Subject=20Classifications:}=2005A16,=2005C30}=0A=0A=0A%=20= \begin{keyword}=0A%=20=20=20Asymptotic=20enumeration,=20automatic=20= combinatorics,=20generating=0A%=20=20=20functions,=20symmetric=20= functions=0A%=20\end{keyword}=0A%\end{frontmatter}=0A\begin{document}=0A=0A= \begin{abstract}=0A=20=20We=20describe=20a=20framework=20for=20= systematic=20enumeration=20of=20families=0A=20=20combinatorial=20= structures=20which=20possess=20a=20certain=20regularity.=20More=0A=20=20= precisely,=20we=20describe=20how=20to=20obtain=20the=20differential=20= equations=0A=20=20satisfied=20by=20their=20generating=20series.=20These=20= differential=20equations=0A=20=20are=20then=20used=20to=20determine=20= the=20initial=20terms=20in=20the=20counting=20sequence=20and=20for=0A=20=20= asymptotic=20analysis.=20=20The=20key=20tool=20is=20the=20scalar=20= product=20for=0A=20=20symmetric=20functions.\\=0A=0A\end{abstract}=0A= \maketitle=0A\section*{Introduction}=0ASome=20classes=20of=20= combinatorial=20objects=20naturally=20possess=20a=20substantial=0Aamount=20= of=20symmetry=20and=20when=20formal=20sums=20of=20monomials=20encoding=0A= some=20parameter=20of=20interest=20are=20taken=20over=20the=20entire=20= class,=20symmetric=0Afunctions,=20or=20symmetric=20series=20appear.=20= There=20has=20been=0Asome=20recent=20activity=20to=20determine=20how=20= to=20extract=20enumerative=20series=20of=0Asparse=20sub-families=20of=20= these=20classes=20directly=20from=20the=20symmetric=0Afunctions.=20The=20= principle=20can=20be=20illustrated=20with=20one=20well=20studied=0A= example,=20the=20subset=20of=20labelled=20graphs=20in=20which=20the=20= degree=20of=20each=0Avertex=20is=20a=20fixed=20value,=20say=20$k$,=20= known=20as=20the=20{\em=20$k$-regular=0A=20=20graphs}.=20Here,=20we=20= encode=20a=20graph=20by=20its=20degree=20sequence.=20When=0Awe=20= consider=20the=20sum=20of=20this=20encoding=20over=20all=20graphs,=20= they=20are=20encoded=0Aby=20the=20infinite=20product=0A= \begin{equation}\label{eq:allgraphs}=0A=20=20G(x_1,=20x_2,=20= \ldots)=3D\prod_{i0$,=20which=20we=20also=0A= denote~$\lambda\vdash=20n$.=20=20Partitions=20serve=20as=20indices=20for=20= the=20five=0Aprincipal=20symmetric=20function=20families=20that=20we=20= use:=20homogeneous=0A($h_\lambda$),=20power=20($p_\lambda$),=20monomial=20= ($m_\lambda$),=20elementary=0A($e_\lambda$),=20and=20Schur=20= ($s_\lambda$).=20=20These=20are=20series=20in=20the=0Ainfinite=20set=20= of=20variables,=20$x_1,x_2,\dotsc$=20over=20a=20field~$\field$=20of=0A= characteristic~0.=20=20When=20the=20indices=20are=20restricted=20to=20= all=20partitions=0Aof=20the=20same=20positive=20integer~$n$,=20any=20of=20= the=20five=20families=20forms=20a=0Abasis=20for=20the=20vector=20space=20= of=20symmetric=20polynomials=20of=20degree~$n$=0Ain~$x_1,x_2,\dotsc$\@{}=20= =20On=20the=20other=20hand,=20the=20family=20of=20$p_i$'s=20indexed=0Aby=20= the=20integers~$i\in\bN$=20generates=20the=20algebra~$\Lambda$=20of=20= symmetric=0Afunctions=20over~$\field$:=20$\Lambda=3D\field[p_1,=20= p_2,\dotsc]$.=0AFurthermore,=20the~$p_i$'s=20are=20algebraically=20= independent=20over~$\bZ$.=0A=0AGenerating=20series=20of=20symmetric=20= functions=20live=20in=20the=20larger=20ring=20of=0Asymmetric=20series,=20= $\field[t][[p_1,p_2,\dotsc]]$.=20There,=20we=20have=20the=0Agenerating=20= series=20of=20homogeneous=20and=20elementary=20functions:=0A\[=0A= H(t)=3D\sum_n=20h_n=20t^n=20=3D\exp\left(\sum_i=20= p_i\frac{t^i}i\right),\qquad=0AE(t)=3D\sum_n=20e_n=20t^n=20= =3D\exp\left(\sum_i=20(-1)^ip_i\frac{t^i}i\right).=0A\]=0AWe=20often=20= refer=20to=20$H=3DH(1)$=20and=20$E=3DE(1)$.=0A=0AAlternatively,=20the=20= power=20notation=20$\lambda=3D1^{n_1}\dotsm=20k^{n_k}$=20for=0A= partitions=20indicates=20that=20$i$~occurs=20$n_i$~times=20in~$\lambda$,=0A= for~$i=3D1,2,\dots,k$.=20=20The=20normalization=20constant=0A\[=0A= z_\lambda:=3D=201^{n_1}n_1!\dotsm=20k^{n_k}n_k!=0A\]=0Aplays=20the=20= role=20of=20the=20square=20of=20a=20norm=20of~$p_\lambda$=20in=20the=20= following=20important=0Aformula:=0A\begin{equation}\label{eq:scalp}=0A= \rsc{p_\lambda}{p_\mu}=3D\delta_{\lambda,\mu}z_\lambda,=0A\end{equation}=0A= where=20$\delta_{\lambda,\mu}$~is~1=20if=20$\lambda=3D\mu$=20and=200=20= otherwise.=20=0A=0AThe=20scalar=20product=20is=20a=20basic=20tool=20for=20= coefficient=20extraction.=20Indeed,=0Aif=20we=20write=20= $F(x_1,x_2,\dotsc)$=20in=20the=20form~$\sum_\lambda=20f_\lambda=0A= m_\lambda$,=20then=20the=20coefficient=20of=20$x_1^{\lambda_1}\dotsm=0A= x_k^{\lambda_k}$=20in~$F$=20is=20$f_\lambda=3D\rsc=20F{h_\lambda}$.=20=20= Moreover,=0Awhen=20$\lambda=3D1^n$,=20the=20identity=20$h_{1^n}=3Dp_{1^n}$= =20yields=20a=20simple=20way=0Ato=20compute=20this=20coefficient=20when=20= $F$=20is=20written=20in=20the=20basis=20of=0Athe~$p$'s.=20When=20viewed=20= at=20the=20level=20of=20generating=20series,=20this=20fact=0Agives=20the=20= following=20theorem:=0A\begin{thm}[Gessel\cite{Gessel90};=20Goulden=20\&=20= Jackson\cite{GoJaRe83}]\label{thm:theta}=0A=20=20Let=20$\theta$=20be=20= the=20$\field$-algebra=20homomorphism=20from=20the=20algebra=0A=20=20of=20= symmetric=20functions=20over~$\field$=20to=20the=20algebra~$\field[[t]]$=20= of=0A=20=20formal=20power=20series=20in~$t$=20defined=20by=20= $\theta(p_1)=3Dt$,=0A=20=20$\theta(p_n)=3D0$=20for=20$n>1$.=20Then=20if=20= $F$=20is=20a=20symmetric=20function,=0A\[\theta(F)=3D\sum_{n=3D0}^\infty=20= a_n\frac{t^n}{n!},\]=0Awhere=20$a_n$=20is=20the=20coefficient=20of=20= $x_1\dotsm=20x_n$=20in~$F$.=0A\end{thm}=0A=0ATo=20end=20our=20brief=20= recollections=20of=20symmetric=20functions=20recall=20that=0Aplethysm=20= is=20a=20way=20to=20compose=20symmetric=20functions.=20=20An=20inner=20= law=0Aof~$\Lambda$,=20denoted=20$u[v]$=20for=20$u,v$=20in~$\Lambda$,=20= it=20satisifies=20the=0Afollowing=20rules~\cite{Stanley99},=20with=20$u,=20= v,=20w\in\Lambda$=20and~=0A$\alpha,\beta$=20in~$\field$=0A= \begin{equation*}=0A=20=20(\alpha=20u+\beta=20v)[w]=3D\alpha=20= u[w]+\beta=20v[w],=0A=20=20\quad=0A=20=20(uv)[w]=3Du[w]v[w],=0A= \end{equation*}=0Aand=20if=20=20$w=3D\sum_\lambda=20c_\lambda=20= p_\lambda$=20then=0A$p_n[w]=3D\sum_\lambda=20c_\lambda=20= p_{(n\lambda_1)}p_{(n\lambda_2)}\ldots$.=0AFor=20example,=20consider=0A= that=20$w[p_n]=3Dp_n[w]$,=20and=20in=20particular=20that=20= $p_n[p_m]=3Dp_{nm}$.=20=20In=20a=0Amnemonic=20way:=0A\[=0A= w[p_n]=3Dw(p_{1n},p_{2n},\dots,p_{kn},\ldots)=0A= \qquad\text{whenever}\qquad=0Aw=3Dw(p_1,p_2,\dots,p_k,\ldots).=0A\]=0A=0A= =0A\subsection{D-finite=20multivariate=20series}=0ARecall=20that=20a=20= series=20$F\in\field[[x_1,\dots,x_n]]$=20is=20{\em=0AD-finite\/}=20in=20= $x_1,\dots,x_n$=20when=20the=20set=20of=20all=20partial=20derivatives=0A= and=20their=20iterates,=20$\partial^{i_1+\dots+i_n}F/\partial=20= x_1^{i_1}\dotsm=0A\partial=20x_n^{i_n}$,=20spans=20a=20= finite-dimensional=20vector=20space=20over=20the=0Afield=20= $\field(x_1,\dots,=20x_n)$.=20=20A=20{\em=20D-finite=20description\/}=20= of=20a=0Aseries~$F$=20is=20a=20set=20of=20differential=20equations=20= which=0Aestablishes=20this=20property.=20=20A=20typical=20example=20of=20= such=20a=20set=20is=20a=0Asystem=20of=20$n$~differential=20equations=20= of=20the=20form=0A\[=0Aq_1(x)f(x)+q_2(x)\frac{\partial=20f}{\partial=20= x_i}(x)+\dots+=0Aq_k(x)\frac{\partial^kf}{\partial=20x_i^k}(x)=3D0,=0A\]=0A= where=20$i$~ranges=20over=20$1,\dots,n$,=20each~$q_j$=20is=20in=20= $\field(x_1,\dots,x_n)$=0Afor=20$1\leq=20j\leq=20k$,=20and=20$k$=20= and~$q_j$=20depend=20on~$i$.=0A=0ASuch=20a=20system=20is=20a=20typical=20= example=20of=20a=20D-finite=20description=20of=20a=0Afunctions,=20and=20= often=20this=20will=20be=20the=20preferred=20form=20for=0A= manipulating~$f$.=20In=20truth=20we=20can=20accept=20any=20basis=20which=20= generates=20the=0Avector=20space=20of=20partial=20derivatives,=20but=20= in=20the=20applications=20below,=0Athis=20form=20is=20particularly=20= easy=20to=20obtain.=0A=0A\subsection{D-finite=20symmetric=20series}=0A= The=20following=20definition=20of=20D-finiteness=20of=20series=20in=20an=20= infinite=0Anumber=20of=20variables=20is=20given=20by=20= Gessel~\cite{Gessel90},=20who=20had=20=0Asymmetric=20functions=20in=20= mind.=20A=20series=20$F\in\field[[x_1,x_2,\dotsc]]$=0Ais=20{\em=20= D-finite\/}=20in=20the=20$x_i$=20if=20the=20specialization=20to=200=20of=20= all=20but=0Aa=20finite=20(arbritrary)=20choice,=20$S$,=20of=20the=20= variable=20set=20results=20in=20a=20D-finite=0Afunction=20(in=20the=20= finite=20sense).=20In=20this=20case,=0Amany=20of=20the=20properties=20of=20= the=20finite=20multivariate=20case=20hold=20true.=20One=0Aexception=20is=20= closure=20under=20algebraic=20substitution,=20which=20requires=0A= additional=20hypotheses.=0A=0AThe=20definition=20is=20then=20tailored=20= to=20symmetric=20series=20by=20considering=20the=0Aalgebra=20of=20= symmetric=20series=20as=20generated=20over~$\field$=20by=20the=20set=0A= $\{p_1,p_2,\dotsc\}$:=20a=20symmetric=20series=20is=20called=20{\em=20= D-finite\/}=0Awhen=20it=20is=20D-finite=20in=20the=20= $p_i$'s\footnote{This=20is=20interestingly=0A=20=20enough=20{\em=20= not\/}=20equivalent=20to=20D-finiteness=20with=20respect=20to=20either=20= the=20$h$=20or=0A=20=20$e$=20basis}.=0A\begin{example}=0ABoth=20$H(t)$=20= and=20$E(t)$=20are=20D-finite=20symmetric=20functions,=20as=20for=20any=0A= specialization=20of=20all=20but=20a=20finite=20number=20of=20the=20= $p_i$'s=20to=200=20results=0Ain=20an=20exponential=20of=20a=20= polynomial.=20Similarly,=20$\exp(h_kt)$=20is=20D-finite=0Abecause=20= $h_k=3D\sum_{\lambda\vdash=20k}=20p_\lambda$=20is=20a=20polynomial=20in=20= the=20$p_i$s.=20=0A\end{example}=0A=0A=0AThe=20closure=20under=20= Hadamard=20product=20of=20D-finite=0Aseries~\cite{Lipshitz88}=20yields=20= the=20consequence:=0A\begin{thm}[Gessel]\label{thm:rsc_pres_df}=0ALet=20= $f$=20and=20$g$=20be=20elements=20of=0A= $\field[t_1,\dots,t_k][[p_1,p_2,\dotsc]]$,=20D-finite=20in=20the=20= $p_i$'s=0Aand=20$t_j$'s,=20and=20suppose=20that=20$g$=20involves=20only=20= finitely=20many=20of=20the=0A$p_i$'s.=20Then=20$\rsc=20fg$=20is=20= D-finite=20in=20the=20$t_j$'s=20provided=20it=20is=0Awell-defined=20as=20= a=20power=20series.=0A\end{thm}=0A=0A=0A\subsection{Effective=20= calculation=20and=20algorithms}=0AIn=20our=20initial=20= study~\cite{ChMiSa05}=20we=20gave=20an=20algorithm=0Awhich,=20given=20a=20= D-finite=20descriptions=20of=20two=20functions=20satisfying=20the=0A= hypothesis=20of=20Theorem~\ref{thm:rsc_pres_df},=20determines=20a=20= D-finite=0Adescription=20of=20the=20series=20of=20the=20scalar=20= product.=20Henceforth,=20we=20shall=0Arefer=20to=20this=20algorithm=20= as~\spa.=20As=20we=20noted=20in~\cite{ChMiSa05},=20a=0Asecond=20= algorithm,~\ham,=20based=20on=20the=20work=20of=20Goulden,=20Jackson=20= and=0AReilly~\cite{GoJaRe83}=20applies=20in=20the=20case=20when=20$g=3D=0A= \exp(h_nt)$,=20which=20we=20shall=20see=20is=20precisely=20how=20one=20= can=0Aextract=20the=20exponential=20generating=20series=20of=20= sub-classes=20with=0A``regularity''.=20=20They=20are=20implemented=20in=20= Maple,=20are=20are=0Aavailable=20for=20public=20distribution=20at=20the=20= website=20{\tt=0A=20=20http://www.math.sfu.ca/$\tilde{}$mmishna}.=20= Maple=20worksheets=20illustrating=20the=0Acalculations=20presented=20are=20= also=20available=20at=20that=20same=20site.=20=0A=0A\section{D-finite=20= symmetric=20series=20appear=20naturally=20in=20combinatorics}=0ASpecies=20= theory=20(in=20the=20sense=20of~\cite{BeLaLe98,Joyal81})=20is=20= formalism=0Afor=20defining=20and=20manipulating=20combinatorial=20= structures=20which=20relates=0Aclasses=20to=20encoding=20series.=20An=20= important=20connection=20to=20our=20work=20here=0Ais=20that=20the=20= series=20for=20structures=20we=20consider=20are=20D-finite=20symmetric=0A= series,=20and=20many=20of=20the=20natural=20combinatorial=20actions=20= preserve=0AD-finiteness=20on=20the=20level=20of=20these=20series.=0A=0A= The=20reader=20unfamiliar=20with=20species=20is=20heartily=20encouraged=20= to=0Aread~\cite{BeLaLe98}.=20The=20key=20features=20that=20we=20use=20= are=20that=20for=0Aevery=20combinatorial=20family=20(species)=20$\sF$=20= that=20one=20can=20define,=0Athere=20is=20an=20associated=20cycle=20= index=20series=20$Z_\sF$=20and=20an=20asymmetric=0Acycle=20index=20= series~$\Gamma_\sF$=20both=20of=20which=20are=20symmetric=0Aseries.=20= Recall=20for=20any=20species=20\sF=20its=20cycle=20index=20series=0A=20= $Z_\sF$=20is=20the=20series=20in=20$\C[\![p_1,=20p_2,=20\ldots]\!]$=20= given=20by=0A\begin{equation}\label{eq:cycle_index}=0AZ_\sF(p_1,=20p_2,=20= \ldots)=0A=20:=3D\sum_n\sum\limits_{\lambda\vdash=20n}\operatorname{Fix}=20= \sF[\lambda]=0A=20=20=20\frac{p_1^{m_1}p_2^{m_2}\cdots=20= p_k^{m_k}}{z_\lambda},=0A=20=20=20\end{equation}=0A%=0A=20=20=20where=20= the=20value=20of=20$\operatorname{Fix}\sF[\lambda]$=20is=20the=0A=20=20=20= number=20of=20structures=20of=20$\sF$=20which=20remain=20fixed=20under=20= some=20labelling=0A=20=20=20permutation=20of=20type\footnote{A=0A=20=20=20= =20=20permutation=20of=20type=20$(1^{m_1},=202^{m_2},=20\ldots)$=20has=20= $m_1$=20fixed=0A=20=20=20=20=20points,=20$m_2$=20cycles=20of=20length=20= 2,=20etc.}=20$\lambda$,=20and=20$m_k$=20gives=0A=20=20=20the=20number=20= of=20parts=20of=20$\lambda$=20equal=20to~$k$.=20=0A=0AThe=20definition=20= of=20the=20{\em=20asymmetry=20index=20series}=20of=20a=0Aspecies~$\sF$,=20= denoted~$\Gamma_\sF$,=20as=20introduced=20by=0ALabelle~\cite{BeLaLe98}=20= is=20related,=20but=20more=20subtle.=20The=20series~$\Gamma$=20behaves=20= analytically=20in=0Amuch=20the=20same=20way=20as=20the=20cycle=20index=20= series,=20notably,=20substitution=20(in=0Aalmost=20all=20cases)=20is=0A= reflected=20by=20plethysm,=20etc.=20Table~\ref{tab:smallspec}=20contains=20= some=0Asmall=20examples=20of=20both=20series.=0A=0A\begin{table}[t]=0A= \center=0A\begin{tabular}{lll|lll}\small=0AObject&Series&Symmetric=20= function&Object&Series&Symmetric=20function\\\hline\hline=0A= 2-sets&$\Gamma_{\sE_2}$&$e_2=3D\frac{p_1^2}{2}-\frac{p_2}{2}$&2-multisets&= $Z_{\sE_2}$&$h_2=3D\frac{p_1^2}{2}=0A+\frac{p_2}{2}$\\=0A= 3-sets&$\Gamma_{\sE_3}$&$e_3$=20=20=20=20=20=20=20=20=20=20=20= &3-multisets&$Z_{\sE_3}$&$h_3$\\=20=0A4-sets&$\Gamma_{\sE_4}$&$e_4$=20=20= =20=20=20=20=20=20=20=20=20&4-multisets&$Z_{\sE_4}$&$h_4$\\=0A$k$-sets=20= &$\Gamma_{\sE_k}$&$e_k$=20=20=20=20=20=20=20=20=20= &$k$-multisets&$Z_{\sE_k}$&=20$h_k=20$\\=0A3-cycles=20= &$Z_{\sC_3}$&$\frac{p_1^3}{3}+\frac{p_3}{3}$=20&=20triples=20= &$Z_{X^3}$&$p_1^3=20$\\=0A4-cycles=20= &$Z_{\sC_4}$&$\frac{p_1^4}{4}+\frac{p_2^2}{12}+\frac{p_4}{12}$&=20= 4-arrays&$Z_{X^4}$&$p_1^4=20$\\=0A5-cycles=20= &$Z_{\sC_5}$&$\frac{p_1^5}{5}+\frac{p_5}{30}$=20&=205-arrays&=20= $Z_{X^5}$&$p_1^5=20$\\=0A$k$-cycles=20&$Z_{\sC_k}$&=20$\sum_{cd=3Dk}=20= \phi(d)\frac{p_d^c}{k!}$=20&=0A$k$-arrays&$Z_{X^k}$&=20= $p_i^k$\\\hline\hline\\=0A\end{tabular}\\=0A=0A\caption{Index=20series=20= of=20small=20species=20and=20their=20corresponding=0A=20=20symmetric=20= functions}=0A\label{tab:smallspec}=0A\hrule=0A\end{table}=0A=0AIn=20a=20= fashion=20similar=20to=20the=20cycle=20index=20series,~$\Gamma_\sF$=20= arises=0Athrough=20the=20enumeration=20of=20colourings=20of=20asymmetric=20= $\sF$-structures.=0A=0AA=20notable=20example=20is=20the=20species=20of=20= sets,=20$\sE$.=20Recall=20for=20any=20finite=0Aset=20$U$=20we=20have=20= that=20$\sE[U]=3DU$.=20The=20two=20series=20above=20turn=20out=20to=20be=0A= $Z_\sE=3D\exp(\sum_n=20p_n/n)=3D\sum_n=20h_n$=0A= and~$\Gamma_\sE=3D\exp(\sum_n(-1)^n=20p_n/n)=3D\sum_n=20e_n$.=20=0A=0A= The=20primary=20advantage=20of=20this=20approach,=20as=20is=20true=20= with=20any=20generating=0Aseries=20approach,=20is=20that=20natural=20= combinatorial=20operations=20(set,=0Acartesian=20product,=20= substitution)=20coincide=20with=20straighforward=20analytic=0Aoperations=20= (sum,=20product,=20plethystic=20substitution)\footnote{This=20is=0A=20= slightly=20less=20true=20with=20the=20asymmetry=20index=20series,=20but=20= true=20enough=20for=20our=20purposes}.=0A=0AThe=20{\em=20exponential=20= generating=20series\/}=20of=20a=20species=20$\sF$=20is=20the=0Asum=20= $\sF(t)=3D\sum_n=20|\sF[n]|=20\frac{t^n}{n!}$,=20where=20$|\sF[n]|$=20is=20= the=20number=20of=0Astructures=20of=20type=20$\sF$=20on=20a=20set=20of=20= size=0A$n$.=20The=20{\em=20ordinary=20generating=0Afunction},=20= $\widetilde{\sF}(t)$,=20is=20the=20sum=20$\sF(t)=3D\sum_n=0A= \operatorname{Orb}(\sF[n])=20t^n$,=20where=20= $\operatorname{Orb}(\sF[n])$=20is=0Athe=20number=20structures=20of=20= $\sF$=20on=20a=20set=20of=20size=20$n$=20distinct=20up=20to=0A= relabelling.=20Also=20recall=20the=20notation=20$[x^n]f(x)$=20refers=20= to=20the=0Acoefficient=20of=20$[x^n]$=20in=20the=20expansion=20of=20= $f(x)$.=20This=20definition=0Aextends=20likewise=20to=20monomials.=20=20=0A= =0AThe=20next=20result=20is=20essentially=20a=20collection=20of=20known=20= results=20and=20basic=20facts=20of=0AD-finite=20series.=20=0A=20= \begin{thm}\label{thm:Dfin_species}=0A=20=20=20=20Suppose=20$\sF$=20is=20= a=20=20species=20such=20that=20$Z_\sF$=20is=20a=0A=20=20=20=20D-finite=20= symmetric=20series=20and=20write=20$p_n=3Dx_1^n+x_2^n+\ldots$.=20Then=0A=20= =20=20=20all=20of=20the=20following=20series=20are=20D-finite=20with=20= respect=20to=20$t$:=0A=20=20\begin{enumerate}=0A=20=20\item=20The=20= exponential=20generating=20function=20$\sF(t)$;=0A=20=20\item=20The=20= ordinary=20generating=0A=20=20function=20$\widetilde{\sF}(t)$,=20if=20= the=20additional=20condition=20that=20$Z_\sF(p_1,=20p_2,=20\ldots)$=20is=20= D-finite=20with=0A=20=20respect=20to=20the=20$x_i$=20variables=20is=20= also=20true;=0A=20=20\item=20The=20series=20$\sum_n=20\left([x_1^k\cdots=0A= =20=20=20=20=20=20x_n^k]Z_\sF\right)=20\frac{t^n}{n!}$,=20for=20fixed=20= $k$;=0A=20=20\item=20=20The=20series=20=0A$\sum_n\sum_{\bar=20k\in=20= S^n}\left(\left[=20x_1^{k_1}x_2^{k_2}\dots=0A=20=20=20=20= x_n^{k_n}\right]=20Z_\sF\right)=20t^n/n!$,=20for=20any=20finite=20set=20= $S\subset=20\bN$.=0A=20=20\end{enumerate}=0A\end{thm}=0A=0A=20\begin{pf}=0A= The=20first=20two=20parts=20are=20proved=20using=20two=20basic=20results=20= about=20cycle=0Aindex=20series:=0A\begin{equation*}=0A=20=20= \sF(t)=3DZ_\sF(t,=200,=200,=20\ldots)=20\quad=20\text{=20and=20}=20\quad=0A= =20=20\widetilde{\sF}(t)=3DZ_\sF(t,=20t^2,=20t^3,=20\ldots)=0A= \end{equation*}=0AThe=20first=20specialization=20is=20well-known=20to=20= preserve=0AD-finiteness~\cite{Stanley80}=20for=20any=20$n$.=20=0AThe=20= additional=20condition=20on=20the=20second=20item=20is=20sufficient=20to=20= =20prove=0Athe=20D-finiteness=20since=20the=20stated=20substitution=20is=20= the=20same=20as=0A$x_1\mapsto=20t$,=20and=20$x_i\mapsto=200$=20= otherwise.=20=0A=0AThe=20third=20item=20of=20the=20proposition=20is=20= proved=20by=20the=20expression=20=0A\begin{equation*}=0A=20=20\sum_n=20= \left([x_1^k\cdots=20x_n^k]Z_\sF\right)=20= \frac{t^n}{n!}=3D\rsc{Z_\sF}{\exp(th_k)},=0A\end{equation*}=0Awhich=20is=20= D-finite=20by=20Theorem~\ref{thm:rsc_pres_df}.=0A=0AThe=20final=20item=20= =20of=20the=20proposition=20is=20true=20because=20the=20series=20is=20= equal=20to=0A\begin{equation*}=0A=20\rsc{Z_\sF}{\exp(t\sum_{i\in=20= S}h_i)},=0A\end{equation*}=0Awhich=20is=20also=20D-finite=20by=20= Theorem~\ref{thm:rsc_pres_df}.=0A\end{pf}=0A=0AWe=20have=20one=20large=20= class=20of=20species=20for=20which=20the=20cycle=20index=20series=20is=0A= D-finite.=20All=20of=20our=20examples=20come=20from=20this=20class.=0A= \begin{thm}=0ALet=20$\sE$=20be=20the=20species=20of=20sets=20and=20= let~$\sP$=20be=20a=20polynomial=0Aspecies=20with=20finite=20= support\footnote{Species=20which=0Acan=20be=20written=20as=20polynomials=20= of=20{\em=20molecular=0A=20=20species}.=20For=20example,=20every=20= species=20in=20Table~\ref{tab:smallspec}=20is=0Apolynomial.}.=20= Then~$\sF=3D\sE\circ=20\sP$=20describes=20a=20species=20for=0A= which~$Z_\sF$=20is=20a=20D-finite=20symmetric=20series=20and=20provided=20= that=20$\sP(0)=3D0$,~$\Gamma_\sF$=20is=20also=20a=20D-finite=20symmetric=20= series.=0A\end{thm}=0A\begin{proof}=0AIf~$\sP$=20is=20a=20polynomial=20= species,=20then=20its=20cycle=20index=20series=20is=0Aa=20polynomial=20= in=20the=20$p_i$'s,=20say=20$P(p_1,=20\ldots,=20p_n)$.=20Composition=20= of=0Aspecies=20is=20reflected=20in=20the=20cycle=20index=20series=20by=20= plethysm,=20thus=0A\[=0AZ_\sF=3D\exp(\sum_k=20p_k/k)[P(p_1,=20\ldots,=20= p_n)]=3D\exp\left(\sum=20P(p_k,=0Ap_{2k},\dots,=20p_{nk})/k\right).=0A\]=0A= For=20any=20specialization=20of=20all=20but=20a=20finite=20number=20of=20= $p_i$=20to=20zero,=0Athis=20gives=20an=20exponential=20of=20a=20= polynomial,=20which=20is=20clearly=0AD-finite.=20Thus,=20$Z_\sF$=20is=20= D-finite.=20We=20can=20similarly=20show=20that=0A$\Gamma_\sF$=20is=20= also=20D-finite=20under=20the=20stated=20conditions,=20since=20the=0A= composition=20also=20results=20in=20a=20plethystic=20composition.=0A= \end{proof}=0A=0AOur=20concluding=20remarks=20in=20= Section~\ref{sec:conclusion}=20address=20the=0Amore=20general=20question=20= of=20combinatorial=20criteria=20on=20a=20species=20$\sF$=0Athat=20ensure=20= that=20$Z_\sF$=20or=20$\Gamma_\sF$=20are=20D-finite.=0A\section{Using=20= species=20to=20describe=20regular=20graph-like=20structures}=0A= Ultimately=20our=20goal=20is=20to=20generalize=20the=20well-studied=20= case=20of=20$k$-regular=0Agraphs=20to=20other=20structures=20whose=20= cycle=20index=20series=20are=20D-finite.=20To=0Ado=20so,=20we=20express=20= the=20graph=20encoding=20by=20degree=20sequence=20as=20symmetric=0A= series,=20and=20describe=20how=20to=20find=20such=20a=20representation=20= in=20general=0Ausing=20species=20theory.=0A=0AIn=20= Eq.~\eqref{eq:allgraphs}=20we=20define=20$G(x_1,=20x_2,=20\ldots)$=20as=0A= the=20encoding=20over=20all=20graphs=20of=20their=20degree=20sequence=20= and=20we=20express=0Athis=20as=20an=20infinite=20product.=20It=20turns=20= out=20that=20this=20series=20is=0Aequivalent=20to=20$E[e_2]$,=20which=20= is=20equivalent=20to=20$\Gamma_{\sE\circ=0A=20=20\sE_2}$.=20The=20= equivalent=20series=20for=20multigraphs=20(with=20loops)=20is=20equal=0A= to=20$H[h_2]=3DZ_{\sE\circ\sE_2}$,=20and=20thus=20suspecting=20an=20= explanation=20via=0Aspecies,=20we=20investigate=20this=20connection.=20= Specifically,=20=20how=20do=20we=0Aconstruct=20symmetric=20function=20= equations=20to=20describe=20the=20generating=0Afunctions=20of=20= different=20families=20of=20objects,=20such=20as=20hypergraphs.=0A=0AWe=20= begin=20with=20the=20remark=20that=20$\sF=3D\sE\circ\sE_2$=20is=20{\em=20= not\/}=20the=0Aspecies=20of=20graphs.=20It=20is=20the=20species=20of=20= partitions=20into=202-sets.=20For=0Aexample,=20$\{\{1,4\},\{2,6\},=20= \{3,7\},\{5,8\}\}$=20is=20an=20element=0Aof~$\sF$,=20and=20we=20should=20= not=20think=20that=20this=20is=20the=20graph=20on=208=0Avertices,=20with=20= four=20edges,=20rather=20it=20just=20gives=20the=20basic=20structure,=0A= i.e.=20four=20edges.=0A=0AWe=20express=20the=20Polya=20cycle=20index=20= in=20the=20power=20series=0Asymmetric=20function.=20As=20a=20series=20in=20= the=20symmetric=20$x_i$=0Aindeterminates,=20it=20is=20an=20inventory=20= of=20distinct=20(non-isomorphic)=0Acolourings=20of=20the=20elements=20of=20= the=20species.=20=0A=20=20For=20example,=20the=20non-isomorphic=20= colourings=20(by=20positive=0Aintegers,=20say)=20of=20the=20set=20=20= $\{a,b\}$=20is=20the=20set=20of=20maps=0A$\{(a,b)\mapsto(i,j)\in\bN^2:=20= i\leq=20j\}$,=20and=20the=20inventory=20of=20all=0Asuch=20colourings=20= is=20$\sum_{i\leq=20j}=20x_ix_j=3Dh_2$.=0A=0AA=20colouring=20of=20an=20= element=20in=20$\sE\circ\sE_2$=20gives=20rise=20to=20a=20graph=0A(See=20= Figure~\ref{fig:graph})=20and=20two=20colourings=20are=20isomorphic=20if=20= one=0Ais=20a=20graph=20relabelling=20of=20the=20other.=20The=20monomial=20= encoding=20a=20colouring=20indicates=0Ahow=20many=20time=20each=20colour=20= was=20used,=20that=20is,=20in=20how=20many=20edges=20the=0Acolour=20= appears,=20that=20is,=20the=20degree=20of=20the=20vertex=20represented=20= by=20the=0Acolour.=0A=20=0A\begin{figure}=0A\center=0A= \includegraphics[width=3D5cm]{graph1.eps}=0A\caption{The=20graph=20= associated=20to=20the=20coloured=20set=20partition=20$\{=20\{1_3,4_2\},=20= \{2_2,6_4\},\{3_4,7_3\},\{5_2,8_1\}\}$}=0A\label{fig:graph}=0A\hrule=0A= \end{figure}=0A=0AWe=20restate=20this=20correspondence.=20The=20species=20= $\sE\circ\sE_2$=20indicates=0Athe=20structure--=20sets=20of=20pairs.=20= The=20cycle=20index=20series=0A$Z_{\sE\circ\sE_2}$=20encodes=20= non-isomorphic=20colourings=20of=20elements,=0Awhich=20are=20in=20turn=20= equivalent=20to=20labelled=20multi-graphs.=20The=20sets=20of=20pairs=0A= indicate=20edges,=20and=20the=20colours=20indicate=20vertices.=0A=0AFor=20= many=20applications,=20like=20regular=20graphs,=20we=20would=20like=20to=20= count=0Acolourings=20without=20repetition.=20In=20this=20case,=20we=20do=20= not=20allow=0Arepetition=20of=20a=20colour=20in=20a=20given=20object,=20= hence=20to=20encode=20a=20$k$-set,=0Aeach=20colour=20appears=20exactly=20= once,=20and=20this=20is=20precisely=20the=20notion=20of=0Aasymmetry=20in=20= the=20asymmetry=20cycle=20index,=20and=20thus=20we=20use=20$\Gamma$=0A= instead=20of=20$Z$.=20Remark,=0Aand=20thus=0A\begin{equation*}=0A=20=20= \Gamma_{\sE_k}=20=3D=20e_k=20\quad\text{and=20thus,=20}=20= \quad\Gamma_\sE=3DE.=0A\end{equation*}=0ATaking=20the=20same=20species=20= $\sE\circ\sE_2$=20as=20above,=20and=20using=20the=0Aasymmetry=20index=20= series=20with=20a=20similar=20argument,=20we=20get=20that=0A= $\Gamma_{\sE\circ\sE_2}=3D\EE[e_2]$=20encodes=20simple=20graphs=20= without=20loops=0Aon=20the=20set=20of=20colours=20precisely=20as=20is=20= determined=20by=0AEq.~\eqref{eq:allgraphs}:=20= $E[e_2]=3D\prod_{i --Apple-Mail-3-402985348--