%%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.7) 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 7266 12479 a Fq(A)862 b(Com)-72 b(binatorial)863 b(Deriv)-143 b(ation)862 b(of)f(the)11001 16851 y(Num)-72 b(b)72 b(er)862 b(of)g(Lab)72 b(eled)861 b(F)-215 b(orests)22302 21994 y Fp(Da)-43 b(vid)520 b(Callan)18435 23986 y(Departmen)-43 b(t)519 b(of)i(Statistics)15554 25979 y(Univ)-43 b(ersit)g(y)518 b(of)j(Wisconsin-Madison)19983 27971 y(1210)h(W.)d(Da)-43 b(yton)521 b(St.)18060 29964 y(Madison,)g(WI)1040 b(53706-1693)p 0 1 0 0 TeXcolorcmyk 18597 31956 a Fo(callan@stat.wisc.edu)p [[239 429 387 441] [1 1 1 [3 3]] [0 0 1]] (mailto:callan@stat.wisc.edu) pdfm Black Black Black 24133 36356 a Fn(Abstract)p Black Black 5870 38459 a Fm(La)67 b(jos)371 b(T)-101 b(ak\266)-606 b(acs)371 b(ga)-34 b(v)g(e)371 b(a)g(somewhat)h(formidable)f (alternating)h(sum)f(expression)g(for)g(the)g(n)-34 b(um-)4052 39964 y(b)34 b(er)440 b(of)i(forests)g(of)f(unro)34 b(oted)442 b(trees)f(on)h Fl(n)f Fm(lab)34 b(eled)440 b(v)-34 b(ertices.)649 b(Here)440 b(w)-34 b(e)442 b(use)g(a)f(w)-34 b(eigh)g(t-rev)g(ersing) 4052 41470 y(in)g(v)g(olution)375 b(on)g(suitable)f(tree)g (con\257gurations)i(to)f(giv)-34 b(e)373 b(a)i(com)-34 b(binatorial)374 b(deriv)-67 b(ation)374 b(of)h(T)-101 b(ak\266)-606 b(acs')4052 42975 y(result.)2751 47357 y Fk(T)-108 b(ak\266)-650 b(acs)435 b([)p 0 1 0 0 TeXcolorcmyk(1)p (#cite.takacs) [[139 291 145 303] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])f(used)f(Lagrange)h(in)-36 b(v)g(ersion)434 b(to)g(obtain)f (the)g(alternating)h(sum)f(expression)17809 50664 y Fj(n)p Fk(!)p 16863 51257 3029 54 v 16863 52474 a Fj(n)296 b Fk(+)f(1)20246 49799 y Fi(b)p Fh(n=)p Fg(2)p Fi(c)20461 50301 y Ff(X)20603 53100 y Fh(j)51 b Fg(=0)22594 51562 y Fk(\()p Fe(\241)p Fk(1\))25289 51014 y Fh(j)25909 50664 y Fk(\(2)p Fj(j)370 b Fk(+)295 b(1\)\()p Fj(n)h Fk(+)f(1\))34477 50182 y Fh(n)p Fi(\241)p Fg(2)p Fh(j)p 25909 51257 10828 54 v 27749 52474 a Fk(2)28399 52090 y Fh(j)28887 52474 y Fj(j)75 b Fk(!\()p Fj(n)295 b Fe(\241)g Fk(2)p Fj(j)75 b Fk(\)!)51138 51562 y(\(1\))800 55714 y(for)495 b(the)e(n)-36 b(um)g(b)36 b(er)493 b(of)h(forests)h(of)g(unro)36 b(oted)493 b(trees)h(on)g([)p Fj(n)p Fk(])473 b(=)f Fe(f)p Fk(1)p Fj(;)221 b Fk(2)p Fj(;)g(:)g(:)g(:)k(;)c(n)p Fe(g)p 0 1 0 0 TeXcolorcmyk 495 w Fk(A001858)p [[420 216 464 228] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001858) pdfm Black(.)762 b(This)494 b(con)-36 b(trasts)800 57319 y(with)384 b(Ca)-36 b(yley's)386 b(simple)e(expression)g(\()p Fj(n)193 b Fk(+)g(1\))22892 56837 y Fh(n)p Fi(\241)p Fg(1)p 0 1 0 0 TeXcolorcmyk 25105 57319 a Fk(A000272)p [[298 201 342 213] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000272) pdfm Black 386 w(for)384 b(the)f(n)-36 b(um)g(b)36 b(er)382 b(of)j(forests)f(of)g(ro)36 b(oted)384 b(trees)800 58924 y(on)539 b([)p Fj(n)p Fk(].)897 b(Here)540 b(w)-36 b(e)539 b(use)g(w)-36 b(ell-kno)g(wn)540 b(coun)-36 b(ts)539 b(for)h(forests)g(of)g(ro)36 b(oted)539 b(trees)h(to)f(giv)-36 b(e)540 b(a)g(com)-36 b(binatorial)800 60529 y(deriv)-72 b(ation)572 b(of)g(T)-108 b(ak\266)-650 b(acs's)573 b(result:)854 b(w)-36 b(e)572 b(presen)-36 b(t)570 b(\()p 0 1 0 0 TeXcolorcmyk(1)p (#equation.1) [[303 172 309 184] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))i(as)f(the)g(total)h(w)-36 b(eigh)g(t)572 b(of)g(certain)g(w) -36 b(eigh)g(ted)571 b(tree)800 62134 y(con\257gurations)460 b(in)h(whic)-36 b(h)461 b(forests)g(of)g(unro)36 b(oted)460 b(trees)h(sho)-36 b(w)461 b(up)e(with)i(w)-36 b(eigh)g(t)461 b(+1)g(and)f(w)-36 b(e)461 b(exhibit)g(a)800 63739 y(w)-36 b(eigh)g(t-rev)g(ersing)525 b(in)-36 b(v)g(olution)525 b(that)f(cancels)h(out)f(the)h(w)-36 b(eigh)g(ts)524 b(of)i(all)f(other)g(con\257gurations.)851 b(First,)800 65344 y(rewrite)434 b(\()p 0 1 0 0 TeXcolorcmyk(1)p (#equation.1) [[123 129 129 141] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))f(as)9431 67653 y Ff(X)8452 70531 y Fg(0)p Fi(\267)p Fh(j)51 b Fi(\267)p Fh(n=)p Fg(2)12763 68915 y Fk(\()p Fe(\241)p Fk(1\))15458 68367 y Fh(j)17550 67042 y Ff(\265)18771 68016 y Fj(n)18528 69826 y Fk(2)p Fj(j)19791 67042 y Ff(\266)20769 68915 y Fk(\(2)p Fj(j)370 b Fe(\241)295 b Fk(1\)!!)17550 70668 y Ff(|)p 18148 70668 3050 160 v 3050 w({z)p 22394 70668 V 3050 w(})21443 71827 y Fh(A)27866 68915 y Fk(\(2)p Fj(j)371 b Fk(+)294 b(1\)\()p Fj(n)i Fk(+)f(1\))36434 68367 y Fg(\()p Fh(n)p Fg(+1\))p Fi(\241)p Fg(\(2)p Fh(j)51 b Fg(+1\))p Fi(\241)p Fg(1)27866 70606 y Ff(|)p 28464 70606 7446 160 v 7446 w({z)p 37106 70606 V 7446 w(})36131 71764 y Fh(B)51138 68915 y Fk(\(2\))p Black 26475 74617 a(1)p Black eop %%Page: 2 2 2 1 bop Black 0 TeXcolorgray Black Black 800 1424 a Fk(where)428 b(\(2)p Fj(j)359 b Fe(\241)284 b Fk(1\)!!)370 b(=)f(1)284 b Fe(\242)g Fk(3)g Fe(\242)g Fk(5)221 b Fj(:)g(:)g(:)j Fk(\(2)p Fj(j)359 b Fe(\241)284 b Fk(1\))429 b(is)f(the)g(double)f (factorial.)578 b(The)429 b(factor)g Fj(B)495 b Fk(is)428 b(the)g(n)-36 b(um)g(b)36 b(er)426 b(of)800 3029 y(forests)382 b(on)f([0)p Fj(;)221 b(n)p Fk(])384 b(consisting)e(of)g(2)p Fj(j)264 b Fk(+)189 b(1)381 b(trees)g(ro)36 b(oted)382 b(at)g(a)f(sp)36 b(eci\257ed)381 b(set)h(of)g(2)p Fj(j)264 b Fk(+)189 b(1)381 b(ro)36 b(ots)382 b([)p 0 1 0 0 TeXcolorcmyk(2)p (#cite.moon) [[489 690 495 702] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(,)392 b(Theorem)800 4634 y(3.3,)427 b(p.)289 b(17])425 b(\(see)f(also)h([)p 0 1 0 0 TeXcolorcmyk(3)p (#cite.pitman) [[182 675 188 687] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(,)h Fe(x)p Fk(2.1])g(for)f(a)f(recen)-36 b(t)424 b(elegan)-36 b(t)424 b(pro)36 b(of)93 b(\).)575 b(The)425 b(factor)g Fj(A)f Fk(is)g(the)g(n)-36 b(um)g(b)36 b(er)422 b(of)j(w)-36 b(a)g(ys)800 6239 y(to)483 b(select)f(2)p Fj(j)558 b Fk(elemen)-36 b(ts)482 b(from)h([)p Fj(n)p Fk(])g(and)f(then)g(divide)h(them)e(up)h(in)-36 b(to)482 b(pairs;)508 b(in)482 b(other)g(w)-36 b(ords,)495 b(to)483 b(form)800 7844 y(a)514 b(p)36 b(erfect)514 b(matc)-36 b(hing)513 b(on)h(some)g(2)p Fj(j)589 b Fk(elemen)-36 b(ts)514 b(of)g([)p Fj(n)p Fk(].)820 b(These)514 b(2)p Fj(j)589 b Fk(elemen)-36 b(ts,)534 b(together)513 b(with)h(0,)535 b(serv)-36 b(e)800 9450 y(nicely)434 b(as)g(the)f(sp)36 b(eci\257ed)433 b(ro)36 b(ots)434 b(to)g(construct)f(con\257gurations)g (coun)-36 b(ted)433 b(b)-36 b(y)433 b(the)g(pro)36 b(duct)433 b Fj(AB)67 b Fk(.)2751 11055 y(De\257ne)349 b(a)h Fd(p)-66 b(artial)66 b(ly-p)-66 b(air)g(e)g(d)386 b(r)-66 b(o)g(ote)g(d)486 b Fk(\(PPR,)349 b(for)h(short\))f Fj(n)p Fd(-for)-66 b(est)475 b Fk(to)350 b(b)36 b(e)349 b(a)h(tree)f(ro)36 b(oted)350 b(at)f(0)h(and)f(zero)800 12660 y(or)405 b(more)f (\(unordered\))f(pairs)h(of)h(ro)36 b(oted)405 b(trees,)410 b(the)404 b(v)-36 b(ertex)405 b(sets)g(of)g(all)g(the)f(trees)g (forming)h(a)g(partition)800 14265 y(of)500 b([0)p Fj(;)221 b(n)p Fk(].)776 b(The)499 b Fd(p)-66 b(air-c)g(ount)623 b Fk(of)500 b(a)f(PPR)g(forest)g(is)g(its)g(n)-36 b(um)g(b)36 b(er)497 b(of)j(pairs)f(of)g(trees.)774 b(The)499 b(pro)36 b(duct)498 b Fj(AB)800 15870 y Fk(is)509 b(then)e(the)h(n)-36 b(um)g(b)36 b(er)507 b(of)j(PPR)e Fj(n)p Fk(-forests)h(with)g (pair-coun)-36 b(t)507 b Fj(j)75 b Fk(.)803 b(If)509 b(w)-36 b(e)509 b(de\257ne)f(the)g Fd(weight)634 b Fk(of)509 b(a)g(PPR)800 17475 y(forest)480 b(of)h(pair-coun)-36 b(t)479 b Fj(j)554 b Fk(to)480 b(b)36 b(e)480 b(\()p Fe(\241)p Fk(1\))19495 16993 y Fh(j)19982 17475 y Fk(,)491 b(then)479 b(the)g(righ)-36 b(t)480 b(hand)f(side)h(of)g(\(1\))g(is)g (the)f(total)i(w)-36 b(eigh)g(t)480 b(of)g(all)800 19080 y(PPR)434 b Fj(n)p Fk(-forests.)2751 20685 y(T)-108 b(o)356 b(include)e(the)h(ob)72 b(jects)356 b(w)-36 b(e're)356 b(trying)f(to)h(coun)-36 b(t)354 b(among)i(these)f(PPR)g Fj(n)p Fk(-forests,)372 b(w)-36 b(e)355 b(supp)36 b(ose)355 b(eac)-36 b(h)800 22290 y(tree)393 b(in)g(an)g(unro)36 b(oted)392 b(forest)i(to)f(b)36 b(e)393 b(ro)36 b(oted)393 b(at)h(its)f Fd(smal)66 b(lest)520 b Fk(v)-36 b(ertex.)566 b(Then)392 b(forests)i(of)g(unro)36 b(oted)392 b(trees)800 23895 y(on)520 b([)p Fj(n)p Fk(])i(corresp)36 b(ond)519 b(precisely)i(to)g(PPR)f Fj(n)p Fk(-forests)h(with)f(pair-coun)-36 b(t)519 b(0)i(and)f(eac)-36 b(h)520 b(c)-36 b(hild)520 b(of)h(v)-36 b(ertex)521 b(0)800 25500 y(smaller)352 b(than)f(all)h(its)f(descendan)-36 b(ts)350 b(\(delete)h(v)-36 b(ertex)352 b(0)g(to)f(get)h(the)e(forest)i(of)g(unro)36 b(oted)351 b(trees\).)550 b(A)351 b(v)-36 b(ertex)800 27106 y Fj(v)513 b Fk(in)465 b(a)g(ro)36 b(oted)465 b(tree)g(is)h Fd(inversion-initiating)576 b Fk(if)466 b(at)f(least)h(one)f(descendan) -36 b(t)464 b(of)h Fj(v)513 b Fk(is)465 b Fj(<)423 b(v)48 b Fk(,)472 b(otherwise)466 b(it)800 28711 y(is)459 b Fd(r)-66 b(e)g(gular)p Fk(.)651 b(Th)-36 b(us)458 b(forests)g(of)h (unro)36 b(oted)458 b(trees)g(on)g([)p Fj(n)p Fk(])h(app)36 b(ear)458 b(as)h(PPR)f Fj(n)p Fk(-forests)g(with)h(pair-coun)-36 b(t)457 b(0)800 30316 y(and)507 b(all)i(c)-36 b(hildren)507 b(of)i(v)-36 b(ertex)509 b(0)f(regular.)801 b(These)509 b(sp)36 b(ecial)508 b(PPR)g(forests)h(are)f(coun)-36 b(ted)507 b(with)h(w)-36 b(eigh)g(t)508 b(1)800 31921 y(and)433 b(here)g(is)h(the)f(promised)g(w)-36 b(eigh)g(t-rev)g(ersing) 434 b(in)-36 b(v)g(olution)434 b(on)f(the)g(rest.)2751 33526 y(Giv)-36 b(en)431 b(a)g(PPR)g(forest,)h(let)f Fj(a)g Fk(denote)f(the)h(smallest)g(v)-36 b(ertex)432 b(among)f(all)h(trees)f(\(if)g(an)-36 b(y\))431 b(other)g(than)800 35131 y(the)514 b(one)g(ro)36 b(oted)514 b(at)g(0,)535 b(let)515 b Fj(u)f Fk(b)36 b(e)514 b(the)g(ro)36 b(ot)514 b(of)h Fj(a)p Fk('s)f(tree)g(\()p Fj(u)h Fk(is)f(p)36 b(ossibly)-108 b(,)535 b(but)513 b(not)h(necessarily)-108 b(,)535 b(=)514 b Fj(a)p Fk(\),)800 36736 y(and)444 b(let)g Fj(v)491 b Fk(b)36 b(e)444 b(the)g(ro)36 b(ot)444 b(of)h(the)f(other)f (tree)h(in)g(its)g(pair.)610 b(A)-36 b(t)444 b(the)f(same)i(time,)i(if) e(0)f(has)g(an)-36 b(y)444 b(in)-36 b(v)g(ersion-)800 38341 y(initiating)439 b(c)-36 b(hildren,)439 b(let)f Fj(a)14324 37859 y Fi(0)15073 38341 y Fk(b)36 b(e)438 b(the)f(smallest)i(among)g(all)g(descendan)-36 b(ts)437 b(of)i(these)f(in)-36 b(v)g(ersion-initiating)800 39946 y(v)g(ertices,)415 b(let)409 b Fj(v)8377 39464 y Fi(0)9095 39946 y Fk(b)36 b(e)409 b(the)f(c)-36 b(hild)409 b(of)g(0)g(of)h(whic) -36 b(h)408 b Fj(a)24526 39464 y Fi(0)25246 39946 y Fk(is)h(a)g (descendan)-36 b(t,)412 b(and)d(let)g Fj(u)39719 39464 y Fi(0)40438 39946 y Fk(\(p)36 b(ossibly)410 b(=)e Fj(a)48023 39464 y Fi(0)48333 39946 y Fk(\))h(b)36 b(e)409 b(the)800 41551 y(c)-36 b(hild)487 b(of)h Fj(v)6209 41069 y Fi(0)7007 41551 y Fk(on)f(the)g(path)g(from)h Fj(v)18052 41069 y Fi(0)18849 41551 y Fk(to)g Fj(a)21176 41069 y Fi(0)21486 41551 y Fk(.)740 b(See)487 b(the)g(illustration)h(b)36 b(elo)-36 b(w)488 b(where)g(solid)g(lines)f(represen)-36 b(t)800 43156 y(mandatory)564 b(edges,)597 b(v)-36 b(ertical)565 b(dotted)e(lines)h(optional)g(edges,)597 b(and)563 b(diagonal)i(dotted) e(lines)h(optional)800 44762 y(subtrees.)26619 49798 y Fj(:)11011 59877 y Fk(.)11011 60507 y(.)11011 61137 y(.)11011 61767 y(.)11011 62397 y(.)11011 56727 y(.)11011 57357 y(.)11011 57987 y(.)11011 58617 y(.)11011 59247 y(.)11052 52992 y(.)11682 53622 y(.)12312 54252 y(.)12942 54882 y(.)13572 55512 y(.)11052 56142 y(.)11682 56772 y(.)12312 57402 y(.)12942 58032 y(.)13572 58661 y(.)11052 59291 y(.)11682 59921 y(.)12312 60551 y(.)12942 61181 y(.)13572 61811 y(.)11052 62441 y(.)11682 63071 y(.)12312 63701 y(.)12942 64331 y(.)13572 64961 y(.)11052 49842 y(.)11682 50472 y(.)12312 51102 y(.)12942 51732 y(.)13572 52362 y(.)26759 53578 y(.)26759 54208 y(.)26759 54838 y(.)26759 55468 y(.)26759 56097 y(.)26759 50428 y(.)26759 51058 y(.)26759 51688 y(.)26759 52318 y(.)26759 52948 y(.)26799 49842 y(.)27430 50472 y(.)28060 51102 y(.)28690 51732 y(.)29320 52362 y(.)26799 52992 y(.)27430 53622 y(.)28060 54252 y(.)28690 54882 y(.)29320 55512 y(.)26799 56142 y(.)27430 56772 y(.)28060 57402 y(.)28690 58032 y(.)29320 58661 y(.)36249 49842 y(.)36879 50472 y(.)37509 51102 y(.)38139 51732 y(.)38769 52362 y(.)p 11122 56097 111 3150 v 11122 52948 V 28602 47435 a Fg(pair)314 b(of)f(trees)25923 48247 y Ff(z)p 26521 48247 3957 160 v 3957 w(}|)p 31674 48247 V 3957 w({)9963 49911 y Fk(0)25665 49769 y Fj(u)8741 b(v)9794 53120 y(v)10471 52638 y Fi(0)9762 56270 y Fj(u)10502 55787 y Fi(0)9791 62569 y Fj(a)10474 62087 y Fi(0)25694 56068 y Fj(a)10834 50130 y Fc(\262)10834 53280 y(\262)10834 56430 y(\262)10834 59579 y(\262)10834 62729 y(\262)26581 50130 y(\262)26581 53280 y(\262)26581 56430 y(\262)36031 50130 y(\262)2592 67451 y Fj(a)3275 66969 y Fi(0)4019 67451 y Fk(is)434 b(smallest)h(descendan)-36 b(t)432 b(of)i(an)2829 68870 y(in)-36 b(v)g(ersion-initiating)434 b(c)-36 b(hild)433 b(of)i(0)23510 67425 y Fj(a)e Fk(is)h(smallest)g(v) -36 b(ertex)434 b(not)25177 69000 y(a)g(descendan)-36 b(t)432 b(of)i(0)p Black 26475 74617 a(2)p Black eop %%Page: 3 3 3 2 bop Black 0 TeXcolorgray Black Black 2751 1424 a Fk(A)-36 b(t)477 b(least)h(one)f(of)h Fj(a;)221 b(a)13660 942 y Fi(0)14448 1424 y Fk(will)478 b(exist)g(unless)f(the)g(pair-coun) -36 b(t)476 b(is)i(0)f(and)g(all)h(c)-36 b(hildren)476 b(of)i(v)-36 b(ertex)478 b(0)g(are)800 3029 y(regular;)489 b(these)470 b(are)g(the)g(sp)36 b(ecial)471 b(PPR)f(forests,)480 b(represen)-36 b(ting)470 b(unro)36 b(oted)469 b(forests,)480 b(and)470 b(they)g(surviv)-36 b(e.)800 4634 y(Cho)36 b(ose)499 b(the)e(smaller)i(of)f Fj(a;)221 b(a)15737 4152 y Fi(0)16048 4634 y Fk(.)771 b(If)498 b(it's)h Fj(a)p Fk(,)514 b(add)497 b(an)h(edge)g(from)g(0)g(to)g Fj(v)545 b Fk(and)498 b(an)f(edge)h(from)g Fj(v)546 b Fk(to)498 b Fj(u)g Fk(so)800 6239 y(that)394 b(v)-36 b(ertex)395 b(0)g(acquires)h(a)f(new)f(in)-36 b(v)g(ersion-initiating)395 b(c)-36 b(hild)395 b Fj(v)442 b Fk(\(with)394 b(a)h(small)h(descendan) -36 b(t)393 b Fj(a)p Fk(\))h(and)h(the)800 7844 y(n)-36 b(um)g(b)36 b(er)366 b(of)i(pairs)f(of)h(trees)f(is)h(reduced)e(b)-36 b(y)367 b(1.)557 b(If)368 b(it's)f Fj(a)27815 7362 y Fi(0)28126 7844 y Fk(,)380 b(delete)368 b(the)e(edges)i(0)p Fj(v)39469 7362 y Fi(0)40146 7844 y Fk(and)f Fj(v)43286 7362 y Fi(0)43596 7844 y Fj(u)44336 7362 y Fi(0)45014 7844 y Fk(to)h(form)f(a)h(new)800 9450 y(pair)468 b(of)i(trees)e(ro)36 b(oted)468 b(at)h Fj(u)14656 8968 y Fi(0)15435 9450 y Fk(and)f Fj(v)18676 8968 y Fi(0)19455 9450 y Fk(\(with)g Fj(a)23641 8968 y Fi(0)24420 9450 y Fk(no)-36 b(w)468 b(the)g(smallest)h(v)-36 b(ertex)469 b(among)g(all)g(pairs)g(of)g (trees\).)800 11055 y(In)489 b(either)f(case,)504 b(the)488 b(n)-36 b(um)g(b)36 b(er)488 b(of)h(pairs)g(of)h(trees)f(c)-36 b(hanges)488 b(b)-36 b(y)489 b(1,)504 b(so)489 b(the)f(w)-36 b(eigh)g(t)490 b(c)-36 b(hanges)488 b(sign.)745 b(The)800 12660 y(mapping)455 b(is)h(clearly)h(an)f(in)-36 b(v)g(olution)456 b(on)g(all)g(non-sp)36 b(ecial)456 b(PPR)g(forests)g(and)f(so)h(their)g (w)-36 b(eigh)g(ts)456 b(cancel)800 14265 y(out.)578 b(Th)-36 b(us)433 b(\()p 0 1 0 0 TeXcolorcmyk(2)p (#equation.2) [[139 589 145 601] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))h(\(=)f(\()p 0 1 0 0 TeXcolorcmyk(1)p (#equation.1) [[175 589 181 601] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\)\))g(is)h(the)f(n)-36 b(um)g(b)36 b(er)432 b(of)i(forests)g(of) h(unro)36 b(oted)432 b(trees)i(on)f([)p Fj(n)p Fk(].)800 20277 y Fb(References)p Black 1450 23197 a Fk([1])p Black 652 w(L.)320 b(T)-108 b(ak\266)-650 b(acs,)345 b(On)320 b(the)h(n)-36 b(um)g(b)36 b(er)319 b(of)j(distinct)e(forests,)344 b Fd(SIAM)360 b(J.)h(Discr)-66 b(ete)360 b(Math.)320 b Fa(3)h Fk(\(1990\),)344 b(574{581.)p Black 1450 25909 a([2])p Black 652 w(J.)380 b(W.)h(Mo)36 b(on,)391 b Fd(Counting)414 b(L)-66 b(ab)g(el)66 b(le)-66 b(d)415 b(T)-100 b(r)-66 b(e)g(es)p Fk(,)390 b(Lectures)380 b(Deliv)-36 b(ered)380 b(to)h(the)e(Tw)-36 b(elfth)381 b(Biennial)g(Semi-)3474 27514 y(nar)298 b(of)i(the)e(Canadian)h(Mathematical)g(Congress)h(\(V) -108 b(ancouv)-36 b(er,)325 b(1969\),)i(Canadian)299 b(Mathematical)3474 29119 y(Monographs,)433 b(No.)h(1,)h(1970.)p Black 1450 31832 a([3])p Black 652 w(J.)f(Pitman,)p 0 1 0 0 TeXcolorcmyk 433 w(Coalescen)-36 b(t)435 b(random)e(forests)p [[161 431 296 443] [1 1 1 [3 3]] [0 0 1]] (http://stat-www.berkeley.edu/users/pitman/457.ps.Z) pdfm Black(,)h Fd(J.)465 b(Combin.)e(The)-66 b(ory)464 b(Ser.)g(A)433 b Fa(85)h Fk(\(1999\),)h(165{193.)p 800 34975 52000 45 v 800 37226 a(2000)g Fd(Mathematics)464 b(Subje)-66 b(ct)463 b(Classi\257c)-66 b(ation)p Fk(:)577 b(05C05.)800 38831 y Fd(Keywor)-66 b(ds:)806 b Fk(tree,)530 b(lab)36 b(eled)510 b(forest,)531 b(partially-paired)511 b(ro)36 b(oted)510 b Fj(n)p Fk(-forest,)530 b(in)-36 b(v)g(ersion-initiating)511 b(v)-36 b(ertex,)800 40436 y(w)g(eigh)g(t-rev)g(ersing)434 b(in)-36 b(v)g(olution.)p 800 42067 V 800 44392 a(\(Concerned)433 b(with)h(sequence)p 0 1 0 0 TeXcolorcmyk 433 w(A001858)p 16090 44604 4878 54 v [[217 317 261 329] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=A001858) pdfm Black 2 w(.\))800 46797 y(Receiv)-36 b(ed)480 b(Octob)36 b(er)478 b(3)h(2003;)503 b(revised)479 b(v)-36 b(ersion)480 b(receiv)-36 b(ed)479 b(No)-36 b(v)g(em)g(b)36 b(er)478 b(3)i(2003.)715 b(Published)478 b(in)h Fd(Journal)800 48402 y(of)465 b(Inte)-66 b(ger)462 b(Se)-66 b(quenc)g(es)432 b Fk(Jan)-36 b(uary)434 b(15)g(2004.)p 800 50033 52000 45 v 800 52284 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 246 338 258] [1 1 1 [3 3]] [0 0 1]] (http://www.math.uwaterloo.ca/JIS/) pdfm Black(.)p Black 26475 74617 a(3)p Black eop %%Trailer end end