%%Page: 1 1 1 0 bop Black 0 TeXcolorgray Black Black Black Black 10800 5267 a @beginspecial 0 @llx 0 @lly 99 @urx 16 @ury 2880 @rwi @setspecial%%BeginDocument: logo129.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: logo128.eps %%Creator: fig2dev Version 3.2.3 Patchlevel %%CreationDate: Thu Nov 8 16:13:04 2001 %%For: pope@fry.research.att.com (Sue Pope) %%BoundingBox: 0 0 99 16 %%Magnification: 0.1500 %%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 16 moveto 0 0 lineto 99 0 lineto 99 16 lineto closepath clip newpath -12.0 26.0 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 %%Page: 1 1 10 setmiterlimit 0.00900 0.00900 sc 7.500 slw % Ellipse n 2213 1988 856 856 0 360 DrawEllipse gs col4 1.00 shd ef gr gs col4 s gr % Ellipse n 2213 1991 813 813 0 360 DrawEllipse gs col8 1.00 shd ef gr gs col8 s gr % Ellipse n 1602 1879 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2001 2575 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2831 1877 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2618 1509 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 1806 1519 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2205 1364 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 1669 2290 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2762 2305 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2439 2579 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2220 1992 440 440 0 360 DrawEllipse gs col4 1.00 shd ef gr gs col4 s gr % Ellipse n 2618 1509 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1805 1515 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1669 2290 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2205 1360 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2762 2305 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1600 1875 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2439 2579 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2831 1877 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2001 2573 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr /Times-Bold ff 225.00 scf sf 1997 2652 m gs 1 -1 sc (23) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2438 2659 m gs 1 -1 sc (11) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Roman ff 480.00 scf sf 3375 2205 m gs 1 -1 sc (Article 03.4.4) col0 sh gr /Times-Roman ff 480.00 scf sf 3375 1650 m gs 1 -1 sc (Journal of Integer Sequences, Vol. 6 \(2003\),) col0 sh gr /Times-Bold ff 225.00 scf sf 2618 1592 m gs 1 -1 sc (2) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2830 1956 m gs 1 -1 sc (3) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2761 2386 m gs 1 -1 sc (6) dup sw pop 2 div neg 0 rm col0 sh gr % Ellipse n 1805 1517 42 42 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Polyline n 2554 1797 m 2554 1796 l 2554 1790 l 2554 1779 l 2554 1765 l 2553 1753 l 2552 1743 l 2550 1736 l 2548 1730 l 2544 1725 l 2540 1721 l 2534 1717 l 2528 1713 l 2521 1711 l 2514 1709 l 2507 1708 l 2499 1707 l 2492 1707 l 2483 1707 l 2474 1707 l 2465 1708 l 2456 1710 l 2447 1712 l 2438 1714 l 2431 1717 l 2423 1720 l 2416 1724 l 2408 1728 l 2401 1734 l 2394 1739 l 2388 1745 l 2382 1751 l 2377 1756 l 2372 1762 l 2368 1768 l 2363 1775 l 2359 1783 l 2356 1791 l 2352 1799 l 2350 1807 l 2348 1814 l 2346 1823 l 2345 1831 l 2345 1841 l 2345 1852 l 2346 1863 l 2349 1873 l 2352 1884 l 2356 1894 l 2360 1902 l 2365 1910 l 2371 1919 l 2378 1928 l 2385 1937 l 2393 1946 l 2401 1955 l 2409 1963 l 2417 1970 l 2425 1977 l 2435 1985 l 2446 1993 l 2457 2000 l 2467 2008 l 2477 2015 l 2487 2021 l 2494 2027 l 2501 2033 l 2506 2038 l 2510 2043 l 2513 2049 l 2515 2055 l 2516 2061 l 2516 2067 l 2516 2073 l 2514 2079 l 2510 2087 l 2505 2095 l 2498 2104 l 2490 2113 l 2481 2120 l 2473 2125 l 2465 2129 l 2458 2131 l 2449 2133 l 2440 2134 l 2431 2134 l 2422 2133 l 2414 2131 l 2406 2128 l 2396 2122 l 2385 2115 l 2375 2107 l 2366 2101 l 2359 2097 l 2353 2096 l 2350 2098 l 2347 2101 l 2346 2107 l 2344 2114 l 2344 2122 l 2344 2130 l 2345 2138 l 2346 2145 l 2347 2151 l 2349 2158 l 2352 2164 l 2355 2169 l 2360 2174 l 2364 2179 l 2370 2182 l 2375 2186 l 2382 2188 l 2390 2190 l 2399 2193 l 2409 2194 l 2419 2195 l 2429 2196 l 2438 2196 l 2448 2196 l 2456 2195 l 2465 2194 l 2475 2192 l 2484 2189 l 2493 2187 l 2501 2183 l 2509 2180 l 2516 2177 l 2524 2172 l 2533 2166 l 2541 2159 l 2548 2152 l 2555 2144 l 2560 2137 l 2565 2129 l 2569 2121 l 2573 2111 l 2576 2102 l 2579 2093 l 2581 2084 l 2583 2076 l 2584 2068 l 2584 2058 l 2584 2049 l 2583 2040 l 2582 2032 l 2580 2023 l 2577 2014 l 2572 2004 l 2568 1994 l 2563 1984 l 2558 1976 l 2552 1968 l 2546 1960 l 2538 1952 l 2531 1945 l 2524 1938 l 2517 1932 l 2509 1926 l 2501 1921 l 2493 1914 l 2484 1908 l 2476 1902 l 2468 1897 l 2461 1890 l 2453 1883 l 2445 1876 l 2437 1869 l 2431 1862 l 2427 1856 l 2423 1849 l 2420 1842 l 2418 1835 l 2417 1830 l 2417 1825 l 2417 1820 l 2417 1816 l 2418 1812 l 2419 1808 l 2419 1806 l 2420 1803 l 2421 1801 l 2422 1798 l 2424 1796 l 2425 1794 l 2427 1792 l 2429 1789 l 2431 1787 l 2433 1785 l 2436 1783 l 2437 1781 l 2439 1780 l 2442 1779 l 2444 1778 l 2446 1778 l 2448 1777 l 2450 1777 l 2452 1777 l 2455 1777 l 2457 1777 l 2460 1776 l 2462 1776 l 2465 1775 l 2468 1775 l 2470 1775 l 2473 1775 l 2476 1775 l 2479 1776 l 2482 1776 l 2484 1777 l 2487 1777 l 2489 1777 l 2492 1778 l 2495 1779 l 2498 1780 l 2502 1782 l 2506 1785 l 2510 1788 l 2514 1790 l 2517 1792 l 2520 1794 l 2522 1795 l 2524 1796 l 2525 1798 l 2527 1799 l 2529 1800 l 2531 1802 l 2534 1805 l 2536 1807 l 2539 1809 l 2540 1811 l 2542 1812 l 2544 1813 l 2546 1814 l 2547 1814 l 2549 1813 l 2550 1811 l 2552 1808 l 2554 1804 l 2555 1801 l 2556 1798 l 2556 1796 l 2557 1795 l 2557 1793 l 2557 1792 l gs 0.00 setgray ef gr gs col0 s gr % Polyline n 1871 1753 m 1902 1705 l 2090 1705 l 2075 1753 l 2075 2255 l 2012 2317 l 1933 2317 l 2012 2255 l 2012 1753 l 1871 1753 l 1918 1737 l cp gs 0.00 setgray ef gr gs col0 s gr % Polyline n 2169 1705 m 2278 1705 l 2263 1720 l 2247 1753 l 2247 2129 l 2278 2191 l 2152 2191 l 2169 2176 l 2185 2129 l 2185 2098 l 2185 1753 l cp gs 0.00 setgray ef gr gs col0 s gr % Ellipse n 1600 1877 42 42 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr /Times-Bold ff 225.00 scf sf 2197 1439 m gs 1 -1 sc (1) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 1667 2376 m gs 1 -1 sc (47) dup sw pop 2 div neg 0 rm col0 sh gr $F2psEnd rs %%EndDocument @endspecial Black Black 3269 11461 a Fv(The)861 b(en)-72 b(umeration)863 b(of)f(simple)g(p)72 b(erm)-72 b(utations)15232 16603 y Fu(M.)520 b(H.)g(Alb)43 b(ert)520 b(and)h(M.)f(D.)g(A)-43 b(tkinson)15409 18596 y(Departmen)g(t)519 b(of)i(Computer)f(Science) 20076 20588 y(Univ)-43 b(ersit)g(y)518 b(of)i(Otago)23906 22581 y(Dunedin)22356 24573 y(New)h(Zealand)p 0 1 0 0 TeXcolorcmyk 17777 26566 a Ft(malbert@cs.otago.ac.nz)p [[232 478 394 490] [1 1 1 [3 3]] [0 0 1]] (mailto:malbert@cs.otago.ac.nz) pdfm Black 23049 30158 a Fu(M.)f(Klazar)p 0 .5 0 TeXcolorrgb -578 x Fs(1)p (#Hfootnote.1) [[341 446 347 458] [1 1 1 [3 3]] [0 0 1]] pdfm Black 11460 32151 a Fu(Departmen)-43 b(t)520 b(of)g(Applied)g (Mathematics)f(\(KAM\))8631 34144 y(and)i(Institute)e(for)h (Theoretical)g(Computer)g(Science)f(\(ITI\))20483 36136 y(Charles)h(Univ)-43 b(ersit)g(y)18333 38129 y(Malostransk)g(\266)-737 b(e)520 b(n\266)-780 b(am)-43 b(\267)-737 b(est)-173 b(\266)-607 b(\263)519 b(25)22280 40121 y(118)j(00)f(Praha)21522 42114 y(Czec)-43 b(h)519 b(Republic)p 0 1 0 0 TeXcolorcmyk 17777 44106 a Ft(klazar@kam.mff.cuni.cz)p [[232 320 394 332] [1 1 1 [3 3]] [0 0 1]] (mailto:klazar@kam.mff.cuni.cz) pdfm Black Black Black 24133 48651 a Fr(Abstract)p Black Black 5870 50898 a Fq(A)430 b Fp(simple)455 b(p)-62 b(ermutation)427 b Fq(is)j(one)g(whic)-34 b(h)430 b(maps)h(no)f(prop)34 b(er)429 b(non-singleton)i(in)-34 b(terv)-67 b(al)429 b(on)-34 b(to)431 b(an)4052 52404 y(in)-34 b(terv)-67 b(al.)836 b(W)-101 b(e)503 b(consider)g(the)h(en)-34 b(umeration)505 b(of)f(simple)f(p)34 b(erm)-34 b(utations)505 b(from)f(sev)-34 b(eral)502 b(asp)34 b(ects.)4052 53909 y(Our)585 b(results)h(include)g(a)g(straigh)-34 b(tforw)g(ard)588 b(relationship)e(b)34 b(et)-34 b(w)g(een)586 b(the)h(ordinary)e (generating)4052 55415 y(function)492 b(for)f(simple)g(p)34 b(erm)-34 b(utations)492 b(and)g(that)h(for)e(all)f(p)34 b(erm)-34 b(utations,)514 b(that)492 b(the)g(co)34 b(e\261cien)-34 b(ts)4052 56920 y(of)455 b(this)h(series)f(are)g(not)h Fo(P)168 b Fq(-recursiv)-34 b(e,)467 b(an)456 b(asymptotic)g(expansion) g(for)f(these)h(co)34 b(e\261cien)-34 b(ts,)468 b(and)4052 58426 y(a)577 b(n)-34 b(um)g(b)34 b(er)579 b(of)f(congruence)f(results) h(for)f(the)h(co)34 b(e\261cien)-34 b(ts)577 b(of)h(the)g(functional)h (in)-34 b(v)g(erse)577 b(of)h(the)4052 59931 y(ordinary)404 b(generating)g(function)h(for)g(all)e(p)34 b(erm)-34 b(utations.)800 64368 y Fn(1)2152 b(In)-60 b(tro)60 b(duction)715 b(and)i(de\257nitions)800 67289 y Fm(The)513 b(p)36 b(erm)-36 b(utation)513 b(2647513)j(maps)d(the)f(in)-36 b(terv)-72 b(al)514 b(2)p Fl(::)p Fm(5)h(on)-36 b(to)513 b(the)g(in)-36 b(terv)-72 b(al)513 b(4)p Fl(::)p Fm(7.)819 b(In)513 b(other)g(w)-36 b(ords,)534 b(it)800 68894 y(has)488 b(a)g Fk(se)-66 b(gment)613 b Fm(\(set)488 b(of)h(consecutiv)-36 b(e)488 b(p)36 b(ositions\))488 b(whose)h(v)-72 b(alues)488 b(form)h(a)f Fk(r)-66 b(ange)586 b Fm(\(set)488 b(of)h(consecutiv)-36 b(e)p Black 800 69801 20800 45 v 2296 70617 a Fj(1)p 0 TeXcolorgray Black 2793 71019 a Fs(ITI)369 b(is)g(supp)31 b(orted)368 b(b)-31 b(y)370 b(the)f(pro)61 b(ject)370 b(LN00A056)i(of)e(the)f(Ministry)h(of)g(Education)h(of)f(the)f(Czec)-31 b(h)370 b(Republic.)p Black Black 26475 74617 a Fm(1)p Black eop %%Page: 2 2 2 1 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(v)-72 b(alues\).)533 b(Suc)-36 b(h)293 b(a)j(segmen)-36 b(t)294 b(is)i(called)g(a)f Fk(blo)-66 b(ck)437 b Fm(of)296 b(the)e(p)36 b(erm)-36 b(utation.)532 b(Ev)-36 b(ery)295 b(p)36 b(erm)-36 b(utation)295 b(has)g(singleton)800 3029 y(blo)36 b(c)-36 b(ks,)490 b(together)477 b(with)h(the)f(blo)36 b(c)-36 b(k)478 b(1)p Fl(::n)p Fm(.)711 b(If)479 b(these)e(are)g(the)g(only)i (blo)36 b(c)-36 b(ks)478 b(the)f(p)36 b(erm)-36 b(utation)477 b(is)g(called)800 4634 y Fk(simple)p Fm(.)608 b(F)-108 b(or)443 b(example,)j(58317462)g(is)e(simple)g(and)f(the)g(simple)g(p) 36 b(erm)-36 b(utations)443 b(of)h(length)f(up)g(to)g(5)h(are)800 6239 y(as)434 b(follo)-36 b(ws:.)p Black Black 9793 7479 34015 45 v 12398 8603 a(Length)3268 b(Simple)433 b(p)36 b(erm)-36 b(utations)p 9793 9129 V 14069 10900 a(1)4940 b(1)14069 12505 y(2)g(12,)435 b(21)14069 14110 y(3)4940 b(None)14069 15715 y(4)g(2413,)435 b(3142)14069 17320 y(5)4940 b(24153,)436 b(25314,)f(31524,)h(35142,)f(41352,)h(42513)2751 19920 y(Simple)524 b(p)36 b(erm)-36 b(utations)524 b(ha)-36 b(v)g(e)524 b(recen)-36 b(tly)525 b(had)f(imp)36 b(ortan)-36 b(t)524 b(applications)h(in)f(the)g(study)g(of)h(pattern)800 21525 y(closed)391 b(classes)h(of)g(p)36 b(erm)-36 b(utations)390 b([)p 0 1 0 0 TeXcolorcmyk(1)p (#cite.AA02) [[238 523 243 535] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)p 0 1 0 0 TeXcolorcmyk 391 w(10)p (#cite.Mu01) [[250 523 262 535] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(].)564 b(Sp)36 b(eci\257cally)-108 b(,)400 b(if)392 b(suc)-36 b(h)390 b(a)h(class)h(con)-36 b(tains)390 b(only)i(\257nitely)f(man)-36 b(y)800 23130 y(simple)627 b(p)36 b(erm)-36 b(utations)626 b(then)f(it)i(is)g(\257nitely)g(based)f (\(determined)f(b)-36 b(y)627 b(a)g(\257nite)f(n)-36 b(um)g(b)36 b(er)625 b(of)i(pattern)800 24735 y(restrictions\),)603 b(and)568 b(its)h(generating)g(function)f(is)i(algebraic.)985 b(In)568 b(general)i(it)f(app)36 b(ears)568 b(that)h(there)f(is)800 26340 y(a)603 b(close)h(connection)f(b)36 b(et)-36 b(w)g(een)602 b(understanding)f(the)i(structure)e(of)j(the)f(simple)g(p)36 b(erm)-36 b(utations)602 b(in)h(a)800 27945 y(pattern)527 b(closed)i(class)g(and)f(b)36 b(eing)528 b(able)g(to)h(describ)36 b(e)528 b(the)f(structure)g(of)i(arbitrary)g(p)36 b(erm)-36 b(utations)527 b(in)800 29550 y(the)433 b(class.)2751 31156 y(Let)529 b Fl(s)5790 31355 y Fi(n)6945 31156 y Fm(denote)g(the)g(n)-36 b(um)g(b)36 b(er)527 b(of)j(simple)g(p)36 b(erm)-36 b(utations)528 b(of)j(length)e Fl(n)p Fm(.)866 b(W)-108 b(e)529 b(shall)h(b)36 b(e)529 b(concerned)800 32761 y(with)434 b(prop)36 b(erties)433 b(of)h(the)f(sequence)h(\()p Fl(s)20107 32960 y Fi(n)20732 32761 y Fm(\).)579 b(Consider)433 b(the)g(ordinary)h(generating)g(functions:)21244 36397 y Fl(F)181 b Fm(\()p Fl(x)p Fm(\))1106 b(=)27732 34736 y Fh(1)27243 35135 y Fg(X)27344 37963 y Fi(k)24 b Ff(=1)29383 36397 y Fl(k)45 b Fm(!)p Fl(x)31204 35848 y Fi(k)31773 36397 y Fm(;)21389 40714 y Fl(S)77 b Fm(\()p Fl(x)p Fm(\))1107 b(=)27732 39053 y Fh(1)27243 39452 y Fg(X)27344 42281 y Fi(k)24 b Ff(=4)29383 40714 y Fl(s)29996 40913 y Fi(k)30565 40714 y Fl(x)31304 40165 y Fi(k)31873 40714 y Fl(:)800 44595 y Fm(W)-108 b(e)526 b(start)h Fl(S)77 b Fm(\()p Fl(x)p Fm(\))526 b(from)h Fl(x)13397 44113 y Ff(4)14449 44595 y Fm(b)36 b(ecause)526 b(simple)h(p)36 b(erm)-36 b(utations)525 b(of)i(length)g(1)f(and)g(2)h(need)e(sp)36 b(ecial)528 b(treat-)800 46201 y(men)-36 b(t.)586 b(Later)437 b(in)f(this)g(section)h(w)-36 b(e)436 b(will)i(see)f(that)f(the)g(co)36 b(e\261cien)-36 b(ts)436 b(of)i Fl(S)513 b Fm(di\256er)436 b(from)h(those)g(of)g Fe(\241)p Fl(F)50811 45719 y Fh(h\241)p Ff(1)p Fh(i)800 47806 y Fm(\(functional)340 b(in)-36 b(v)g(erse,)359 b(not)339 b(recipro)36 b(cal\))340 b(alternately)h(b) -36 b(y)339 b(2)h(and)f Fe(\241)p Fm(2.)548 b(The)339 b(co)36 b(e\261cien)-36 b(ts)340 b(of)g Fl(F)46155 47324 y Fh(h\241)p Ff(1)p Fh(i)48145 47806 y Fm(\()p Fl(x)p Fm(\))f(w)-36 b(ere)800 49411 y(considered)391 b(b)-36 b(y)392 b(Com)-36 b(tet)392 b([)p 0 1 0 0 TeXcolorcmyk(4)p (#cite.Co01) [[197 272 203 284] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)401 b(p.)564 b(171])393 b(without)e(an)-36 b(y)392 b(com)-36 b(binatorial)392 b(in)-36 b(terpretation.)564 b(The)392 b(sequence)f(of)800 51016 y(absolute)491 b(v)-72 b(alues)492 b(of)g(these)e(co)36 b(e\261cien)-36 b(ts)492 b(app)36 b(ears)490 b(as)i(sequence)f(A059372)i(of)f([)p 0 1 0 0 TeXcolorcmyk(12)p (#cite.S01) [[439 258 450 270] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(],)506 b(and)490 b(the)h(\257rst)f(few)800 52621 y(terms)433 b(are:)9190 54226 y(1)p Fl(;)444 b Fm(2)p Fl(;)f Fm(2)p Fl(;)h Fm(4)p Fl(;)f Fm(4)p Fl(;)g Fm(48)p Fl(;)h Fm(336)p Fl(;)g Fm(2928)p Fl(;)h Fm(28144)p Fl(;)f Fm(298528)p Fl(;)h Fm(3454432)p Fl(;)h Fm(43286528)p Fl(:)800 56418 y Fm(So)434 b(w)-36 b(e)433 b(shall)i(see)e(that)g(the)g (n)-36 b(um)g(b)36 b(ers)432 b Fl(s)20583 56617 y Fi(n)21643 56418 y Fm(are:)9190 59042 y(1)p Fl(;)444 b Fm(2)p Fl(;)f Fm(0)p Fl(;)h Fm(2)p Fl(;)f Fm(6)p Fl(;)g Fm(46)p Fl(;)h Fm(338)p Fl(;)g Fm(2926)p Fl(;)h Fm(28146)p Fl(;)f Fm(298526)p Fl(;)h Fm(3454434)p Fl(;)h Fm(43286526)p Fl(:)800 61665 y Fm(In)565 b(section)p 0 1 0 0 TeXcolorcmyk 564 w(2)p (#section.2) [[135 162 141 174] [1 1 1 [3 3]] [0 0 1]] pdfm Black 565 w(w)-36 b(e)565 b(shall)h(pro)-36 b(v)g(e)564 b(that)h(\()p Fl(s)21169 61864 y Fi(n)21794 61665 y Fm(\))g(is)g(not)f (P-recursiv)-36 b(e)564 b(\(it)h(cannot)f(b)36 b(e)565 b(de\257ned)e(b)-36 b(y)565 b(a)g(linear)800 63270 y(recurrence)400 b(with)g(p)36 b(olynomial)403 b(co)36 b(e\261cien)-36 b(ts\).)567 b(In)401 b(section)p 0 1 0 0 TeXcolorcmyk 400 w(3)p (#section.3) [[343 148 349 160] [1 1 1 [3 3]] [0 0 1]] pdfm Black 401 w(w)-36 b(e)401 b(deriv)-36 b(e)401 b(the)f(asymptotic)i(b)36 b(eha)-36 b(viour)400 b(of)800 64875 y Fl(s)1413 65074 y Fi(n)2432 64875 y Fm(\(the)393 b(main)h(term)f(is)g Fl(n)p Fm(!)p Fl(=)p Fm(e)15049 64393 y Ff(2)15576 64875 y Fm(\))g(and)g(section)p 0 1 0 0 TeXcolorcmyk 394 w(4)p (#section.4) [[281 133 287 145] [1 1 1 [3 3]] [0 0 1]] pdfm Black 394 w(giv)-36 b(es)394 b(v)-72 b(arious)394 b(congruences)f (satis\257ed)g(b)-36 b(y)394 b(the)f(n)-36 b(um)g(b)36 b(ers)800 66480 y Fl(s)1413 66679 y Fi(n)2039 66480 y Fm(.)2751 68086 y(In)424 b(the)f(remainder)h(of)g(this)g(section)g(w) -36 b(e)424 b(deriv)-36 b(e)425 b(a)f(structure)e(theorem)i(that)f(sho) -36 b(ws)425 b(ho)-36 b(w)424 b(arbitrary)800 69691 y(p)36 b(erm)-36 b(utations)302 b(are)h(built)f(from)i(simple)f(ones,)329 b(and)302 b(read)h(o\256)g(from)g(it)g(equations)g(satis\257ed)g(b)-36 b(y)303 b(generating)800 71296 y(functions.)578 b(W)-108 b(e)434 b(b)36 b(egin)433 b(with)h(some)g(terminology)h(and)e(notation) g(that)g(will)i(b)36 b(e)434 b(used)e(throughout.)p Black 26475 74617 a(2)p Black eop %%Page: 3 3 3 2 bop Black 0 TeXcolorgray Black Black Black Black Black 22076 9545 a @beginspecial 0 @llx 0 @lly 146 @urx 146 @ury 850 @rwi @setspecial%%BeginDocument: 001_Blocks.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: 001_Blocks.eps %%Creator: fig2dev Version 3.2 Patchlevel 3d %%CreationDate: Thu Mar 20 14:08:39 2003 %%For: malbert@arthur.otago.ac.nz (Mike Albert) %%BoundingBox: 0 0 146 146 %%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 146 moveto 0 0 lineto 146 0 lineto 146 146 lineto closepath clip newpath -89.3 270.7 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.06000 0.06000 sc % % Fig objects follow % 7.500 slw % Ellipse n 2550 2250 120 120 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Ellipse n 3150 3150 120 120 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Ellipse n 3450 4050 120 120 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Ellipse n 3750 3450 120 120 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Ellipse n 1650 2850 120 120 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Ellipse n 1950 2550 120 120 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Ellipse n 2250 4350 120 120 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Ellipse n 2850 3750 120 120 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Polyline n 1500 2100 m 3900 2100 l 3900 4500 l 1500 4500 l cp gs col0 s gr % Polyline n 1500 2400 m 3900 2400 l gs col0 s gr % Polyline n 1500 3000 m 3900 3000 l gs col0 s gr % Polyline n 1500 4200 m 3900 4200 l gs col0 s gr % Polyline n 2100 4500 m 2100 2100 l gs col0 s gr % Polyline n 2400 4500 m 2400 2100 l gs col0 s gr % Polyline n 2700 4500 m 2700 2100 l gs col0 s gr $F2psEnd rs %%EndDocument @endspecial 800 13696 a Fm(Figure)404 b(1:)p 0 TeXcolorgray Black 564 w(A)f(blo)36 b(c)-36 b(k)405 b(decomp)36 b(osition)404 b(of)h(67183524)h(represen)-36 b(ted)402 b(on)i(the)f(graph)h(of)g Fl(\276)48 b Fm(.)569 b(The)403 b(pattern)g(of)800 15301 y(the)444 b(blo)36 b(c)-36 b(k)445 b(decomp)36 b(osition)445 b(is)g(the)f(p)36 b(erm)-36 b(utation)444 b(whose)h(graph)f(is)h (de\257ned)e(b)-36 b(y)445 b(the)f(o)36 b(ccupied)444 b(cells)h(of)800 16906 y(the)460 b(graphical)h(blo)36 b(c)-36 b(k)462 b(decomp)36 b(osition,)467 b(namely)462 b(3142.)660 b(Within)461 b(eac)-36 b(h)460 b(o)36 b(ccupied)460 b(cell,)469 b(the)460 b(individual)800 18511 y(blo)36 b(c)-36 b(ks)434 b(also)h(de\257ne)d(p)36 b(erm)-36 b(utations)433 b(namely)h(12,)h(1,)f(1,)g(and)f(2413.)p Black 2751 22233 a(A)366 b Fk(blo)-66 b(ck)402 b(de)-66 b(c)g(omp)g(osition)363 b Fm(of)k(a)f(p)36 b(erm)-36 b(utation)365 b Fl(\276)414 b Fm(is)366 b(a)g(partition)g(of)h Fl(\276)413 b Fm(in)-36 b(to)366 b(blo)36 b(c)-36 b(ks.)557 b(Of)366 b(course,)379 b(if)367 b Fl(\276)414 b Fm(is)800 23838 y(simple)447 b(there)e(will)j(only)f(b)36 b(e)446 b(the)g(t)-36 b(w)g(o)447 b(trivial)g(blo)36 b(c)-36 b(k)448 b(decomp)36 b(ositions.)617 b(An)446 b(example)h(of)g(a)g(non-trivial)800 25443 y(decomp)36 b(osition)434 b(is)g Fl(\276)417 b Fm(=)368 b(67183524)437 b(with)c(blo)36 b(c)-36 b(ks)435 b(\(67\)\(1\)\(8\)\(3524\).)2751 27048 y(Giv)-36 b(en)555 b(a)h(blo)36 b(c)-36 b(k)557 b(decomp)36 b(osition)556 b(of)g Fl(\276)48 b Fm(,)586 b(its)556 b Fk(p)-66 b(attern)654 b Fm(is)556 b(the)f(p)36 b(erm)-36 b(utation)554 b(de\257ned)g(b)-36 b(y)556 b(the)f(rela-)800 28654 y(tiv)-36 b(e)603 b(order)f(of)h(the)e(blo)36 b(c)-36 b(ks.)1086 b(In)602 b(the)g(example)h(ab)36 b(o)-36 b(v)g(e,)645 b(the)602 b(pattern)f(of)i(the)f(blo)36 b(c)-36 b(k)603 b(decomp)36 b(osition)800 30259 y(\(67\)\(1\)\(8\)\(3524\))470 b(is)f(3142.)686 b(W)-108 b(e)469 b(ma)-36 b(y)469 b(think)g(of)g(the)g (p)36 b(erm)-36 b(utation)468 b(67183524)j(as)e(b)36 b(eing)469 b(constructed)800 31864 y(from)506 b(the)e(p)36 b(erm)-36 b(utation)504 b(3142)j(b)-36 b(y)504 b Fk(in\260ating)f Fm(eac)-36 b(h)505 b(of)h(the)e(elemen)-36 b(ts)505 b(in)-36 b(to)505 b(a)g(blo)36 b(c)-36 b(k,)524 b(in)505 b(this)g(case)h(the)800 33469 y(blo)36 b(c)-36 b(ks)429 b(12,)i(1,)f(1,)g(and)e(2413)i(\(w)-36 b(e)429 b(view)h(eac)-36 b(h)428 b(blo)36 b(c)-36 b(k)429 b(as)g(a)g(p)36 b(erm)-36 b(utation)428 b(in)g(its)h(o)-36 b(wn)429 b(righ)-36 b(t\).)576 b(W)-108 b(e)428 b(write:)17500 36265 y(67183524)372 b(=)c(\(3142\)[12)p Fl(;)221 b Fm(1)p Fl(;)g Fm(1)p Fl(;)g Fm(2413])p Fl(:)800 39062 y Fm(This)401 b(example)f(is)h(further)e(illustrated)i(in)f(Figure)p 0 1 0 0 TeXcolorcmyk 400 w(1)p (#figure.1) [[307 365 313 377] [1 1 1 [3 3]] [0 0 1]] pdfm Black(.)567 b(The)401 b(in\260ation)f(pro)36 b(cedure)399 b(is)h(an)h(instance)f(of)h(the)800 40667 y(wreath)434 b(pro)36 b(duct)432 b(for)i(p)36 b(erm)-36 b(utations)433 b([)p 0 1 0 0 TeXcolorcmyk(2)p (#cite.AS01) [[255 351 261 363] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(].)2751 42272 y(A)421 b(p)36 b(erm)-36 b(utation)421 b(whic)-36 b(h)421 b(cannot)g(b)36 b(e)422 b(written)f(in)g(the)g(form) h(\(12\)[)p Fl(\256)8 b(;)221 b(\257)74 b Fm(])423 b(is)f(called)g Fk(plus)455 b(inde)-66 b(c)g(omp)g(os-)800 43877 y(able)p Fm(,)402 b(and)394 b(one)g(whic)-36 b(h)394 b(cannot)g(b)36 b(e)395 b(written)f(in)g(the)g(form)g(\(21\)[)p Fl(\256)8 b(;)221 b(\257)74 b Fm(])397 b(is)d(called)h Fk(minus)429 b(inde)-66 b(c)g(omp)g(osable)p Fm(.)800 45482 y(Let)520 b Fl(i)3661 45681 y Fi(n)4807 45482 y Fm(denote)g(the)g(n)-36 b(um)g(b)36 b(er)519 b(of)i(plus)f(indecomp)36 b(osable)521 b(p)36 b(erm)-36 b(utations)519 b(of)j(length)e Fl(n)p Fm(.)839 b(The)521 b(n)-36 b(um)g(b)36 b(er)800 47087 y(of)423 b(min)-36 b(us)421 b(indecomp)36 b(osable)422 b(p)36 b(erm)-36 b(utations)421 b(of)i(length)e Fl(n)i Fm(is)f(also)h Fl(i)34324 47286 y Fi(n)35372 47087 y Fm(as)f(is)g(easily)i(seen)d(b)-36 b(y)422 b(considering)800 48692 y(the)433 b(bijection)h(on)g(p)36 b(erm)-36 b(utations)432 b(of)j(length)e Fl(n)h Fm(whic)-36 b(h)433 b(sends)g Fl(\274)481 b Fm(to)434 b Fl(\274)35578 48210 y Fh(0)36321 48692 y Fm(where)g Fl(\274)40865 48210 y Fh(0)41175 48692 y Fm(\()p Fl(t)p Fm(\))368 b(=)h Fl(n)295 b Fm(+)g(1)h Fe(\241)f Fl(\274)48 b Fm(\()p Fl(t)p Fm(\).)p Black 800 51580 a Fd(Theorem)499 b(1)p Black 651 w Fk(F)-100 b(or)333 b(every)e(non-singleton)f(p)-66 b(ermutation)330 b Fl(\274)380 b Fk(ther)-66 b(e)331 b(exists)h(a)g(unique)f(simple)h (non-singleton)800 53185 y(p)-66 b(ermutation)463 b Fl(\276)48 b Fk(,)465 b(and)g(p)-66 b(ermutations)463 b Fl(\256)20911 53384 y Ff(1)21438 53185 y Fl(;)221 b(\256)22847 53384 y Ff(2)23373 53185 y Fl(;)g(:)g(:)g(:)j(;)d(\256)27113 53384 y Fi(k)28148 53185 y Fk(such)465 b(that)20798 55981 y Fl(\274)416 b Fm(=)369 b Fl(\276)48 b Fm([)p Fl(\256)25308 56180 y Ff(1)25834 55981 y Fl(;)221 b(\256)27243 56180 y Ff(2)27770 55981 y Fl(;)g(:)g(:)g(:)j(;)d(\256)31510 56180 y Fi(k)32080 55981 y Fm(])p Fl(:)800 58778 y Fk(Mor)-66 b(e)g(over,)478 b(if)e Fl(\276)440 b Fe(6)p Fm(=)391 b(12)p Fl(;)221 b Fm(21)479 b Fk(then)d Fl(\256)18173 58977 y Ff(1)18700 58778 y Fl(;)221 b(\256)20109 58977 y Ff(2)20635 58778 y Fl(;)g(:)g(:)g(:)j(;)d(\256)24375 58977 y Fi(k)25422 58778 y Fk(ar)-66 b(e)477 b(also)h(uniquely)e (determine)-66 b(d.)632 b(If)476 b Fl(\276)439 b Fm(=)391 b(12)478 b Fk(\(r)-66 b(esp)g(e)g(c-)800 60383 y(tively)425 b Fm(21)p Fk(\))i(then)e Fl(\256)10150 60582 y Ff(1)11102 60383 y Fk(and)h Fl(\256)14414 60582 y Ff(2)15367 60383 y Fk(ar)-66 b(e)425 b(uniquely)h(determine)-66 b(d)423 b(subje)-66 b(ct)425 b(to)h(the)g(additional)f(c)-66 b(ondition)424 b(that)i Fl(\256)52274 60582 y Ff(1)800 61988 y Fk(b)-66 b(e)464 b(plus)i(\(r)-66 b(esp)g(e)g(ctively)463 b(minus\))h(inde)-66 b(c)g(omp)g(osable.)2751 64875 y Fm(The)545 b(ca)-36 b(v)g(eat)545 b(added)f(for)h(the)g(case)g(where)f Fl(\276)606 b Fm(=)558 b(12)546 b(\(or)e(21\))h(is)g(necessary)-108 b(,)573 b(as)545 b(is)g(easily)i(seen)d(b)-36 b(y)800 66480 y(considering)437 b Fl(\274)422 b Fm(=)375 b(123.)589 b(This)438 b(can)f(b)36 b(e)436 b(decomp)36 b(osed)437 b(as)g(\(12\)[1)p Fl(;)221 b Fm(12])440 b(or)d(as)g(\(12\)[12)p Fl(;)221 b Fm(1].)591 b(Ho)-36 b(w)g(ev)g(er,)439 b(only)800 68086 y(the)433 b(former)h(decomp)36 b(osition)434 b(has)f(a)h(plus)f (indecomp)36 b(osable)434 b(\257rst)f(part.)2751 69691 y Fd(Pro)42 b(of)p Fm(:)1149 b(W)-108 b(e)427 b(\257rst)e(of)i(all)h (supp)36 b(ose)426 b(that)g Fl(\274)474 b Fm(has)426 b(t)-36 b(w)g(o)427 b(distinct)f(maximal)h(prop)36 b(er)426 b(blo)36 b(c)-36 b(ks)428 b Fl(A)e Fm(and)g Fl(B)800 71296 y Fm(that)350 b(ha)-36 b(v)g(e)351 b(a)g(non-empt)-36 b(y)350 b(in)-36 b(tersection.)550 b(Then,)367 b(as)351 b(the)f(union)g(of)i(in)-36 b(tersecting)350 b(segmen)-36 b(ts)350 b(is)h(a)g(segmen)-36 b(t)p Black 26475 74617 a(3)p Black eop %%Page: 4 4 4 3 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(and)391 b(the)g(union)g(of)i(in)-36 b(tersecting)391 b(ranges)h(is)g(a)g (range,)401 b Fl(A)210 b Fe([)g Fl(B)457 b Fm(is)392 b(a)g(blo)36 b(c)-36 b(k.)566 b(Because)392 b(of)g(the)f(maximalit)-36 b(y)-108 b(,)800 3029 y Fl(A)198 b Fe([)g Fl(B)435 b Fm(=)369 b([)p Fl(n)p Fm(].)563 b(But)386 b(it)g(is)g(also)h(clear)f (that)g Fl(A)g Fm(cannot)f(b)36 b(e)386 b(an)g(in)-36 b(terior)386 b(segmen)-36 b(t)385 b(of)i([)p Fl(n)p Fm(])g(nor)e(can)h (it)g(de\257ne)800 4634 y(an)434 b(in)-36 b(terior)433 b(range.)578 b(In)434 b(other)f(w)-36 b(ords)434 b(w)-36 b(e)433 b(ha)-36 b(v)g(e)23665 7270 y Fl(\274)416 b Fm(=)369 b Fl(\276)48 b Fm([)p Fl(\256)8 b(;)221 b(\257)74 b Fm(])800 9906 y(where)439 b Fl(\276)427 b Fm(=)379 b(12)440 b(or)f Fl(\276)427 b Fm(=)378 b(21.)597 b(These)439 b(t)-36 b(w)g(o)440 b(p)36 b(ossibilities)440 b(are)g(ob)-36 b(viously)441 b(m)-36 b(utually)439 b(exclusiv)-36 b(e.)597 b(In)439 b(either)800 11511 y(case)369 b(consider)f(all)h(decomp)36 b(ositions)369 b(of)g Fl(\274)415 b Fm(as)369 b Fl(\276)48 b Fm([)p Fl(\260)72 b(;)221 b(\261)50 b Fm(].)558 b(The)368 b(in)-36 b(tersection)368 b(of)h(their)f Fl(\260)440 b Fm(parts)368 b(is)g(also)h(the)f Fl(\260)800 13116 y Fm(part)344 b(of)h(a)g(decomp)36 b(osition)345 b(of)g(this)f(t)-36 b(yp)36 b(e.)549 b(So)344 b(there)g(is)h(a)g(unique)f(suc)-36 b(h)344 b(decomp)36 b(osition)344 b(with)h(smallest)g Fl(\260)800 14721 y Fm(part.)553 b(Clearly)-108 b(,)375 b(this)357 b(part)h(is)g(plus)g(indecomp)36 b(osable)358 b(in)g(the)g(case)h Fl(\276)416 b Fm(=)369 b(12)359 b(and)e(min)-36 b(us)358 b(indecomp)36 b(osable)800 16327 y(if)434 b Fl(\276)417 b Fm(=)369 b(21.)2751 17932 y(W)-108 b(e)300 b(next)h(supp)36 b(ose)299 b(that)h(ev)-36 b(ery)302 b(pair)e(of)h(distinct)f(maximal)i(prop)36 b(er)300 b(blo)36 b(c)-36 b(ks)301 b(has)f(empt)-36 b(y)300 b(in)-36 b(tersection.)800 19537 y(Ob)g(viously)-108 b(,)521 b(then)502 b(the)h(maximal)i(blo)36 b(c)-36 b(ks)504 b(form)f(a)h(blo)36 b(c)-36 b(k)504 b(decomp)36 b(osition)503 b(of)h Fl(\274)551 b Fm(and)502 b(this)h(decomp)36 b(osi-)800 21142 y(tion)487 b(m)-36 b(ust)487 b(b)36 b(e)487 b(coarser)g(than)g(ev)-36 b(ery)488 b(other)e(non)-36 b(trivial)488 b(blo)36 b(c)-36 b(k)488 b(decomp)36 b(osition)488 b(of)g Fl(\274)48 b Fm(.)738 b(It)487 b(follo)-36 b(ws)489 b(that)800 22747 y(this)j(decomp)36 b(osition)493 b(is)g(the)f(only)h(one)f(whose)h(pattern)f Fl(\276)540 b Fm(is)493 b(simple)g(and)f(so)g(w)-36 b(e)493 b(obtain)g(the)e(unique)800 24352 y(represen)-36 b(tation)433 b(claimed)h(for)g Fl(\274)48 b Fm(.)p 52228 24352 572 572 v 2751 25957 a(W)-108 b(e)423 b(shall)g(shortly)g(see)g(that)f (this)g(theorem)h(giv)-36 b(es)423 b(relations)h(b)36 b(et)-36 b(w)g(een)422 b(the)g(follo)-36 b(wing)425 b(three)d(gener-) 800 27562 y(ating)434 b(functions:)21244 31137 y Fl(F)181 b Fm(\()p Fl(x)p Fm(\))1106 b(=)27732 29476 y Fh(1)27243 29875 y Fg(X)27344 32704 y Fi(k)24 b Ff(=1)29383 31137 y Fl(k)45 b Fm(!)p Fl(x)31204 30588 y Fi(k)31773 31137 y Fm(;)21589 35454 y Fl(I)104 b Fm(\()p Fl(x)p Fm(\))1106 b(=)27732 33793 y Fh(1)27243 34192 y Fg(X)27344 37021 y Fi(k)24 b Ff(=1)29383 35454 y Fl(i)29827 35653 y Fi(k)30396 35454 y Fl(x)31135 34905 y Fi(k)31704 35454 y Fm(;)21389 39771 y Fl(S)77 b Fm(\()p Fl(x)p Fm(\))1107 b(=)27732 38110 y Fh(1)27243 38509 y Fg(X)27344 41338 y Fi(k)24 b Ff(=4)29383 39771 y Fl(s)29996 39970 y Fi(k)30565 39771 y Fl(x)31304 39222 y Fi(k)31873 39771 y Fl(:)800 43535 y Fm(Note)494 b(that)f(our)g(generating)g(functions)g(are)h(all)g(tak) -36 b(en)494 b(to)f(ha)-36 b(v)g(e)494 b(zero)f(constan)-36 b(t)493 b(term.)757 b(This)494 b(sligh)-36 b(tly)800 45140 y(uncon)g(v)g(en)g(tional)433 b(c)-36 b(hoice)434 b(turns)e(out)i(to)f(b)36 b(e)434 b(algebraically)i(con)-36 b(v)g(enien)g(t)433 b(at)h(sev)-36 b(eral)434 b(p)36 b(oin)-36 b(ts.)2751 46745 y(F)-108 b(rom)439 b(Theorem)p 0 1 0 0 TeXcolorcmyk 440 w(1)p (#definition.1) [[177 296 183 308] [1 1 1 [3 3]] [0 0 1]] pdfm Black 439 w(it)h(is)g(easy)g(to)g(see)f(that)g(there)g(is)h(a)g(one)f (to)h(one)f(corresp)36 b(ondence)439 b(b)36 b(et)-36 b(w)g(een)439 b(the)800 48350 y(collection)c(of)f(all)h(p)36 b(erm)-36 b(utations)432 b(with)i(length)f(at)h(least)g(2)g(and)f(the)g (collection)i(of)f(sequences:)21555 50986 y(\()p Fl(\276)-25 b(;)444 b(\256)24407 51185 y Ff(1)24933 50986 y Fl(;)221 b(\256)26342 51185 y Ff(2)26868 50986 y Fl(;)g(:)g(:)g(:)j(;)d(\256) 30608 51185 y Fi(k)31178 50986 y Fm(\))p Fl(:)800 53622 y Fm(Here)464 b Fl(\276)512 b Fm(ma)-36 b(y)464 b(b)36 b(e)464 b(an)-36 b(y)464 b(simple)g(p)36 b(erm)-36 b(utation)463 b(of)i(length)f Fl(k)h Fe(\270)421 b Fm(2,)472 b(and)464 b(if)g Fl(\276)469 b Fe(6)p Fm(=)420 b(12)p Fl(;)221 b Fm(21)466 b(then)d Fl(\256)47330 53821 y Ff(1)48320 53622 y Fm(through)800 55227 y Fl(\256)1627 55426 y Fi(k)2651 55227 y Fm(are)456 b(arbitrary)g(p)36 b(erm)-36 b(utations,)460 b(while)c(if)g Fl(\276)e Fm(=)405 b(12)456 b(\(resp)36 b(ectiv)-36 b(ely)456 b(21\),)462 b Fl(\256)38805 55426 y Ff(1)39786 55227 y Fm(is)456 b(plus-indecomp)36 b(osable)800 56832 y(\(resp)g(ectiv)-36 b(ely)434 b(min)-36 b(us)433 b(indecomp)36 b(osable\))434 b(and)f Fl(\256)25422 57031 y Ff(2)26382 56832 y Fm(is)h(arbitrary)-108 b(.)2751 58437 y(This)416 b(corresp)36 b(ondence,)419 b(together)d(with)g(the)g (earlier)g(observ)-72 b(ation)417 b(that)e(the)h(n)-36 b(um)g(b)36 b(ers)414 b(of)j(plus)f(and)800 60042 y(min)-36 b(us)449 b(indecomp)36 b(osable)451 b(p)36 b(erm)-36 b(utations)449 b(of)h(length)g Fl(n)h Fm(are)f(the)f(same,)455 b(translates)450 b(naturally)h(in)-36 b(to)450 b(the)800 61647 y(follo)-36 b(wing)436 b(equation:)16502 63252 y Fl(F)181 b Fm(\()p Fl(x)p Fm(\))368 b(=)h Fl(x)295 b Fm(+)g(2)p Fl(I)104 b Fm(\()p Fl(x)p Fm(\))p Fl(F)181 b Fm(\()p Fl(x)p Fm(\))294 b(+)h(\()p Fl(S)373 b Fe(\261)295 b Fl(F)181 b Fm(\)\()p Fl(x)p Fm(\))p Fl(:)14039 b Fm(\(1\))800 65450 y(Ho)-36 b(w)g(ev)g(er,)448 b(since)c(a)g(plus)g(indecomp)36 b(osable)444 b(p)36 b(erm)-36 b(utation)444 b(cannot)f(corresp)36 b(ond)444 b(to)g(a)g(sequence)g(b)36 b(egin-)800 67055 y(ning)520 b(with)g(12,)542 b(while)521 b(all)g(other)e(sequences)h(do) g(represen)-36 b(t)519 b(plus)g(indecomp)36 b(osables,)542 b(it)520 b(is)h(also)f(clear)800 68660 y(from)434 b(the)f(corresp)36 b(ondence)433 b(that)16999 71296 y Fl(I)104 b Fm(\()p Fl(x)p Fm(\))369 b(=)g Fl(x)295 b Fm(+)g Fl(I)104 b Fm(\()p Fl(x)p Fm(\))p Fl(F)181 b Fm(\()p Fl(x)p Fm(\))294 b(+)h(\()p Fl(S)372 b Fe(\261)295 b Fl(F)181 b Fm(\)\()p Fl(x)p Fm(\))p Fl(:)p Black 26475 74617 a Fm(4)p Black eop %%Page: 5 5 5 4 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(Solving)510 b(this)e(latter)h(equation)h(for)f Fl(I)104 b Fm(,)528 b(and)509 b(then)e(substituting)h(in)h(equation)g(\()p 0 1 0 0 TeXcolorcmyk(1)p (#equation.1) [[442 704 448 716] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))g(b)36 b(efore)509 b(solving)h(for)800 3029 y Fl(S)372 b Fe(\261)296 b Fl(F)614 b Fm(giv)-36 b(es:)17624 5350 y(\()p Fl(S)372 b Fe(\261)296 b Fl(F)181 b Fm(\)\()p Fl(x)p Fm(\))368 b(=)25423 4451 y Fl(F)181 b Fm(\()p Fl(x)p Fm(\))295 b Fe(\241)g Fl(F)181 b Fm(\()p Fl(x)p Fm(\))32594 3969 y Ff(2)p 25423 5044 7697 54 v 26758 6261 a Fm(1)296 b(+)f Fl(F)181 b Fm(\()p Fl(x)p Fm(\))33547 5350 y Fe(\241)296 b Fl(x:)800 8419 y Fm(No)-36 b(w)434 b(letting)g Fl(t)369 b Fm(=)f Fl(F)181 b Fm(\()p Fl(x)p Fm(\))433 b(w)-36 b(e)434 b(obtain:)18966 12142 y Fl(S)77 b Fm(\()p Fl(t)p Fm(\))369 b(=)g Fl(t)294 b Fe(\241)25839 11243 y Fm(2)p Fl(t)26959 10761 y Ff(2)p 25301 11836 2723 54 v 25301 13053 a Fm(1)h(+)g Fl(t)28451 12142 y Fe(\241)g Fl(F)30802 11593 y Fh(h\241)p Ff(1)p Fh(i)32791 12142 y Fm(\()p Fl(t)p Fm(\))p Fl(:)16504 b Fm(\(2\))800 15516 y(W)-108 b(e)397 b(can)f(also)i(obtain)e(an)h(equation)g(for)g (the)f(ordinary)g(generating)h(function)f(of)i(plus)e(indecomp)36 b(osable)800 17121 y(p)g(erm)-36 b(utations)488 b(through)g(the)g (observ)-72 b(ation)489 b(that)f(ev)-36 b(ery)490 b(p)36 b(erm)-36 b(utation)488 b(decomp)36 b(oses)488 b(in)-36 b(to)489 b(a)g(sequence)800 18726 y(of)434 b(plus)f(indecomp)36 b(osable)434 b(p)36 b(erm)-36 b(utations)433 b(so)22054 22318 y Fl(F)181 b Fm(\()p Fl(x)p Fm(\))369 b(=)27847 21420 y Fl(I)104 b Fm(\()p Fl(x)p Fm(\))p 26710 22013 4703 54 v 26710 23230 a(1)296 b Fe(\241)f Fl(I)104 b Fm(\()p Fl(x)p Fm(\))800 25923 y(or)434 b(equiv)-72 b(alen)-36 b(tly)21885 28187 y Fl(I)104 b Fm(\()p Fl(x)p Fm(\))368 b(=)27322 27288 y Fl(F)181 b Fm(\()p Fl(x)p Fm(\))p 26196 27882 5026 54 v 26196 29098 a(1)295 b(+)g Fl(F)181 b Fm(\()p Fl(x)p Fm(\))31354 28187 y Fl(:)19423 b Fm(\(3\))2751 31407 y(Denoting)426 b(the)e(co)36 b(e\261cien)-36 b(t)425 b(of)h Fl(t)18596 30925 y Fi(n)19647 31407 y Fm(in)f Fl(F)22179 30925 y Fh(h\241)p Ff(1)p Fh(i)24169 31407 y Fm(\()p Fl(t)p Fm(\))f(b)-36 b(y)425 b(Com)30547 31606 y Fi(n)31598 31407 y Fm(\(in)g(reference)g(to)g(Com)-36 b(tet)426 b(who)f(initiated)800 33012 y(the)415 b(consideration)h(of)g (this)f(sequence)g(in)g(an)h(exercise)g(of)g([)p 0 1 0 0 TeXcolorcmyk(4)p (#cite.Co01) [[344 420 350 432] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(]\))f(w)-36 b(e)416 b(obtain)g(directly)f(from)h(equation)g (\()p 0 1 0 0 TeXcolorcmyk(2)p (#equation.2) [[537 420 543 432] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))800 34617 y(the)433 b(simple)h(relationship)f(that)h(for)g Fl(n)369 b Fe(\270)g Fm(4:)19091 37550 y Fl(s)19704 37749 y Fi(n)20699 37550 y Fm(=)f Fe(\241)p Fm(Com)25786 37749 y Fi(n)26708 37550 y Fm(+)294 b(\()p Fe(\241)p Fm(1\))30709 37002 y Fi(n)p Ff(+1)32833 37550 y Fe(\242)i Fm(2)p Fl(:)800 41988 y Fn(2)2152 b(Non)716 b(P-recursiv)-60 b(eness)800 44908 y Fm(A)424 b(sequence)h(of)g(n)-36 b(um)g(b)36 b(ers)422 b(\()p Fl(a)15478 45107 y Fi(n)16104 44908 y Fm(\))i(is)h(called)g(P-recursiv)-36 b(e)424 b(if)h(it)f(satis\257es) h(a)f(linear)h(recurrence)e(with)i(p)36 b(oly-)800 46513 y(nomial)353 b(co)36 b(e\261cien)-36 b(ts.)551 b(If)352 b Fl(a)13944 46712 y Fi(n)14939 46513 y Fm(=)369 b Fl(n)p Fm(!)352 b(then)f Fl(a)21373 46712 y Fi(n)22128 46513 y Fe(\241)128 b Fl(na)24748 46712 y Fi(n)p Fh(\241)p Ff(1)26946 46513 y Fm(=)368 b(0,)h(and)351 b(th)-36 b(us)351 b(the)g(sequence)h(\()p Fl(n)p Fm(!\))g(is)g(P-recursiv)-36 b(e.)800 48118 y(A)471 b(p)36 b(o)-36 b(w)g(er)471 b(series)h(is)g (called)f(D-\257nite)g(if)h(it)f(satis\257es)g(a)h(linear)g(di\256eren) -36 b(tial)471 b(equation)g(with)h(p)36 b(olynomial)800 49723 y(co)g(e\261cien)-36 b(ts.)872 b(A)531 b(sequence)g(\()p Fl(a)16365 49922 y Fi(n)16991 49723 y Fm(\))g(is)h(P-recursiv)-36 b(e)530 b(if)i(and)f(only)h(if)g(its)f(ordinary)h(generating)f (function)800 51328 y Fl(A)p Fm(\()p Fl(x)p Fm(\))478 b(=)5494 50332 y Fg(P)6897 51716 y Fi(n)7744 51328 y Fl(a)8427 51527 y Fi(n)9053 51328 y Fl(x)9792 50846 y Fi(n)10917 51328 y Fm(is)498 b(D-\257nite.)770 b(More)498 b(information)h(on)f(D-\257niteness)f(and)g(P-recursiv)-36 b(eness)497 b(can)h(b)36 b(e)800 52934 y(found)403 b(in)g(Stanley)g([)p 0 1 0 0 TeXcolorcmyk(13)p (#cite.St02) [[170 241 182 253] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(,)410 b(Chapter)402 b(6].)569 b(W)-108 b(e)403 b(sho)-36 b(w)404 b(that)e(on)h(the)g(other)g(hand)f(neither)g (sequence)i(\()p Fl(i)49387 53133 y Fi(n)50012 52934 y Fm(\))f(nor)800 54539 y(\()p Fl(s)1919 54738 y Fi(n)2545 54539 y Fm(\))433 b(is)h(P-recursiv)-36 b(e.)578 b(By)434 b(\()p 0 1 0 0 TeXcolorcmyk(2)p (#equation.2) [[203 226 209 238] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)g(instead)f(of)i(the)e(latter)g(sequence)h(w)-36 b(e)434 b(can)f(w)-36 b(ork)435 b(with)e(\(Com)47302 54738 y Fi(n)47928 54539 y Fm(\).)p Black 800 57583 a Fd(Prop)42 b(osition)500 b(2)p Black 650 w Fk(The)594 b(p)-66 b(ower)594 b(series)f Fl(I)104 b Fm(\()p Fl(x)p Fm(\))593 b Fk(and)h Fl(C)95 b Fm(\()p Fl(x)p Fm(\))607 b(=)g Fl(F)32421 57101 y Fh(h\241)p Ff(1)p Fh(i)34410 57583 y Fm(\()p Fl(x)p Fm(\))g(=)38387 56586 y Fg(P)39789 56937 y Fh(1)39789 57970 y Fi(k)24 b Ff(=1)41782 57583 y Fm(Com)44456 57782 y Fi(k)45024 57583 y Fl(x)45763 57101 y Fi(k)46926 57583 y Fk(satisfy)593 b(the)800 59188 y(di\256er)-66 b(ential)463 b(e)-66 b(quations)16205 62121 y Fl(I)16883 61573 y Fh(0)18300 62121 y Fm(=)1107 b Fe(\241)p Fl(x)22191 61573 y Fh(\241)p Ff(2)23449 62121 y Fl(I)24127 61573 y Ff(2)24948 62121 y Fm(+)295 b(\()p Fl(x)27500 61573 y Fh(\241)p Ff(2)29053 62121 y Fm(+)f Fl(x)31098 61573 y Fh(\241)p Ff(1)32356 62121 y Fm(\))p Fl(I)399 b Fe(\241)296 b Fl(x)35903 61573 y Fh(\241)p Ff(1)37160 62121 y Fm(;)15857 64848 y Fl(C)16883 64299 y Fh(0)18300 64848 y Fm(=)23472 63949 y Fl(C)24498 63467 y Ff(2)p 20552 64542 7392 54 v 20552 65759 a Fl(x)f Fe(\241)h Fm(\(1)f(+)g Fl(x)p Fm(\))p Fl(C)28076 64848 y(:)2751 68693 y Fd(Pro)42 b(of)p Fm(:)1518 b(It)524 b(follo)-36 b(ws)526 b(from)e(the)g(recurrence)f(for)i Fl(n)p Fm(!)f(that)g Fl(F)181 b Fm(\()p Fl(x)p Fm(\))523 b(satis\257es)h Fl(x)357 b Fm(+)g Fl(xF)537 b Fm(+)357 b Fl(x)47500 68211 y Ff(2)48025 68693 y Fl(F)49048 68211 y Fh(0)49882 68693 y Fm(=)522 b Fl(F)181 b Fm(.)800 70298 y(Th)-36 b(us)407 b Fl(F)5092 69816 y Fh(0)5771 70298 y Fm(=)369 b(\(\(1)242 b Fe(\241)h Fl(x)p Fm(\))p Fl(F)422 b Fe(\241)243 b Fl(x)p Fm(\))p Fl(=x)16751 69816 y Ff(2)17277 70298 y Fm(.)570 b(Com)-36 b(bining)408 b(this)f(with)h Fl(F)549 b Fm(=)369 b Fl(I)104 b(=)p Fm(\(1)243 b Fe(\241)f Fl(I)104 b Fm(\))408 b(w)-36 b(e)408 b(obtain)f(the)g(di\256eren)-36 b(tial)p Black 26475 74617 a(5)p Black eop %%Page: 6 6 6 5 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(equation)503 b(for)g Fl(I)104 b Fm(\()p Fl(x)p Fm(\).)784 b(Similarly)-108 b(,)521 b Fl(C)18703 942 y Fh(0)19499 1424 y Fm(=)486 b(1)p Fl(=F)23320 942 y Fh(0)23631 1424 y Fm(\()p Fl(C)95 b Fm(\))485 b(=)h Fl(C)28678 942 y Ff(2)29203 1424 y Fl(=)p Fm(\(\(1)343 b Fe(\241)f Fl(C)95 b Fm(\))p Fl(x)342 b Fe(\241)g Fl(C)95 b Fm(\))502 b(whic)-36 b(h)502 b(is)h(the)e (di\256eren)-36 b(tial)800 3029 y(equation)434 b(for)g Fl(C)95 b Fm(\()p Fl(x)p Fm(\).)p 52228 3029 572 572 v 2751 4634 a(Klazar)539 b([)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.Kl01) [[139 675 145 687] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])f(used)g(the)g(follo)-36 b(wing)540 b(metho)36 b(d)538 b(to)g(sho)-36 b(w)538 b(that)g(a)h(sequence)f(\()p Fl(a)40628 4833 y Fi(n)41254 4634 y Fm(\))g(is)g(not)g(P-recursiv)-36 b(e.)800 6239 y(Supp)36 b(ose)368 b(that)g(the)g(ordinary)h(generating) f(function)h Fl(A)p Fm(\()p Fl(x)p Fm(\))f(is)h(non-analytic)g(and)f (satis\257es)h(a)g(\257rst)e(order)800 7844 y(di\256eren)-36 b(tial)425 b(equation)g Fl(A)13572 7362 y Fh(0)14252 7844 y Fm(=)368 b Fl(R)11 b Fm(\()p Fl(x;)221 b(A)p Fm(\))426 b(where)f Fl(R)436 b Fm(is)425 b(some)g(expression.)576 b(Di\256eren)-36 b(tiating)425 b(this)g(relation-)800 9450 y(ship)557 b(and)h(replacing)g Fl(A)12994 8968 y Fh(0)13862 9450 y Fm(b)-36 b(y)558 b Fl(R)11 b Fm(\()p Fl(x;)221 b(A)p Fm(\),)590 b(the)557 b(deriv)-72 b(ativ)-36 b(es)559 b(of)f Fl(A)g Fm(are)g(expressed)g(as)g Fl(A)44098 8968 y Ff(\()p Fi(k)24 b Ff(\))45979 9450 y Fm(=)580 b Fl(R)48561 9649 y Fi(k)49130 9450 y Fm(\()p Fl(x;)221 b(A)p Fm(\);)800 11055 y Fl(R)1790 11254 y Ff(0)2316 11055 y Fm(\()p Fl(x;)g(A)p Fm(\))369 b(=)g Fl(A)400 b Fm(and)g Fl(R)12235 11254 y Ff(1)12760 11055 y Fm(\()p Fl(x;)221 b(A)p Fm(\))370 b(=)f Fl(R)11 b Fm(\()p Fl(x;)221 b(A)p Fm(\).)567 b(Substituting)399 b Fl(R)31463 11254 y Fi(k)32032 11055 y Fm(\()p Fl(x;)221 b(A)p Fm(\))400 b(in)g(the)g(equation)g(of)h(D-\257niteness)16301 13977 y Fl(b)16854 14176 y Ff(0)17380 13977 y Fl(A)295 b Fm(+)g Fl(b)20510 14176 y Ff(1)21036 13977 y Fl(A)22011 13429 y Fh(0)22617 13977 y Fm(+)f Fl(b)24476 14176 y Ff(2)25002 13977 y Fl(A)25977 13429 y Fh(00)26838 13977 y Fm(+)h Fe(\242)221 b(\242)g(\242)296 b Fm(+)f Fl(b)31850 14176 y Fi(s)32340 13977 y Fl(A)33315 13429 y Ff(\()p Fi(s)p Ff(\))34907 13977 y Fm(=)368 b(0)p Fl(;)800 16900 y Fm(where)441 b Fl(s)381 b Fe(\270)g Fm(1,)444 b Fl(b)8981 17099 y Fi(i)9738 16900 y Fe(2)381 b Fd(C)p Fm(\()p Fl(x)p Fm(\))440 b(and)h Fl(b)17365 17099 y Fi(s)18237 16900 y Fe(6)p Fm(=)381 b(0,)443 b(w)-36 b(e)441 b(get)g(a)g(non-di\256eren)-36 b(tial)440 b(equation)40630 15904 y Fg(P)42032 16255 y Fi(s)42032 17288 y(k)24 b Ff(=0)44025 16900 y Fl(b)44578 17099 y Fi(k)45147 16900 y Fl(R)46137 17099 y Fi(k)46706 16900 y Fm(\()p Fl(x;)221 b(A)p Fm(\))381 b(=)g(0.)800 18505 y(If)533 b Fl(R)543 b Fm(is)532 b(suc)-36 b(h)532 b(that)g(the)f(expressions)i Fl(R)21293 18704 y Ff(0)21819 18505 y Fl(;)221 b(R)23391 18704 y Ff(1)23917 18505 y Fl(;)g(R)25489 18704 y Ff(2)26016 18505 y Fl(;)g(:)g(:)g(:)755 b Fm(are)533 b(\(i\))f(analytic)h(or)g(ev)-36 b(en)532 b(algebraic)h(and)f(\(ii\))800 20110 y(linearly)469 b(indep)36 b(enden)-36 b(t)466 b(o)-36 b(v)g(er)469 b Fd(C)p Fm(\()p Fl(x)p Fm(\),)477 b(w)-36 b(e)468 b(ha)-36 b(v)g(e)468 b(a)g(non)-36 b(trivial)469 b(analytic)g(equation)g(for)f Fl(A)p Fm(.)682 b(This)469 b(implies)800 21716 y(that)500 b Fl(A)g Fm(is)h(analytic)h(\(see)e(Klazar's)i(pap)36 b(er)500 b([)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.Kl01) [[283 522 289 534] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])h(for)g(more)g(details\))f(whic)-36 b(h)501 b(is)f(a)h(con)-36 b(tradiction.)779 b(So)500 b Fl(A)800 23321 y Fm(cannot)433 b(b)36 b(e)434 b(D-\257nite)e(and)i(the)f(sequence)g(of)h(its)g(co)36 b(e\261cien)-36 b(ts)434 b(cannot)f(b)36 b(e)434 b(P-recursiv)-36 b(e.)2751 24926 y(T)-108 b(o)507 b(state)g(the)f(result)h(of)g([)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.Kl01) [[215 493 221 505] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])g(precisely)-108 b(,)526 b(w)-36 b(e)507 b(remind)f(the)g(reader)h(that)f(a)i(p)36 b(o)-36 b(w)g(er)506 b(series)i Fl(R)11 b Fm(\()p Fl(x;)221 b(y)48 b Fm(\))493 b Fe(2)800 26531 y Fd(C)p Fm([[)p Fl(x;)221 b(y)48 b Fm(]])664 b(is)e(analytic)g(if)g(it)g(absolutely)g(con)-36 b(v)g(erges)663 b(in)e(a)h(neigh)-36 b(b)36 b(orho)g(o)g(d)661 b(of)h(the)f(origin)h(and)f(that)800 28136 y Fl(R)11 b Fm(\()p Fl(x;)221 b(y)48 b Fm(\))369 b Fe(2)g Fd(C)p Fm(\(\()p Fl(x;)221 b(y)48 b Fm(\)\))320 b(is)g(an)f(analytic)i(Lauren) -36 b(t)318 b(series)i(if,)344 b(for)320 b(some)g(p)36 b(ositiv)-36 b(e)321 b(in)-36 b(teger)319 b Fl(k)45 b Fm(,)343 b(\()p Fl(xy)48 b Fm(\))46961 27654 y Fi(k)47529 28136 y Fl(R)11 b Fm(\()p Fl(x;)221 b(y)48 b Fm(\))369 b Fe(2)800 29741 y Fd(C)p Fm([[)p Fl(x;)221 b(y)48 b Fm(]])579 b(is)f(analytic.)1011 b(Theorem)577 b(1)h(of)g([)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.Kl01) [[271 449 277 461] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])f(sa)-36 b(ys)578 b(that)f(if)h Fl(A)614 b Fe(2)f Fd(C)p Fm([[)p Fl(x)p Fm(]])579 b(is)f(non-analytic,)614 b Fl(R)11 b Fm(\()p Fl(x;)221 b(y)48 b Fm(\))613 b Fe(2)800 31346 y Fd(C)p Fm(\(\()p Fl(x;)221 b(y)48 b Fm(\)\))557 b(is)h(analytic,)589 b Fl(A)14335 30864 y Fh(0)15225 31346 y Fm(=)579 b Fl(R)11 b Fm(\()p Fl(x;)221 b(A)p Fm(\),)589 b(and)557 b Fl(R)568 b Fm(con)-36 b(tains)557 b(at)h(least)f(one)g(monomial)i Fl(ax)46442 30864 y Fi(i)46817 31346 y Fl(y)47499 30864 y Fi(j)47986 31346 y Fm(,)588 b Fl(a)579 b Fe(6)p Fm(=)g(0,)800 32951 y(with)418 b Fl(j)444 b(<)368 b Fm(0,)422 b(then)416 b Fl(A)i Fm(is)g(not)f (D-\257nite.)572 b(This)418 b(result)g(applies)f(directly)h(neither)f (to)h Fl(I)104 b Fm(\()p Fl(x)p Fm(\))417 b(nor)h Fl(C)95 b Fm(\()p Fl(x)p Fm(\))417 b(\(see)800 34556 y(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 413 w(2)p (#definition.2) [[142 406 148 418] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))412 b(b)36 b(ecause)413 b(in)f(the)g(case)h(of)g Fl(I)104 b Fm(\()p Fl(x)p Fm(\))412 b(the)g(last)h(condition)f(on)g Fl(R)424 b Fm(is)412 b(not)g(satis\257ed)g(and)g(in)h(the)800 36161 y(case)434 b(of)g Fl(C)95 b Fm(\()p Fl(x)p Fm(\))434 b(the)f(righ)-36 b(t)433 b(hand)g(side)g Fl(R)445 b Fm(cannot)433 b(ev)-36 b(en)434 b(b)36 b(e)433 b(expanded)g(as)h(a)g(Lauren)-36 b(t)432 b(series.)2751 37766 y(Ho)-36 b(w)g(ev)g(er,)646 b(the)602 b(substitution)f Fl(x)411 b Fe(\241)f Fm(\(1)g(+)g Fl(x)p Fm(\))p Fl(C)95 b Fm(\()p Fl(x)p Fm(\))657 b(=)f Fl(\265)36 b Fm(\()p Fl(x)p Fm(\))602 b(transforms)h(the)f(second)g (di\256eren)-36 b(tial)800 39372 y(equation)434 b(of)g(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 434 w(2)p (#definition.2) [[203 363 209 375] [1 1 1 [3 3]] [0 0 1]] pdfm Black 434 w(in)-36 b(to)19431 43010 y Fl(\265)20073 42461 y Fh(0)20752 43010 y Fm(=)369 b Fe(\241)24162 42111 y Fl(x)24901 41629 y Ff(2)p 23299 42704 2992 54 v 23299 43921 a Fm(1)296 b(+)e Fl(x)26719 43010 y Fe(\242)27516 42111 y Fm(1)p 27516 42704 651 54 v 27520 43921 a Fl(\265)28594 43010 y Fm(+)30034 42111 y(1)h(+)g(2)p Fl(x)p 30034 42704 3642 54 v 30359 43921 a Fm(1)g(+)g Fl(x)33808 43010 y(:)800 46447 y Fm(No)-36 b(w)506 b(all)f(conditions)g(are)g(satis\257ed)g(\()p Fl(F)181 b Fm(\()p Fl(x)p Fm(\))504 b(is)h(clearly)h(non-analytic)g (whic)-36 b(h)504 b(implies)i(that)e Fl(C)95 b Fm(\()p Fl(x)p Fm(\))505 b(and)800 48052 y Fl(\265)36 b Fm(\()p Fl(x)p Fm(\))495 b(are)g(non-analytic\))g(and)g(th)-36 b(us)494 b Fl(\265)36 b Fm(\()p Fl(x)p Fm(\))495 b(is)g(not)g (D-\257nite)f(b)-36 b(y)495 b(Theorem)g(1)g(of)h([)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.Kl01) [[445 285 450 297] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(].)763 b(The)495 b(dep)36 b(endence)800 49657 y(of)460 b Fl(C)95 b Fm(\()p Fl(x)p Fm(\))458 b(and)h Fl(S)77 b Fm(\()p Fl(x)p Fm(\))459 b(on)f Fl(\265)36 b Fm(\()p Fl(x)p Fm(\))459 b(and)g(the)f(fact)i(that)e(D-\257nite)g(p) 36 b(o)-36 b(w)g(er)459 b(series)g(form)h(a)f Fd(C)p Fm(\()p Fl(x)p Fm(\)-algebra)g(\([)p 0 1 0 0 TeXcolorcmyk(13)p (#cite.St02) [[532 270 544 282] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(,)800 51262 y(Theorem)434 b(6.4.9]\))h(sho)-36 b(ws)434 b(that)f(neither)g Fl(C)95 b Fm(\()p Fl(x)p Fm(\))433 b(nor)g Fl(S)77 b Fm(\()p Fl(x)p Fm(\))434 b(is)g(D-\257nite.)2751 52867 y(In)449 b(order)f(to)h(deal)g(with)g (the)g(case)g(of)g Fl(I)104 b Fm(\()p Fl(x)p Fm(\),)453 b(w)-36 b(e)449 b(use)g(this)g(opp)36 b(ortunit)-36 b(y)448 b(to)h(complemen)-36 b(t)448 b(Theorem)800 54472 y(1)441 b(of)g([)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.Kl01) [[106 227 112 239] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])g(in)f(whic)-36 b(h)441 b Fl(R)391 b Fe(2)380 b Fd(C)p Fm(\(\()p Fl(x;)221 b(y)48 b Fm(\)\))441 b(b)-36 b(y)440 b(the)g(follo)-36 b(wing)442 b(theorem)e(whic)-36 b(h)441 b(treats)f(the)g(case)h Fl(R)391 b Fe(2)380 b Fd(C)p Fm(\()p Fl(x;)221 b(y)48 b Fm(\).)800 56078 y(Neither)448 b(of)g(the)g(theorems)f(subsumes)g(the)g(other)h(b)36 b(ecause)448 b(not)f(ev)-36 b(ery)449 b(rational)f(function)g(in)g Fl(x)g Fm(and)f Fl(y)800 57683 y Fm(can)502 b(b)36 b(e)501 b(represen)-36 b(ted)500 b(b)-36 b(y)502 b(an)g(elemen)-36 b(t)501 b(of)i Fd(C)p Fm(\(\()p Fl(x;)221 b(y)48 b Fm(\)\))502 b(\(as)f(w)-36 b(e)503 b(ha)-36 b(v)g(e)501 b(seen\))h(and,)518 b(of)503 b(course,)519 b(not)501 b(ev)-36 b(ery)800 59288 y(Lauren)g(t)408 b(series)i(sums)f(up)g(to)g(a)h(rational)h(function.) 570 b(Ho)-36 b(w)g(ev)g(er,)415 b(the)409 b(next)g(theorem)g(seems)h (to)g(b)36 b(e)409 b(more)800 60893 y(useful)477 b(b)36 b(ecause)477 b(in)g(b)36 b(oth)477 b(examples)h(in)f([)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.Kl01) [[267 169 273 181] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])g(and)g(b)36 b(oth)476 b(examples)i(here)f(the)g(righ)-36 b(t)476 b(hand)h(side)g Fl(R)11 b Fm(\()p Fl(x;)221 b(y)48 b Fm(\))800 62498 y(is,)434 b(in)g(fact,)g(a)g(rational)g(function.)p Black 800 65530 a Fd(Theorem)499 b(3)p Black 651 w Fk(L)-66 b(et)558 b Fl(P)36 b(;)221 b(Q)546 b Fe(2)d Fd(C)p Fm([)p Fl(x;)221 b(y)48 b Fm(])561 b Fk(b)-66 b(e)559 b(two)h(nonzer)-66 b(o)559 b(c)-66 b(oprime)558 b(p)-66 b(olynomials)559 b(and)g Fl(A)544 b Fe(2)g Fd(C)p Fm([[)p Fl(x)p Fm(]])561 b Fk(b)-66 b(e)559 b(a)800 67135 y(non-analytic)463 b(p)-66 b(ower)465 b(series)g(which)g(satis\257es)g(the)f(di\256er)-66 b(ential)463 b(e)-66 b(quation)22800 70717 y Fl(A)23775 70168 y Fh(0)24454 70717 y Fm(=)25973 69818 y Fl(P)181 b Fm(\()p Fl(x;)221 b(A)p Fm(\))p 25968 70411 4339 54 v 25968 71628 a Fl(Q)p Fm(\()p Fl(x;)g(A)p Fm(\))30439 70717 y Fl(:)p Black 26475 74617 a Fm(6)p Black eop %%Page: 7 7 7 6 bop Black 0 TeXcolorgray Black Black 800 1424 a Fk(If)482 b Fm(deg)4151 1738 y Fi(y)4925 1424 y Fl(Q)402 b Fm(=)f(0)483 b Fk(and)g Fm(deg)13414 1738 y Fi(y)14188 1424 y Fl(P)583 b Fe(\267)402 b Fm(1)483 b Fk(then)f Fl(A)h Fk(is,)j(trivial)66 b(ly,)486 b(D-\257nite.)649 b(In)482 b(al)66 b(l)484 b(r)-66 b(emaining)479 b(c)-66 b(ases)483 b Fl(A)g Fk(is)g(not)800 3029 y(D-\257nite.)2751 6073 y Fd(Pro)42 b(of)p Fm(:)1122 b(The)400 b(\257rst)f(claim)h(is)g(clear.)568 b(If)400 b(deg)24690 6387 y Fi(y)25464 6073 y Fl(Q)369 b Fm(=)g(0)399 b(and)h Fl(r)405 b Fm(=)368 b(deg)36130 6387 y Fi(y)36903 6073 y Fl(P)550 b Fe(\270)369 b Fm(2)400 b(then)f Fl(A)44647 5591 y Fh(0)45326 6073 y Fm(=)369 b Fl(a)47390 6272 y Ff(0)48141 6073 y Fm(+)226 b Fl(a)50062 6272 y Ff(1)50588 6073 y Fl(A)f Fm(+)800 7678 y Fe(\242)c(\242)g(\242)296 b Fm(+)f Fl(a)4635 7877 y Fi(r)5141 7678 y Fl(A)6116 7196 y Fi(r)7055 7678 y Fm(where)434 b Fl(a)11496 7877 y Fi(i)12240 7678 y Fe(2)369 b Fd(C)p Fm(\()p Fl(x)p Fm(\),)434 b Fl(r)405 b Fe(\270)369 b Fm(2,)434 b(and)f Fl(a)24170 7877 y Fi(r)25045 7678 y Fe(6)p Fm(=)369 b(0.)578 b(Di\256eren)-36 b(tiation)434 b(b)-36 b(y)434 b Fl(x)f Fm(giv)-36 b(es)11146 10612 y Fl(A)12121 10063 y Ff(\()p Fi(k)24 b Ff(\))13791 10612 y Fm(=)369 b Fl(R)16162 10811 y Fi(k)16731 10612 y Fm(\()p Fl(x;)221 b(A)p Fm(\))369 b(=)g Fl(a)22472 10811 y Ff(0)p Fi(;k)24067 10612 y Fm(+)295 b Fl(a)26057 10811 y Ff(1)p Fi(;k)27358 10612 y Fl(A)g Fm(+)g Fe(\242)221 b(\242)g(\242)296 b Fm(+)e Fl(a)33769 10811 y Fi(k)24 b(r)i Fh(\241)p Fi(k)e Ff(+1)p Fi(;k)38011 10612 y Fl(A)38986 10063 y Fi(k)g(r)i Fh(\241)p Fi(k)e Ff(+1)800 13545 y Fm(where)434 b Fl(a)5241 13744 y Fi(i;j)6678 13545 y Fe(2)368 b Fd(C)p Fm(\()p Fl(x)p Fm(\))434 b(and)10484 16479 y Fl(a)11167 16678 y Fi(k)24 b(r)i Fh(\241)p Fi(k)e Ff(+1)p Fi(;k)15778 16479 y Fm(=)368 b Fl(r)36 b Fm(\(2)p Fl(r)332 b Fe(\241)295 b Fm(1\)\(3)p Fl(r)332 b Fe(\241)296 b Fm(2\))221 b Fl(:)g(:)g(:)i Fm(\(\()p Fl(k)340 b Fe(\241)295 b Fm(1\))p Fl(r)332 b Fe(\241)295 b Fl(k)341 b Fm(+)294 b(2\))p Fl(a)39786 15930 y Fi(k)39786 16807 y(r)40724 16479 y Fe(6)p Fm(=)369 b(0)p Fl(:)800 19412 y Fm(Th)-36 b(us)543 b Fl(R)5195 19611 y Fi(k)5764 19412 y Fm(\()p Fl(x;)221 b(y)48 b Fm(\))556 b Fe(2)f Fd(C)p Fm(\()p Fl(x)p Fm(\)[)p Fl(y)48 b Fm(])544 b(ha)-36 b(v)g(e)544 b Fl(y)48 b Fm(-degrees)543 b Fl(k)45 b(r)406 b Fe(\241)370 b Fl(k)415 b Fm(+)370 b(1,)571 b Fl(k)601 b Fm(=)556 b(0)p Fl(;)221 b Fm(1)p Fl(;)g Fm(2)p Fl(;)g(:)g(:)g(:)226 b Fm(,)571 b(whic)-36 b(h)543 b(is)h(for)g Fl(r)592 b Fe(\270)556 b Fm(2)544 b(a)800 21017 y(strictly)561 b(increasing)g (sequence.)960 b(Therefore)561 b Fl(R)24866 21216 y Ff(0)25392 21017 y Fl(;)221 b(R)26964 21216 y Ff(1)27491 21017 y Fl(;)g(R)29063 21216 y Ff(2)29589 21017 y Fl(;)g(:)g(:)g(:)785 b Fm(are)561 b(linearly)g(indep)36 b(enden)-36 b(t)559 b(o)-36 b(v)g(er)561 b Fd(C)p Fm(\()p Fl(x)p Fm(\))800 22622 y(and,)433 b(b)-36 b(y)434 b(the)f(ab)36 b(o)-36 b(v)g(e)434 b(discussion,)g Fl(A)f Fm(is)h(not)g Fl(D)36 b Fm(-\257nite.)2751 24227 y(In)416 b(the)h(remaining)f(case)i(deg) 17341 24541 y Fi(y)18114 24227 y Fl(Q)369 b Fe(\270)h Fm(1.)573 b(Di\256eren)-36 b(tiation)416 b(of)i Fl(A)33575 23745 y Fh(0)34254 24227 y Fm(=)369 b Fl(R)11 b Fm(\()p Fl(x;)221 b(A)p Fm(\))369 b(=)g Fl(P)181 b Fm(\()p Fl(x;)221 b(A)p Fm(\))p Fl(=Q)p Fm(\()p Fl(x;)g(A)p Fm(\))418 b(b)-36 b(y)800 25970 y Fl(x)434 b Fm(giv)-36 b(es)434 b Fl(A)6134 25488 y Ff(\()p Fi(k)24 b Ff(\))7804 25970 y Fm(=)369 b Fl(R)10175 26169 y Fi(k)10744 25970 y Fm(\()p Fl(x;)221 b(A)p Fm(\))434 b(where)f Fl(R)19233 26169 y Fi(k)19802 25970 y Fm(\()p Fl(x;)221 b(y)48 b Fm(\))369 b Fe(2)g Fd(C)p Fm(\()p Fl(x;)221 b(y)48 b Fm(\).)579 b(F)-108 b(or)433 b(example,)15325 29636 y Fl(R)16315 29835 y Ff(2)17948 29636 y Fm(=)20199 28738 y(\()p Fl(P)21543 28937 y Fi(x)22424 28738 y Fm(+)294 b Fl(P)24568 28937 y Fi(y)25121 28738 y Fl(R)26111 28937 y Ff(1)26637 28738 y Fm(\))p Fl(Q)h Fe(\241)g Fl(P)181 b Fm(\()p Fl(Q)32351 28937 y Fi(x)33231 28738 y Fm(+)295 b Fl(Q)35568 28937 y Fi(y)36121 28738 y Fl(R)37111 28937 y Ff(1)37636 28738 y Fm(\))p 20199 29331 17944 54 v 28393 30547 a Fl(Q)29423 30164 y Ff(2)17948 33143 y Fm(=)20199 32245 y Fl(P)21037 32444 y Fi(x)21623 32245 y Fl(Q)g Fe(\241)g Fl(P)181 b(Q)26325 32444 y Fi(x)p 20199 32838 6712 54 v 22777 34055 a Fl(Q)23807 33671 y Ff(2)27338 33143 y Fm(+)28778 32245 y Fl(P)g Fm(\()p Fl(P)31141 32444 y Fi(y)31693 32245 y Fl(Q)296 b Fe(\241)f Fl(P)181 b(Q)36396 32444 y Fi(y)36949 32245 y Fm(\))p 28778 32838 8677 54 v 32338 34055 a Fl(Q)33368 33671 y Ff(3)37587 33143 y Fl(:)800 36748 y Fm(Let)408 b Fl(\256)8 b Fm(,)415 b Fl(Q)p Fm(\()p Fl(x;)221 b(\256)8 b Fm(\))370 b(=)f(0,)414 b(b)36 b(e)409 b(a)g(p)36 b(ole)409 b(of)g Fl(R)20098 36947 y Ff(1)20624 36748 y Fm(\()p Fl(x;)221 b(y)48 b Fm(\))409 b(of)h(order)e(ord)30755 36947 y Fi(\256)31414 36748 y Fm(\()p Fl(R)32910 36947 y Ff(1)33436 36748 y Fm(\))369 b(=)f(ord)37570 36947 y Fi(\256)38230 36748 y Fm(\()p Fl(P)108 b(=Q)p Fm(\))370 b(=)e Fe(\241)p Fm(ord)46530 36947 y Fi(\256)47190 36748 y Fm(\()p Fl(Q)p Fm(\))h(=)f Fl(l)399 b Fe(\270)800 38353 y Fm(1.)592 b(W)-108 b(e)439 b(ha)-36 b(v)g(e)438 b(ord)9530 38552 y Fi(\256)10189 38353 y Fm(\(\()p Fl(P)12039 38552 y Fi(x)12624 38353 y Fl(Q)299 b Fe(\241)f Fl(P)181 b(Q)17333 38552 y Fi(x)17918 38353 y Fm(\))p Fl(Q)19454 37871 y Fh(\241)p Ff(2)20712 38353 y Fm(\))376 b Fe(\267)h Fm(2)p Fl(l)468 b Fm(and)438 b(ord)28922 38552 y Fi(\256)29582 38353 y Fm(\()p Fl(P)181 b Fm(\()p Fl(P)32451 38552 y Fi(y)33003 38353 y Fl(Q)298 b Fe(\241)h Fl(P)181 b(Q)37712 38552 y Fi(y)38264 38353 y Fm(\))p Fl(Q)39800 37871 y Fh(\241)p Ff(3)41058 38353 y Fm(\))376 b(=)g(3)p Fl(l)329 b Fm(+)298 b(ord)47882 38552 y Fi(\256)48542 38353 y Fm(\()p Fl(P)49886 38552 y Fi(y)50438 38353 y Fl(Q)h Fe(\241)800 39958 y Fl(P)181 b(Q)2849 40157 y Fi(y)3401 39958 y Fm(\))369 b(=)g(2)p Fl(l)198 b Fm(+)169 b(1)373 b(since)e(ord)14099 40157 y Fi(\256)14759 39958 y Fm(\()p Fl(P)181 b Fm(\))368 b(=)h(0,)385 b(ord)21814 40157 y Fi(\256)22473 39958 y Fm(\()p Fl(P)23817 40157 y Fi(y)24370 39958 y Fl(Q)p Fm(\))369 b Fe(\267)g(\241)p Fl(l)29 b Fm(,)385 b(and)371 b(ord)34218 40157 y Fi(\256)34878 39958 y Fm(\()p Fl(P)181 b(Q)37433 40157 y Fi(y)37985 39958 y Fm(\))369 b(=)f Fe(\241)p Fl(l)198 b Fm(+)169 b(1.)559 b(So)372 b(ord)48232 40157 y Fi(\256)48892 39958 y Fm(\()p Fl(R)50388 40157 y Ff(2)50914 39958 y Fm(\))c(=)800 41563 y(2)p Fl(l)391 b Fm(+)360 b(1.)869 b(In)530 b(general,)555 b(the)529 b(same)i(argumen)-36 b(t)529 b(sho)-36 b(ws)530 b(that)g(ord)32395 41762 y Fi(\256)33054 41563 y Fm(\()p Fl(R)34550 41762 y Fi(k)24 b Ff(+1)36321 41563 y Fm(\))534 b(=)e(2)362 b Fe(\242)f Fm(ord)42525 41762 y Fi(\256)43185 41563 y Fm(\()p Fl(R)44681 41762 y Fi(k)45250 41563 y Fm(\))f(+)h(1.)868 b(Hence)800 43169 y(ord)2679 43368 y Fi(\256)3338 43169 y Fm(\()p Fl(R)4834 43368 y Fi(k)5403 43169 y Fm(\))557 b(=)g(2)8685 42687 y Fi(k)24 b Fh(\241)p Ff(1)10456 43169 y Fl(l)400 b Fm(+)370 b(2)13275 42687 y Fi(k)24 b Fh(\241)p Ff(1)15417 43169 y Fe(\241)371 b Fm(1,)572 b Fl(k)602 b Fm(=)557 b(1)p Fl(;)221 b Fm(2)p Fl(;)g(:)g(:)g(:)k Fm(.)910 b(This)544 b(is)h(a)f(strictly)h (increasing)f(sequence)g(and)g(w)-36 b(e)800 44774 y(conclude)519 b(again,)542 b(since)519 b Fl(R)14432 44973 y Ff(0)14958 44774 y Fl(;)221 b(R)16530 44973 y Ff(1)17056 44774 y Fl(;)g(R)18628 44973 y Ff(2)19155 44774 y Fl(;)g(:)g(:)g(:)743 b Fm(are)519 b(linearly)i(indep)36 b(enden)-36 b(t)517 b(o)-36 b(v)g(er)520 b Fd(C)p Fm(\()p Fl(x)p Fm(\),)541 b(that)519 b Fl(A)g Fm(is)g(not)g Fl(D)36 b Fm(-)800 46379 y(\257nite.)p 52228 46379 572 572 v 2751 47984 a(Prop)g(osition)p 0 1 0 0 TeXcolorcmyk 455 w(2)p (#definition.2) [[160 285 166 297] [1 1 1 [3 3]] [0 0 1]] pdfm Black 456 w(and)454 b(Theorem)p 0 1 0 0 TeXcolorcmyk 455 w(3)p (#definition.3) [[242 285 248 297] [1 1 1 [3 3]] [0 0 1]] pdfm Black 455 w(sho)-36 b(w)455 b(that)g Fl(I)104 b Fm(\()p Fl(x)p Fm(\))455 b(is)g(not)f Fl(D)36 b Fm(-\257nite)454 b(and)h(w)-36 b(e)455 b(can)g(summarize)g(the)800 49589 y(results)433 b(of)i(this)e(section)h(in)f(the)g(follo)-36 b(wing)436 b(corollary)-108 b(.)p Black 800 52633 a Fd(Corollary)500 b(4)p Black 650 w Fk(The)465 b(se)-66 b(quenc)g(es)464 b Fm(\()p Fl(i)18254 52832 y Fi(n)18880 52633 y Fm(\))p Fk(,)g Fm(\(Com)23428 52832 y Fi(n)24055 52633 y Fm(\))p Fk(,)g(and)h Fm(\()p Fl(s)29067 52832 y Fi(n)29692 52633 y Fm(\))g Fk(ar)-66 b(e)465 b(not)f(P-r)-66 b(e)g(cursive.)800 57070 y Fn(3)2152 b(Asymptotics)800 59991 y Fm(W)-108 b(e)481 b(turn)f(no)-36 b(w)482 b(to)f(the)f(computation)h(of)h(an)f (asymptotic)h(expansion)g(for)f(the)g(n)-36 b(um)g(b)36 b(ers)480 b Fl(s)46782 60190 y Fi(n)47407 59991 y Fm(.)722 b(W)-108 b(e)481 b(will)800 61596 y(pro)-36 b(v)g(e)434 b(that:)p Black 800 64308 a Fd(Theorem)499 b(5)p Black 15374 66345 a Fl(s)15987 66544 y Fi(n)16982 66345 y Fm(=)18496 65446 y Fl(n)p Fm(!)p 18496 66039 1138 54 v 18513 67256 a(e)19091 66872 y Ff(2)19988 64472 y Fg(\265)20965 66345 y Fm(1)296 b Fe(\241)23435 65446 y Fm(4)p 23372 66039 777 54 v 23372 67256 a Fl(n)24577 66345 y Fm(+)28110 65446 y(2)p 26016 66039 4839 54 v 26016 67256 a Fl(n)p Fm(\()p Fl(n)g Fe(\241)f Fm(1\))31283 66345 y(+)f Fl(O)36 b Fm(\()p Fl(n)34901 65796 y Fh(\241)p Ff(3)36159 66345 y Fm(\))36665 64472 y Fg(\266)37864 66345 y Fl(:)p Black 26475 74617 a Fm(7)p Black eop %%Page: 8 8 8 7 bop Black 0 TeXcolorgray Black Black 2751 1424 a Fm(Our)626 b(metho)36 b(ds)626 b(are)g(suc)-36 b(h)626 b(that,)675 b(in)626 b(principle,)675 b(higher)626 b(order)h(terms)f (could)g(b)36 b(e)627 b(obtained)f(as)h(a)800 3029 y(matter)364 b(of)h(brute)e(force)i(computation.)555 b(In)364 b(order)g(to)g(carry)h (out)e(this)h(expansion)h(w)-36 b(e)364 b(will)i(\257rst)d(consider)800 4634 y(p)36 b(erm)-36 b(utations)409 b(whic)-36 b(h)409 b(ma)-36 b(y)410 b(not)f(b)36 b(e)409 b(simple,)415 b(but)409 b(whose)g(non-trivial)h(blo)36 b(c)-36 b(ks)411 b(all)f(ha)-36 b(v)g(e)410 b(length)f(greater)800 6239 y(than)434 b(some)i(\257xed)e (v)-72 b(alue)436 b Fl(m)p Fm(.)582 b(W)-108 b(e)435 b(will)h(apply)g(inclusion-exclusion)f(argumen)-36 b(ts)434 b(\(dressed)g(in)h(the)g(form)800 7844 y(of)447 b(generating)g (functions)f([)p 0 1 0 0 TeXcolorcmyk(5)p (#cite.FS01) [[204 646 210 658] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(,)p 0 1 0 0 TeXcolorcmyk 447 w(6)p (#cite.GJ01) [[217 646 223 658] [1 1 1 [3 3]] [0 0 1]] pdfm Black(]\),)k(an)d(argumen)-36 b(t)445 b(whic)-36 b(h)447 b(allo)-36 b(ws)448 b(us)e(to)h(reduce)e(the)h(n)-36 b(um)g(b)36 b(er)445 b(of)i(terms)800 9450 y(considered,)433 b(and)g(a)h(b)36 b(o)g(otstrapping)434 b(approac)-36 b(h.)2751 11055 y(The)397 b(case)g Fl(m)369 b Fm(=)g(2,)404 b(w)-36 b(as)398 b(already)g(considered)e(b)-36 b(y)397 b(Kaplansky)h([)p 0 1 0 0 TeXcolorcmyk(7)p (#cite.Ka01) [[381 618 386 630] [1 1 1 [3 3]] [0 0 1]] pdfm Black(].)567 b(P)-36 b(erm)g(utations)396 b(of)h(this)g(t)-36 b(yp)36 b(e)397 b(are)800 12660 y(those)342 b(in)g(whic)-36 b(h)342 b(no)g(t)-36 b(w)g(o)343 b(elemen)-36 b(ts)342 b(consecutiv)-36 b(e)342 b(in)g(p)36 b(osition)343 b(are)f(also)h (consecutiv)-36 b(e)343 b(in)f(v)-72 b(alue)343 b(\(in)e(either)800 14265 y(order\).)794 b(These)506 b(w)-36 b(ere)506 b(called)h (irreducible)e(p)36 b(erm)-36 b(utations)505 b(b)-36 b(y)506 b(A)-36 b(tkinson)505 b(and)h(Stitt)f([)p 0 1 0 0 TeXcolorcmyk(2)p (#cite.AS01) [[470 589 475 601] [1 1 1 [3 3]] [0 0 1]] pdfm Black(],)525 b(but)505 b(there)g(is)800 15870 y(no)482 b(standard)g(terminology)i(in)e(the)g(\257eld.)725 b(Indeed)482 b(the)g(p)36 b(erm)-36 b(utations)481 b(that)h(w)-36 b(e)483 b(ha)-36 b(v)g(e)483 b(referred)f(to)h(as)800 17475 y(plus)433 b(and)g(min)-36 b(us)433 b(indecomp)36 b(osable)434 b(ha)-36 b(v)g(e)434 b(also)g(b)36 b(een)433 b(called)h(irreducible)f(in)h(other)f(con)-36 b(texts.)2751 19080 y(An)318 b(am)-36 b(using)318 b(equiv)-72 b(alen)-36 b(t)319 b(form)g(for)g(the)f(case)h Fl(m)368 b Fm(=)h(2)319 b(is)f(that)g(the)g(n)-36 b(um)g(b)36 b(er)317 b(of)i(suc)-36 b(h)317 b(p)36 b(erm)-36 b(utations)318 b(is)800 20685 y(also)393 b(the)e(n)-36 b(um)g(b)36 b(er)390 b(of)i(w)-36 b(a)g(ys)393 b(of)f(placing)g Fl(n)g Fm(m)-36 b(utually)392 b(non-attac)-36 b(king)392 b Fk(kr)-66 b(o)g(oks)391 b Fm(on)g(an)h Fl(n)210 b Fe(\243)g Fl(n)391 b Fm(c)-36 b(hessb)36 b(oard.)800 22290 y(A)622 b(kro)36 b(ok)623 b(is)f(a)g(piece)g(whic)-36 b(h)622 b(can)g(mo)-36 b(v)g(e)622 b(either)f(lik)-36 b(e)623 b(a)f(king,)670 b(or)622 b(a)g(ro)36 b(ok)623 b(in)f(c)-36 b(hess.)1142 b(Kaplansky's)800 23895 y(expansion)434 b(is:)18324 25292 y Fl(n)p Fm(!)p 18324 25885 1138 54 v 18341 27102 a(e)18919 26718 y Ff(2)19815 24318 y Fg(\265)20793 26191 y Fm(1)296 b Fe(\241)25294 25292 y Fm(2)p 23200 25885 4839 54 v 23200 27102 a Fl(n)p Fm(\()p Fl(n)g Fe(\241)f Fm(1\))28466 26191 y(+)g Fl(O)36 b Fm(\()p Fl(n)32085 25642 y Fh(\241)p Ff(3)33343 26191 y Fm(\))33849 24318 y Fg(\266)35048 26191 y Fl(:)2751 29205 y Fm(In)409 b(fact)h(he)f(deriv)-36 b(es)409 b(asymptotic)h (forms)g(for)g(the)f(n)-36 b(um)g(b)36 b(er)407 b(of)j(p)36 b(erm)-36 b(utations)409 b(con)-36 b(taining)409 b(exactly)i Fl(r)800 30810 y Fm(blo)36 b(c)-36 b(ks)394 b(of)g(length)f(2)g(for)h (an)-36 b(y)393 b Fl(r)36 b Fm(.)566 b(Our)392 b(metho)36 b(ds)392 b(parallel)j(his,)401 b(and)393 b(could)g(also)h(b)36 b(e)393 b(used)f(to)i(deriv)-36 b(e)393 b(suc)-36 b(h)800 32415 y(detailed)434 b(information.)2751 34020 y(The)566 b(decomp)36 b(osition)566 b(pro)-36 b(vided)565 b(b)-36 b(y)565 b(Theorem)p 0 1 0 0 TeXcolorcmyk 566 w(1)p (#definition.1) [[318 411 324 423] [1 1 1 [3 3]] [0 0 1]] pdfm Black 566 w(of)i(a)f(p)36 b(erm)-36 b(utation)564 b(in)-36 b(to)566 b(its)g(maximal)h(prop)36 b(er)800 35626 y(blo)g(c)-36 b(ks)564 b(represen)-36 b(ts)562 b(a)i(top)f(do)-36 b(wn)563 b(view)h(of)g(ho)-36 b(w)563 b(non-simple)g(p)36 b(erm)-36 b(utations)562 b(are)i(constructed)e(from)800 37231 y(simple)335 b(ones.)545 b(There)334 b(is)h(a)f(corresp)36 b(onding)334 b(b)36 b(ottom-up)333 b(view)j(that)e(fo)36 b(cuses)335 b(on)f(minimal)h(non-singleton)800 38836 y(blo)36 b(c)-36 b(ks,)394 b(put)381 b(together)i(in)f(an)g(arbitrary)h(order.)561 b(By)383 b(a)g Fk(minimal)416 b(blo)-66 b(ck)381 b Fm(in)i Fl(\274)430 b Fm(w)-36 b(e)383 b(mean)f(a)h(non-singleton)800 40441 y(blo)36 b(c)-36 b(k)376 b(in)f Fl(\274)423 b Fm(minimal)376 b(with)g(resp)36 b(ect)375 b(to)g(inclusion.)559 b(The)376 b(reader)f(should)g(carefully)h(note)g(that)f(the)f(term)800 42046 y(\\minimal)529 b(blo)36 b(c)-36 b(k")529 b(includes)f(the)g (non-singleton)g(condition.)862 b(Note)528 b(also)h(that)f(the)g (pattern)f(of)i(eac)-36 b(h)800 43651 y(minimal)498 b(blo)36 b(c)-36 b(k)499 b(is)f(that)g(of)g(a)g(simple)g(p)36 b(erm)-36 b(utation.)770 b(An)-36 b(y)498 b(p)36 b(erm)-36 b(utation)497 b(can)h(b)36 b(e)498 b(decomp)36 b(osed)497 b(in)-36 b(to)800 45256 y(minimal)321 b(blo)36 b(c)-36 b(ks)321 b(and)e(singletons,)344 b(e.g.,)g(3524716)371 b(=)e(\(3524\)\(7\)\(1\)\(6\).)541 b(Ho)-36 b(w)g(ev)g(er,)344 b(this)320 b(decomp)36 b(osition)800 46861 y(is)591 b(not)g(unique,)630 b(for)592 b(t)-36 b(w)g(o)591 b(essen)-36 b(tially)593 b(di\256eren)-36 b(t)589 b(reasons.)1051 b(The)591 b(\257rst)g(one)g (is)g(that)g(decomp)36 b(ositions)800 48466 y Fl(\274)417 b Fm(=)368 b Fl(\276)48 b Fm([)p Fl(\256)5310 48665 y Ff(1)5836 48466 y Fl(;)221 b(\256)7245 48665 y Ff(2)7772 48466 y Fl(;)g(:)g(:)g(:)j(;)d(\256)11512 48665 y Fi(k)12082 48466 y Fm(],)422 b(where)c Fl(\276)467 b Fm(is)419 b(arbitrary)f(and)g Fl(\256)28320 48665 y Fi(i)29115 48466 y Fm(are)g(simple,)k(are)d(not)f (unique)g(b)36 b(ecause)419 b(it)f(ma)-36 b(y)800 50071 y(b)36 b(e)437 b(p)36 b(ossible)438 b(to)g(coalesce)h(singletons)f(in) -36 b(to)437 b(simple)h(blo)36 b(c)-36 b(ks,)439 b(or)f(vice)g(v)-36 b(ersa.)591 b(Th)-36 b(us)437 b(b)36 b(esides)437 b(3524716)378 b(=)800 51676 y(2413[2413)p Fl(;)221 b Fm(1)p Fl(;)g Fm(1)p Fl(;)g Fm(1])518 b(w)-36 b(e)513 b(also)g(ha)-36 b(v)g(e)512 b(3524716)504 b(=)f(3524716[1)p Fl(;)221 b Fm(1)p Fl(;)g Fm(1)p Fl(;)g Fm(1)p Fl(;)g Fm(1)p Fl(;)g Fm(1)p Fl(;)g Fm(1].)822 b(The)512 b(second)g(problem)g(is)800 53282 y(that)317 b(w)-36 b(e)319 b(require)e(an)-36 b(y)318 b(t)-36 b(w)g(o)319 b(minimal)f(blo)36 b(c)-36 b(ks)319 b(to)e(b)36 b(e)318 b(disjoin)-36 b(t.)540 b(While)318 b(this)g(is)g(necessarily)h(true)e(whenev)-36 b(er)800 54887 y(either)455 b(of)h(them)e(has)h(length)g(more)h(than)e(2,)461 b(t)-36 b(w)g(o)456 b(minimal)f(blo)36 b(c)-36 b(ks)456 b(of)g(length)f(2)h(ma)-36 b(y)455 b(in)-36 b(tersect,)461 b(as)455 b(in)800 56492 y(123.)556 b(Th)-36 b(us)363 b(w)-36 b(e)363 b(consider)g(decomp)36 b(ositions)364 b Fl(\274)416 b Fm(=)369 b Fl(\276)48 b Fm([)p Fl(\256)27254 56691 y Ff(1)27780 56492 y Fl(;)221 b(\256)29189 56691 y Ff(2)29716 56492 y Fl(;)g(:)g(:)g(:)j(;)d(\256)33456 56691 y Fi(k)34025 56492 y Fm(])364 b(where)f Fl(\276)411 b Fm(is)364 b(arbitrary)f(and)g(eac)-36 b(h)363 b Fl(\256)52424 56691 y Fi(i)800 58097 y Fm(is)455 b(either)f(1,)461 b(a)455 b(simple)g(p)36 b(erm)-36 b(utation)454 b(of)h(length)g(at)g (least)g(4,)461 b(or)454 b(the)h(iden)-36 b(tit)g(y)454 b(p)36 b(erm)-36 b(utation)454 b(of)h(length)800 59702 y(at)434 b(least)g(2)g(or)f(its)h(rev)-36 b(erse.)579 b(W)-108 b(e)433 b(refer)h(to)g(blo)36 b(c)-36 b(ks)434 b(of)g(the)f(latter)h(t)-36 b(yp)36 b(e)434 b(as)g Fk(clusters)g Fm(in)f Fl(\274)48 b Fm(.)2751 61307 y(By)555 b(using)f(clusters)h(w) -36 b(e)554 b(ha)-36 b(v)g(e)555 b(solv)-36 b(ed)555 b(the)f(second)h(problem)f(but)f(the)h(non-uniqueness)f(remains)800 62912 y(and,)671 b(moreo)-36 b(v)g(er,)671 b(w)-36 b(e)624 b(ha)-36 b(v)g(e)623 b(in)-36 b(tro)36 b(duced)623 b(another)g(source)g (of)h(it:)958 b(consecutiv)-36 b(e)624 b(\(rev)-36 b(ersed\))622 b(iden)-36 b(tit)g(y)800 64517 y(p)36 b(erm)-36 b(utations)614 b(ma)-36 b(y)616 b(coalesce)g(in)-36 b(to)615 b(longer)h(\(rev)-36 b(ersed\))614 b(iden)-36 b(tit)g(y)615 b(p)36 b(erm)-36 b(utations,)660 b(as)615 b(in)g(345612)680 b(=)800 66122 y(21[1234)p Fl(;)221 b Fm(12])634 b(=)629 b(231[12)p Fl(;)221 b Fm(12)p Fl(;)g Fm(12].)1043 b(T)-108 b(o)587 b(remedy)f(the)g(non-uniqueness)g(w)-36 b(e)587 b(in)-36 b(tro)36 b(duce)585 b(the)i(notion)f(of)800 67727 y Fk(marking)521 b Fm(a)i(p)36 b(erm)-36 b(utation.)844 b(A)523 b Fk(marke)-66 b(d)546 b(p)-66 b(ermutation)521 b Fm(\()p Fl(\274)48 b(;)221 b(M)139 b Fm(\))522 b(consists)h(of)g(a)g(p)36 b(erm)-36 b(utation)522 b Fl(\274)570 b Fm(and)522 b(a)800 69332 y(collection)584 b Fl(M)722 b Fm(of)584 b(minimal)f(blo)36 b(c)-36 b(ks)584 b(of)f Fl(\274)48 b Fm(.)1026 b(A)583 b Fk(marke)-66 b(d)601 b(cluster)583 b Fm(in)g(\()p Fl(\274)48 b(;)221 b(M)139 b Fm(\))583 b(is)g(a)g(maximal)i(c)-36 b(hain)582 b(of)800 70938 y(mark)-36 b(ed)510 b(o)-36 b(v)g(erlapping)510 b(minimal)g(blo)36 b(c)-36 b(ks)510 b(of)h(length)e(2)h(\(a)g(mark)-36 b(ed)509 b(cluster)g(ma)-36 b(y)511 b(b)36 b(e)509 b(a)h(prop)36 b(er)509 b(subset)p Black 26475 74617 a(8)p Black eop %%Page: 9 9 9 8 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(of)448 b(a)f(maximal)i(cluster\).)618 b(Let)446 b Fe(B)17182 1623 y Ff(1)18156 1424 y Fm(denote)g(the)h(set)g(of)g(all)h(simple)f(p) 36 b(erm)-36 b(utations)447 b(of)g(length)g(at)g(least)h(4)800 3029 y(and)502 b Fe(B)4270 3228 y Ff(2)5299 3029 y Fm(denote)g(the)g (set)h(of)g(all)g(iden)-36 b(tit)g(y)503 b(p)36 b(erm)-36 b(utations)501 b(of)j(length)e(at)h(least)g(2)g(and)f(their)g(rev)-36 b(ersals.)800 4634 y(Marking)434 b(mak)-36 b(es)434 b(our)g(decomp)36 b(osition)434 b(unique:)p Black 800 7678 a Fd(Theorem)499 b(6)p Black 651 w Fk(L)-66 b(et)581 b Fl(X)688 b Fk(b)-66 b(e)581 b(the)i(set)f(of)g(al)66 b(l)584 b(marke)-66 b(d)581 b(p)-66 b(ermutations)582 b Fm(\()p Fl(\274)48 b(;)221 b(M)139 b Fm(\))582 b Fk(and)h Fl(Y)871 b Fk(b)-66 b(e)581 b(the)i(set)f(of)g(al)66 b(l)800 9284 y(se)-66 b(quenc)g(es)425 b Fm(\()p Fl(\276)48 b Fm(;)221 b Fl(\256)9275 9483 y Ff(1)9801 9284 y Fl(;)g(\256)11210 9483 y Ff(2)11737 9284 y Fl(;)g(:)g(:)g(:)j(;)d(\256)15477 9483 y Fi(k)16046 9284 y Fm(\))426 b Fk(wher)-66 b(e)426 b Fl(\276)473 b Fk(is)426 b(any)g(p)-66 b(ermutation)424 b(of)h(length)g Fl(k)414 b Fe(\270)370 b Fm(1)426 b Fk(and)g Fl(\256)45028 9483 y Fi(i)45772 9284 y Fe(2)369 b(f)p Fm(1)p Fe(g)208 b([)g(B)51179 9483 y Ff(1)51914 9284 y Fe([)800 10889 y(B)1672 11088 y Ff(2)2198 10889 y Fk(.)595 b(Ther)-66 b(e)456 b(is)g(a)h(bije)-66 b(ction)454 b(b)-66 b(etwe)g(en)454 b(the)j(sets)g Fl(X)561 b Fk(and)457 b Fl(Y)745 b Fk(such)457 b(that)g(if)f Fm(\()p Fl(\274)48 b(;)221 b(M)139 b Fm(\))368 b Fe(7!)i Fm(\()p Fl(\276)48 b Fm(;)221 b Fl(\256)45124 11088 y Ff(1)45650 10889 y Fl(;)g(\256)47059 11088 y Ff(2)47586 10889 y Fl(;)g(:)g(:)g(:)j(;)d(\256)51326 11088 y Fi(k)51896 10889 y Fm(\))p Fk(,)800 12494 y(wher)-66 b(e)465 b Fl(r)501 b Fk(of)464 b(the)h Fl(\256)10070 12693 y Fi(i)10911 12494 y Fk(b)-66 b(elong)464 b(to)g Fe(B)17262 12693 y Ff(1)18254 12494 y Fk(and)h Fl(s)f Fk(of)h(them)f(to)h Fe(B)29037 12693 y Ff(2)29563 12494 y Fk(,)g(then)20979 15427 y Fl(\274)416 b Fm(=)369 b Fl(\276)48 b Fm([)p Fl(\256)25489 15626 y Ff(1)26015 15427 y Fl(;)221 b(\256)27424 15626 y Ff(2)27951 15427 y Fl(;)g(:)g(:)g(:)i(;)e(\256)31690 15626 y Fi(k)32260 15427 y Fm(])800 18361 y Fk(and)465 b Fe(j)p Fl(M)139 b Fe(j)369 b Fm(=)g Fl(r)331 b Fm(+)295 b Fl(l)325 b Fe(\241)295 b Fl(s)465 b Fk(wher)-66 b(e)464 b Fl(l)495 b Fk(is)465 b(the)f(total)h(length)f(of)h(the)f Fl(\256)31976 18560 y Fi(i)32817 18361 y Fk(b)-66 b(elonging)463 b(to)i Fe(B)40896 18560 y Ff(2)41422 18361 y Fk(.)2751 21405 y Fd(Pro)42 b(of)p Fm(:)1347 b(Giv)-36 b(en)481 b(a)h(mark)-36 b(ed)481 b(p)36 b(erm)-36 b(utation,)492 b(collapse)483 b(its)e(mark)-36 b(ed)481 b(minimal)h(blo)36 b(c)-36 b(ks)482 b(of)g(length)f(at)800 23010 y(least)530 b(4)h(and)e(its)h (mark)-36 b(ed)530 b(clusters)f(in)-36 b(to)530 b(singletons.)867 b(This)531 b(giv)-36 b(es)530 b(the)g(p)36 b(erm)-36 b(utation)529 b Fl(\276)48 b Fm(.)867 b(If)530 b(the)f Fl(i)p Fm(-th)800 24615 y(term)461 b(of)h Fl(\276)509 b Fm(w)-36 b(as)461 b(not)g(obtained)g(b)-36 b(y)461 b(collapse)h(then)e Fl(\256)27461 24814 y Fi(i)28253 24615 y Fm(=)416 b(1,)468 b(otherwise)462 b Fl(\256)37803 24814 y Fi(i)38640 24615 y Fm(equals)g(the)e(corresp)36 b(onding)800 26220 y(elemen)-36 b(t)465 b(of)i Fe(B)8023 26419 y Ff(1)8866 26220 y Fe([)317 b(B)10941 26419 y Ff(2)11467 26220 y Fm(.)675 b(Since)465 b(eac)-36 b(h)465 b Fl(\256)19716 26419 y Fi(i)20516 26220 y Fe(2)423 b(B)22697 26419 y Ff(1)23689 26220 y Fm(con)-36 b(tributes)465 b(1)h(to)f Fe(j)p Fl(M)139 b Fe(j)466 b Fm(and)f(eac)-36 b(h)466 b Fl(\256)42170 26419 y Fi(i)42969 26220 y Fe(2)424 b(B)45151 26419 y Ff(2)46143 26220 y Fm(of)466 b(length)f Fl(m)800 27825 y Fm(con)-36 b(tributes)465 b Fl(m)317 b Fe(\241)g Fm(1,)475 b(w)-36 b(e)466 b(ha)-36 b(v)g(e)467 b Fe(j)p Fl(M)139 b Fe(j)424 b Fm(=)g Fl(r)353 b Fm(+)317 b Fl(l)347 b Fe(\241)318 b Fl(s)p Fm(.)675 b(It)466 b(is)g(clear)h (that)e Fl(\274)472 b Fm(=)424 b Fl(\276)48 b Fm([)p Fl(\256)40255 28024 y Ff(1)40781 27825 y Fl(;)221 b(\256)42190 28024 y Ff(2)42717 27825 y Fl(;)g(:)g(:)g(:)j(;)d(\256)46457 28024 y Fi(k)47027 27825 y Fm(])466 b(and)g(that)800 29430 y(\()p Fl(\274)48 b(;)221 b(M)139 b Fm(\))433 b(can)h(b)36 b(e)433 b(uniquely)h(reco)-36 b(v)g(ered)434 b(from)g(\()p Fl(\276)48 b Fm(;)221 b Fl(\256)25958 29629 y Ff(1)26484 29430 y Fl(;)g(\256)27893 29629 y Ff(2)28420 29430 y Fl(;)g(:)g(:)g(:)j(;)d(\256)32160 29629 y Fi(k)32730 29430 y Fm(\).)p 52228 29430 572 572 v 2751 31035 a(No)-36 b(w)437 b(supp)36 b(ose)436 b Fl(m)g Fm(to)g(b)36 b(e)436 b(some)h(\257xed)f(v)-72 b(alue)437 b(\(w)-36 b(e)436 b(will)i(later)e(mak)-36 b(e)437 b(c)-36 b(hoices)437 b(of)g Fl(m)f Fm(suitable)g(for)h(our)800 32640 y(purp)36 b(oses,)528 b(but)508 b(will)i(alw)-36 b(a)g(ys)511 b(assume)e(that)g Fl(m)498 b Fe(\270)g Fm(2)509 b(since)h(smaller)g(v)-72 b(alues)509 b(of)h Fl(m)f Fm(are)h(trivial\).)806 b(Eac)-36 b(h)800 34245 y(p)36 b(erm)-36 b(utation)597 b Fl(\274)644 b Fm(has)598 b(an)f(asso)36 b(ciated)598 b(collection)h Fl(B)27532 34444 y Fi(m)28419 34245 y Fm(\()p Fl(\274)48 b Fm(\))597 b(consisting)h(of)g(the)e(minimal)i(blo)36 b(c)-36 b(ks)598 b(of)h Fl(\274)800 35851 y Fm(whose)523 b(length)f(is)h(less)g(than)f(or)h(equal)g(to)g Fl(m)p Fm(.)845 b(So,)545 b(if)523 b Fl(\274)570 b Fm(is)523 b(simple)g(and)f(of)h(length)f(greater)h(than)f Fl(m)p Fm(,)800 37456 y Fl(B)1788 37655 y Fi(m)2676 37456 y Fm(\()p Fl(\274)48 b Fm(\))469 b(is)h(empt)-36 b(y)-108 b(,)479 b(while)471 b(for)g Fl(\274)478 b Fm(=)431 b(5672413,)482 b Fl(B)25057 37655 y Ff(2)25583 37456 y Fm(\()p Fl(\274)48 b Fm(\))430 b(=)h Fe(f)p Fm(56)p Fl(;)221 b Fm(67)r Fe(g)p Fm(,)480 b(and)469 b Fl(B)38160 37655 y Ff(4)38686 37456 y Fm(\()p Fl(\274)48 b Fm(\))430 b(=)h Fe(f)p Fm(56)p Fl(;)221 b Fm(67)p Fl(;)g Fm(2413)t Fe(g)p Fm(.)688 b(An)800 39061 y Fl(m)p Fk(-marking)441 b Fm(of)j Fl(\274)491 b Fm(is)443 b(simply)h(a)f(subset)f(of)i Fl(B)23224 39260 y Fi(m)24112 39061 y Fm(\()p Fl(\274)48 b Fm(\).)606 b(Let)442 b Fe(j)p Fl(\274)48 b Fe(j)443 b Fm(denote)g(the)f(length)h (of)h(a)f(p)36 b(erm)-36 b(utation)442 b Fl(\274)48 b Fm(.)800 40666 y(W)-108 b(e)434 b(consider)f(the)g(generating)h (function:)11203 43758 y Fl(F)12045 43957 y Fi(m)12933 43758 y Fm(\()p Fl(x;)221 b(v)48 b Fm(\))369 b(=)17693 42496 y Fg(X)18366 45286 y Fi(\274)19833 43758 y Fl(x)20572 43209 y Fh(j)p Fi(\274)32 b Fh(j)23247 42496 y Fg(X)21943 45374 y Fi(M)94 b Fh(\265)p Fi(B)24383 45485 y Fc(m)25165 45374 y Ff(\()p Fi(\274)32 b Ff(\))26690 43758 y Fl(v)27367 43209 y Fh(j)p Fi(M)94 b Fh(j)29311 43758 y Fm(=)30692 42496 y Fg(X)31365 45286 y Fi(\274)32832 43758 y Fl(x)33571 43209 y Fh(j)p Fi(\274)32 b Fh(j)34721 43758 y Fm(\(1)296 b(+)f Fl(v)48 b Fm(\))38663 43209 y Fh(j)p Fi(B)39634 43320 y Fc(m)40415 43209 y Ff(\()p Fi(\274)32 b Ff(\))p Fh(j)42035 43758 y Fl(:)800 48164 y Fm(Then)440 b(of)h(course)f Fl(F)10521 48363 y Fi(m)11409 48164 y Fm(\()p Fl(x;)221 b Fe(\241)p Fm(1\))441 b(is)g(the)e(ordinary)i(generating)f(function)g (for)h(p)36 b(erm)-36 b(utations)439 b(all)j(of)f(whose)800 49769 y(non-singleton)433 b(blo)36 b(c)-36 b(ks)434 b(ha)-36 b(v)g(e)434 b(length)f(greater)h(than)f Fl(m)p Fm(.)2751 51374 y(W)-108 b(e)506 b(remark)h(that)f Fl(F)13313 51573 y Fi(m)14201 51374 y Fm(\()p Fl(x;)221 b(t)345 b Fe(\241)g Fm(1\))506 b(is)h(the)f(generating)g(function)h(where)f(the)g(co)36 b(e\261cien)-36 b(t)506 b(of)h Fl(x)49754 50892 y Fi(n)50381 51374 y Fl(t)50851 50892 y Fi(k)51926 51374 y Fm(is)800 52979 y(precisely)436 b(the)f(n)-36 b(um)g(b)36 b(er)434 b(of)j(p)36 b(erm)-36 b(utations)434 b(of)j(length)e Fl(n)h Fm(with)f Fl(k)481 b Fm(minimal)436 b(blo)36 b(c)-36 b(ks)436 b(of)h(length)e(less)h(than)800 54584 y(or)e(equal)g(to)g Fl(m)p Fm(.)2751 56189 y(Let)21793 58474 y Fl(S)22593 58673 y Fi(m)23480 58474 y Fm(\()p Fl(x)p Fm(\))369 b(=)27524 56814 y Fi(m)26980 57212 y Fg(X)27123 60012 y Fi(j)51 b Ff(=4)29121 58474 y Fl(s)29734 58673 y Fi(j)30220 58474 y Fl(x)30959 57926 y Fi(j)31446 58474 y Fl(:)800 62070 y Fm(W)-108 b(e)350 b(wish)h(to)g(determine)e(the)h(consequences)h(of)g (the)f(bijection)h(of)g(Theorem)p 0 1 0 0 TeXcolorcmyk 350 w(6)p (#definition.6) [[422 158 428 170] [1 1 1 [3 3]] [0 0 1]] pdfm Black 351 w(with)f(resp)36 b(ect)350 b(to)h(mark)-36 b(ed)800 63675 y(p)36 b(erm)-36 b(utations)455 b(whic)-36 b(h)456 b(con)-36 b(tain)456 b(no)g(mark)-36 b(ed)457 b(minimal)f(blo)36 b(c)-36 b(ks)457 b(of)g(length)f(more)g(than)g Fl(m)p Fm(.)645 b(The)457 b(gener-)800 65280 y(ating)486 b(function)f(of)h(the)e(p)36 b(erm)-36 b(utations)485 b Fl(\256)466 b Fe(2)456 b(f)p Fm(1)p Fe(g)331 b([)f(B)28186 65479 y Ff(1)29043 65280 y Fe([)g(B)31131 65479 y Ff(2)31657 65280 y Fm(,)499 b(in)485 b(whic)-36 b(h)485 b Fl(x)g Fm(coun)-36 b(ts)485 b(the)g(length)g(and)g Fl(v)800 66885 y Fm(the)433 b(con)-36 b(tribution)433 b(to)g Fe(j)p Fl(M)139 b Fe(j)p Fm(,)434 b(is)20613 70552 y Fl(x)295 b Fm(+)g Fl(v)48 b(S)24431 70751 y Fi(m)25318 70552 y Fm(\()p Fl(x)p Fm(\))295 b(+)29352 69653 y(2)p Fl(v)48 b(x)31418 69171 y Ff(2)p 28804 70246 3690 54 v 28804 71463 a Fm(1)295 b Fe(\241)g Fl(v)48 b(x)32626 70552 y(:)p Black 26475 74617 a Fm(9)p Black eop %%Page: 10 10 10 9 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(So,)434 b(from)g(Theorem)p 0 1 0 0 TeXcolorcmyk 434 w(6)p (#definition.6) [[176 704 182 716] [1 1 1 [3 3]] [0 0 1]] pdfm Black(:)14454 5036 y Fl(F)15296 5235 y Fi(m)16184 5036 y Fm(\()p Fl(x;)221 b(v)48 b Fm(\))369 b(=)20943 3774 y Fg(X)21045 6603 y Fi(k)24 b Fh(\270)p Ff(1)23083 5036 y Fl(k)45 b Fm(!)24608 3163 y Fg(\265)25586 5036 y Fl(x)296 b Fm(+)28609 4137 y(2)p Fl(v)48 b(x)30675 3655 y Ff(2)p 28060 4730 3690 54 v 28060 5947 a Fm(1)296 b Fe(\241)f Fl(v)48 b(x)32178 5036 y Fm(+)295 b Fl(v)48 b(S)34962 5235 y Fi(m)35849 5036 y Fm(\()p Fl(x)p Fm(\))37600 3163 y Fg(\266)38577 3435 y Fi(k)800 8945 y Fm(from)434 b(whic)-36 b(h)433 b(it)h(follo)-36 b(ws)436 b(that:)11630 12298 y Fl(f)12271 12497 y Fi(m)13159 12298 y Fm(\()p Fl(x)p Fm(\))368 b(:=)h Fl(F)17862 12497 y Fi(m)18750 12298 y Fm(\()p Fl(x;)221 b Fe(\241)p Fm(1\))370 b(=)24516 11037 y Fg(X)24618 13865 y Fi(k)24 b Fh(\270)p Ff(1)26656 12298 y Fl(k)45 b Fm(!)28182 10425 y Fg(\265)29159 12298 y Fl(x)296 b Fe(\241)32193 11400 y Fm(2)p Fl(x)33582 10918 y Ff(2)p 31655 11993 2992 54 v 31655 13210 a Fm(1)f(+)g Fl(x)35074 12298 y Fe(\241)h Fl(S)37203 12497 y Fi(m)38090 12298 y Fm(\()p Fl(x)p Fm(\))39841 10425 y Fg(\266)40819 10698 y Fi(k)41609 12298 y Fl(:)9168 b Fm(\(4\))2751 16208 y(Before)344 b(using)f(this)g(equation)h(to)f(deriv)-36 b(e)343 b(asymptotic)h(information)g(ab)36 b(out)343 b Fl(s)40743 16407 y Fi(n)41712 16208 y Fm(w)-36 b(e)344 b(digress)f(brie\260y)g(to)800 17813 y(sho)-36 b(w)377 b(ho)-36 b(w)377 b(it)g(can)f(b)36 b(e)377 b(used)f(to)h(obtain)g(an)f (alternativ)-36 b(e)378 b(deriv)-72 b(ation)377 b(of)g(\()p 0 1 0 0 TeXcolorcmyk(2)p (#equation.2) [[401 557 406 569] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\).)560 b(Instead)376 b(of)i(using)e Fl(S)48701 18012 y Fi(m)49589 17813 y Fm(\()p Fl(x)p Fm(\))g(in)800 19418 y(\()p 0 1 0 0 TeXcolorcmyk(4)p (#equation.4) [[84 542 90 554] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)402 b(use)393 b Fl(S)77 b Fm(\()p Fl(x)p Fm(\).)565 b(This)394 b(giv)-36 b(es)394 b(us)f Fl(f)17332 19617 y Fh(1)18329 19418 y Fm(\()p Fl(x)p Fm(\),)401 b(an)393 b(ordinary)h(generating)g(function)f(for)h(p)36 b(erm)-36 b(utations)393 b(ha)-36 b(ving)800 21023 y(no)434 b(minimal)g(blo)36 b(c)-36 b(k.)579 b(The)433 b(only)i(suc)-36 b(h)432 b(p)36 b(erm)-36 b(utation)433 b(is)h(1)g(so)g Fl(f)32137 21222 y Fh(1)33133 21023 y Fm(\()p Fl(x)p Fm(\))369 b(=)f Fl(x)p Fm(.)579 b(That)434 b(is:)19603 24444 y Fl(x)369 b Fm(=)g Fl(F)181 b Fm(\()p Fl(x)294 b Fe(\241)26654 23545 y Fm(2)p Fl(x)28043 23063 y Ff(2)p 26116 24139 V 26116 25355 a Fm(1)h(+)g Fl(x)29535 24444 y Fe(\241)g Fl(S)77 b Fm(\()p Fl(x)p Fm(\)\))800 27741 y(whic)-36 b(h)433 b(yields)i(\()p 0 1 0 0 TeXcolorcmyk(2)p (#equation.2) [[150 467 156 479] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))e(after)h(applying)g Fl(F)19678 27259 y Fh(h\241)p Ff(1)p Fh(i)22101 27741 y Fm(to)g(b)36 b(oth)433 b(sides.)2751 29346 y(No)-36 b(w)550 b(recall)g(that)f Fl(f)12988 29545 y Fi(m)13876 29346 y Fm(\()p Fl(x)p Fm(\))g(is)h(the)f(generating)h (function)f(for)h(p)36 b(erm)-36 b(utations)549 b(all)h(of)g(whose)g (blo)36 b(c)-36 b(ks)800 30951 y(ha)g(v)g(e)619 b(length)g(greater)g (than)f Fl(m)p Fm(.)1134 b(In)619 b(order)f(to)h(mak)-36 b(e)620 b(use)e(of)i(these)e(generating)h(functions)g(in)g(the)800 32556 y(asymptotic)430 b(computation)f(of)h Fl(s)17160 32755 y Fi(n)18215 32556 y Fm(w)-36 b(e)429 b(m)-36 b(ust)428 b(determine)h(a)g(suitable)g(v)-72 b(alue)430 b(of)g Fl(m)f Fm(so)g(that)g Fl(f)46779 32755 y Fi(m)48096 32556 y Fm(pro)-36 b(vides)800 34161 y(useful)434 b(information)g(ab)36 b(out)433 b Fl(s)15908 34360 y Fi(n)16534 34161 y Fm(.)579 b(T)-108 b(o)433 b(that)h(end)e(the)h(follo)-36 b(wing)436 b(lemma)e(is)g(useful.)p Black 800 36861 a Fd(Lemma)499 b(7)p Black 651 w Fk(If)461 b Fl(p)9507 37060 y Fi(n;k)11370 36861 y Fk(denotes)h(the)g(numb)-66 b(er)462 b(of)g(p)-66 b(ermutations)461 b(of)h(length)f Fl(n)i Fk(which)g(c)-66 b(ontain)460 b(a)j(minimal)800 38466 y(blo)-66 b(ck)464 b(of)h(length)f Fl(k)510 b Fk(then)464 b(for)h(any)f(\257xe)-66 b(d)464 b(p)-66 b(ositive)464 b(inte)-66 b(ger)462 b Fl(c)p Fk(:)21613 40529 y Fi(n)p Fh(\241)p Fi(c)21508 40928 y Fg(X)21040 43757 y Fi(k)24 b Ff(=)p Fi(c)p Ff(+2)24249 41291 y Fl(p)24902 41490 y Fi(n;k)p 24249 41884 2054 54 v 24708 43101 a Fl(n)p Fm(!)26805 42190 y(=)369 b Fl(O)36 b Fm(\()p Fl(n)30498 41641 y Fh(\241)p Fi(c)31693 42190 y Fm(\))p Fl(:)2751 46110 y Fd(Pro)42 b(of)p Fm(:)1156 b(First)434 b(observ)-36 b(e)433 b(that)17731 48742 y Fl(p)18384 48941 y Fi(n;k)20154 48742 y Fe(\267)369 b Fl(s)22169 48941 y Fi(k)22738 48742 y Fm(\()p Fl(n)295 b Fe(\241)g Fl(k)341 b Fm(+)295 b(1\)\()p Fl(n)g Fe(\241)g Fl(k)341 b Fm(+)294 b(1\)!)800 51374 y(since)506 b(the)g(righ)-36 b(t)505 b(hand)g(side)h(coun)-36 b(ts)505 b(the)h(n)-36 b(um)g(b)36 b(er)504 b(of)j(w)-36 b(a)g(ys)507 b(to)f(c)-36 b(ho)36 b(ose)506 b(the)g(structure)e(of)j(a)f(minimal)800 52979 y(blo)36 b(c)-36 b(k)466 b(of)f(length)g Fl(k)45 b Fm(,)473 b(to)465 b(c)-36 b(ho)36 b(ose)465 b(its)g(minimal)h(elemen) -36 b(t,)472 b(and)465 b(to)g(arrange)g(it)g(with)g(other)f(elemen)-36 b(ts,)473 b(so)800 54584 y(it)434 b(o)-36 b(v)g(ercoun)g(ts)433 b(p)36 b(erm)-36 b(utations)433 b(with)g(more)h(than)f(one)g(suc)-36 b(h)433 b(blo)36 b(c)-36 b(k.)2751 56189 y(The)512 b(estimate)g(giv)-36 b(en)512 b(then)f(follo)-36 b(ws)514 b(directly)e(b)-36 b(y)511 b(using)h(the)f(fact)i(that)e Fl(s)40303 56388 y Fi(k)41373 56189 y Fe(\267)503 b Fl(k)45 b Fm(!.)813 b(Only)512 b(the)f(t)-36 b(w)g(o)800 57794 y(extreme)427 b(terms)f(in)h(the)f(sum)g(can)h(ha)-36 b(v)g(e)427 b(magnitude)f(as)h (large)h(as)f Fl(O)36 b Fm(\()p Fl(n)36305 57312 y Fh(\241)p Fi(c)37500 57794 y Fm(\),)428 b(and)e(the)g(remaining)h(terms)800 59399 y(ha)-36 b(v)g(e)434 b(magnitude)f Fl(O)36 b Fm(\()p Fl(n)12542 58917 y Fh(\241)p Fi(c)p Fh(\241)p Ff(1)14939 59399 y Fm(\).)578 b(Since)434 b(there)f(are)g(few)-36 b(er)434 b(than)f Fl(n)h Fm(terms,)g(the)f(result)g(follo)-36 b(ws.)p 52228 59399 572 572 v 2751 61004 a(So)517 b(when)h(seeking)g (an)f(asymptotic)i(expansion)e(of)i Fl(s)29698 61203 y Fi(n)30324 61004 y Fl(=n)p Fm(!)f(with)g(an)f(error)h(term)f(of)h Fl(O)36 b Fm(\()p Fl(n)47898 60522 y Fh(\241)p Fi(c)p Fh(\241)p Ff(1)50295 61004 y Fm(\))518 b(w)-36 b(e)800 62609 y(ma)g(y)420 b(coun)-36 b(t)419 b(instead)h(the)f(p)36 b(erm)-36 b(utations)419 b(whic)-36 b(h)419 b(con)-36 b(tain)420 b(no)g(blo)36 b(c)-36 b(ks)420 b(of)h(length)e(less)h(than)g (or)f(equal)i(to)800 64214 y Fl(c)303 b Fm(+)g(2,)449 b(or)c(greater)h(than)f(or)g(equal)h(to)g Fl(n)303 b Fe(\241)h Fl(c)p Fm(.)613 b(In)445 b(particular,)k(as)d(a)f(direct)g (consequence)g(of)i(the)d(result)800 65819 y(quoted)433 b(ab)36 b(o)-36 b(v)g(e)435 b(due)d(to)i(Kaplansky)h([)p 0 1 0 0 TeXcolorcmyk(7)p (#cite.Ka01) [[249 125 255 137] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])f(w)-36 b(e)433 b(obtain:)p Black 800 68519 a Fd(Observ)-83 b(ation)500 b(8)p Black 21601 69486 a Fl(s)22214 69685 y Fi(n)p 21601 70079 1239 54 v 21652 71296 a Fl(n)p Fm(!)23342 70385 y(=)25082 69486 y(1)p 24856 70079 1104 54 v 24856 71296 a(e)25434 70912 y Ff(2)26388 70385 y Fm(+)294 b Fl(O)36 b Fm(\()p Fl(n)30006 69836 y Fh(\241)p Ff(1)31264 70385 y Fm(\))p Fl(:)p Black 26150 74617 a Fm(10)p Black eop %%Page: 11 11 11 10 bop Black 0 TeXcolorgray Black Black 2751 1424 a Fm(An)514 b(alternativ)-36 b(e)515 b(pro)36 b(of)514 b(of)h(this)f(result)f(follo)-36 b(ws)516 b(from)f(a)f(more)g(general)h (theorem)f(of)g(Bender)g(and)800 3029 y(Ric)-36 b(hmond)524 b([)p 0 1 0 0 TeXcolorcmyk(3)p (#cite.BR01) [[139 690 145 702] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])h(whic)-36 b(h)524 b(pro)-36 b(vides)525 b(the)e(\257rst)h (order)g(asymptotics)h(of)g(a)g(class)g(of)g(series)f(whic)-36 b(h)525 b(include)800 4634 y(the)433 b(in)-36 b(v)g(erse)434 b(series)g(of)g Fl(F)181 b Fm(\()p Fl(x)p Fm(\).)2751 6239 y(W)-108 b(e)631 b(will)h(set)f(as)g(our)f(goal)i(to)f(obtain)g (the)f(asymptotics)i(of)f Fl(s)35477 6438 y Fi(n)36103 6239 y Fl(=n)p Fm(!)h(with)f(error)g(term)f Fl(O)36 b Fm(\()p Fl(n)50675 5757 y Fh(\241)p Ff(3)51933 6239 y Fm(\).)800 7844 y(Ho)-36 b(w)g(ev)g(er,)382 b(the)367 b(tec)-36 b(hnique)367 b(w)-36 b(e)368 b(use)f(is)h(completely)g (general,)382 b(and)367 b(could)g(b)36 b(e)367 b(applied,)381 b(at)368 b(the)f(exp)36 b(ense)367 b(of)800 9450 y(a)450 b(great)g(deal)g(of)h(tedious)e(computation,)454 b(to)c(an)-36 b(y)450 b(\257xed)f(error)h(b)36 b(ound)448 b(of)j(this)e(t)-36 b(yp)36 b(e.)627 b(By)450 b(the)g(remarks)800 11055 y(ab)36 b(o)-36 b(v)g(e,)462 b(w)-36 b(e)457 b(ma)-36 b(y)456 b(ignore)g(minimal)h(blo)36 b(c)-36 b(k)456 b(sizes)g(b)36 b(et)-36 b(w)g(een)456 b(5)g(and)f Fl(n)311 b Fe(\241)f Fm(3)457 b(inclusiv)-36 b(e.)645 b(W)-108 b(e)456 b(\257rst)f(consider) 800 12660 y Fl(f)1441 12859 y Ff(4)1967 12660 y Fm(\()p Fl(x)p Fm(\))403 b(whic)-36 b(h)403 b(en)-36 b(umerates)403 b(p)36 b(erm)-36 b(utations)402 b(ha)-36 b(ving)404 b(no)g(minimal)g (blo)36 b(c)-36 b(ks)404 b(of)g(size)g(less)g(than)e(or)i(equal)g(to) 800 14265 y(4.)579 b(Recall)435 b(that:)16501 16591 y Fl(f)17142 16790 y Ff(4)17668 16591 y Fm(\()p Fl(x)p Fm(\))369 b(=)21168 15329 y Fg(X)21270 18158 y Fi(k)24 b Fh(\270)p Ff(1)23308 16591 y Fl(k)45 b Fm(!)24833 14718 y Fg(\265)25811 16591 y Fl(x)296 b Fe(\241)28845 15693 y Fm(2)p Fl(x)30234 15211 y Ff(2)p 28307 16286 2992 54 v 28307 17503 a Fm(1)f(+)g Fl(x)31726 16591 y Fe(\241)h Fm(2)p Fl(x)34444 16043 y Ff(4)34970 14718 y Fg(\266)35948 14991 y Fi(k)36738 16591 y Fl(:)800 20154 y Fm(So,)434 b(for)g Fl(n)369 b Fe(\270)g Fm(1:)8115 23078 y(1)p 7871 23671 1138 54 v 7871 24888 a Fl(n)p Fm(!)9142 23976 y([)p Fl(t)9973 23428 y Fi(n)10599 23976 y Fm(])p Fl(f)11601 24175 y Ff(4)12127 23976 y Fm(\()p Fl(t)p Fm(\))1106 b(=)17210 23078 y(1)p 16967 23671 V 16967 24888 a Fl(n)p Fm(!)18948 22316 y Fh(1)18459 22714 y Fg(X)18560 25543 y Fi(k)24 b Ff(=0)20599 23976 y Fl(k)45 b Fm(!)221 b([)p Fl(t)22733 23428 y Fi(n)23360 23976 y Fm(])23942 22103 y Fg(\265)24920 23976 y Fl(t)295 b Fe(\241)27684 23078 y Fm(2)p Fl(t)28804 22596 y Ff(2)p 27146 23671 2723 54 v 27146 24888 a Fm(1)h(+)f Fl(t)30296 23976 y Fe(\241)h Fm(2)p Fl(t)32745 23428 y Ff(4)33271 22103 y Fg(\266)34248 22376 y Fi(k)14715 28310 y Fm(=)17210 27411 y(1)p 16967 28004 1138 54 v 16967 29221 a Fl(n)p Fm(!)18948 26649 y Fh(1)18459 27048 y Fg(X)18560 29877 y Fi(k)24 b Ff(=0)20599 28310 y Fl(k)45 b Fm(!)221 b([)p Fl(t)22733 27761 y Fi(n)p Fh(\241)p Fi(k)24605 28310 y Fm(])25187 26437 y Fg(\265)26166 28310 y Fm(1)295 b Fe(\241)29373 27411 y Fm(2)p Fl(t)p 28572 28004 2723 54 v 28572 29221 a Fm(1)h(+)f Fl(t)31722 28310 y Fe(\241)h Fm(2)p Fl(t)34171 27761 y Ff(3)34697 26437 y Fg(\266)35674 26734 y Fi(k)14715 32643 y Fm(=)17210 31744 y(1)p 16967 32337 1138 54 v 16967 33554 a Fl(n)p Fm(!)19133 30982 y Fi(n)18459 31381 y Fg(X)18671 34210 y Fi(l)11 b Ff(=0)20377 32643 y Fm(\()p Fl(n)296 b Fe(\241)f Fl(l)29 b Fm(\)!)221 b([)p Fl(t)25618 32094 y Fi(l)25966 32643 y Fm(])26548 30770 y Fg(\265)27527 32643 y Fm(1)295 b Fe(\241)30734 31744 y Fm(2)p Fl(t)p 29933 32337 2723 54 v 29933 33554 a Fm(1)h(+)f Fl(t)33083 32643 y Fe(\241)h Fm(2)p Fl(t)35532 32094 y Ff(3)36057 30770 y Fg(\266)37035 31067 y Fi(n)p Fh(\241)p Fi(l)14715 37194 y Fm(=)17210 36295 y(1)p 16967 36888 1138 54 v 16967 38105 a Fl(n)p Fm(!)19133 35533 y Fi(n)18459 35932 y Fg(X)18671 38761 y Fi(l)11 b Ff(=0)20377 37194 y Fm(\()p Fl(n)296 b Fe(\241)f Fl(l)29 b Fm(\)!)25602 35533 y Fi(l)24788 35932 y Fg(X)24986 38731 y Fi(i)p Ff(=0)26707 37194 y Fm(\()p Fe(\241)p Fm(2\))29402 36645 y Fi(i)29778 35321 y Fg(\265)30756 36295 y Fl(n)295 b Fe(\241)h Fl(l)31942 38105 y(i)33572 35321 y Fg(\266)34550 37194 y Fm([)p Fl(t)35381 36645 y Fi(l)35728 37194 y Fm(])36310 35321 y Fg(\265)38547 36295 y Fl(t)p 37421 36888 2723 54 v 37421 38105 a Fm(1)g(+)e Fl(t)40571 37194 y Fm(+)h Fl(t)42348 36645 y Ff(3)42873 35321 y Fg(\266)43851 35618 y Fi(i)14715 41744 y Fm(=)17210 40846 y(1)p 16967 41439 1138 54 v 16967 42656 a Fl(n)p Fm(!)19133 40084 y Fi(n)18459 40482 y Fg(X)18671 43311 y Fi(l)11 b Ff(=0)20377 41744 y Fm(\()p Fl(n)296 b Fe(\241)f Fl(l)29 b Fm(\)!)25602 40084 y Fi(l)24788 40482 y Fg(X)24986 43282 y Fi(i)p Ff(=0)26707 41744 y Fm(\()p Fe(\241)p Fm(2\))29402 41196 y Fi(i)29778 39871 y Fg(\265)30756 40846 y Fl(n)295 b Fe(\241)h Fl(l)31942 42656 y(i)33572 39871 y Fg(\266)34550 41744 y Fm([)p Fl(t)35381 41196 y Fi(l)11 b Fh(\241)p Fi(i)36780 41744 y Fm(])37362 39871 y Fg(\265)39509 40846 y Fm(1)p 38473 41439 2723 54 v 38473 42656 a(1)296 b(+)f Fl(t)41623 41744 y Fm(+)g Fl(t)43400 41196 y Ff(2)43926 39871 y Fg(\266)44903 40169 y Fi(i)45501 41744 y Fl(:)p Black 5276 w Fm(\(5\))p Black 2751 45789 a(Consider)440 b(no)-36 b(w)440 b(an)-36 b(y)440 b(\257xed)g(v)-72 b(alue)440 b(of)h Fl(l)469 b Fm(in)440 b(equation)g(\()p 0 1 0 0 TeXcolorcmyk(5)p (#equation.5) [[338 305 344 317] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\).)598 b(In)439 b(order)h(to)g(obtain)g(terms)f(whose)h(order) 800 47394 y(in)408 b Fl(n)h Fm(is)g Fl(n)5536 46912 y Fh(\241)p Ff(2)7202 47394 y Fm(or)f(more,)414 b(w)-36 b(e)409 b(need)e(only)i(consider)f(the)g(v)-72 b(alues)409 b Fl(l)273 b Fe(\241)244 b Fm(2)369 b Fe(\267)g Fl(i)g Fe(\267)g Fl(l)29 b Fm(.)571 b(Despite)408 b(the)g(fact)h(that)f(w)-36 b(e)800 48999 y(sum)396 b(o)-36 b(v)g(er)396 b(v)-72 b(alues)397 b(of)g Fl(l)426 b Fm(running)395 b(from)h(0)h(through)e Fl(n)p Fm(,)404 b(w)-36 b(e)397 b(ma)-36 b(y)396 b(safely)i(ignore)f (the)e(other)h(terms.)566 b(As)396 b(w)-36 b(e)800 50604 y(shall)460 b(see)f(in)f(computing)h(the)f(three)h(signi\257can)-36 b(t)458 b(terms)h(the)f(summation)h(o)-36 b(v)g(er)459 b Fl(l)489 b Fm(do)36 b(es)459 b(not)g(a\256ect)g(the)800 52209 y(order)433 b(of)i(the)e(terms.)2751 53814 y(So,)h(the)f(three)g (terms)g(that)g(w)-36 b(e)434 b(need)f(to)h(consider)f(are:)12841 56085 y Ff(\()p Fi(n)p Fh(\241)p Fi(l)11 b Ff(\)!)p 12841 56412 2588 54 v 13718 57176 a Fi(n)p Ff(!)15561 56718 y Fm(\()p Fe(\241)p Fm(2\))18256 56236 y Fi(l)18603 55642 y Fg(\241)19212 56128 y Fi(n)p Fh(\241)p Fi(l)19863 57176 y(l)20806 55642 y Fg(\242)21414 56718 y Fm(+)12841 57863 y Ff(\()p Fi(n)p Fh(\241)p Fi(l)g Ff(\)!)p 12841 58191 V 13718 58955 a Fi(n)p Ff(!)15782 57421 y Fg(\241)16391 58497 y Fm(\()p Fe(\241)p Fm(2\))19086 58015 y Fi(l)g Fh(\241)p Ff(1)20635 57421 y Fg(\241)21244 57907 y Fi(n)p Fh(\241)p Fi(l)21294 58955 y(l)g Fh(\241)p Ff(1)22838 57421 y Fg(\242)23447 58497 y Fm(\()p Fe(\241)p Fl(l)325 b Fm(+)295 b(1\))28161 57421 y Fg(\242)28991 58497 y Fm(+)12841 59711 y Ff(\()p Fi(n)p Fh(\241)p Fi(l)11 b Ff(\)!)p 12841 60039 V 13718 60802 a Fi(n)p Ff(!)15782 59268 y Fg(\241)16391 60344 y Fm(\()p Fe(\241)p Fm(2\))19086 59862 y Fi(l)g Fh(\241)p Ff(2)20635 59268 y Fg(\241)21244 59755 y Fi(n)p Fh(\241)p Fi(l)21294 60802 y(l)g Fh(\241)p Ff(2)22838 59268 y Fg(\242)23668 60344 y Fm(\(\()p Fe(\241)p Fl(l)325 b Fm(+)295 b(2\)\()p Fe(\241)p Fl(l)325 b Fm(+)295 b(1\))p Fl(=)p Fm(2)h(+)e Fl(l)325 b Fe(\241)296 b Fm(2\))39701 59268 y Fg(\242)40531 60344 y Fl(:)51138 58490 y Fm(\(6\))800 63165 y(Eac)-36 b(h)433 b(of)i(these)e(terms)g(will)i(b)36 b(e)433 b(con)-36 b(v)g(erted)433 b(to)h(the)f(form:)15955 65610 y(\()p Fe(\241)p Fm(2\))18650 65128 y Fi(l)p 15955 66203 3042 54 v 17087 67420 a Fl(l)29 b Fm(!)19351 66509 y(\(an)433 b(asymptotic)i(expansion)e(in)h Fl(n)p Fm(\))222 b Fl(:)800 69691 y Fm(Since)405 b(the)f(\257rst)g(t)-36 b(w)g(o)406 b(and)e(the)h(\257rst)f(part)h(of)g(the)g(third,)410 b(are)405 b(the)g(same)g(as)g(those)g(arising)h(in)f(the)f Fl(m)369 b Fm(=)g(2)800 71296 y(case,)488 b(w)-36 b(e)477 b(can)f(mak)-36 b(e)477 b(use)f(of)h(their)f(kno)-36 b(wn)477 b(form,)488 b(that)476 b(is,)488 b(use)476 b(the)f (asymptotics)j(from)e(Kaplansky's)p Black 26150 74617 a(11)p Black eop %%Page: 12 12 12 11 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(result,)434 b(lea)-36 b(ving)434 b(only)h(the)e(term)5404 3996 y(\()p Fl(n)295 b Fe(\241)h Fl(l)29 b Fm(\)!\()p Fe(\241)p Fm(2\))12288 3514 y Fi(l)11 b Fh(\241)p Ff(2)13838 3996 y Fm(\()p Fl(l)324 b Fe(\241)296 b Fm(2\))p 5404 4589 12136 54 v 10903 5806 a Fl(n)p Fm(!)17673 3022 y Fg(\265)18650 3996 y Fl(n)g Fe(\241)f Fl(l)18713 5806 y(l)325 b Fe(\241)296 b Fm(2)21467 3022 y Fg(\266)23552 4895 y Fm(=)25803 3996 y(\()p Fe(\241)p Fm(2\))28498 3514 y Fi(l)p 25803 4589 3042 54 v 26935 5806 a Fl(l)29 b Fm(!)29199 3022 y Fg(\265)30310 3996 y Fl(l)g Fm(\()p Fl(l)325 b Fe(\241)296 b Fm(1\)\()p Fl(l)324 b Fe(\241)296 b Fm(2\))p 30310 4589 7821 54 v 33895 5806 a(4)38618 3996 y(\()p Fl(n)f Fe(\241)h Fl(l)29 b Fm(\)!\()p Fl(n)296 b Fe(\241)f Fl(l)29 b Fm(\)!)p 38618 4589 8380 54 v 38693 5806 a Fl(n)p Fm(!\()p Fl(n)296 b Fe(\241)f Fm(2)p Fl(l)325 b Fm(+)295 b(2\)!)47130 3022 y Fg(\266)23552 8595 y Fm(=)25803 7697 y(\()p Fe(\241)p Fm(2\))28498 7215 y Fi(l)p 25803 8290 3042 54 v 26935 9506 a Fl(l)29 b Fm(!)29199 6722 y Fg(\265)30310 7697 y Fl(l)g Fm(\()p Fl(l)325 b Fe(\241)296 b Fm(1\)\()p Fl(l)324 b Fe(\241)296 b Fm(2\))p 30310 8290 7821 54 v 31476 9506 a(4)p Fl(n)p Fm(\()p Fl(n)g Fe(\241)g Fm(1\))38559 8595 y(+)f Fl(O)36 b Fm(\()p Fl(n)42178 8047 y Fh(\241)p Ff(3)43436 8595 y Fm(\))43942 6722 y Fg(\266)800 12127 y Fm(Summing)433 b(this)g(expression)h(o)-36 b(v)g(er)434 b Fl(l)463 b Fm(giv)-36 b(es)435 b Fe(\241)p Fm(2e)24462 11645 y Fh(\241)p Ff(2)25720 12127 y Fl(=n)p Fm(\()p Fl(n)296 b Fe(\241)f Fm(1\))h(+)f Fl(O)36 b Fm(\()p Fl(n)35123 11645 y Fh(\241)p Ff(3)36381 12127 y Fm(\).)2751 13732 y(No)-36 b(w)528 b(w)-36 b(e)527 b(com)-36 b(bine)527 b(this)g(additional)h(term)e(with)i(Kaplansky's)g(results)f(to)h(giv) -36 b(e)528 b(the)e(asymptotic)800 15337 y(expansion)434 b(of)g([)p Fl(t)9153 14855 y Fi(n)9779 15337 y Fm(])p Fl(f)10781 15536 y Ff(4)11308 15337 y Fm(\()p Fl(t)p Fm(\))f(through)f(three)h(terms)g(as:)15083 18812 y([)p Fl(t)15914 18263 y Fi(n)16540 18812 y Fm(])p Fl(f)17542 19011 y Ff(4)18068 18812 y Fm(\()p Fl(t)p Fm(\))368 b(=)21432 17913 y Fl(n)p Fm(!)p 21432 18506 1138 54 v 21449 19723 a(e)22027 19339 y Ff(2)22924 16939 y Fg(\265)23901 18812 y Fm(1)296 b Fe(\241)28402 17913 y Fm(4)p 26308 18506 4839 54 v 26308 19723 a Fl(n)p Fm(\()p Fl(n)g Fe(\241)f Fm(1\))31574 18812 y(+)g Fl(O)36 b Fm(\()p Fl(n)35193 18263 y Fh(\241)p Ff(3)36451 18812 y Fm(\))36957 16939 y Fg(\266)38156 18812 y Fl(:)2751 22213 y Fm(Finally)383 b(w)-36 b(e)382 b(use)g(this)g(in)g(establishing)g(the)f(second)h (order)f(asymptotics)i(of)g Fl(s)41054 22412 y Fi(n)41680 22213 y Fm(.)561 b(F)-108 b(rom)381 b(Observ)-72 b(ation)p 0 1 0 0 TeXcolorcmyk 800 23818 a(8)p (#definition.8) [[79 503 85 515] [1 1 1 [3 3]] [0 0 1]] pdfm Black 434 w(applied)433 b(to)h Fl(s)8639 24017 y Fi(n)p Fh(\241)p Ff(1)10901 23818 y Fm(w)-36 b(e)434 b(obtain:)19263 27252 y Fl(s)19876 27451 y Fi(n)p Fh(\241)p Ff(1)22073 27252 y Fm(=)23587 26354 y Fl(n)p Fm(!)p 23587 26947 1138 54 v 23604 28164 a(e)24182 27780 y Ff(2)25079 25379 y Fg(\265)26252 26354 y Fm(1)p 26189 26947 777 54 v 26189 28164 a Fl(n)27394 27252 y Fm(+)295 b Fl(O)36 b Fm(\()p Fl(n)31013 26704 y Fh(\241)p Ff(2)32271 27252 y Fm(\))32777 25379 y Fg(\266)33976 27252 y Fl(:)800 30654 y Fm(F)-108 b(urthermore,)537 b(the)518 b(n)-36 b(um)g(b)36 b(er)516 b(of)i(p)36 b(erm)-36 b(utations)517 b(of)i(length)e Fl(n)h Fm(con)-36 b(taining)518 b(a)g(simple)g(blo)36 b(c)-36 b(k)519 b(of)f(length)800 32259 y Fl(n)347 b Fe(\241)g Fm(1)509 b(is)g(precisely)h(4)p Fl(s)12502 32458 y Fi(n)p Fh(\241)p Ff(1)14330 32259 y Fm(.)805 b(Since,)527 b(in)509 b(computing)f(the)h(1)p Fl(=n)h Fm(term)e(in)h(the)f(expansion)h(of)h Fl(s)47724 32458 y Fi(n)48859 32259 y Fm(w)-36 b(e)509 b(can)800 33864 y(ignore)526 b(con)-36 b(tributions)525 b(arising)h(from)h(blo)36 b(c)-36 b(ks)526 b(of)h(length)e Fl(n)359 b Fe(\241)f Fm(2,)549 b(and)525 b(since)h(the)f(ev)-36 b(en)g(ts)526 b(of)g(ha)-36 b(ving)527 b(a)800 35469 y(simple)429 b(blo)36 b(c)-36 b(k)430 b(of)f(length)g(from)g(2)g(to)g(4,)h(and)e(ha)-36 b(ving)430 b(a)f(simple)g(blo)36 b(c)-36 b(k)429 b(of)h(length)e(\()p Fl(n)286 b Fe(\241)g Fm(1\))429 b(are)g(disjoin)-36 b(t:)16278 38180 y Fl(s)16891 38379 y Fi(n)18624 38180 y Fm(=)1106 b([)p Fl(t)21573 37631 y Fi(n)22199 38180 y Fm(])p Fl(f)23201 38379 y Ff(4)23728 38180 y Fm(\()p Fl(t)p Fm(\))294 b Fe(\241)i Fm(4)p Fl(s)28096 38379 y Fi(n)p Fh(\241)p Ff(1)30219 38180 y Fm(+)f Fl(O)36 b Fm(\()p Fl(n)33838 37631 y Fh(\241)p Ff(2)35096 38180 y Fl(n)p Fm(!\);)18624 40881 y(=)20875 39982 y Fl(n)p Fm(!)p 20875 40575 1138 54 v 20892 41792 a(e)21470 41408 y Ff(2)22367 39008 y Fg(\265)23345 40881 y Fm(1)295 b Fe(\241)25815 39982 y Fm(4)p 25752 40575 777 54 v 25752 41792 a Fl(n)26956 40881 y Fm(+)g Fl(O)36 b Fm(\()p Fl(n)30575 40332 y Fh(\241)p Ff(2)31833 40881 y Fm(\))32339 39008 y Fg(\266)33538 40881 y Fl(:)2751 44282 y Fm(W)-108 b(e)381 b(apply)h(this)f(b)36 b(o)g(otstrap)381 b(approac)-36 b(h)381 b(once)g(more)g(to)h(get)f(the) g(second)g(order)g(b)36 b(eha)-36 b(viour.)561 b(W)-108 b(e)381 b(no)-36 b(w)800 45887 y(kno)g(w)434 b(that:)15342 49030 y Fl(s)15955 49229 y Fi(n)p Fh(\241)p Ff(1)18890 49030 y Fm(=)21142 48131 y Fl(n)p Fm(!)p 21142 48725 1138 54 v 21159 49941 a(e)21737 49557 y Ff(2)22634 47157 y Fg(\265)23807 48131 y Fm(1)p 23744 48725 777 54 v 23744 49941 a Fl(n)24949 49030 y Fe(\241)28504 48131 y Fm(4)p 26410 48725 4839 54 v 26410 49941 a Fl(n)p Fm(\()p Fl(n)296 b Fe(\241)f Fm(1\))31676 49030 y(+)g Fl(O)36 b Fm(\()p Fl(n)35295 48482 y Fh(\241)p Ff(3)36553 49030 y Fm(\))37059 47157 y Fg(\266)15342 52661 y Fl(s)15955 52860 y Fi(n)p Fh(\241)p Ff(2)18890 52661 y Fm(=)21142 51762 y Fl(n)p Fm(!)p 21142 52355 1138 54 v 21159 53572 a(e)21737 53188 y Ff(2)22634 50788 y Fg(\265)25838 51762 y Fm(1)p 23744 52355 4839 54 v 23744 53572 a Fl(n)p Fm(\()p Fl(n)296 b Fe(\241)f Fm(1\))29011 52661 y(+)f Fl(O)36 b Fm(\()p Fl(n)32629 52112 y Fh(\241)p Ff(3)33887 52661 y Fm(\))34393 50788 y Fg(\266)35592 52661 y Fl(:)800 56062 y Fm(F)-108 b(urthermore)452 b(there)h(are)h(18)p Fl(s)15798 56261 y Fi(n)p Fh(\241)p Ff(2)18081 56062 y Fm(p)36 b(erm)-36 b(utations)453 b(of)i(length)f Fl(n)g Fm(con)-36 b(taining)454 b(a)g(simple)g(blo)36 b(c)-36 b(k)455 b(of)f(length)800 57667 y Fl(n)296 b Fe(\241)f Fm(2.)579 b(Ho)-36 b(w)g(ev)g(er,)434 b(of)h(these)e(8)p Fl(s)16465 57866 y Fi(n)p Fh(\241)p Ff(2)18727 57667 y Fm(also)h(con)-36 b(tain)434 b(a)g(simple)g(blo)36 b(c)-36 b(k)434 b(of)g(length)f(2.)579 b(So:)13886 60378 y Fl(s)14499 60577 y Fi(n)16232 60378 y Fm(=)1107 b([)p Fl(t)19182 59830 y Fi(n)19808 60378 y Fm(])p Fl(f)20810 60577 y Ff(4)21336 60378 y Fm(\()p Fl(t)p Fm(\))295 b Fe(\241)g Fm(4)p Fl(s)25704 60577 y Fi(n)p Fh(\241)p Ff(1)27828 60378 y Fe(\241)g Fm(10)p Fl(s)31069 60577 y Fi(n)p Fh(\241)p Ff(2)33193 60378 y Fm(+)g Fl(O)36 b Fm(\()p Fl(n)36812 59830 y Fh(\241)p Ff(3)38070 60378 y Fl(n)p Fm(!\))16232 63079 y(=)18484 62181 y Fl(n)p Fm(!)p 18484 62774 1138 54 v 18501 63990 a(e)19079 63607 y Ff(2)19976 61206 y Fg(\265)20953 63079 y Fm(1)296 b Fe(\241)23423 62181 y Fm(4)p 23360 62774 777 54 v 23360 63990 a Fl(n)24565 63079 y Fm(+)28098 62181 y(2)p 26004 62774 4839 54 v 26004 63990 a Fl(n)p Fm(\()p Fl(n)g Fe(\241)f Fm(1\))31271 63079 y(+)f Fl(O)36 b Fm(\()p Fl(n)34889 62531 y Fh(\241)p Ff(3)36147 63079 y Fm(\))36653 61206 y Fg(\266)37852 63079 y Fl(;)800 66480 y Fm(as)434 b(w)-36 b(e)434 b(claimed)g(at)g(the)f(b)36 b(eginning)433 b(of)h(this)g (section.)2751 68086 y(Finally)-108 b(,)330 b(in)302 b(this)g(section)g(w)-36 b(e)302 b(note)g(that)g(the)g(asymptotic)h (estimate)f(of)h Fl(s)38266 68285 y Fi(n)39194 68086 y Fm(is,)329 b(as)303 b(migh)-36 b(t)302 b(b)36 b(e)302 b(exp)36 b(ected,)800 69691 y(a)325 b(p)36 b(o)g(or)324 b(appro)-36 b(ximation.)543 b(F)-108 b(or)324 b(example,)347 b Fl(s)22043 69890 y Ff(20)23408 69691 y Fm(=)369 b(264111424634864638) 330 b(and)324 b(our)g(asymptotic)h(estimate)800 71296 y(has)434 b(a)f(relativ)-36 b(e)435 b(error)e(of)i(ab)36 b(out)433 b(3)p Fl(:)p Fm(89)297 b Fe(\243)e Fm(10)22446 70814 y Fh(\241)p Ff(3)23704 71296 y Fm(.)p Black 26150 74617 a(12)p Black eop %%Page: 13 13 13 12 bop Black 0 TeXcolorgray Black Black 800 1424 a Fn(4)2152 b(Congruences)800 4345 y Fm(In)426 b(this)f(section)h(w)-36 b(e)426 b(deriv)-36 b(e)426 b(congruence)g(prop)36 b(erties)425 b(of)i(the)e(n)-36 b(um)g(b)36 b(ers)424 b(Com)39446 4544 y Fi(n)40498 4345 y Fm(for)i(the)f(mo)36 b(duli)426 b(2)49723 3863 y Fi(a)50705 4345 y Fm(and)800 5950 y(3)439 b(\(from)f(whic)-36 b(h)438 b(follo)-36 b(w)440 b(similar)f (congruences)f(for)h Fl(s)27076 6149 y Fi(n)27702 5950 y Fm(\).)592 b(Our)437 b(main)h(to)36 b(ol)439 b(is)g(the)e(follo)-36 b(wing)441 b(result)c(that)800 7555 y(follo)-36 b(ws)436 b(immediately)e(from)g(the)f(Lagrange)h(in)-36 b(v)g(ersion)434 b(form)-36 b(ula.)p Black 800 10537 a Fd(Lemma)499 b(9)p Black 12113 13003 a Fl(n)295 b Fe(\242)g Fm(Com)16522 13202 y Fi(n)17517 13003 y Fm(=)369 b([)p Fl(x)19998 12455 y Fi(n)p Fh(\241)p Ff(1)21827 13003 y Fm(])22409 10732 y Fg(\303)23461 11741 y(X)23563 14570 y Fi(k)24 b Fh(\270)p Ff(0)25380 13003 y Fm(\()p Fe(\241)p Fm(1\))28075 12455 y Fi(k)28644 13003 y Fm(\(2!)p Fl(x)296 b Fm(+)e(3!)p Fl(x)34252 12455 y Ff(2)35074 13003 y Fm(+)h Fe(\242)221 b(\242)g(\242)h Fm(\))38658 12455 y Fi(k)39227 10732 y Fg(!)40278 11029 y Fi(n)41126 13003 y Fl(:)2751 17337 y Fm(F)-108 b(or)482 b(a)h(prime)g Fl(p)p Fm(,)495 b(let)483 b(ord)15313 17536 y Fi(p)15842 17337 y Fm(\()p Fl(n)p Fm(\))g(denote)f(the)g(largest)i(in)-36 b(teger)482 b Fl(m)h Fm(suc)-36 b(h)481 b(that)i Fl(p)41362 16855 y Fi(m)42732 17337 y Fm(divides)g Fl(n)p Fm(.)726 b(As)483 b(the)800 18942 y(follo)-36 b(wing)436 b(table)d(sho)-36 b(ws,)434 b(ord)15519 19141 y Ff(2)16045 18942 y Fm(\(Com)19224 19141 y Fi(n)19851 18942 y Fm(\))f(is)h(unexp)36 b(ectedly)433 b(large:)p Black Black 6540 23183 a Fl(n)p 13898 23665 45 1606 v 14120 23665 V 7490 w Fm(1)p 16098 23665 V 1329 w(2)p 18077 23665 V 1328 w(3)p 20056 23665 V 1329 w(4)p 22034 23665 V 1329 w(5)p 24013 23665 V 1328 w(6)p 25992 23665 V 1329 w(7)p 27970 23665 V 1329 w(8)p 29949 23665 V 1328 w(9)p 31928 23665 V 1329 w(10)p 34557 23665 V 1329 w(11)p 37186 23665 V 1329 w(12)p 39815 23665 V 1329 w(13)p 42444 23665 V 1329 w(14)p 45073 23665 V 1329 w(15)p 5876 23709 41849 45 v 6540 24832 a(ord)8419 25031 y Ff(2)8945 24832 y Fm(\(Com)12124 25031 y Fi(n)12750 24832 y Fm(\))p 13898 25314 45 1606 v 14120 25314 V 1550 w(0)p 16098 25314 V 1329 w(1)p 18077 25314 V 1328 w(1)p 20056 25314 V 1329 w(2)p 22034 25314 V 1329 w(2)p 24013 25314 V 1328 w(4)p 25992 25314 V 1329 w(4)p 27970 25314 V 1329 w(4)p 29949 25314 V 1328 w(4)p 31928 25314 V 1979 w(5)p 34557 25314 V 1979 w(5)p 37186 25314 V 1329 w(15)p 39815 25314 V 1329 w(13)p 42444 25314 V 1329 w(12)p 45073 25314 V 1329 w(12)7747 27846 y(16)p 9689 28327 V 1329 w(17)p 12318 28327 V 1329 w(18)p 14947 28327 V 1329 w(19)p 17576 28327 V 1329 w(20)p 20205 28327 V 1329 w(21)p 22834 28327 V 1329 w(22)p 25463 28327 V 1329 w(23)p 28092 28327 V 1329 w(24)p 30721 28327 V 1329 w(25)p 33350 28327 V 1329 w(26)p 35979 28327 V 1329 w(27)p 38608 28327 V 1329 w(28)p 41238 28327 V 1329 w(29)p 43867 28327 V 1329 w(30)p 7082 28372 39436 45 v 8397 29495 a(8)p 9689 29977 45 1606 v 1979 w(8)p 12318 29977 V 1979 w(9)p 14947 29977 V 1979 w(9)p 17576 29977 V 1329 w(10)p 20205 29977 V 1329 w(10)p 22834 29977 V 1329 w(12)p 25463 29977 V 1329 w(12)p 28092 29977 V 1329 w(14)p 30721 29977 V 1329 w(14)p 33350 29977 V 1329 w(15)p 35979 29977 V 1329 w(15)p 38608 29977 V 1329 w(17)p 41238 29977 V 1329 w(17)p 43867 29977 V 1329 w(22)800 33758 y(In)507 b(Theorem)p 0 1 0 0 TeXcolorcmyk 508 w(11)p (#definition.11) [[145 413 156 425] [1 1 1 [3 3]] [0 0 1]] pdfm Black 508 w(w)-36 b(e)508 b(giv)-36 b(e)508 b(a)g(lo)-36 b(w)g(er)508 b(b)36 b(ound)506 b(on)h(ord)27080 33957 y Ff(2)27606 33758 y Fm(\(Com)30785 33957 y Fi(n)31411 33758 y Fm(\))h(whic)-36 b(h)507 b(is)h(tigh)-36 b(t)507 b(for)h(in\257nitely)f(man)-36 b(y)508 b Fl(n)800 35364 y Fm(and)433 b(w)-36 b(e)434 b(completely)g(c)-36 b(haracterize)434 b(the)f(v)-72 b(alues)434 b(of)h Fl(n)f Fm(for)g(whic)-36 b(h)433 b(the)g(equalit)-36 b(y)435 b(is)f(attained.)2751 36969 y(F)-108 b(or)516 b(con)-36 b(v)g(enience)516 b(w)-36 b(e)516 b(note)g(the)f(follo)-36 b(wing)518 b(result)e(that)f(follo)-36 b(ws)518 b(directly)f(from)f(the)f(w)-36 b(ell-kno)g(wn)800 38574 y(form)g(ula)18116 40611 y(ord)19994 40810 y Fi(p)20523 40611 y Fm(\()p Fl(m)p Fm(!\))369 b(=)24784 38738 y Fg(\271)25691 39712 y Fl(m)p 25691 40305 1138 54 v 25934 41522 a(p)26962 38738 y Fg(\272)28032 40611 y Fm(+)29339 38738 y Fg(\271)30267 39712 y Fl(m)p 30246 40305 1179 54 v 30246 41522 a(p)30899 41138 y Ff(2)31558 38738 y Fg(\272)32628 40611 y Fm(+)295 b Fe(\242)221 b(\242)g(\242)p Black 800 44490 a Fd(Lemma)499 b(10)p Black 651 w Fk(F)-100 b(or)497 b(al)66 b(l)498 b Fl(m)p Fk(,)505 b Fm(ord)16510 44689 y Ff(2)17035 44490 y Fm(\(\()p Fl(m)319 b Fm(+)g(1\)!\))428 b Fe(\270)24748 43414 y Fg(\247)25508 43967 y Fi(m)p 25508 44184 833 54 v 25689 44948 a Ff(2)26474 43414 y Fg(\250)27598 44490 y Fk(wher)-66 b(e)497 b(e)-66 b(quality)496 b(holds)i(if)e(and)h(only)h (if)e Fl(m)428 b Fm(=)g(1)498 b Fk(or)800 46095 y Fm(2)p Fk(.)598 b(A)-33 b(lso,)464 b Fm(ord)7649 46294 y Ff(3)8175 46095 y Fm(\()p Fl(m)p Fm(!\))368 b Fe(\267)h Fl(m)295 b Fe(\241)h Fm(1)465 b Fk(for)f(al)66 b(l)466 b Fl(m)p Fk(.)p Black 800 49077 a Fd(Theorem)499 b(11)p Black 20124 51114 a Fm(ord)22002 51313 y Ff(2)22528 51114 y Fm(\(Com)25708 51313 y Fi(n)26334 51114 y Fm(\))369 b Fe(\270)28611 49241 y Fg(\273)29518 50215 y Fl(n)296 b Fe(\241)f Fm(1)p 29518 50809 3051 54 v 30718 52025 a(2)32702 49241 y Fg(\274)800 54343 y Fk(L)-66 b(et)483 b Fl(m)405 b Fm(=)g Fe(b)p Fl(n=)p Fm(2)p Fe(c)p Fk(.)658 b(Then)484 b(e)-66 b(quality)483 b(holds)j(if)d(and)i(only)f(if)29799 53267 y Fg(\241)30408 53754 y Ff(3)p Fi(m)30643 54801 y(m)31711 53267 y Fg(\242)32804 54343 y Fk(is)h(o)-66 b(dd)484 b(and)h(this)f(happ)-66 b(ens)484 b(if)g(and)g(only)800 55948 y(if)464 b(the)h(binary)e(exp)-66 b(ansion)464 b(of)h Fl(m)f Fk(has)i(no)f(two)g(c)-66 b(onse)g(cutive)463 b(unit)h(digits.)2751 58931 y Fd(Pro)42 b(of)p Fm(:)1156 b(Let)433 b(the)g(n)-36 b(um)g(b)36 b(ers)432 b Fl(b)18261 59130 y Fi(k)18830 58931 y Fm(,)i Fl(k)414 b Fe(\270)369 b Fm(0,)435 b(b)36 b(e)433 b(de\257ned)f(b)-36 b(y)15577 60707 y Fg(X)15678 63536 y Fi(k)24 b Fh(\270)p Ff(0)17717 61969 y Fl(b)18270 62168 y Fi(k)18839 61969 y Fl(x)19578 61420 y Fi(k)20516 61969 y Fm(=)21896 60707 y Fg(X)21998 63536 y Fi(k)g Fh(\270)p Ff(0)23815 61969 y Fm(\()p Fe(\241)p Fm(1\))26510 61420 y Fi(k)27079 61969 y Fm(\(2!)p Fl(x)296 b Fm(+)f(3!)p Fl(x)32688 61420 y Ff(2)33509 61969 y Fm(+)g Fe(\242)221 b(\242)g(\242)h Fm(\))37093 61420 y Fi(k)37662 61969 y Fl(:)800 66126 y Fm(Th)-36 b(us)433 b Fl(b)4648 66325 y Ff(0)5543 66126 y Fm(=)368 b(1)434 b(and)f(for)i Fl(k)414 b Fe(\270)369 b Fm(1,)10442 69164 y Fl(b)10995 69363 y Fi(k)11933 69164 y Fm(=)15761 67902 y Fg(X)14041 70818 y Fi(c)14449 70941 y Fb(1)14909 70818 y Fi(;c)15578 70941 y Fb(2)16040 70818 y Fi(;:::)q(;c)17754 70929 y Fc(s)18197 70818 y Fh(\270)p Ff(1)13313 71704 y Fi(c)13721 71827 y Fb(1)14182 71704 y Ff(+)p Fi(c)15322 71827 y Fb(2)15783 71704 y Ff(+)p Fh(\242\242\242)q Ff(+)p Fi(c)18439 71815 y Fc(s)18882 71704 y Ff(=)p Fi(k)20127 69164 y Fm(\()p Fe(\241)p Fm(1\))22822 68615 y Fi(s)23608 69164 y Fe(\242)295 b Fm(\()p Fl(c)25338 69363 y Ff(1)26158 69164 y Fm(+)g(1\)!)h Fe(\242)f Fm(\()p Fl(c)31008 69363 y Ff(2)31829 69164 y Fm(+)f(1\)!)i Fe(\242)f(\242)221 b(\242)g(\242)296 b(\242)f Fm(\()p Fl(c)39187 69363 y Fi(s)39973 69164 y Fm(+)f(1\)!)p Fl(:)p Black 26150 74617 a Fm(13)p Black eop %%Page: 14 14 14 13 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(By)434 b(Lemma)p 0 1 0 0 TeXcolorcmyk 434 w(9)p (#definition.9) [[139 704 145 716] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)15518 3188 y Fl(n)295 b Fe(\242)g Fm(Com)19927 3387 y Fi(n)20922 3188 y Fm(=)25565 1926 y Fg(X)23660 4866 y Fi(k)24150 4989 y Fb(1)24611 4866 y Fi(;k)25362 4989 y Fb(2)25824 4866 y Fi(;:::)q(;k)27620 4977 y Fc(n)28187 4866 y Fh(\270)p Ff(0)22303 5751 y Fi(k)22793 5874 y Fb(1)23254 5751 y Ff(+)p Fi(k)24476 5874 y Fb(2)24937 5751 y Ff(+)p Fh(\242\242\242)q Ff(+)p Fi(k)27675 5862 y Fc(n)28241 5751 y Ff(=)p Fi(n)p Fh(\241)p Ff(1)30968 3188 y Fl(b)31521 3387 y Fi(k)32011 3510 y Fb(1)32527 3188 y Fl(b)33080 3387 y Fi(k)33570 3510 y Fb(2)34308 3188 y Fl(:)221 b(:)g(:)i(b)36609 3387 y Fi(k)37099 3498 y Fc(n)37721 3188 y Fl(:)800 7833 y Fm(By)434 b(Lemma)p 0 1 0 0 TeXcolorcmyk 434 w(10)p (#definition.10) [[139 647 151 659] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)g(ord)11458 8032 y Ff(2)11984 7833 y Fm(\(\()p Fl(c)294 b Fm(+)h(1\)!\))369 b Fe(\270)g Fl(c=)p Fm(2)434 b(for)h(all)f Fl(c)p Fm(.)578 b(Hence,)434 b(for)g(all)g Fl(k)479 b Fm(and)433 b Fl(n)p Fm(,)14287 11426 y(ord)16166 11625 y Ff(2)16692 11426 y Fm(\()p Fl(b)17751 11625 y Fi(k)18319 11426 y Fm(\))369 b Fe(\270)20729 10527 y Fl(k)p 20729 11120 722 54 v 20764 12337 a Fm(2)22450 11426 y(and)867 b(ord)27292 11625 y Ff(2)27817 11426 y Fm(\()p Fl(n)296 b Fe(\242)f Fm(Com)32733 11625 y Fi(n)33359 11426 y Fm(\))369 b Fe(\270)35769 10527 y Fl(n)295 b Fe(\241)g Fm(1)p 35769 11120 3051 54 v 36969 12337 a(2)38952 11426 y Fl(:)800 14772 y Fm(In)433 b(particular,)h(for)g(o)36 b(dd)434 b Fl(n)g Fm(w)-36 b(e)433 b(ha)-36 b(v)g(e)434 b(ord)21339 14971 y Ff(2)21865 14772 y Fm(\(Com)25044 14971 y Fi(n)25670 14772 y Fm(\))369 b(=)g(ord)29804 14971 y Ff(2)30330 14772 y Fm(\()p Fl(n)296 b Fe(\242)f Fm(Com)35245 14971 y Fi(n)35872 14772 y Fm(\))369 b Fe(\270)g Fm(\()p Fl(n)295 b Fe(\241)g Fm(1\))p Fl(=)p Fm(2.)2751 16377 y(T)-108 b(o)500 b(obtain)g(the)f(more)h(exact)h(result)e(of)i (the)e(theorem)g(w)-36 b(e)500 b(need)f(the)h(follo)-36 b(wing)502 b(b)36 b(etter)499 b(estimates)800 17982 y(for)434 b(ord)4666 18181 y Ff(2)5192 17982 y Fm(\()p Fl(b)6251 18181 y Fi(k)6819 17982 y Fm(\):)14573 21165 y(ord)16452 21364 y Ff(2)16977 21165 y Fm(\()p Fl(b)18036 21364 y Fi(k)18605 21165 y Fm(\))19332 18442 y Fg(8)19332 19637 y(<)19332 22028 y(:)21066 19549 y Fm(=)369 b Fl(k)45 b(=)p Fm(2)4372 b(for)434 b(ev)-36 b(en)433 b Fl(k)45 b Fm(;)21066 21154 y(=)369 b(\()p Fl(k)340 b Fm(+)295 b(1\))p Fl(=)p Fm(2)1108 b(for)434 b Fl(k)414 b Fe(\264)369 b Fm(1)434 b(mo)36 b(d)433 b(4;)21066 22759 y Fl(>)369 b Fm(\()p Fl(k)340 b Fm(+)295 b(1\))p Fl(=)p Fm(2)1108 b(for)434 b Fl(k)414 b Fe(\264)369 b Fm(3)434 b(mo)36 b(d)433 b(4.)800 24993 y(T)-108 b(o)479 b(pro)-36 b(v)g(e)478 b(them)g(w)-36 b(e)478 b(lo)36 b(ok)480 b(more)f(closely)g(at)g(the)f (sum)g(for)g Fl(b)31305 25192 y Fi(k)31874 24993 y Fm(.)713 b(Supp)36 b(ose)477 b(\257rst)h(that)g Fl(k)523 b Fm(is)479 b(ev)-36 b(en.)712 b(Then)800 26598 y(the)570 b(sum)g(has)h(exactly)h (one)f(summand)e(with)i(ord)26710 26797 y Ff(2)27807 26598 y Fm(equal)g(to)g Fl(k)45 b(=)p Fm(2,)606 b(namely)571 b(that)f(with)h Fl(c)47359 26797 y Ff(1)48487 26598 y Fm(=)602 b Fl(c)50661 26797 y Ff(2)51788 26598 y Fm(=)800 28203 y Fe(\242)221 b(\242)g(\242)410 b Fm(=)e Fl(c)4739 28410 y Fi(k)24 b(=)p Ff(2)6657 28203 y Fm(=)409 b(2)457 b(\(b)-36 b(y)456 b(Lemma)p 0 1 0 0 TeXcolorcmyk 457 w(10)p (#definition.10) [[218 463 229 475] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)464 b(ord)20190 28402 y Ff(2)20716 28203 y Fm(\(\()p Fl(c)310 b Fm(+)h(1\)!\))409 b(=)f Fl(c=)p Fm(2)457 b(only)h(if)g Fl(c)408 b Fm(=)h(2\),)463 b(and)456 b(the)h(other)f(summands)800 29808 y(ha)-36 b(v)g(e)479 b(ord)5723 30007 y Ff(2)6727 29808 y Fm(bigger)g(than)f Fl(k)45 b(=)p Fm(2.)715 b(Hence)478 b(ord)22640 30007 y Ff(2)23166 29808 y Fm(\()p Fl(b)24225 30007 y Fi(k)24794 29808 y Fm(\))445 b(=)h Fl(k)45 b(=)p Fm(2.)714 b(No)-36 b(w)479 b(supp)36 b(ose)478 b(that)h Fl(k)523 b Fm(is)479 b(o)36 b(dd.)714 b(Then)478 b(eac)-36 b(h)800 31413 y(summand)509 b(has)i(an)f(o)36 b(dd)510 b(n)-36 b(um)g(b)36 b(er)509 b(of)i(o)36 b(dd)510 b Fl(c)23301 31612 y Fi(i)23677 31413 y Fm('s.)809 b(The)510 b(summands)g Fl(t)g Fm(with)g(three)g(and)g(more)g(o)36 b(dd)510 b Fl(c)51550 31612 y Fi(i)51926 31413 y Fm('s)800 33019 y(satisfy)482 b(ord)6787 33218 y Ff(2)7313 33019 y Fm(\()p Fl(t)p Fm(\))448 b Fe(\270)h Fm(\()p Fl(k)372 b Fm(+)327 b(3\))p Fl(=)p Fm(2)482 b(\(eac)-36 b(h)480 b(o)36 b(dd)480 b Fl(c)23207 33218 y Fi(i)24063 33019 y Fm(con)-36 b(tributes)480 b(1)p Fl(=)p Fm(2)h(to)g Fl(k)45 b(=)p Fm(2\).)720 b(The)481 b(same)g(is)g(true)e(if)j Fl(t)e Fm(has)800 34624 y(only)401 b(one)e(o)36 b(dd)400 b Fl(c)9063 34823 y Fi(i)9838 34624 y Fm(but)f(that)g Fl(c)15533 34823 y Fi(i)16309 34624 y Fm(is)h(not)f(1)i(\(b)-36 b(y)399 b(Lemma)p 0 1 0 0 TeXcolorcmyk 400 w(10)p (#definition.10) [[322 405 334 417] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)407 b(ord)31746 34823 y Ff(2)32272 34624 y Fm(\(\()p Fl(c)226 b Fm(+)g(1\)!\))369 b Fe(\270)g Fm(\()p Fl(c)226 b Fm(+)g(3\))p Fl(=)p Fm(2)400 b(for)h(o)36 b(dd)399 b Fl(c)369 b(>)g Fm(1\),)800 36229 y(or)480 b(if)g(some)g(ev)-36 b(en)479 b Fl(c)10547 36428 y Fi(i)11402 36229 y Fm(is)h(not)f(2)h (\(Lemma)p 0 1 0 0 TeXcolorcmyk 479 w(10)p (#definition.10) [[265 391 277 403] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\).)716 b(The)480 b(remaining)f(summands)g Fl(t)p Fm(,)490 b(in)480 b(whic)-36 b(h)479 b Fl(c)46860 36428 y Fi(i)47683 36229 y Fm(=)446 b(2)480 b(with)800 37834 y(m)-36 b(ultiplicit)g(y)525 b(\()p Fl(k)403 b Fe(\241)357 b Fm(1\))p Fl(=)p Fm(2)526 b(and)e(once)h Fl(c)20055 38033 y Fi(i)20955 37834 y Fm(=)f(1,)548 b(satisfy)526 b(ord)30081 38033 y Ff(2)30607 37834 y Fm(\()p Fl(t)p Fm(\))d(=)h(\()p Fl(k)403 b Fm(+)357 b(1\))p Fl(=)p Fm(2.)853 b(W)-108 b(e)524 b(see)i(that,)547 b(for)525 b(o)36 b(dd)800 39439 y Fl(k)45 b Fm(,)469 b(ord)4229 39638 y Ff(2)4755 39439 y Fm(\()p Fl(b)5814 39638 y Fi(k)6383 39439 y Fm(\))416 b(=)g(\()p Fl(k)359 b Fm(+)314 b(1\))p Fl(=)p Fm(2)462 b(if)g(and)f(only)h(if)g(the)f(n)-36 b(um)g(b)36 b(er)460 b(of)i(the)f(remaining)g(summands)g(is)g(o)36 b(dd.)662 b(This)800 41044 y(n)-36 b(um)g(b)36 b(er)383 b(equals)i(\()p Fl(k)240 b Fe(\241)195 b Fm(1\))p Fl(=)p Fm(2)g(+)g(1)370 b(=)f(\()p Fl(k)240 b Fm(+)195 b(1\))p Fl(=)p Fm(2.)562 b(So)385 b(ord)27933 41243 y Ff(2)28459 41044 y Fm(\()p Fl(b)29518 41243 y Fi(k)30087 41044 y Fm(\))369 b(=)f(\()p Fl(k)240 b Fm(+)195 b(1\))p Fl(=)p Fm(2)385 b(if)g(and)f(only)i(if)f Fl(k)414 b Fe(\264)369 b Fm(1)385 b(mo)36 b(d)384 b(4.)2751 42649 y(Let)g Fl(n)370 b Fm(=)e(2)p Fl(m)195 b Fm(+)g(1)385 b(b)36 b(e)384 b(o)36 b(dd.)562 b(If)385 b Fl(s)f Fm(is)h(a)g(summand)e (of)j(the)e(ab)36 b(o)-36 b(v)g(e)385 b(sum)f(for)h Fl(n)195 b Fe(\242)g Fm(Com)43095 42848 y Fi(n)43721 42649 y Fm(,)395 b(then)384 b(ord)49269 42848 y Ff(2)49795 42649 y Fm(\()p Fl(s)p Fm(\))368 b(=)800 44254 y(\()p Fl(n)307 b Fe(\241)h Fm(1\))p Fl(=)p Fm(2)452 b(if)f(and)g(only)h(if)g(all)g Fl(k)16976 44453 y Fi(i)17803 44254 y Fm(in)f Fl(s)g Fm(are)g(ev)-36 b(en;)460 b(other)451 b(summands)f Fl(t)h Fm(ha)-36 b(v)g(e)451 b(ord)41630 44453 y Ff(2)42156 44254 y Fm(\()p Fl(t)p Fm(\))398 b Fl(>)h Fm(\()p Fl(n)307 b Fe(\241)g Fm(1\))p Fl(=)p Fm(2.)632 b(It)800 45859 y(follo)-36 b(ws)417 b(that)e(ord)9731 46058 y Ff(2)10256 45859 y Fm(\(Com)13436 46058 y Fi(n)14062 45859 y Fm(\))369 b(=)f(\()p Fl(n)258 b Fe(\241)g Fm(1\))p Fl(=)p Fm(2)416 b(if)g(and)e(only)i(if)g(the)e(n)-36 b(um)g(b)36 b(er)414 b(of)i(the)e(former)i(summands)e Fl(s)h Fm(is)800 47464 y(o)36 b(dd.)578 b(This)434 b(n)-36 b(um)g(b)36 b(er)432 b(equals)5410 51517 y([)p Fl(x)6510 50969 y Fi(n)p Fh(\241)p Ff(1)8339 51517 y Fm(])8921 49246 y Fg(\303)9973 50255 y(X)10106 53061 y Fi(r)26 b Fh(\270)p Ff(0)12113 51517 y Fl(x)12852 50969 y Ff(2)p Fi(r)13829 49246 y Fg(!)14880 49543 y Fi(n)15876 51517 y Fm(=)368 b([)p Fl(x)18356 50969 y Fi(n)p Fh(\241)p Ff(1)20185 51517 y Fm(])22942 50618 y(1)p 20679 51212 5177 54 v 20679 52428 a(\(1)296 b Fe(\241)f Fl(x)24198 52045 y Ff(2)24724 52428 y Fm(\))25230 52045 y Fi(n)26358 51517 y Fm(=)368 b([)p Fl(x)28838 50969 y Fi(n)p Fh(\241)p Ff(1)30667 51517 y Fm(])31249 50255 y Fg(X)31383 53061 y Fi(r)26 b Fh(\270)p Ff(0)33390 49644 y Fg(\265)34368 50618 y Fl(n)296 b Fm(+)e Fl(r)332 b Fe(\241)295 b Fm(1)36694 52428 y Fl(r)39642 49644 y Fg(\266)40620 51517 y Fl(x)41359 50969 y Ff(2)p Fi(r)42705 51517 y Fm(=)44086 49644 y Fg(\265)45063 50618 y Fm(3)p Fl(m)45389 52428 y(m)46851 49644 y Fg(\266)47829 51517 y Fl(:)2751 55779 y Fm(Let)445 b Fl(n)390 b Fm(=)f(2)p Fl(m)446 b Fm(b)36 b(e)445 b(ev)-36 b(en.)615 b(W)-108 b(e)445 b(kno)-36 b(w)446 b(that)g(ord)25549 55978 y Ff(2)26075 55779 y Fm(\()p Fl(b)27134 55978 y Fi(k)27703 55779 y Fm(\))389 b(=)g Fl(k)45 b(=)p Fm(2)446 b(for)h(ev)-36 b(en)445 b Fl(k)491 b Fm(and)445 b(ord)43027 55978 y Ff(2)43552 55779 y Fm(\()p Fl(b)44611 55978 y Fi(k)45180 55779 y Fm(\))389 b Fe(\270)h Fm(\()p Fl(k)348 b Fm(+)303 b(1\))p Fl(=)p Fm(2)800 57384 y(for)466 b(o)36 b(dd)465 b Fl(k)45 b Fm(.)674 b(In)465 b(the)g(sum)g(for)h Fl(n)317 b Fe(\242)g Fm(Com)20357 57583 y Fi(n)20984 57384 y Fm(,)473 b(ev)-36 b(ery)466 b(comp)36 b(osition)466 b Fl(k)33259 57583 y Ff(1)34103 57384 y Fm(+)316 b Fl(k)36107 57583 y Ff(2)36950 57384 y Fm(+)h Fe(\242)221 b(\242)g(\242)317 b Fm(+)g Fl(k)42150 57583 y Fi(n)43200 57384 y Fm(=)422 b Fl(n)318 b Fe(\241)f Fm(1)465 b(of)h Fl(n)318 b Fe(\241)f Fm(1)800 58989 y(has)552 b(an)h(o)36 b(dd)551 b(n)-36 b(um)g(b)36 b(er)551 b(of)i(o)36 b(dd)552 b(parts.)934 b(F)-108 b(or)552 b(an)-36 b(y)553 b Fl(t)p Fm(-tuple)e Fl(l)30934 59188 y Ff(1)31460 58989 y Fl(;)221 b(l)32429 59188 y Ff(2)32956 58989 y Fl(;)g(:)g(:)g(:)j(;)d(l)36256 59188 y Fi(t)36652 58989 y Fm(,)582 b(where)552 b Fl(t)g Fm(and)g(all)h Fl(l)47453 59188 y Fi(i)48382 58989 y Fm(are)f(o)36 b(dd)800 60594 y(and)508 b Fl(l)3791 60793 y Ff(1)4663 60594 y Fm(+)346 b Fe(\242)221 b(\242)g(\242)346 b Fm(+)g Fl(l)9661 60793 y Fi(t)10553 60594 y Fe(\267)496 b Fl(n)346 b Fe(\241)h Fm(1,)527 b(w)-36 b(e)509 b(let)f Fl(S)77 b Fm(\()p Fl(l)21835 60793 y Ff(1)22361 60594 y Fl(;)221 b(l)23330 60793 y Ff(2)23857 60594 y Fl(;)g(:)g(:)g(:)j(;)d (l)27157 60793 y Fi(t)27553 60594 y Fm(\))508 b(denote)g(the)g(sum)f (of)i(those)f Fl(b)43562 60793 y Fi(k)44052 60916 y Fb(1)44569 60594 y Fl(b)45122 60793 y Fi(k)45612 60916 y Fb(2)46350 60594 y Fl(:)221 b(:)g(:)i(b)48651 60793 y Fi(k)49141 60904 y Fc(n)50271 60594 y Fm(with)800 62199 y Fl(k)1476 62398 y Ff(1)2244 62199 y Fm(+)242 b Fl(k)4174 62398 y Ff(2)4943 62199 y Fm(+)f Fe(\242)221 b(\242)g(\242)243 b Fm(+)f Fl(k)9918 62398 y Fi(n)10914 62199 y Fm(=)368 b Fl(n)243 b Fe(\241)f Fm(1)408 b(in)g(whic)-36 b(h)407 b Fl(k)21509 62398 y Fi(i)22254 62199 y Fm(=)369 b Fl(l)24022 62398 y Fi(i)24398 62199 y Fm(,)413 b(1)369 b Fe(\267)g Fl(i)g Fe(\267)g Fl(t)p Fm(,)413 b(and)407 b Fl(k)34231 62398 y Fi(i)35015 62199 y Fm(is)h(ev)-36 b(en)407 b(for)i Fl(i)368 b(>)h(t)p Fm(.)569 b(It)408 b(follo)-36 b(ws)409 b(that)16974 65822 y Fl(n)296 b Fe(\242)f Fm(Com)21384 66021 y Fi(n)22379 65822 y Fm(=)23760 64561 y Fg(X)25900 63949 y(\265)26877 64924 y Fl(n)27031 66734 y(t)27654 63949 y Fg(\266)28632 65822 y Fl(S)77 b Fm(\()p Fl(l)30402 66021 y Ff(1)30928 65822 y Fl(;)221 b(l)31897 66021 y Ff(2)32424 65822 y Fl(;)g(:)g(:)g(:)j(;)d(l)35724 66021 y Fi(t)36120 65822 y Fm(\))800 69446 y(where)454 b(w)-36 b(e)454 b(sum)g(o)-36 b(v)g(er)454 b(all)h(men)-36 b(tioned)453 b Fl(t)p Fm(-tuples)g Fl(l)25407 69645 y Ff(1)25933 69446 y Fl(;)221 b(l)26902 69645 y Ff(2)27429 69446 y Fl(;)g(:)g(:)g(:)j(;)d (l)30729 69645 y Fi(t)31125 69446 y Fm(.)640 b(By)455 b(the)e(prop)36 b(erties)454 b(of)h(ord)45962 69645 y Ff(2)46942 69446 y Fm(and)f(of)h(the)800 71051 y(n)-36 b(um)g(b)36 b(ers)589 b Fl(b)6756 71250 y Fi(k)7325 71051 y Fm(,)630 b(ord)10195 71250 y Ff(2)10720 71051 y Fm(\()p Fl(S)77 b Fm(\()p Fl(l)12996 71250 y Ff(1)13523 71051 y Fl(;)221 b(l)14492 71250 y Ff(2)15018 71051 y Fl(;)g(:)g(:)g(:)j(;)d (l)18318 71250 y Fi(t)18714 71051 y Fm(\)\))636 b Fe(\270)g Fm(\()p Fl(n)403 b Fm(+)e Fl(t)h Fe(\241)g Fm(1\))p Fl(=)p Fm(2.)1050 b(Also,)631 b(for)591 b(o)36 b(dd)590 b Fl(t)g Fm(w)-36 b(e)591 b(ha)-36 b(v)g(e)591 b(ord)47826 71250 y Ff(2)48352 71051 y Fm(\()48858 69975 y Fg(\241)49467 70462 y Fi(n)49582 71509 y(t)50038 69975 y Fg(\242)50647 71051 y Fm(\))635 b(=)p Black 26150 74617 a(14)p Black eop %%Page: 15 15 15 14 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(ord)2679 1623 y Ff(2)3205 1424 y Fm(\()3844 901 y Fi(n)p 3844 1119 571 54 v 3960 1882 a(t)4547 348 y Fg(\241)5156 835 y Fi(n)p Fh(\241)p Ff(1)5271 1882 y Fi(t)p Fh(\241)p Ff(1)6929 348 y Fg(\242)7538 1424 y Fm(\))644 b(=)h(ord)12224 1623 y Ff(2)12749 1424 y Fm(\()p Fl(n)p Fm(\))406 b Fe(\241)g Fm(ord)18260 1623 y Ff(2)18786 1424 y Fm(\()p Fl(t)p Fm(\))f(+)g(ord)23969 1623 y Ff(2)24495 1424 y Fm(\()25001 348 y Fg(\241)25609 835 y Fi(n)p Fh(\241)p Ff(1)25725 1882 y Fi(t)p Fh(\241)p Ff(1)27383 348 y Fg(\242)27991 1424 y Fm(\))645 b Fe(\270)g Fm(ord)32699 1623 y Ff(2)33224 1424 y Fm(\()p Fl(n)p Fm(\),)637 b(and)595 b(ord)40580 1623 y Ff(2)41106 1424 y Fm(\()41612 348 y Fg(\241)42220 835 y Fi(n)42270 1882 y Ff(1)42791 348 y Fg(\242)43400 1424 y Fm(\))645 b(=)f(ord)48086 1623 y Ff(2)48612 1424 y Fm(\()p Fl(n)p Fm(\).)1064 b(It)800 3029 y(follo)-36 b(ws)436 b(that)d(ord)9767 3228 y Ff(2)10293 3029 y Fm(\(Com)13473 3228 y Fi(n)14099 3029 y Fm(\))369 b Fe(\270)g Fl(n=)p Fm(2)434 b(and,)g(moreo)-36 b(v)g(er,)434 b(ord)29617 3228 y Ff(2)30143 3029 y Fm(\(Com)33322 3228 y Fi(n)33948 3029 y Fm(\))369 b(=)g Fl(n=)p Fm(2)434 b(if)h(and)e(only)h(if)18972 6776 y(ord)20851 6975 y Ff(2)21598 4504 y Fg(\303)23796 5514 y(X)22650 8343 y Fi(l)11 b Fh(\267)p Fi(n;)261 b(l)271 b Ff(o)26 b(dd)27083 6776 y Fl(S)77 b Fm(\()p Fl(l)29 b Fm(\))29388 4504 y Fg(!)30809 6776 y Fm(=)369 b Fl(n=)p Fm(2)p Fl(:)800 10734 y Fm(In)337 b(the)g(last)h(sum)g(man)-36 b(y)337 b(summands)g(still)h(ha)-36 b(v)g(e)338 b(ord)26515 10933 y Ff(2)27378 10734 y Fm(bigger)g(than)f Fl(n=)p Fm(2:)531 b(if)339 b Fl(l)367 b Fm(is)338 b(congruen)-36 b(t)336 b(to)i(3)g(mo)36 b(dulo)800 12339 y(4)587 b(then)f(ord\()p Fl(S)77 b Fm(\()p Fl(l)29 b Fm(\)\))630 b Fl(>)f(n=)p Fm(2.)1039 b(On)586 b(the)g(other)g(hand,)625 b(if)587 b Fl(l)617 b Fm(is)587 b(congruen)-36 b(t)585 b(to)i(1)g(mo)36 b(dulo)587 b(4)g(then)f(eac)-36 b(h)800 13944 y(summand)444 b Fl(b)7297 14143 y Fi(l)7644 13944 y Fl(b)8197 14143 y Fi(k)8687 14266 y Fb(2)9425 13944 y Fl(:)221 b(:)g(:)i(b)11726 14143 y Fi(k)12216 14254 y Fc(n)13283 13944 y Fm(in)445 b Fl(S)77 b Fm(\()p Fl(l)29 b Fm(\))446 b(has)f(ord)21772 14143 y Ff(2)22298 13944 y Fm(\()p Fl(b)23357 14143 y Fi(l)23704 13944 y Fl(b)24257 14143 y Fi(k)24747 14266 y Fb(2)25485 13944 y Fl(:)221 b(:)g(:)i(b)27786 14143 y Fi(k)28276 14254 y Fc(n)28898 13944 y Fm(\))388 b(=)h Fl(n=)p Fm(2.)614 b(W)-108 b(e)445 b(conclude)g(that)g(ord)46562 14143 y Ff(2)47088 13944 y Fm(\(Com)50268 14143 y Fi(n)50894 13944 y Fm(\))388 b(=)800 15550 y Fl(n=)p Fm(2)395 b(if)g(and)f(only)g (if)h(the)f(n)-36 b(um)g(b)36 b(er)392 b Fl(c)p Fm(\()p Fl(n)p Fm(\))i(of)h(comp)36 b(ositions)395 b(of)f Fl(n)215 b Fe(\241)g Fm(1)394 b(in)-36 b(to)394 b Fl(n)h Fm(parts,)402 b(where)394 b(the)f(\257rst)g(part)800 17155 y(is)478 b Fe(\264)444 b Fm(1)478 b(mo)36 b(d)478 b(4)g(and)f(the)g(remaining)h Fl(n)326 b Fe(\241)f Fm(1)478 b(parts)f(are)h(ev)-36 b(en)478 b(\(zero)g(parts)f(are)h(allo)-36 b(w)g(ed\),)490 b(is)478 b(o)36 b(dd.)710 b(W)-108 b(e)800 18760 y(ha)-36 b(v)g(e)9041 21604 y Fl(c)p Fm(\()p Fl(n)p Fm(\))1118 b(=)f([)p Fl(x)15736 21056 y Fi(n)p Fh(\241)p Ff(1)17565 21604 y Fm(])19459 20706 y Fl(x)p 18059 21299 3539 54 v 18059 22516 a Fm(1)295 b Fe(\241)h Fl(x)21072 22132 y Ff(4)22026 21604 y Fe(\242)25687 20706 y Fm(1)p 22823 21299 6379 54 v 22823 22516 a(\(1)f Fe(\241)g Fl(x)26341 22132 y Ff(2)26867 22516 y Fm(\))27373 22132 y Fi(n)p Fh(\241)p Ff(1)29704 21604 y Fm(=)368 b([)p Fl(x)32184 21056 y Fi(n)p Fh(\241)p Ff(1)34013 21604 y Fm(])35896 20706 y Fl(x)p 34507 21299 3518 54 v 34507 22516 a Fm(1)296 b(+)f Fl(x)37499 22132 y Ff(2)38453 21604 y Fe(\242)41513 20706 y Fm(1)p 39250 21299 5177 54 v 39250 22516 a(\(1)g Fe(\241)g Fl(x)42768 22132 y Ff(2)43294 22516 y Fm(\))43800 22132 y Fi(n)12496 25045 y Fe(\264)1107 b Fm([)p Fl(x)15736 24497 y Fi(n)p Fh(\241)p Ff(1)17565 25045 y Fm(])19459 24147 y Fl(x)p 18059 24740 3539 54 v 18059 25956 a Fm(1)295 b Fe(\241)h Fl(x)21072 25573 y Ff(2)22026 25045 y Fe(\242)25086 24147 y Fm(1)p 22823 24740 5177 54 v 22823 25956 a(\(1)f Fe(\241)g Fl(x)26341 25573 y Ff(2)26867 25956 y Fm(\))27373 25573 y Fi(n)28501 25045 y Fm(=)369 b([)p Fl(x)30982 24497 y Fi(n)p Fh(\241)p Ff(1)32811 25045 y Fm(])36125 24147 y Fl(x)p 33305 24740 6379 54 v 33305 25956 a Fm(\(1)295 b Fe(\241)h Fl(x)36824 25573 y Ff(2)37350 25956 y Fm(\))37856 25573 y Fi(n)p Ff(+1)40250 25045 y Fm(mo)36 b(d)434 b(2)12507 28657 y(=)14636 26784 y Fg(\265)15614 27759 y Fm(3)p Fl(m)295 b Fe(\241)g Fm(1)15939 29569 y Fl(m)g Fe(\241)g Fm(1)19676 26784 y Fg(\266)21022 28657 y Fe(\264)22557 27759 y Fm(3)p Fl(m)p 22557 28352 1789 54 v 22883 29569 a(m)24478 26784 y Fg(\265)25456 27759 y Fm(3)p Fl(m)g Fe(\241)h Fm(1)25781 29569 y Fl(m)f Fe(\241)g Fm(1)29518 26784 y Fg(\266)30929 28657 y Fm(mo)36 b(d)434 b(2)12507 32288 y(=)14636 30415 y Fg(\265)15614 31390 y Fm(3)p Fl(m)15939 33199 y(m)17402 30415 y Fg(\266)18380 32288 y Fl(:)800 35845 y Fm(It)333 b(w)-36 b(as)334 b(noted)f(b)-36 b(y)333 b(Kummer)g([)p 0 1 0 0 TeXcolorcmyk(9)p (#cite.kumm) [[211 394 217 406] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(],)354 b(see)333 b(also)h(Singmaster)f([)p 0 1 0 0 TeXcolorcmyk(11)p (#cite.Si01) [[330 394 341 406] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(],)354 b(that)333 b(ord)35606 36044 y Fi(p)36135 35845 y Fm(\()36641 34769 y Fg(\241)37250 35255 y Fi(a)p Ff(+)p Fi(b)37865 36303 y(b)38884 34769 y Fg(\242)39493 35845 y Fm(\))g(is)g(equal)h(to)g(the)f(n)-36 b(um)g(b)36 b(er)800 37450 y(of)318 b(carries)g(required)f(when)g(adding)g Fl(a)g Fm(and)g Fl(b)g Fm(in)g(the)g Fl(p)p Fm(-ary)g(notation.)540 b(Applying)317 b(this)g(for)h Fl(p)369 b Fm(=)g(2,)341 b Fl(a)368 b Fm(=)h Fl(m)p Fm(,)800 39055 y(and)433 b Fl(b)369 b Fm(=)g(2)p Fl(m)p Fm(,)434 b(w)-36 b(e)433 b(get)h(the)f(stated)g(criterion.)p 52228 39055 572 572 v Black 800 41700 a Fd(Corollary)500 b(12)p Black 651 w Fk(F)-100 b(or)465 b(al)66 b(l)466 b Fl(n)369 b Fe(\270)g Fm(3)p Fk(,)15321 45008 y Fl(s)15934 45207 y Fi(n)16929 45008 y Fe(\264)18331 43135 y Fg(\275)20914 44195 y Fm(2)1108 b(mo)36 b(d)465 b(2)26280 43713 y Ff(\()p Fi(n)p Fh(\241)p Ff(1\))p Fi(=)p Ff(2)31353 44195 y Fk(for)g(o)-66 b(dd)465 b Fl(n)p Fm(;)19881 45822 y Fe(\241)p Fm(2)1108 b(mo)36 b(d)465 b(2)26280 45340 y Fi(n=)p Ff(2)31353 45822 y Fk(for)g(even)e Fl(n)p Fk(.)2751 48363 y Fm(Let)21808 50399 y Fl(C)22739 50598 y Fi(n)23734 50399 y Fm(=)26437 49501 y(1)p 25248 50094 3029 54 v 25248 51311 a Fl(n)295 b Fm(+)g(1)28409 48526 y Fg(\265)29387 49501 y Fm(2)p Fl(n)29712 51311 y(n)30814 48526 y Fg(\266)800 53264 y Fm(b)36 b(e)433 b(the)g Fl(n)p Fm(th)h(Catalan)g(n)-36 b(um)g(b)36 b(er.)p Black 800 55910 a Fd(Prop)42 b(osition)500 b(13)p Black 651 w Fk(F)-100 b(or)465 b(al)66 b(l)466 b Fl(n)p Fk(,)f Fm(Com)19617 56109 y Fi(n)20612 55910 y Fe(\264)370 b Fl(C)22946 56109 y Fi(n)p Fh(\241)p Ff(1)25239 55910 y Fm(mo)36 b(d)464 b(3)p Fk(.)2751 58555 y Fd(Pro)42 b(of)p Fm(:)1156 b(W)-108 b(e)434 b(ha)-36 b(v)g(e,)434 b(for)g(ev)-36 b(ery)434 b(non-negativ)-36 b(e)434 b(in)-36 b(teger)433 b Fl(k)45 b Fm(,)16521 61139 y(\(2!)p Fl(x)296 b Fm(+)f(3!)p Fl(x)22130 60591 y Ff(2)22952 61139 y Fm(+)g Fe(\242)221 b(\242)g(\242)h Fm(\))26536 60591 y Fi(k)27473 61139 y Fm(=)369 b(\(2)p Fl(x)p Fm(\))31255 60591 y Fi(k)32119 61139 y Fm(+)295 b(3)p Fl(a)34759 61338 y Fi(k)35328 61139 y Fm(\()p Fl(x)p Fm(\))800 63724 y(with)434 b Fl(a)4446 63923 y Fi(k)5014 63724 y Fm(\()p Fl(x)p Fm(\))369 b Fe(2)g Fd(Z)p Fm([[)p Fl(x)p Fm(]].)579 b(Th)-36 b(us)10021 65639 y Fg(X)10123 68468 y Fi(k)24 b Fh(\270)p Ff(0)11940 66901 y Fm(\()p Fe(\241)p Fm(1\))14635 66352 y Fi(k)15204 66901 y Fm(\(2!)p Fl(x)296 b Fm(+)f(3!)p Fl(x)20813 66352 y Ff(2)21634 66901 y Fm(+)g Fe(\242)221 b(\242)g(\242)h Fm(\))25218 66352 y Fi(k)26894 66901 y Fm(=)30641 66002 y(1)p 29145 66595 3642 54 v 29145 67812 a(1)296 b(+)f(2)p Fl(x)33215 66901 y Fm(+)g(3)35393 65639 y Fg(X)35495 68468 y Fi(k)24 b Fh(\270)p Ff(0)37312 66901 y Fm(\()p Fe(\241)p Fm(1\))40007 66352 y Fi(k)40576 66901 y Fl(a)41259 67100 y Fi(k)41828 66901 y Fm(\()p Fl(x)p Fm(\))26894 70947 y(=)30641 70049 y(1)p 29145 70642 V 29145 71858 a(1)296 b(+)f(2)p Fl(x)33215 70947 y Fm(+)g(3)p Fl(b)p Fm(\()p Fl(x)p Fm(\))p Black 26150 74617 a(15)p Black eop %%Page: 16 16 16 15 bop Black 0 TeXcolorgray Black Black 800 1424 a Fm(with)502 b Fl(b)p Fm(\()p Fl(x)p Fm(\))484 b Fe(2)h Fd(Z)p Fm([[)p Fl(x)p Fm(]].)784 b(Let)501 b Fl(m)484 b Fm(=)g(ord)19626 1623 y Ff(3)20152 1424 y Fm(\()p Fl(n)p Fm(\).)782 b(Since)502 b(ord)28426 1623 y Ff(3)28952 1424 y Fm(\()p Fl(k)45 b Fm(!\))485 b Fe(\267)g Fl(k)386 b Fe(\241)342 b Fm(1)502 b(for)g(ev)-36 b(ery)503 b Fl(k)546 b Fm(\(Lemma)p 0 1 0 0 TeXcolorcmyk 501 w(10)p (#definition.10) [[510 704 521 716] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)520 b(w)-36 b(e)800 3029 y(ha)g(v)g(e)15307 4634 y(ord)17186 4833 y Ff(3)17712 3160 y Fg(\263)18505 4634 y Fm(3)19155 4152 y Fi(k)19724 3558 y Fg(\241)20333 4045 y Fi(n)20362 5092 y(k)20904 3558 y Fg(\242)21513 3160 y(\264)22675 4634 y Fe(\270)369 b Fl(m)295 b Fm(+)g(1)434 b(for)g Fl(k)414 b Fm(=)369 b(1)p Fl(;)221 b Fm(2)p Fl(;)g(:)g(:)g(:)k (;)c(n)p Fm(.)800 7223 y(By)434 b(Lemma)p 0 1 0 0 TeXcolorcmyk 434 w(9)p (#definition.9) [[139 652 145 664] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)7037 10849 y Fl(n)296 b Fe(\242)f Fm(Com)11447 11048 y Fi(n)12442 10849 y Fm(=)369 b([)p Fl(x)14923 10300 y Fi(n)p Fh(\241)p Ff(1)16752 10849 y Fm(])17334 8976 y Fg(\265)19941 9950 y Fm(1)p 18445 10543 3642 54 v 18445 11760 a(1)295 b(+)g(2)p Fl(x)22515 10849 y Fm(+)g(3)p Fl(b)p Fm(\()p Fl(x)p Fm(\))26776 8976 y Fg(\266)27753 9273 y Fi(n)29487 10849 y Fe(\264)1107 b Fm([)p Fl(x)32727 10300 y Fi(n)p Fh(\241)p Ff(1)34556 10849 y Fm(])37365 9950 y(1)p 35050 10543 5280 54 v 35050 11760 a(\(1)295 b(+)g(2)p Fl(x)p Fm(\))39703 11376 y Fi(n)40896 10849 y Fm(mo)36 b(d)433 b(3)44472 10300 y Fi(m)p Ff(+1)29497 14480 y Fm(=)1118 b(\()p Fe(\241)p Fm(2\))34322 13931 y Fi(n)p Fh(\241)p Ff(1)36150 12607 y Fg(\265)37128 13581 y Fm(2)p Fl(n)296 b Fe(\241)g Fm(2)37453 15391 y Fl(n)g Fe(\241)f Fm(1)40829 12607 y Fg(\266)41807 14480 y Fl(:)800 18074 y Fm(Canceling)435 b(in)e(the)g(last)h(congruence)f(the)g(common) h(factor)g(3)31553 17592 y Fi(m)32441 18074 y Fm(,)g(w)-36 b(e)434 b(get)11373 20796 y Fl(n)p 10992 21389 1538 54 v 10992 22605 a Fm(3)11642 22222 y Fi(m)12958 21694 y Fe(\242)295 b Fm(Com)16296 21893 y Fi(n)17291 21694 y Fe(\264)18826 20796 y Fm(\()p Fe(\241)p Fm(2\))21521 20314 y Fi(n)p Fh(\241)p Ff(1)p 18826 21389 4524 54 v 20319 22605 a Fm(3)20969 22222 y Fi(m)23482 19821 y Fg(\265)24460 20796 y Fm(2)p Fl(n)h Fe(\241)f Fm(2)24785 22605 y Fl(n)h Fe(\241)f Fm(1)28161 19821 y Fg(\266)29507 21694 y Fe(\264)31486 20796 y Fm(1)p 31042 21389 1538 54 v 31042 22605 a(3)31692 22222 y Fi(m)32713 19821 y Fg(\265)33691 20796 y Fm(2)p Fl(n)h Fe(\241)f Fm(2)34016 22605 y Fl(n)h Fe(\241)f Fm(1)37392 19821 y Fg(\266)38803 21694 y Fm(mo)36 b(d)434 b(3)p Fl(:)800 25363 y Fm(Since)f Fl(n=)p Fm(3)6272 24881 y Fi(m)7530 25363 y Fe(6\264)369 b Fm(0)434 b(mo)36 b(d)433 b(3,)i(w)-36 b(e)433 b(can)h(divide)g(b)-36 b(y)433 b(it)h(and)f(get) 18730 29031 y(Com)21403 29230 y Fi(n)22398 29031 y Fe(\264)23996 28133 y Fm(1)p 23933 28726 777 54 v 23933 29942 a Fl(n)24843 27158 y Fg(\265)25820 28133 y Fm(2)p Fl(n)296 b Fe(\241)g Fm(2)26146 29942 y Fl(n)f Fe(\241)h Fm(1)29521 27158 y Fg(\266)30932 29031 y Fm(mo)36 b(d)434 b(3)p Fl(:)p 52228 32275 572 572 v Black 800 35287 a Fd(Corollary)500 b(14)p Black 651 w Fk(F)-100 b(or)465 b(al)66 b(l)466 b Fl(n)369 b(>)g Fm(2)p Fk(,)18720 38191 y Fl(s)19333 38390 y Fi(n)20328 38191 y Fe(\264)g(\241)p Fl(C)23694 38390 y Fi(n)p Fh(\241)p Ff(1)25817 38191 y Fm(+)295 b(\()p Fe(\241)p Fm(1\))29819 37643 y Fi(n)30911 38191 y Fm(mo)36 b(d)464 b(3)p Fl(:)800 42624 y Fn(5)2152 b(Concluding)715 b(remarks)800 45545 y Fm(The)587 b(simplicit)-36 b(y)588 b(prop)36 b(ert)-36 b(y)587 b(for)h(p)36 b(erm)-36 b(utations)586 b(do)36 b(es)587 b(not)g(seem)g(to)h(ha)-36 b(v)g(e)587 b(b)36 b(een)587 b(studied)f(un)-36 b(til)586 b(v)-36 b(ery)800 47150 y(recen)g(tly)463 b([)p 0 1 0 0 TeXcolorcmyk(10)p (#cite.Mu01) [[127 293 139 305] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(,)p 0 1 0 0 TeXcolorcmyk 463 w(1)p (#cite.AA02) [[146 293 152 305] [1 1 1 [3 3]] [0 0 1]] pdfm Black(].)667 b(W)-108 b(e)463 b(ha)-36 b(v)g(e)463 b(b)36 b(egun)462 b(the)g(study)g(of)i(the)e(n)-36 b(um)g(b)36 b(ers)461 b Fl(s)35010 47349 y Fi(n)36099 47150 y Fm(b)-36 b(y)463 b(sho)-36 b(wing)463 b(that)g(they)f(are)h(not)800 48755 y(P-recursiv)-36 b(e,)412 b(giving)c(the)e(\257rst)f(few)j(terms) e(of)h(their)f(asymptotic)i(expansion,)k(and)406 b(sho)-36 b(wing)407 b(that)f(they)800 50360 y(satisfy)435 b(some)f(unexp)36 b(ected)433 b(congruence)g(prop)36 b(erties.)2751 51965 y(These)335 b(results)f(suggest)h(a)g(n)-36 b(um)g(b)36 b(er)333 b(of)j(natural)e(con)-36 b(tin)g(uations.)545 b(Although,)354 b(in)335 b(principle,)354 b(w)-36 b(e)335 b(could)800 53570 y(obtain)531 b(more)g(terms)g(of)h(the)e(asymptotic)i (expansion)f(the)g(en)-36 b(tire)531 b(expansion)g(remains)g(elusiv)-36 b(e,)557 b(and)800 55175 y(computing)428 b(it)g(seems)g(to)g(b)36 b(e)428 b(rather)f(a)i(di\261cult)e(problem.)577 b(On)427 b(the)g(other)h(hand)f(w)-36 b(e)429 b(ha)-36 b(v)g(e)428 b(some)g(com-)800 56780 y(putational)335 b(evidence)g(to)g(suggest)g (that)f(the)g(sequence)h(Com)30913 56979 y Fi(n)31874 56780 y Fm(has)g(additional)g(congruence)f(prop)36 b(erties,)800 58385 y(particularly)434 b(with)g(resp)36 b(ect)433 b(to)h(o)36 b(dd)433 b(primes.)2751 59990 y(W)-108 b(e)386 b(suggest)g(also)g(some) g(algorithmic)h(problems)e(that)g(are)h(natural)f(coun)-36 b(terparts)385 b(to)g(the)h(en)-36 b(umer-)800 61596 y(ativ)g(e)434 b(results:)p Black 2737 64283 a Fe(\262)p Black 651 w Fm(Ho)-36 b(w)434 b(can)f(one)h(e\261cien)-36 b(tly)434 b(generate)g(simple)f(p)36 b(erm)-36 b(utations)433 b(in)h(lexicographic)h(order?)p Black 2737 66987 a Fe(\262)p Black 651 w Fm(Is)358 b(it)g(p)36 b(ossible)358 b(to)g(generate)g (simple)g(p)36 b(erm)-36 b(utations)357 b(uniformly)i(at)f(random)g(in) f(w)-36 b(orst-case)359 b(linear)4052 68592 y(time)433 b(p)36 b(er)433 b(p)36 b(erm)-36 b(utation?)p Black 2737 71296 a Fe(\262)p Black 651 w Fm(Ho)g(w)434 b(e\261cien)-36 b(tly)434 b(can)f(one)h(recognise)g(a)g(simple)g(p)36 b(erm)-36 b(utation?)p Black 26150 74617 a(16)p Black eop %%Page: 17 17 17 16 bop Black 0 TeXcolorgray Black Black 2751 1424 a Fm(With)503 b(regards)h(to)f(the)g(\257nal)g(question,)522 b(there)503 b(is)g(a)h(natural)f(dynamic)h(programming)f(algorithm)800 3029 y(that)602 b(ac)-36 b(hiev)g(es)602 b(the)g(task)g(in)g Fl(O)36 b Fm(\()p Fl(n)18348 2547 y Ff(2)18875 3029 y Fm(\))601 b(time.)1084 b(Namely)-108 b(,)645 b(for)603 b(a)f(p)36 b(erm)-36 b(utation)601 b Fl(\274)650 b Fm(of)603 b(length)e Fl(n)i Fm(w)-36 b(e)602 b(can)800 4634 y(compute)433 b(the)g(v)-72 b(alues:)17515 7568 y Fl(m)18653 7767 y Fi(\274)19280 7568 y Fm(\()p Fl(i;)221 b(j)75 b Fm(\))1107 b(=)f(min)p Fe(f)p Fl(\274)28726 7767 y Fi(t)29490 7568 y Fm(:)369 b Fl(i)g Fe(\267)g Fl(t)g Fe(\267)g Fl(j)75 b Fe(g)17394 9505 y Fl(M)18652 9704 y Fi(\274)19280 9505 y Fm(\()p Fl(i;)221 b(j)75 b Fm(\))1107 b(=)f(max)q Fe(f)p Fl(\274)28979 9704 y Fi(t)29743 9505 y Fm(:)369 b Fl(i)g Fe(\267)g Fl(t)g Fe(\267)g Fl(j)75 b Fe(g)800 12438 y Fm(for)434 b(1)369 b Fe(\267)h Fl(i)e Fe(\267)h Fl(j)444 b Fe(\267)369 b Fl(n)434 b Fm(in)g(time)f Fl(O)36 b Fm(\()p Fl(n)17809 11956 y Ff(2)18336 12438 y Fm(\))433 b(using)g(the)g(facts)i (that)17370 15372 y Fl(m)18508 15571 y Fi(\274)19135 15372 y Fm(\()p Fl(i;)221 b(j)75 b Fm(\))1107 b(=)f(min\()p Fl(m)28823 15571 y Fi(\274)29450 15372 y Fm(\()p Fl(i;)221 b(j)75 b Fm(\))p Fl(;)221 b(\274)33421 15571 y Fi(j)51 b Ff(+1)35110 15372 y Fm(\))17249 17309 y Fl(M)18507 17508 y Fi(\274)19135 17309 y Fm(\()p Fl(i;)221 b(j)75 b Fm(\))1107 b(=)f(max)q(\()p Fl(M)29196 17508 y Fi(\274)29823 17309 y Fm(\()p Fl(i;)221 b(j)75 b Fm(\))p Fl(;)221 b(\274)33794 17508 y Fi(j)51 b Ff(+1)35484 17309 y Fm(\))p Fl(:)800 20242 y Fm(Then)509 b(w)-36 b(e)511 b(can)e(test)h(for)g(eac)-36 b(h)510 b Fl(i)499 b(<)f(j)585 b Fm(whether)509 b Fl(M)26299 20441 y Fi(\274)26927 20242 y Fm(\()p Fl(i;)221 b(j)75 b Fm(\))347 b Fe(\241)g Fl(m)32443 20441 y Fi(\274)33070 20242 y Fm(\()p Fl(i;)221 b(j)75 b Fm(\))499 b(=)f Fl(j)422 b Fe(\241)347 b Fl(i)p Fm(.)807 b(If)511 b(this)e(nev)-36 b(er)510 b(o)36 b(ccurs)800 21848 y(then)423 b Fl(\274)471 b Fm(is)425 b(simple,)h(if)e(it)g(do)36 b(es,)427 b(then)c(it)h(is)g (not.)575 b(So)423 b(in)h(this)g(instance)f(the)h(question)g(is)g (whether)f(or)h(not)800 23453 y(one)434 b(can)f(do)h(b)36 b(etter)432 b(than)h(this.)2751 25058 y(W)-108 b(e)434 b(w)-36 b(ould)433 b(lik)-36 b(e)435 b(to)e(thank)h(an)f(anon)-36 b(ymous)434 b(referee)g(for)g(a)g(n)-36 b(um)g(b)36 b(er)432 b(of)i(helpful)g(commen)-36 b(ts.)800 29495 y Fn(References)p Black 1450 32415 a Fm([1])p Black 652 w(M.)501 b(H.)g(Alb)36 b(ert)501 b(and)f(M.)h(D.)h(A)-36 b(tkinson,)794 b(Simple)501 b(p)36 b(erm)-36 b(utations,)517 b(partial)502 b(w)-36 b(ell-order,)518 b(and)500 b(en)-36 b(u-)3474 34020 y(meration.)442 b(In)351 b(M.H.)h(Alb)36 b(ert)351 b(ed.,)368 b Fk(Pr)-66 b(o)g(c)g(e)g(e)g(dings,)400 b(Permutation)389 b(Patterns)f(2003)p Fm(,)p 0 1 0 0 TeXcolorcmyk 369 w Fa(www.cs.otago.)p [[467 411 547 423] [1 1 1 [3 3]] [0 0 1]] (www.cs.otago.ac.nz/trseries/oucs-2003-02.pdf) pdfm 3474 35625 a(ac.nz/trseries/oucs-)55 b(2003-)g(02.pdf)p [[79 396 295 408] [1 1 1 [3 3]] [0 0 1]] (www.cs.otago.ac.nz/trseries/oucs-2003-02.pdf) pdfm Black Fm(,)420 b(2003,)435 b(pp.)e(5{9.)p Black 1450 38338 a([2])p Black 652 w(M.)350 b(D.)h(A)-36 b(tkinson)351 b(and)f(T.)h(Stitt,)458 b(Restricted)350 b(p)36 b(erm)-36 b(utations)350 b(and)g(the)g(wreath)g(pro)36 b(duct.)441 b Fk(Discr)-66 b(ete)3474 39943 y(Math.)p Fm(,)433 b Fd(259)h Fm(\(2002\),)h(19{36.)p Black 1450 42655 a([3])p Black 652 w(Edw)-36 b(ard)308 b(A.)i(Bender)f(and)g(L.)g(Bruce)g(Ric) -36 b(hmond,)399 b(An)308 b(asymptotic)i(expansion)g(for)g(the)f(co)36 b(e\261cien)-36 b(ts)3474 44260 y(of)434 b(some)g(p)36 b(o)-36 b(w)g(er)433 b(series.)i(I)36 b(I.)434 b(Lagrange)g(in)-36 b(v)g(ersion.)577 b Fk(Discr)-66 b(ete)463 b(Math.)p Fm(,)434 b Fd(50)g Fm(\(1984\),)g(135{141.)p Black 1450 46972 a([4])p Black 652 w(Louis)f(Com)-36 b(tet,)577 b Fk(A)-66 b(dvanc)g(e)g(d)463 b(c)-66 b(ombinatorics)p Fm(.)575 b(D.)434 b(Reidel,)g(1974.)p Black 1450 49684 a([5])p Black 652 w(P)-108 b(.)1121 b(Fla)72 b(jolet)1123 b(and)e(R.)i(Sedgewic)-36 b(k,)2800 b Fk(A)-33 b(nalytic)1095 b(Combinatorics|Symb)-66 b(olic)1094 b(Combina-)3474 51289 y(torics)p Fm(,)2218 b(Preprin)-36 b(t)941 b(published)f (electronically)k(at,)p 0 1 0 0 TeXcolorcmyk 1070 w Fa (http://algo.inria.fr/flajolet/)p [[363 255 547 267] [1 1 1 [3 3]] [0 0 1]] (http://algo.inria.fr/flajolet/Publications/books.html) pdfm 3474 52894 a(Publications/books.html)p [[79 241 245 253] [1 1 1 [3 3]] [0 0 1]] (http://algo.inria.fr/flajolet/Publications/books.html) pdfm Black Fm(,)423 b(2002.)p Black 1450 55606 a([6])p Black 652 w(I.)538 b(P)-108 b(.)539 b(Goulden)e(and)h(D.)h(M.)f(Jac)-36 b(kson,)916 b Fk(Combinatorial)560 b(enumer)-66 b(ation)p Fm(.)887 b(John)538 b(Wiley)h(&)f(Sons,)3474 57211 y(1983.)p Black 1450 59923 a([7])p Black 652 w(Irving)494 b(Kaplansky)-108 b(,)770 b(The)494 b(asymptotic)f(distribution)g(of)h(runs)e(of)i (consecutiv)-36 b(e)494 b(elemen)-36 b(ts,)769 b Fk(A)-33 b(nn.)3474 61528 y(Math.)464 b(Statistics)p Fm(,)432 b Fd(16)i Fm(\(1945\),)h(200{203.)p Black 1450 64240 a([8])p Black 652 w(Martin)441 b(Klazar,)603 b(Non-P-recursiv)-36 b(eness)440 b(of)i(n)-36 b(um)g(b)36 b(ers)440 b(of)i(matc)-36 b(hings)441 b(or)h(linear)g(c)-36 b(hord)440 b(diagrams)3474 65845 y(with)433 b(man)-36 b(y)434 b(crossings,)577 b Fk(A)-66 b(dv.)464 b(Appl.)g(Math.)p Fm(,)434 b Fd(30)g Fm(\(2003\),)g(126{136.)p Black 1450 68558 a([9])p Black 652 w(E.)516 b(E.)h(Kummer,)13352 68222 y(\304)13190 68558 y(Ub)36 b(er)516 b(die)g(Erg\304)-650 b(anzungss\304)g(atze)517 b(zu)f(den)g(allgemeinen)h(Recipro)36 b(cit\304)-650 b(atsgezetzen,)3474 70163 y Fk(J.)464 b(R)-66 b(eine)463 b(A)-33 b(ngew.)463 b(Math.)p Fm(,)433 b Fd(44)h Fm(\(1852\),)h (93{146.)p Black 26150 74617 a(17)p Black eop %%Page: 18 18 18 17 bop Black 0 TeXcolorgray Black Black Black 800 1424 a Fm([10])p Black 652 w(M.)468 b(M.)h(Murph)-36 b(y)-108 b(,)689 b Fk(R)-66 b(estricte)g(d)494 b(p)-66 b(ermutations,)504 b(antichains,)f(atomic)497 b(classes)h(and)f(stack)g (sorting)p Fm(,)3474 3029 y(PhD)433 b(thesis,)h(Univ)-36 b(ersit)g(y)434 b(of)g(St.)g(Andrews,)f(2002.)p Black 800 5741 a([11])p Black 652 w(Da)-36 b(vid)411 b(Singmaster,)543 b(Notes)410 b(on)g(binomial)h(co)36 b(e\261cien)-36 b(ts.)410 b(I.)h(A)f(generalization)h(of)g(Lucas')f(congru-)3474 7346 y(ence,)576 b Fk(J.)465 b(L)-66 b(ondon)464 b(Math.)g(So)-66 b(c.)464 b(\(2\))p Fm(,)435 b Fd(8)e Fm(\(1974\),)i(545{548.)p Black 800 10058 a([12])p Black 652 w(N.)364 b(J.)g(A.)h(Sloane,)477 b(The)364 b(on-line)g(encyclop)36 b(edia)365 b(of)g(in)-36 b(teger)364 b(sequences,)p 0 1 0 0 TeXcolorcmyk 477 w Fa(http://www.research.)p [[424 626 547 638] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/~njas/sequences/) pdfm 3474 11663 a(att.com/~njas/sequences/)p [[79 612 251 624] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/~njas/sequences/) pdfm Black Fm(,)423 b(2003.)p Black 800 14376 a([13])p Black 652 w(Ric)-36 b(hard)337 b(P)-108 b(.)338 b(Stanley)-108 b(,)440 b Fk(Enumer)-66 b(ative)375 b(c)-66 b(ombinatorics.)374 b(Vol.)i(2)p Fm(,)358 b(v)-36 b(olume)338 b(62)g(of)h Fk(Cambridge)376 b(Studies)3474 15981 y(in)464 b(A)-66 b(dvanc)g(e)g(d)462 b(Mathematics)p Fm(,)576 b(Cam)-36 b(bridge)434 b(Univ)-36 b(ersit)g(y)434 b(Press,)g(1999.)p 800 19051 52000 45 v 800 21301 a(2000)423 b Fk(Mathematics)454 b(Subje)-66 b(ct)452 b(Classi\257c)-66 b(ation:)570 b Fm(Primary)423 b(05A05;)k(Secondary)422 b(05A15,)k(05A16,)g(11A07.)800 22907 y Fk(Keywor)-66 b(ds:)1250 b Fm(P)-36 b(erm)g(utation,)433 b Fl(P)181 b Fm(-recursiv)-36 b(eness,)434 b(asymptotic)g(en)-36 b(umeration.)p 800 25884 V 800 28209 a(\(Concerned)433 b(with)h(sequence)p 0 1 0 0 TeXcolorcmyk 433 w(A059372)p 16090 28421 4878 54 v [[217 463 261 475] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=A059372) pdfm Black 2 w(.\))p 800 29914 52000 45 v 800 32964 a(Receiv)-36 b(ed)474 b(April)f(15)h(2003;)494 b(revised)474 b(v)-36 b(ersion)473 b(receiv)-36 b(ed)474 b(Octob)36 b(er)472 b(30)i(2003.)699 b(Published)472 b(in)h Fk(Journal)501 b(of)800 34570 y(Inte)-66 b(ger)463 b(Se)-66 b(quenc)g(es)p Fm(,)431 b(Decem)-36 b(b)36 b(er)434 b(13)g(2003.)p 800 36200 V 800 38451 a(Return)f(to)p 0 1 0 0 TeXcolorcmyk 433 w(Journal)h(of)g(In)-36 b(teger)434 b(Sequences)f(home)g(page)p [[133 371 338 383] [1 1 1 [3 3]] [0 0 1]] (http://www.math.uwaterloo.ca/JIS/) pdfm Black(.)p Black 26150 74617 a(18)p Black eop %%Trailer end end