%%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.3) 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 15944 11461 a Ft(Coun)-72 b(ting)863 b(Biorders)6319 16603 y Fs(Julie)519 b(Christophe)p 0 .5 0 TeXcolorrgb -578 x Fr(1)p (#Hfootnote.1) [[230 568 235 580] [1 1 1 [3 3]] [0 0 1]] pdfm Black 18144 16603 a Fs(,)g(Jean-P)-43 b(aul)521 b(Doignon)p 0 .5 0 TeXcolorrgb -578 x Fr(2)p (#Hfootnote.2) [[361 568 366 580] [1 1 1 [3 3]] [0 0 1]] pdfm Black 32690 16603 a Fs(,)f(and)h(Sam)-43 b(uel)520 b(Fiorini)p 0 .5 0 TeXcolorrgb -578 x Fr(3)p (#Hfootnote.3) [[492 568 498 580] [1 1 1 [3 3]] [0 0 1]] pdfm Black 16864 18596 a Fs(Univ)-43 b(ersit)g(\266)-737 b(e)517 b(Libre)j(de)g(Bruxelles)13003 20588 y(D)-43 b(\266)-737 b(epartemen)-43 b(t)519 b(de)h(Math)-43 b(\266)-737 b(ematique,)519 b(c.p.)g(216)21153 22581 y(Bd)i(du)f(T)-130 b(riomphe)21030 24573 y(B-1050)522 b(Bruxelles)23993 26566 y(Belgium)p 0 1 0 0 TeXcolorcmyk 19418 28559 a Fq(juchrist@ulb.ac.be)p [[247 460 380 472] [1 1 1 [3 3]] [0 0 1]] (mailto:juchrist@ulb.ac.be) pdfm Black 0 1 0 0 TeXcolorcmyk 19828 30551 a(doignon@ulb.ac.be)p [[250 442 376 454] [1 1 1 [3 3]] [0 0 1]] (mailto:doignon@ulb.ac.be) pdfm Black 0 1 0 0 TeXcolorcmyk 19418 32544 a(sfiorini@ulb.ac.be)p [[247 424 380 436] [1 1 1 [3 3]] [0 0 1]] (mailto:sfiorini@ulb.ac.be) pdfm Black Black Black 24133 37088 a Fp(Abstract)p Black Black 5870 39336 a Fo(Biorders)567 b(w)-34 b(ere)568 b(in)-34 b(tro)34 b(duced)568 b(\257rst)h(as)f(Guttman)h(scales)f(and)g(then)h (as)f(F)-101 b(errers)567 b(relations.)4052 40841 y(They)364 b(are)g(no)-34 b(w)366 b(w)-34 b(ell)364 b(recognized)f(in)i(com)-34 b(binatorics)364 b(and)i(its)e(applications.)526 b(Ho)-34 b(w)g(ev)g(er,)372 b(it)365 b(seems)4052 42347 y(that)580 b(no)g(pro)34 b(cedure)579 b(b)34 b(esides)579 b(plain)g(en)-34 b(umeration)581 b(w)-34 b(as)580 b(made)g(a)-34 b(v)-67 b(ailable)578 b(for)h(obtaining)i(the)4052 43852 y(n)-34 b(um)g(b)34 b(er)488 b(of)f(biorders)g(from)g(an)g Fn(m)p Fo(-elemen)-34 b(t)487 b(set)g(to)g(an)h Fn(n)p Fo(-elemen)-34 b(t)486 b(set.)787 b(W)-101 b(e)486 b(establish)i(\257rst)f(a)4052 45357 y(double-recurrence)413 b(form)-34 b(ula)416 b(for)e(computing)i (this)f(n)-34 b(um)g(b)34 b(er,)418 b(and)d(then)g(t)-34 b(w)g(o)416 b(explicit)d(form)-34 b(ulas)4052 46863 y(in)g(v)g(olving) 392 b(Stirling)g(n)-34 b(um)g(b)34 b(ers)393 b(of)f(the)g(second)g (kind.)535 b(Our)392 b(metho)34 b(ds)392 b(do)g(not)h(seem)f(to)g (extend)g(to)4052 48368 y(other,)487 b(similar)470 b(structures.)739 b(F)-101 b(or)470 b(instance,)488 b(in)-34 b(terv)-67 b(al)470 b(orders)g(on)h(a)g(\257nite)g(set)g(are)f(exactly)g(the)4052 49874 y(irre\260exiv)-34 b(e)483 b(biorders)j(on)g(that)g(set.)783 b(T)-101 b(o)486 b(our)f(kno)-34 b(wledge,)506 b(no)486 b(direct)f(form)-34 b(ula)486 b(is)g(a)-34 b(v)-67 b(ailable)484 b(for)4052 51379 y(deriving)403 b(their)h(n)-34 b(um)g(b)34 b(er.)800 55816 y Fm(1)2152 b(In)-60 b(tro)60 b(duction)800 58737 y Fl(Throughout)558 b(the)h(text,)590 b Fk(X)664 b Fl(and)559 b Fk(Y)847 b Fl(denote)559 b(\257nite)f(sets)h(of)g(resp) 36 b(ectiv)-36 b(e)559 b(cardinalities)h Fk(m)f Fl(and)f Fk(n)p Fl(.)955 b(A)800 60342 y Fj(bior)-66 b(der)576 b Fl(from)434 b Fk(X)538 b Fl(to)434 b Fk(Y)722 b Fl(is)434 b(an)-36 b(y)434 b(relation)g(from)g Fk(X)538 b Fl(to)434 b Fk(Y)722 b Fl(that)434 b(admits)f(a)h(step-lik)-36 b(e)434 b(tableau,)g(meaning:)800 61947 y(there)512 b(exists)h(some)f (ordering)h Fk(x)17159 62146 y Fi(1)17684 61947 y Fl(,)533 b Fk(x)19317 62146 y Fi(2)19843 61947 y Fl(,)f(.)217 b(.)g(.)g(,)533 b Fk(x)24103 62146 y Fh(m)25503 61947 y Fl(of)513 b(the)e(elemen)-36 b(ts)512 b(in)h Fk(X)617 b Fl(and)512 b(some)g(ordering)g Fk(y)49859 62146 y Fi(1)50385 61947 y Fl(,)533 b Fk(y)51913 62146 y Fi(2)52439 61947 y Fl(,)800 63552 y(.)217 b(.)g(.)g(,)505 b Fk(y)4034 63751 y Fh(n)5150 63552 y Fl(of)491 b(the)f(elemen)-36 b(ts)490 b(in)g Fk(Y)779 b Fl(suc)-36 b(h)489 b(that)h(the)f(corresp)36 b(onding)490 b(\(b)36 b(o)g(olean\))491 b(tableau)f(of)h(the)f (relation)p Black 800 64460 20800 45 v 2296 65276 a Fg(1)p 0 TeXcolorgray Black 2793 65678 a Fr(J.)369 b(C.)h(is)f(a)g(F)-92 b(ello)-31 b(w)371 b(of)f(the)f(F)-92 b(onds)368 b(p)31 b(our)369 b(la)h(F)-92 b(ormation)371 b(\265)-553 b(a)369 b(la)h(Rec)-31 b(herc)g(he)369 b(dans)g(l'Industrie)h(et)f(dans)h (l'Agriculture.)2296 66604 y Fg(2)p 0 TeXcolorgray Black 2793 67006 a Fr(Corresp)31 b(onding)369 b(author.)2296 67933 y Fg(3)p 0 TeXcolorgray Black 2793 68334 a Fr(S.)g(F.)g(is)g (supp)31 b(orted)369 b(b)-31 b(y)369 b(a)h(F)-92 b(ello)-31 b(wship)371 b(of)e(the)h(Belgian)h(American)f(Educational)i(F)-92 b(oundation.)p Black Black 26475 74617 a Fl(1)p Black eop %%Page: 2 2 2 1 bop Black 0 TeXcolorgray Black Black 800 1424 a Fl(has)434 b(its)f(0's)h(separated)g(from)g(its)f(1's)i(b)-36 b(y)433 b(a)h(staircase,)h(as)f(in)f(the)g(follo)-36 b(wing)436 b(example:)17350 4245 y Fk(y)17984 4444 y Fi(1)20724 4245 y Fk(y)21358 4444 y Fi(2)24160 4245 y Fk(y)24794 4444 y Fi(3)27597 4245 y Fk(y)28231 4444 y Fi(4)30971 4245 y Fk(y)31605 4444 y Fi(5)34345 4245 y Fk(y)34979 4444 y Fi(6)37719 4245 y Fk(y)38353 4444 y Fi(7)12507 7110 y Fk(x)13246 7309 y Fi(1)p 16180 7110 63 945 v 17604 7110 a Fl(1)2724 b(1)2787 b(1)g(1)2724 b(1)g(1)g(1)12507 10320 y Fk(x)13246 10519 y Fi(2)p 16180 10320 V 17604 10320 a Fl(1)g(1)2787 b(1)g(1)2724 b(1)g(1)g(1)p 17457 11610 945 63 v 20831 11610 V 12507 13530 a Fk(x)13246 13729 y Fi(3)17604 13530 y Fl(0)g(0)p 22990 13530 63 945 v 2787 w(1)2787 b(1)2724 b(1)g(1)g(1)p 24268 14820 945 63 v 12507 16740 a Fk(x)13246 16939 y Fi(4)17604 16740 y Fl(0)g(0)2787 b(0)p 26427 16740 63 945 v 2787 w(1)2724 b(1)g(1)g(1)12507 19951 y Fk(x)13246 20150 y Fi(5)17604 19951 y Fl(0)g(0)2787 b(0)p 26427 19951 V 2787 w(1)2724 b(1)g(1)g(1)p 27705 21241 945 63 v 31079 21241 V 34453 21241 V 37827 21241 V Black 51138 12911 a(\(1\))p Black 800 24399 a(Also,)539 b(a)518 b(relation)g Fk(R)528 b Fl(from)518 b Fk(X)622 b Fl(to)517 b Fk(Y)806 b Fl(is)518 b(a)f(biorder)g(if)h(and)f(only)h(if)g(it)f(satis\257es)h (an)-36 b(y)517 b(of)h(the)f(follo)-36 b(wing)800 26004 y(equiv)-72 b(alen)-36 b(t)434 b(conditions:)p Black 2390 28716 a(1.)p Black 651 w(for)g(all)g Fk(w)36 b(;)221 b(x)370 b Ff(2)e Fk(X)539 b Fl(and)433 b Fk(y)48 b(;)221 b(z)429 b Ff(2)368 b Fk(Y)289 b Fl(:)16158 31649 y(\()p Fk(w)36 b(R)11 b(y)480 b Fl(and)433 b Fk(xR)11 b(z)59 b Fl(\))1541 b(implies)g(\()p Fk(w)36 b(R)11 b(z)492 b Fl(or)434 b Fk(xR)11 b(y)48 b Fl(\);)p Black 10444 w(\(2\))p Black Black 2390 35136 a(2.)p Black 651 w(all)419 b(subsets)f Fk(R)11 b Fl(\()p Fk(x)p Fl(\))369 b(=)g Ff(f)p Fk(y)417 b Ff(2)368 b Fk(Y)510 b Ff(j)221 b Fk(xR)11 b(y)48 b Ff(g)p Fl(,)423 b(for)c Fk(x)369 b Ff(2)g Fk(X)104 b Fl(,)423 b(form)c(a)g(c)-36 b(hain)419 b(of)g(subsets)f(of)i Fk(Y)707 b Fl(\(rep)36 b(etitions)4052 36741 y(b)g(eing)433 b(allo)-36 b(w)g(ed\);)p Black 2390 39453 a(3.)p Black 651 w(all)434 b(subsets)f Fk(R)11361 38971 y Fe(\241)p Fi(1)12619 39453 y Fl(\()p Fk(y)48 b Fl(\))368 b(=)h Ff(f)p Fk(x)g Ff(2)f Fk(X)327 b Ff(j)221 b Fk(xR)11 b(y)48 b Ff(g)p Fl(,)434 b(for)g Fk(y)417 b Ff(2)369 b Fk(Y)288 b Fl(,)434 b(form)g(a)g(c)-36 b(hain)433 b(of)i(subsets)d(of)j Fk(X)104 b Fl(;)p Black 2390 42165 a(4.)p Black 651 w(no)433 b(tableau)h(for)g Fk(R)444 b Fl(con)-36 b(tains)434 b(a)g(subtableau)f (of)h(the)f(form)18267 43669 y Fd(\265)19799 44728 y Fl(0)1107 b(1)19799 46333 y(1)g(0)22760 43669 y Fd(\266)26560 45542 y Fl(or)30539 43669 y Fd(\265)32070 44728 y Fl(1)h(0)32070 46333 y(0)g(1)35031 43669 y Fd(\266)36231 45542 y Fk(:)p Black 14546 w Fl(\(3\))p Black 2751 49730 a(These)339 b(simple)f(conditions,)358 b(and)338 b(sev)-36 b(eral)339 b(other)f(ones,)358 b(w)-36 b(ere)339 b(established)f(when)g(biorders)g (w)-36 b(ere)339 b(\257rst)800 51335 y(in)-36 b(tro)36 b(duced)525 b(in)i(psyc)-36 b(hology)528 b(as)f(`scales')h(b)-36 b(y)526 b(Guttman)g([)p 0 1 0 0 TeXcolorcmyk(7)p (#cite.Guttman44) [[341 255 347 267] [1 1 1 [3 3]] [0 0 1]] pdfm Black(],)551 b(and)526 b(then)f(in)i(mathematics)g(as)g(`F)-108 b(errers)800 52940 y(relations')523 b(b)-36 b(y)522 b(Riguet)h([)p 0 1 0 0 TeXcolorcmyk(10)p (#cite.Riguet51) [[190 241 201 253] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(].)844 b(F)-108 b(or)522 b(a)g(surv)-36 b(ey)523 b(of)f(the)g(early)h(history)g(of)f(biorders,)545 b(see)522 b(Monjardet)g([)p 0 1 0 0 TeXcolorcmyk(9)p (#cite.Monjardet1978) [[535 241 541 253] [1 1 1 [3 3]] [0 0 1]] pdfm Black(].)800 54545 y(Besides)365 b(their)g(use)g(in)g(so)36 b(cial)367 b(sciences,)380 b(biorders)364 b(ha)-36 b(v)g(e)366 b(pro)-36 b(v)g(ed)365 b(useful)g(in)g(a)h(v)-72 b(ariet)-36 b(y)366 b(of)g(situations.)555 b(F)-108 b(or)800 56150 y(instance,)455 b(they)450 b(come)g(as)h(a)g(con)-36 b(v)g(enien)g(t,)454 b(tec)-36 b(hnical)450 b(to)36 b(ol)451 b(for)g(Y)-108 b(annak)-72 b(akis)451 b([)p 0 1 0 0 TeXcolorcmyk(12)p (#cite.Yannakakis1982) [[427 212 439 224] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(],)k(or)450 b(they)h(are)f(used)g(as)800 57755 y(the)343 b(1-dimensional)h(constituen)-36 b(ts)342 b(in)h(a)h (dimensional)g(theory)f(of)h(relations)g(b)-36 b(y)344 b(Cogis)h([)p 0 1 0 0 TeXcolorcmyk(2)p (#cite.Cogis1982b) [[467 197 473 209] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])f(and)f(Doignon,)800 59360 y(Ducamp)433 b(and)g(F)-108 b(almagne)434 b([)p 0 1 0 0 TeXcolorcmyk(4)p (#cite.DoignonDucampFalmagne84) [[205 183 211 195] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])g(\(the)f(latter)g(reference)h(in)-36 b(tro)36 b(duced)432 b(the)h(term)g(`biorder'\).)2751 60965 y(Although)405 b(biorders)g(are)h(b)-36 b(y)405 b(no)-36 b(w)406 b(w)-36 b(ell)406 b(assimilated)g(in)g(some)f(c)-36 b(hapters)405 b(of)h(com)-36 b(binatorics)406 b(and)f(its)800 62570 y(applications,)488 b(it)477 b(seems)f(that)g(no)g(direct)g(metho)36 b(d)476 b(for)h(coun)-36 b(ting)476 b(biorders)g(w)-36 b(as)477 b(ev)-36 b(er)477 b(published.)705 b(W)-108 b(e)800 64176 y(will)482 b(pro)-36 b(vide)480 b(three)g(form)-36 b(ulas)481 b(for)g(obtaining)g(the)f(n)-36 b(um)g(b)36 b(er)479 b(of)i(biorders)f(from)h(an)f Fk(m)p Fl(-elemen)-36 b(t)480 b(set)g(to)800 65781 y(an)468 b Fk(n)p Fl(-elemen)-36 b(t)467 b(set.)681 b(A)468 b(\257rst)f(form)-36 b(ula)469 b(captures)e(a)h(double-recurrence)e(approac)-36 b(h.)681 b(Then)467 b(an)h(explicit)800 67386 y(form)-36 b(ula)392 b(is)g(deriv)-36 b(ed)391 b(whic)-36 b(h)391 b(relies)h(on)g(Stirling)f (n)-36 b(um)g(b)36 b(ers)390 b(of)i(the)f(second)g(kind.)565 b(Still)391 b(another)h(form)-36 b(ula)800 68991 y(is)578 b(established)f(along)h(another)e(line)i(of)g(reasoning,)614 b(whic)-36 b(h)577 b(also)h(mak)-36 b(es)578 b(use)f(of)h(the)e(same)i (Stirling)800 70596 y(n)-36 b(um)g(b)36 b(ers.)p Black 26475 74617 a(2)p Black eop %%Page: 3 3 3 2 bop Black 0 TeXcolorgray Black Black 2751 1424 a Fl(Our)472 b(metho)36 b(d)472 b(do)36 b(es)473 b(not)g(seem)g(to)f(b)36 b(e)473 b(applicable)g(to)g(related,)483 b(similar)474 b(structures.)695 b(F)-108 b(or)472 b(instance)800 3029 y(\(see,)491 b(e.g.,)i(Fish)-36 b(burn)477 b([)p 0 1 0 0 TeXcolorcmyk(5)p (#cite.Fishburn1985) [[185 690 191 702] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])j(for)g(these)f(concepts\),)490 b(in)-36 b(terv)-72 b(al)480 b(orders)f(on)h(a)g(\257nite)e(set)i Fk(Z)575 b Fl(are)480 b(exactly)h(the)800 4634 y(irre\260exiv)-36 b(e)461 b(biorders)e(from)h Fk(Z)555 b Fl(to)460 b Fk(Z)95 b Fl(,)467 b(while)461 b(semiorders)e(are)h(the)f(in)-36 b(terv)-72 b(al)460 b(orders)g(satisfying)h(also)f(for)800 6239 y Fk(x)p Fl(,)434 b Fk(y)48 b Fl(,)434 b Fk(z)59 b Fl(,)434 b Fk(t)369 b Ff(2)f Fk(Z)15028 9173 y Fl(\()p Fk(xR)11 b(y)481 b Fl(and)433 b Fk(y)48 b(R)11 b(z)59 b Fl(\))1541 b(implies)g(\()p Fk(xR)11 b(t)433 b Fl(or)g Fk(tR)11 b(z)59 b Fl(\))p Fk(:)p Black 12566 w Fl(\(4\))p Black 800 12106 a(F)-108 b(orm)-36 b(ulas)451 b(for)h(the)f(n)-36 b(um)g(b)36 b(er)449 b(of)j(semiorders)f(on)h(an)f Fk(n)p Fl(-elemen)-36 b(t)451 b(set)g(are)g(giv)-36 b(en)452 b(in)f(Chandon,)456 b(Lemaire)800 13711 y(and)643 b(P)-36 b(ouget)643 b([)p 0 1 0 0 TeXcolorcmyk(1)p (#cite.ChandonLemairePouget1978) [[148 594 154 606] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])h(\(see)f(also)h(Sequence)f(A006531)i(in)e(the)g(On-Line)e (Encyclop)36 b(edia)644 b(of)g(In)-36 b(teger)643 b(Se-)800 15316 y(quences)494 b([)p 0 1 0 0 TeXcolorcmyk(11)p (#cite.SloaneEIS) [[126 579 138 591] [1 1 1 [3 3]] [0 0 1]] pdfm Black(]\),)509 b(but)493 b(apparen)-36 b(tly)493 b(no)h(explicit)g (form)-36 b(ula)494 b(is)g(kno)-36 b(wn)494 b(in)f(the)g(literature)h (for)g(the)f(similar)800 16922 y(n)-36 b(um)g(b)36 b(er)432 b(of)i(in)-36 b(terv)-72 b(al)434 b(orders.)2751 18527 y(Notice)487 b(that)g(all)g(coun)-36 b(ts)487 b(men)-36 b(tioned)485 b(so)j(far)f(are)g(for)g(lab)36 b(eled)487 b(structures.)737 b(As)487 b(regards)g(coun)-36 b(ting)800 20132 y(up)587 b(to)h(isomorphism,)627 b(the)588 b(case)g(of)h (semiorders)f(leads)g(to)g(the)g(Catalan)h(n)-36 b(um)g(b)36 b(er)44562 19609 y Fi(1)p 43911 19826 1774 54 v 43911 20590 a Fh(n)p Fi(+1)45817 19056 y Fd(\241)46426 19542 y Fi(2)p Fh(n)46661 20590 y(n)47467 19056 y Fd(\242)48664 20132 y Fl(\(see)588 b([)p 0 1 0 0 TeXcolorcmyk(5)p (#cite.Fishburn1985) [[538 536 544 548] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])800 21737 y(or)404 b(Sequence)f(A000108)j([)p 0 1 0 0 TeXcolorcmyk(11)p (#cite.SloaneEIS) [[194 521 206 533] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(]\),)k(while)405 b(a)f(p)36 b(olynomial-time)405 b(algorithm)f(for)h(computing)e(the)g(n)-36 b(um)g(b)36 b(er)402 b(of)800 23342 y(isomorphism)311 b(t)-36 b(yp)36 b(es)311 b(of)h(in)-36 b(terv)-72 b(al)311 b(orders)g(is)g(due)g(to)g (Haxell,)337 b(McDonald)312 b(and)e(Thomason)i([)p 0 1 0 0 TeXcolorcmyk(8)p (#cite.HaxellMcDonaldThomason1987) [[484 507 490 519] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])g(\(Sequence)800 24947 y(A022493)c([)p 0 1 0 0 TeXcolorcmyk(11)p (#cite.SloaneEIS) [[129 492 141 504] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(]\).)536 b(On)305 b(the)h(other)f(hand,)331 b(the)306 b(case)g(of)h(biorders)f(from)g Fk(X)411 b Fl(to)306 b Fk(Y)595 b Fl(is)306 b(easy)h(in)f(case)h Fk(X)139 b Ff(\\)35 b Fk(Y)657 b Fl(=)369 b Fc(?)p Fl(:)800 26552 y(there)552 b(are)6530 25476 y Fd(\241)7139 25963 y Fh(m)p Fi(+)p Fh(n)7921 27010 y(n)9274 25476 y Fd(\242)10436 26552 y Fl(isomorphism)h(t)-36 b(yp)36 b(es)553 b(of)g(biorders)g(from) g(an)g Fk(m)p Fl(-elemen)-36 b(t)551 b(set)i Fk(X)658 b Fl(to)553 b(a)g(disjoin)-36 b(t)553 b Fk(n)p Fl(-)800 28157 y(elemen)-36 b(t)446 b(set)g Fk(Y)289 b Fl(.)617 b(T)-108 b(o)447 b(pro)-36 b(v)g(e)446 b(this,)k(w)-36 b(e)447 b(need)e(only)i(indicate)g(ho)-36 b(w)446 b(to)h(coun)-36 b(t)446 b(step-lik)-36 b(e)446 b(tableaus,)k(and)c(it)800 29762 y(su\261ces)f(to)h(p)36 b(oin)-36 b(t)445 b(out)h(that)f(the)g (separating)g(staircase)i(is)f(made)f(of)i Fk(m)303 b Fl(+)g Fk(n)446 b Fl(strok)-36 b(es,)449 b(of)d(whic)-36 b(h)446 b Fk(m)f Fl(are)800 31367 y(v)-36 b(ertical)435 b(and)e Fk(n)h Fl(are)f(horizon)-36 b(tal.)800 35804 y Fm(2)2152 b(Double)716 b(Recurrence)800 38725 y Fl(Let)472 b(us)h(denote)f(b)-36 b(y)472 b Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))474 b(the)e(quan)-36 b(tit)g(y)473 b(w)-36 b(e)473 b(are)g(in)-36 b(terested)472 b(in,)483 b(that)472 b(is)h(the)f(n)-36 b(um)g(b)36 b(er)471 b(of)i(biorders)800 40330 y(from)582 b(the)f Fk(m)p Fl(-elemen)-36 b(t)580 b(set)h Fk(X)686 b Fl(to)582 b(the)e Fk(n)p Fl(-elemen)-36 b(t)581 b(set)h Fk(Y)288 b Fl(.)1022 b(Assuming)581 b Fk(X)501 b Ff(\\)395 b Fk(Y)909 b Fl(=)620 b Fc(?)582 b Fl(do)36 b(es)581 b(not)g(set)800 41935 y(an)-36 b(y)469 b(restriction)g(here,)477 b(b)36 b(ecause)469 b(of)g(the)g(duplication) f(construction)g(of)i(Doignon,)479 b(Ducamp)468 b(and)g(F)-108 b(al-)800 43540 y(magne)403 b([)p 0 1 0 0 TeXcolorcmyk(4)p (#cite.DoignonDucampFalmagne84) [[119 325 125 337] [1 1 1 [3 3]] [0 0 1]] pdfm Black(];)414 b(the)402 b(reader)g(migh)-36 b(t)402 b(\257nd)f(it)i (helpful)f(to)g(assume)h Fk(X)336 b Ff(\\)231 b Fk(Y)658 b Fl(=)369 b Fc(?)p Fl(.)568 b(The)402 b(follo)-36 b(wing)405 b(prop)36 b(osition)800 45145 y(sho)-36 b(ws)434 b(ho)-36 b(w)434 b(to)f(compute)g(n)-36 b(um)g(b)36 b(ers)432 b Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))435 b(b)-36 b(y)434 b(a)f(double)g(recurrence.)p Black 800 48079 a Fb(Prop)42 b(osition)500 b(1)p Black 650 w Fa(F)-108 b(or)433 b Fk(m)369 b(>)g Fl(0)434 b Fa(and)f Fk(n)369 b(>)g Fl(0)p Fa(,)434 b(w)-36 b(e)434 b(ha)-36 b(v)g(e)15059 52140 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))1108 b(=)22706 50480 y Fh(m)p Fe(\241)p Fi(1)22764 50878 y Fd(X)22906 53678 y Fh(j)51 b Fi(=0)25404 50480 y Fh(n)p Fe(\241)p Fi(1)25331 50878 y Fd(X)25432 53707 y Fh(k)24 b Fi(=0)28209 50267 y Fd(\265)29187 51241 y Fk(m)29449 53051 y(j)30324 50267 y Fd(\266)369 b(\265)32649 51241 y Fk(n)32677 53051 y(k)33425 50267 y Fd(\266)34772 52140 y Ff(B)40 b Fl(\()p Fk(j)r(;)221 b(k)45 b Fl(\))p Black 12599 w(\(5\))p Black 800 56344 a Fa(and)18585 59278 y Ff(B)40 b Fl(\()p Fk(m;)221 b Fl(0\))739 b(=)f Ff(B)40 b Fl(\(0)p Fk(;)221 b(n)p Fl(\))740 b(=)d(1)p Fk(;)p Black 18338 w Fl(\(6\))p Black 800 62211 a Fa(together)433 b(with)22778 65144 y Ff(B)40 b Fl(\(0)p Fk(;)221 b Fl(0\))1108 b(=)f(2)p Fk(:)p Black 20316 w Fl(\(7\))p Black 800 68078 a Fj(Pr)-66 b(o)g(of)p Fl(.)642 b(A)455 b(tableau)g(is)h(said)f(to)g(b) 36 b(e)455 b(of)h(T)-36 b(yp)36 b(e)455 b(0)g(if)h(it)f(has)g(a)h (column)e(of)i(0's,)462 b(and)454 b(of)i(T)-36 b(yp)36 b(e)455 b(1)h(if)g(it)f(has)g(a)800 69683 y(ro)-36 b(w)472 b(of)g(1's.)692 b(Corresp)36 b(ondingly)-108 b(,)482 b(a)471 b(biorder)g(from)h Fk(X)576 b Fl(to)472 b Fk(Y)760 b Fl(is)471 b(of)h(T)-36 b(yp)36 b(e)472 b(0)g(if)g(at)f(least)h(one)g (set)f Fk(R)49849 69201 y Fe(\241)p Fi(1)51107 69683 y Fl(\()p Fk(y)48 b Fl(\))800 71288 y(is)475 b(empt)-36 b(y)-108 b(,)484 b(where)475 b Fk(y)486 b Ff(2)438 b Fk(Y)289 b Fl(;)495 b(denote)474 b(b)-36 b(y)475 b Ff(B)21562 71487 y Fi(0)22088 71288 y Fl(\()p Fk(m;)221 b(n)p Fl(\))475 b(the)f(n)-36 b(um)g(b)36 b(er)473 b(of)i(biorders)f(of)h(T)-36 b(yp)36 b(e)475 b(0.)702 b(Similarly)-108 b(,)486 b(a)p Black 26475 74617 a(3)p Black eop %%Page: 4 4 4 3 bop Black 0 TeXcolorgray Black Black 800 1424 a Fl(biorder)419 b(from)h Fk(X)524 b Fl(to)420 b Fk(Y)708 b Fl(is)420 b(of)g(T)-36 b(yp)36 b(e)420 b(1)f(if)i Fk(R)11 b Fl(\()p Fk(x)p Fl(\))368 b(=)h Fk(Y)708 b Fl(holds)419 b(for)h(at)g(least)g (one)f(elemen)-36 b(t)419 b Fk(x)h Fl(in)f Fk(X)104 b Fl(;)426 b(denote)800 3029 y(b)-36 b(y)434 b Ff(B)3519 3228 y Fi(1)4045 3029 y Fl(\()p Fk(m;)221 b(n)p Fl(\))434 b(the)f(n)-36 b(um)g(b)36 b(er)432 b(of)i(suc)-36 b(h)433 b(biorders.)578 b(Notice)434 b(the)f(equalit)-36 b(y)20060 5963 y Ff(B)20972 6162 y Fi(0)21498 5963 y Fl(\()p Fk(m;)221 b(n)p Fl(\))1108 b(=)e Ff(B)29144 6162 y Fi(1)29671 5963 y Fl(\()p Fk(n;)221 b(m)p Fl(\))p Fk(;)p Black 17598 w Fl(\(8\))p Black 800 8896 a(whic)-36 b(h)404 b(follo)-36 b(ws)407 b(from)d(the)g(follo)-36 b(wing)407 b(t)-36 b(w)g(o)405 b(facts:)564 b(\257rst,)410 b(taking)405 b(the)f(complemen)-36 b(t)404 b(of)h(the)f(con)-36 b(v)g(erse)405 b(of)g(a)800 10501 y(biorder)441 b(from)i Fk(X)547 b Fl(to)442 b Fk(Y)730 b Fl(alw)-36 b(a)g(ys)444 b(giv)-36 b(es)443 b(a)f(biorder)f(from)i Fk(Y)730 b Fl(to)442 b Fk(X)104 b Fl(,)446 b(second)441 b(this)h(op)36 b(eration)442 b(transforms)800 12106 y(a)434 b(T)-36 b(yp)36 b(e)434 b(0)g(tableau)f(in)-36 b(to)434 b(a)g(T)-36 b(yp)36 b(e)434 b(1)g(tableau.)2751 13711 y(Moreo)-36 b(v)g(er,)434 b(from)g(the)f (de\257nition)g(of)h(biorders,)g(w)-36 b(e)434 b(get)f(at)h(once)17048 16645 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))1108 b(=)f Ff(B)25607 16844 y Fi(0)26133 16645 y Fl(\()p Fk(m;)221 b(n)p Fl(\))296 b(+)f Ff(B)32156 16844 y Fi(1)32682 16645 y Fl(\()p Fk(m;)221 b(n)p Fl(\))p Fk(:)p Black 14587 w Fl(\(9\))p Black 2751 19578 a(T)-108 b(o)486 b(obtain)g(recurrence)f (relations)h(\257rst)f(for)i Ff(B)26175 19777 y Fi(1)26701 19578 y Fl(\()p Fk(m;)221 b(n)p Fl(\))487 b(and)e(then)g(for)h Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\),)501 b(w)-36 b(e)486 b(no)-36 b(w)486 b(supp)36 b(ose)800 21183 y Fk(m)369 b(>)f Fl(0)411 b(and)e Fk(n)370 b(>)e Fl(0)411 b(and)e(\257x)i(some)f(orderings)g(of)h Fk(X)515 b Fl(and)410 b Fk(Y)288 b Fl(.)571 b(Th)-36 b(us)409 b(an)-36 b(y)411 b(biorder)e(\(ev)-36 b(en,)415 b(an)-36 b(y)411 b(relation\))800 22788 y(corresp)36 b(onds)433 b(to)h(exactly)h(one)e(tableau.)2751 24394 y(An)-36 b(y)454 b(T)-36 b(yp)36 b(e)454 b(1)g(biorder)f(is)h (univ)-36 b(o)36 b(cally)455 b(formed)f(b)-36 b(y)453 b(\(i\))h(selecting)g Fk(j)529 b Fl(among)454 b(the)f Fk(m)g Fl(ro)-36 b(ws,)460 b(for)454 b(some)800 25999 y Fk(j)522 b Fl(with)447 b(0)391 b Ff(\267)h Fk(j)467 b(<)391 b(m)p Fl(,)450 b(\(ii\))d(then)f(setting)g(all)i(en)-36 b(tries)447 b(in)f(the)h Fk(m)303 b Ff(\241)i Fk(j)521 b Fl(other)447 b(ro)-36 b(ws)447 b(to)g(1,)k(and)446 b(\(iii\))h(\257nally)800 27604 y(sp)36 b(ecifying)435 b(some)f(T)-36 b(yp)36 b(e)434 b(0)g(tableau)f(on)h(the)f(selected)g Fk(j)509 b Fl(ro)-36 b(ws.)579 b(This)433 b(sho)-36 b(ws)10447 31665 y Ff(B)11359 31864 y Fi(1)11886 31665 y Fl(\()p Fk(m;)221 b(n)p Fl(\))738 b(=)17882 30005 y Fh(m)p Fe(\241)p Fi(1)17940 30403 y Fd(X)18082 33202 y Fh(j)51 b Fi(=0)21245 29792 y Fd(\265)22222 30766 y Fk(m)22485 32576 y(j)23360 29792 y Fd(\266)24707 31665 y Ff(B)25619 31864 y Fi(0)26146 31665 y Fl(\()p Fk(j)r(;)221 b(n)p Fl(\))739 b(=)31544 30005 y Fh(m)p Fe(\241)p Fi(1)31602 30403 y Fd(X)31745 33202 y Fh(j)51 b Fi(=0)34907 29792 y Fd(\265)35885 30766 y Fk(m)36148 32576 y(j)37023 29792 y Fd(\266)38370 31665 y Ff(B)39282 31864 y Fi(1)39808 31665 y Fl(\()p Fk(n;)221 b(j)75 b Fl(\))p Fk(:)7336 b Fl(\(10\))2751 35943 y(No)-36 b(w)377 b(the)f(follo)-36 b(wing)379 b(computations)d(based)g(on)h (Equations)g(\()p 0 1 0 0 TeXcolorcmyk(8)p (#equation.8) [[371 394 377 406] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\){\()p 0 1 0 0 TeXcolorcmyk(10)p (#equation.10) [[392 394 403 406] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))g(giv)-36 b(e)378 b(us)e(Equation)h(\()p 0 1 0 0 TeXcolorcmyk(5)p (#equation.5) [[504 394 510 406] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))f(in)h(the)800 37548 y(statemen)-36 b(t:)7438 40481 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))1108 b(=)f Ff(B)15997 40680 y Fi(0)16524 40481 y Fl(\()p Fk(m;)221 b(n)p Fl(\))295 b(+)g Ff(B)22546 40680 y Fi(1)23073 40481 y Fl(\()p Fk(m;)221 b(n)p Fl(\))12966 42419 y(=)1107 b Ff(B)15997 42618 y Fi(1)16524 42419 y Fl(\()p Fk(n;)221 b(m)p Fl(\))295 b(+)g Ff(B)22546 42618 y Fi(1)23073 42419 y Fl(\()p Fk(m;)221 b(n)p Fl(\))12966 45557 y(=)15158 43897 y Fh(n)p Fe(\241)p Fi(1)15085 44295 y Fd(X)15186 47124 y Fh(k)24 b Fi(=0)18332 43684 y Fd(\265)19310 44659 y Fk(n)19338 46469 y(k)20086 43684 y Fd(\266)21433 45557 y Ff(B)22345 45756 y Fi(1)22872 45557 y Fl(\()p Fk(m;)221 b(k)45 b Fl(\))295 b(+)27927 43897 y Fh(m)p Fe(\241)p Fi(1)27985 44295 y Fd(X)28127 47095 y Fh(j)51 b Fi(=0)31290 43684 y Fd(\265)32268 44659 y Fk(m)32530 46469 y(j)33405 43684 y Fd(\266)34752 45557 y Ff(B)35664 45756 y Fi(1)36191 45557 y Fl(\()p Fk(n;)221 b(j)75 b Fl(\))12966 50207 y(=)15158 48546 y Fh(n)p Fe(\241)p Fi(1)15085 48945 y Fd(X)15186 51774 y Fh(k)24 b Fi(=0)17225 48334 y Fd(\265)18203 49308 y Fk(n)18231 51118 y(k)18979 48334 y Fd(\266)20179 48546 y Fh(m)p Fe(\241)p Fi(1)20236 48945 y Fd(X)20379 51744 y Fh(j)51 b Fi(=0)22435 48334 y Fd(\265)23412 49308 y Fk(m)23675 51118 y(j)24550 48334 y Fd(\266)25528 50207 y Ff(B)26440 50406 y Fi(0)26967 50207 y Fl(\()p Fk(j)r(;)221 b(k)45 b Fl(\))296 b(+)31424 48546 y Fh(m)p Fe(\241)p Fi(1)31482 48945 y Fd(X)31625 51744 y Fh(j)51 b Fi(=0)33680 48334 y Fd(\265)34658 49308 y Fk(m)34921 51118 y(j)35796 48334 y Fd(\266)37068 48546 y Fh(n)p Fe(\241)p Fi(1)36995 48945 y Fd(X)37097 51774 y Fh(k)24 b Fi(=0)39135 48334 y Fd(\265)40113 49308 y Fk(n)40141 51118 y(k)40889 48334 y Fd(\266)41867 50207 y Ff(B)42779 50406 y Fi(1)43306 50207 y Fl(\()p Fk(j)r(;)221 b(k)45 b Fl(\))12966 54856 y(=)15085 53195 y Fh(m)p Fe(\241)p Fi(1)15143 53594 y Fd(X)15285 56393 y Fh(j)51 b Fi(=0)17783 53195 y Fh(n)p Fe(\241)p Fi(1)17710 53594 y Fd(X)17811 56423 y Fh(k)24 b Fi(=0)20957 52983 y Fd(\265)21935 53957 y Fk(m)22197 55767 y(j)23073 52983 y Fd(\266)368 b(\265)25397 53957 y Fk(n)25425 55767 y(k)26174 52983 y Fd(\266)27520 54856 y Ff(B)40 b Fl(\()p Fk(j)r(;)221 b(k)45 b Fl(\))p Fk(:)2751 59134 y Fl(Finally)-108 b(,)553 b(the)527 b(v)-72 b(alues)529 b(in)f(Equations)h(\()p 0 1 0 0 TeXcolorcmyk(6)p (#equation.6) [[272 185 278 197] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\){\()p 0 1 0 0 TeXcolorcmyk(7)p (#equation.7) [[293 185 298 197] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))f(are)h(c)-36 b(hosen)527 b(to)i(generate)f(the)g(correct)g (expressions)800 60739 y Ff(B)40 b Fl(\()p Fk(m;)221 b Fl(1\))370 b(=)f(2)7495 60257 y Fh(m)8816 60739 y Fl(and)433 b Ff(B)40 b Fl(\(1)p Fk(;)221 b(n)p Fl(\))371 b(=)e(2)17679 60257 y Fh(n)18306 60739 y Fl(.)p 52170 60739 630 630 v 2751 63008 a(With)435 b(a)g(program)g(implemen)-36 b(ting)434 b(the)g(form)-36 b(ulas)435 b(from)g(Equation)g(\()p 0 1 0 0 TeXcolorcmyk(5)p (#equation.5) [[407 150 413 162] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)h(w)-36 b(e)435 b(computed)e(the)i(v)-72 b(alues)800 64613 y(of)355 b Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))356 b(sho)-36 b(wn)354 b(in)g(T)-108 b(able)354 b(1.)553 b(Notice)355 b Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))370 b(=)e Ff(B)40 b Fl(\()p Fk(n;)221 b(m)p Fl(\))356 b(\(whic)-36 b(h)354 b(holds)g(b)36 b(ecause)354 b(the)g(con)-36 b(v)g(erse)354 b(of)800 66218 y(a)376 b(biorder)f(is)h(alw)-36 b(a)g(ys)377 b(a)f(biorder\).)558 b(The)376 b(\257rst)f(t)-36 b(w)g(o)376 b(ro)-36 b(ws)376 b(in)f(T)-108 b(able)376 b(1)g(are)g(easily)h (explained.)559 b(F)-108 b(or)375 b Fk(m)369 b Fl(=)f(1,)800 67823 y(w)-36 b(e)491 b(ha)-36 b(v)g(e)491 b Ff(B)40 b Fl(\(1)p Fk(;)221 b(n)p Fl(\))468 b(=)d(2)12355 67341 y Fh(n)12982 67823 y Fl(.)749 b(F)-108 b(or)490 b Fk(m)466 b Fl(=)g(2,)505 b(the)490 b(tableaux)h(of)h(biorders)e(are)h(exactly)h (those)e(tableaux)h(not)800 69428 y(con)-36 b(taining)318 b(b)36 b(oth)318 b(a)g(column)15501 68839 y Fi(0)15501 69886 y(1)16422 69428 y Fl(and)g(a)g(column)24374 68839 y Fi(1)24374 69886 y(0)24977 69428 y Fl(.)540 b(Hence)318 b(their)g(n)-36 b(um)g(b)36 b(er)316 b(satis\257es)i Ff(B)40 b Fl(\(2)p Fk(;)221 b(n)p Fl(\))371 b(=)e(2)59 b Ff(\242)g Fl(3)49383 68946 y Fh(n)50070 69428 y Ff(\241)g Fl(2)51812 68946 y Fh(n)52439 69428 y Fl(.)p Black 26475 74617 a(4)p Black eop %%Page: 5 5 5 4 bop Black 0 TeXcolorgray Black Black Black 800 1092 a Fk(m)p Ff(n)p Fk(n)2602 b Fl(1)1951 b(2)2602 b(3)3473 b(4)4774 b(5)6296 b(6)6947 b(7)7818 b(8)p 800 2413 44242 45 v 800 4214 a(1)4530 b(2)1951 b(4)2602 b(8)2823 b(16)4124 b(32)5646 b(64)g(128)6518 b(256)800 5819 y(2)6481 b(14)1951 b(46)2173 b(146)3474 b(454)4125 b(1)221 b(394)4775 b(4)221 b(246)4997 b(12)221 b(866)800 7424 y(3)9082 b(230)1302 b(1)221 b(066)2603 b(4)221 b(718)3474 b(20)221 b(266)4126 b(85)221 b(310)4347 b(354)221 b(106)800 9029 y(4)12334 b(6)221 b(902)1952 b(41)221 b(506)2825 b(237)221 b(686)2604 b(1)221 b(315)g(666)3476 b(7)221 b(107)g(302)800 10635 y(5)16457 b(329)221 b(462)1953 b(2)221 b(441)g(314)1954 b(17)221 b(234)g(438)2176 b(117)221 b(437)g(746)800 12240 y(6)21881 b(22)221 b(934)g(773)1304 b(202)221 b(229)g(266)1305 b(1)221 b(701)g(740)g(006)p Black Black Black 17414 17996 a(T)-108 b(able)434 b(1:)p 0 TeXcolorgray Black 579 w(Some)f(v)-72 b(alues)434 b(of)g Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\).)p Black Black 800 21593 a Fm(3)2152 b(A)717 b(First)g(Explicit)f (F)-179 b(orm)-60 b(ula)800 24513 y Fl(Some)400 b(hand)f(computations)h (exploiting)i(the)d(double-recurrence)g(in)h(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 400 w(5)p (#equation.5) [[456 496 461 508] [1 1 1 [3 3]] [0 0 1]] pdfm Black 401 w(strongly)401 b(suggest)800 26119 y(to)456 b(write)h Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))457 b(as)g(a)f(w)-36 b(eigh)g(ted)456 b(sum)g(of)h Fk(n)p Fl(-th)e(p)36 b(o)-36 b(w)g(ers.)646 b(T)-108 b(o)457 b(iden)-36 b(tify)456 b(the)g(co)36 b(e\261cien)-36 b(ts,)462 b(w)-36 b(e)457 b(use)f(the)800 27724 y(Stirling)338 b(n)-36 b(um)g(b)36 b(ers)336 b(of)j(the)e(second)h(kind,)357 b(here)337 b(denoted)g(as)i Ff(S)100 b Fl(\()p Fk(m;)221 b(j)75 b Fl(\))337 b(\(see,)358 b(e.g.,)g([)p 0 1 0 0 TeXcolorcmyk(6)p (#cite.GrahamKnuthPatashnik1989) [[440 467 446 479] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])338 b(where)g(the)f(notation)800 28220 y Fd(n)1818 29105 y Fh(m)2019 30152 y(j)2784 28220 y Fd(o)4171 29694 y Fl(is)501 b(used\).)782 b(Remem)-36 b(b)36 b(er)501 b(that)g Ff(S)100 b Fl(\()p Fk(m;)221 b(j)75 b Fl(\),)518 b(the)501 b(n)-36 b(um)g(b)36 b(er)500 b(of)i(w)-36 b(a)g(ys)503 b(of)f(partitioning)g(an)f Fk(m)p Fl(-elemen)-36 b(t)800 31591 y(set)434 b(in)-36 b(to)433 b Fk(j)508 b Fl(classes,)435 b(equals)16572 35235 y Ff(S)100 b Fl(\()p Fk(m;)221 b(j)75 b Fl(\))1107 b(=)24341 34337 y(1)p 24179 34930 975 54 v 24179 36147 a Fk(j)75 b Fl(!)26620 33521 y Fh(j)25876 33974 y Fd(X)26074 36773 y Fh(i)p Fi(=1)27795 35235 y Fl(\()p Ff(\241)p Fl(1\))30490 34687 y Fh(j)51 b Fe(\241)p Fh(i)32398 33362 y Fd(\265)33376 34337 y Fk(j)33461 36147 y(i)33989 33362 y Fd(\266)35336 35235 y Fk(i)35780 34687 y Fh(m)36667 35235 y Fk(:)p Black 13460 w Fl(\(11\))p Black 800 38782 a(Here)434 b(are)f(some)h(other)f(prop)36 b(erties)434 b(of)g(these)f(n)-36 b(um)g(b)36 b(ers,)432 b(for)i Fk(m)369 b(>)g Fl(0:)15478 41230 y Ff(S)100 b Fl(\()p Fk(m;)221 b(j)75 b Fl(\))1107 b(=)f(0)2602 b(when)433 b Fk(j)444 b(<)369 b Fl(1)434 b(or)f Fk(m)369 b(<)g(j)r(;)p Black 12063 w Fl(\(12\))p Black 14953 43167 a Ff(S)100 b Fl(\()p Fk(m;)221 b(m)p Fl(\))1107 b(=)f Ff(S)100 b Fl(\()p Fk(m;)221 b Fl(1\))739 b(=)e(1)p Fk(;)p Black 19751 w Fl(\(13\))p Black 800 45615 a(and)13676 48064 y Ff(S)100 b Fl(\()p Fk(m;)221 b(u)p Fl(\))1107 b(=)g Ff(S)100 b Fl(\()p Fk(m)294 b Ff(\241)i Fl(1)p Fk(;)221 b(u)296 b Ff(\241)f Fl(1\))h(+)f Fk(u)369 b Ff(S)100 b Fl(\()p Fk(m)295 b Ff(\241)g Fl(1)p Fk(;)221 b(u)p Fl(\))p Fk(:)p Black 10565 w Fl(\(14\))p Black 800 50512 a(W)-108 b(e)460 b(will)i(also)g(need)d(\(see)i([)p 0 1 0 0 TeXcolorcmyk(6)p (#cite.GrahamKnuthPatashnik1989) [[200 262 206 274] [1 1 1 [3 3]] [0 0 1]] pdfm Black(],)468 b(Equation)461 b(\(6.17\))g(and)f(on)g(page)h(264,)469 b(the)459 b(form)-36 b(ula)461 b(for)g Fk(x)45559 50030 y Fh(n)46186 50512 y Fl(,)467 b(with)461 b Fk(x)f Fl(set)800 52117 y(to)434 b(1\):)578 b(for)434 b(1)370 b Ff(\267)f Fk(j)444 b Ff(\267)369 b Fk(m)p Fl(,)12945 55577 y Ff(S)100 b Fl(\()p Fk(m;)221 b(j)75 b Fl(\))1107 b(=)20963 53917 y Fh(m)20419 54315 y Fd(X)20540 57144 y Fh(k)24 b Fi(=)p Fh(j)23298 53704 y Fd(\265)24275 54679 y Fk(m)24484 56488 y(k)25413 53704 y Fd(\266)26760 55577 y Fl(\()p Ff(\241)p Fl(1\))29455 55029 y Fh(m)p Fe(\241)p Fh(k)31957 55577 y Ff(S)100 b Fl(\()p Fk(k)340 b Fl(+)295 b(1)p Fk(;)221 b(j)371 b Fl(+)295 b(1\))p Fk(;)p Black 9833 w Fl(\(15\))p Black 800 59325 a(and)433 b(for)h Fk(m)369 b Ff(\270)g Fl(1,)18189 62712 y(1)1107 b(=)22608 61052 y Fh(m)22064 61450 y Fd(X)22253 64240 y Fh(t)p Fi(=1)24721 62712 y Fl(\()p Ff(\241)p Fl(1\))27416 62164 y Fh(m)p Fi(+)p Fh(t)29745 62712 y Fk(t)p Fl(!)368 b Ff(S)100 b Fl(\()p Fk(m;)221 b(t)p Fl(\))p Fk(:)p Black 15077 w Fl(\(16\))p Black Black 800 66249 a Fb(Prop)42 b(osition)500 b(2)p Black 650 w Fa(F)-108 b(or)433 b Fk(m)369 b(>)g Fl(0)434 b Fa(and)f Fk(n)369 b Ff(\270)g Fl(0)p Fa(,)434 b(w)-36 b(e)434 b(ha)-36 b(v)g(e)13939 69635 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))1108 b(=)22129 67975 y Fh(m)21586 68373 y Fd(X)21774 71163 y Fh(t)p Fi(=1)24242 69635 y Fl(\()p Ff(\241)p Fl(1\))26937 69087 y Fh(m)p Fi(+)p Fh(t)29266 69635 y Fk(t)p Fl(!)369 b Ff(S)100 b Fl(\()p Fk(m;)221 b(t)p Fl(\))368 b(\()p Fk(t)295 b Fl(+)g(1\))38674 69087 y Fh(n)39300 69635 y Fk(:)p Black 10827 w Fl(\(17\))p Black Black 26475 74617 a(5)p Black eop %%Page: 6 6 6 5 bop Black 0 TeXcolorgray Black Black 800 1424 a Fj(Pr)-66 b(o)g(of)p Fl(.)578 b(Setting)433 b(for)h Fk(m)369 b(>)f Fl(0)434 b(and)f Fk(m)369 b Ff(\270)g Fk(t)g Ff(\270)g Fl(1)18821 4358 y Fk(b)19374 4557 y Fh(m;t)21970 4358 y Fl(=)1107 b(\()p Ff(\241)p Fl(1\))26784 3809 y Fh(m)p Fi(+)p Fh(t)29112 4358 y Fk(t)p Fl(!)369 b Ff(S)100 b Fl(\()p Fk(m;)221 b(t)p Fl(\))p Fk(;)p Black 15709 w Fl(\(18\))p Black 800 7291 a(and)433 b(also)i(for)f(con)-36 b(v)g(enience)433 b Fk(b)15595 7490 y Fh(m;m)p Fi(+1)19148 7291 y Fl(=)369 b(0,)434 b(w)-36 b(e)434 b(\257rst)e(record)i(some)g (prop)36 b(erties)433 b(of)h(the)f(n)-36 b(um)g(b)36 b(ers)432 b Fk(b)49436 7490 y Fh(m;n)51156 7291 y Fl(:)11751 10224 y Fk(b)12304 10423 y Fh(m;)p Fi(1)15030 10224 y Fl(=)1107 b(\()p Ff(\241)p Fl(1\))19844 9676 y Fh(m)p Fi(+1)21934 10224 y Fl(;)p Black 28193 w(\(19\))p Black 11389 12162 a Fk(b)11942 12361 y Fh(m;m)15030 12162 y Fl(=)g Fk(m)p Fl(!)369 b(;)p Black 31110 w(\(20\))p Black 11881 15340 a Fk(b)12434 15539 y Fh(m;t)15030 15340 y Fl(=)17484 13679 y Fh(m)p Fe(\241)p Fi(1)17542 14078 y Fd(X)17149 16877 y Fh(j)51 b Fi(=)p Fh(t)p Fe(\241)p Fi(1)20814 13467 y Fd(\265)21791 14441 y Fk(m)22054 16251 y(j)22929 13467 y Fd(\266)23907 15340 y Fl(\()p Fk(b)24966 15539 y Fh(j)o(;t)p Fe(\241)p Fi(1)27499 15340 y Ff(\241)295 b Fk(b)29380 15539 y Fh(j)o(;t)30416 15340 y Fl(\))p Fk(;)2823 b Fl(for)434 b(1)369 b Fk(<)g(t)g(<)f(m:)p Black 8277 w Fl(\(21\))p Black 800 19618 a(Equation)354 b(\()p 0 1 0 0 TeXcolorcmyk(19)p (#equation.19) [[134 540 145 552] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))f(follo)-36 b(ws)355 b(from)f Ff(S)100 b Fl(\()p Fk(m;)221 b Fl(1\))369 b(=)g(1,)h(and)353 b(Equation)g(\()p 0 1 0 0 TeXcolorcmyk(20)p (#equation.19) [[361 540 373 552] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))h(from)g Ff(S)100 b Fl(\()p Fk(m;)221 b(m)p Fl(\))368 b(=)h(1.)552 b(More)353 b(compu-)800 21223 y(tations)362 b(are)f(needed)g(for)h(the)f(next)g(equation.)555 b(Starting)361 b(from)g(the)g(righ)-36 b(t-hand)360 b(side)i(of)g (Equation)f(\()p 0 1 0 0 TeXcolorcmyk(21)p (#equation.19) [[528 526 539 538] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)800 22828 y(w)-36 b(e)434 b(ha)-36 b(v)g(e)434 b(\(in)f(view)i(of)f(Equations)g(\()p 0 1 0 0 TeXcolorcmyk(14)p (#equation.14) [[242 512 253 524] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))g(and)f(\()p 0 1 0 0 TeXcolorcmyk(15)p (#equation.15) [[289 512 301 524] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\)\))9096 25302 y Fh(m)p Fe(\241)p Fi(1)9154 25701 y Fd(X)8761 28500 y Fh(j)51 b Fi(=)p Fh(t)p Fe(\241)p Fi(1)12426 25090 y Fd(\265)13404 26064 y Fk(m)13666 27874 y(j)14541 25090 y Fd(\266)15519 26963 y Fl(\()p Fk(b)16578 27162 y Fh(j)o(;t)p Fe(\241)p Fi(1)19111 26963 y Ff(\241)296 b Fk(b)20993 27162 y Fh(j)o(;t)22028 26963 y Fl(\))12703 31612 y(=)15157 29952 y Fh(m)p Fe(\241)p Fi(1)15215 30350 y Fd(X)14821 33150 y Fh(j)51 b Fi(=)p Fh(t)p Fe(\241)p Fi(1)18486 29739 y Fd(\265)19464 30713 y Fk(m)19726 32523 y(j)20602 29739 y Fd(\266)21579 31612 y Fl(\()p Ff(\241)p Fl(1\))24274 31064 y Fh(j)g Fi(+)p Fh(t)p Fe(\241)p Fi(1)27035 31612 y Fl(\()p Fk(t)295 b Ff(\241)g Fl(1\)!)31521 30138 y Fd(\263)32314 31612 y Ff(S)100 b Fl(\()p Fk(j)r(;)221 b(t)296 b Ff(\241)f Fl(1\))h(+)f Fk(t)368 b Ff(S)100 b Fl(\()p Fk(j)r(;)221 b(t)p Fl(\))44045 30138 y Fd(\264)12703 36261 y Fl(=)1106 b(\()p Fk(t)295 b Ff(\241)g Fl(1\)!)370 b(\()p Ff(\241)p Fl(1\))22002 35713 y Fh(t)p Fe(\241)p Fi(1)24525 34601 y Fh(m)p Fe(\241)p Fi(1)24583 34999 y Fd(X)24190 37799 y Fh(j)51 b Fi(=)p Fh(t)p Fe(\241)p Fi(1)27854 34388 y Fd(\265)28832 35363 y Fk(m)29095 37173 y(j)29970 34388 y Fd(\266)31317 36261 y Fl(\()p Ff(\241)p Fl(1\))34012 35713 y Fh(j)34868 36261 y Ff(S)100 b Fl(\()p Fk(j)370 b Fl(+)294 b(1)p Fk(;)221 b(t)p Fl(\))12703 39676 y(=)1106 b(\()p Fk(t)295 b Ff(\241)g Fl(1\)!)370 b(\()p Ff(\241)p Fl(1\))22002 39127 y Fh(t)p Fe(\241)p Fi(1)23968 39676 y Fl(\()p Ff(\241)p Fl(1\))26663 39127 y Fh(m)27920 38600 y Fd(\241)28529 39676 y Ff(S)100 b Fl(\()p Fk(m;)221 b(t)295 b Ff(\241)g Fl(1\))h Ff(\241)f(S)100 b Fl(\()p Fk(m)295 b Fl(+)f(1)p Fk(;)221 b(t)p Fl(\))42889 38600 y Fd(\242)12703 41613 y Fl(=)1106 b(\()p Ff(\241)p Fl(1\))17516 41064 y Fh(m)p Fi(+)p Fh(t)19845 41613 y Fl(\()p Fk(t)294 b Ff(\241)i Fl(1\)!)369 b Fk(t)g Ff(S)100 b Fl(\()p Fk(m;)221 b(t)p Fl(\))12703 43550 y(=)1106 b Fk(b)15374 43749 y Fh(m;t)800 46484 y Fl(whic)-36 b(h)433 b(establishes)h(Equation)g(\()p 0 1 0 0 TeXcolorcmyk(21)p (#equation.19) [[226 299 238 311] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\).)2751 48089 y(Next)476 b(w)-36 b(e)475 b(establish)h(b)-36 b(y)475 b(double)g(recurrence)f(on)h Fk(m)440 b(>)g Fl(0)475 b(and)g Fk(n)441 b Ff(\270)f Fl(0)476 b(the)e(equalit)-36 b(y)477 b(in)e(the)g(thesis,)800 49694 y(rephrased)433 b(as:)18341 53566 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))1108 b(=)26531 51905 y Fh(m)25987 52304 y Fd(X)26176 55093 y Fh(t)p Fi(=1)28128 53566 y Fk(b)28681 53765 y Fh(m;t)30538 53566 y Fl(\()p Fk(t)295 b Fl(+)g(1\))34272 53017 y Fh(n)34898 53566 y Fk(:)p Black 15229 w Fl(\(22\))p Black 800 57661 a(This)385 b(equalit)-36 b(y)385 b(holds)f(for)h(sure)f (in)g(case)h Fk(m)369 b Fl(=)f(1)385 b(b)36 b(ecause)384 b(of)h Ff(B)40 b Fl(\(1)p Fk(;)221 b(n)p Fl(\))371 b(=)e(2)37240 57179 y Fh(n)38251 57661 y Fl(and)384 b(Equation)g(\()p 0 1 0 0 TeXcolorcmyk(19)p (#equation.19) [[493 198 505 210] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\);)402 b(it)384 b(also)800 59266 y(holds)433 b(in)h(case)g Fk(n)369 b Fl(=)g(0,)434 b(in)g(view)g(of)h Ff(B)40 b Fl(\()p Fk(m;)221 b Fl(0\))370 b(=)e(1)434 b(for)g Fk(m)369 b Ff(6)p Fl(=)g(0)434 b(and)f(Equation)h(\()p 0 1 0 0 TeXcolorcmyk(16)p (#equation.16) [[434 184 445 196] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\).)2751 60872 y(Supp)36 b(osing)433 b(no)-36 b(w)433 b(that)h(the)f(follo)-36 b(wing)435 b(equation)f(holds)g(for)g(1)369 b Ff(\267)g Fk(j)444 b(<)369 b(m)433 b Fl(and)g(0)369 b Ff(\267)g Fk(k)415 b(<)368 b(n)18922 65002 y Ff(B)40 b Fl(\()p Fk(j)r(;)221 b(k)45 b Fl(\))1109 b(=)26660 63287 y Fh(j)25916 63740 y Fd(X)26105 66529 y Fh(t)p Fi(=1)28057 65002 y Fk(b)28610 65201 y Fh(j)o(;t)30014 65002 y Fl(\()p Fk(t)295 b Fl(+)g(1\))33748 64453 y Fh(k)34317 65002 y Fk(;)p Black 15810 w Fl(\(23\))p Black Black 26475 74617 a(6)p Black eop %%Page: 7 7 7 6 bop Black 0 TeXcolorgray Black Black 800 1424 a Fl(w)-36 b(e)479 b(pro)36 b(ceed)478 b(to)g(infer)h(Equation)f(\()p 0 1 0 0 TeXcolorcmyk(22)p (#equation.22) [[238 704 250 716] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\).)714 b(After)478 b(ha)-36 b(ving)479 b(inserted)e(Equation)i (\()p 0 1 0 0 TeXcolorcmyk(23)p (#equation.23) [[433 704 445 716] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))g(in)-36 b(to)478 b(Equation)h(\()p 0 1 0 0 TeXcolorcmyk(5)p (#equation.5) [[534 704 539 716] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)800 3029 y(w)-36 b(e)434 b(get)g(successiv)-36 b(ely)6489 5963 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))8541 9101 y(=)10660 7441 y Fh(m)p Fe(\241)p Fi(1)10718 7840 y Fd(X)10860 10639 y Fh(j)51 b Fi(=0)13358 7441 y Fh(n)p Fe(\241)p Fi(1)13285 7840 y Fd(X)13386 10668 y Fh(k)24 b Fi(=0)16163 7229 y Fd(\265)17141 8203 y Fk(m)17403 10013 y(j)18278 7229 y Fd(\266)369 b(\265)20603 8203 y Fk(n)20631 10013 y(k)21379 7229 y Fd(\266)22726 9101 y Ff(B)40 b Fl(\()p Fk(j)r(;)221 b(k)45 b Fl(\))8541 13820 y(=)1107 b Ff(B)40 b Fl(\(0)p Fk(;)221 b Fl(0\))297 b(+)16143 12159 y Fh(n)p Fe(\241)p Fi(1)16070 12558 y Fd(X)16171 15387 y Fh(k)24 b Fi(=1)18579 11947 y Fd(\265)19557 12921 y Fk(n)19584 14731 y(k)20333 11947 y Fd(\266)21680 13820 y Ff(B)40 b Fl(\(0)p Fk(;)221 b(k)45 b Fl(\))297 b(+)27160 12159 y Fh(m)p Fe(\241)p Fi(1)27218 12558 y Fd(X)27361 15357 y Fh(j)51 b Fi(=1)29489 12159 y Fh(n)p Fe(\241)p Fi(1)29416 12558 y Fd(X)29518 15387 y Fh(k)24 b Fi(=0)31557 11947 y Fd(\265)32534 12921 y Fk(m)32797 14731 y(j)33672 11947 y Fd(\266)369 b(\265)35997 12921 y Fk(n)36024 14731 y(k)36773 11947 y Fd(\266)39085 12105 y Fh(j)38341 12558 y Fd(X)38530 15347 y Fh(t)p Fi(=1)40850 13820 y Fk(b)41403 14019 y Fh(j)o(;t)42808 13820 y Fl(\()p Fk(t)295 b Fl(+)g(1\))46542 13271 y Fh(k)8541 18538 y Fl(=)1107 b(2)295 b(+)g(\(2)14068 17989 y Fh(n)14990 18538 y Ff(\241)g Fl(2\))g(+)19076 16877 y Fh(m)p Fe(\241)p Fi(1)19134 17276 y Fd(X)19277 20075 y Fh(j)51 b Fi(=1)21701 16665 y Fd(\265)22679 17639 y Fk(m)22942 19449 y(j)23817 16665 y Fd(\266)26129 16823 y Fh(j)25385 17276 y Fd(X)25573 20065 y Fh(t)p Fi(=1)27894 18538 y Fk(b)28447 18737 y Fh(j)o(;t)30146 16877 y(n)p Fe(\241)p Fi(1)30073 17276 y Fd(X)30175 20105 y Fh(k)24 b Fi(=0)32582 16665 y Fd(\265)33560 17639 y Fk(n)33588 19449 y(k)34337 16665 y Fd(\266)35683 18538 y Fl(\()p Fk(t)295 b Fl(+)g(1\))39417 17989 y Fh(k)8541 23256 y Fl(=)1107 b(2)11310 22707 y Fh(n)12232 23256 y Fl(+)13538 21595 y Fh(m)p Fe(\241)p Fi(1)13596 21994 y Fd(X)13739 24793 y Fh(j)51 b Fi(=1)16163 21383 y Fd(\265)17141 22357 y Fk(m)17404 24167 y(j)18279 21383 y Fd(\266)20222 21541 y Fh(j)19478 21994 y Fd(X)19666 24783 y Fh(t)p Fi(=1)21987 23256 y Fk(b)22540 23455 y Fh(j)o(;t)23576 23256 y Fl(\(1)295 b(+)g Fk(t)g Fl(+)g(1\))29562 22707 y Fh(n)30483 23256 y Ff(\241)31812 21595 y Fh(m)p Fe(\241)p Fi(1)31870 21994 y Fd(X)32012 24793 y Fh(j)51 b Fi(=1)34068 21383 y Fd(\265)35046 22357 y Fk(m)35308 24167 y(j)36183 21383 y Fd(\266)38126 21541 y Fh(j)37383 21994 y Fd(X)37571 24783 y Fh(t)p Fi(=1)39892 23256 y Fk(b)40445 23455 y Fh(j)o(;t)41480 23256 y Fl(\()p Fk(t)295 b Fl(+)g(1\))45214 22707 y Fh(n)45840 23256 y Fk(:)800 27460 y Fl(Then)433 b(replacing)h Fk(t)295 b Fl(+)g(1)434 b(with)f Fk(t)h Fl(in)f(the)g(second)g(term,)h(w)-36 b(e)434 b(ha)-36 b(v)g(e)7042 30393 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))8464 33601 y(=)1107 b(2)11233 33052 y Fh(n)12154 33601 y Fl(+)13461 31940 y Fh(m)p Fe(\241)p Fi(1)13519 32339 y Fd(X)13662 35138 y Fh(j)51 b Fi(=1)16086 31728 y Fd(\265)17064 32702 y Fk(m)17326 34512 y(j)18202 31728 y Fd(\266)19912 31886 y Fh(j)g Fi(+1)19770 32339 y Fd(X)19958 35128 y Fh(t)p Fi(=2)22279 33601 y Fk(b)22832 33800 y Fh(j)o(;t)p Fe(\241)p Fi(1)25439 33601 y Fl(\()p Fk(t)295 b Fl(+)g(1\))29173 33052 y Fh(n)30094 33601 y Ff(\241)31423 31940 y Fh(m)p Fe(\241)p Fi(1)31480 32339 y Fd(X)31623 35138 y Fh(j)51 b Fi(=1)34047 31728 y Fd(\265)35025 32702 y Fk(m)35288 34512 y(j)36163 31728 y Fd(\266)38475 31886 y Fh(j)37731 32339 y Fd(X)37919 35128 y Fh(t)p Fi(=1)40609 33601 y Fk(b)41162 33800 y Fh(j)o(;t)42198 33601 y Fl(\()p Fk(t)295 b Fl(+)g(1\))45932 33052 y Fh(n)8464 38319 y Fl(=)10583 36047 y Fd(\303)11634 38319 y Fl(1)h Ff(\241)13908 36659 y Fh(m)p Fe(\241)p Fi(1)13966 37057 y Fd(X)14109 39856 y Fh(j)51 b Fi(=1)16164 36446 y Fd(\265)17142 37420 y Fk(m)17404 39230 y(j)18280 36446 y Fd(\266)19626 38319 y Fk(b)20179 38518 y Fh(j)o(;)p Fi(1)21346 36047 y Fd(!)22619 38319 y Fl(2)23269 37770 y Fh(n)24191 38319 y Fl(+)25497 36659 y Fh(m)p Fe(\241)p Fi(1)25555 37057 y Fd(X)25698 39856 y Fh(j)g Fi(=1)28122 36446 y Fd(\265)29100 37420 y Fk(m)29363 39230 y(j)30238 36446 y Fd(\266)31949 36604 y Fh(j)g Fi(+1)31806 37057 y Fd(X)31994 39847 y Fh(t)p Fi(=2)34315 38319 y Fl(\()p Fk(b)35374 38518 y Fh(j)o(;t)p Fe(\241)p Fi(1)37907 38319 y Ff(\241)296 b Fk(b)39789 38518 y Fh(j)o(;t)40824 38319 y Fl(\))591 b(\()p Fk(t)294 b Fl(+)h(1\))45654 37770 y Fh(n)800 42523 y Fl(and)433 b(using)h Fk(b)7286 42722 y Fh(j)o(;j)51 b Fi(+1)9984 42523 y Fl(=)369 b(0)5328 45456 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))6750 48595 y(=)8869 46324 y Fd(\303)9921 48595 y Fl(1)295 b Ff(\241)12194 46935 y Fh(m)p Fe(\241)p Fi(1)12252 47333 y Fd(X)12395 50133 y Fh(j)51 b Fi(=1)14450 46722 y Fd(\265)15428 47697 y Fk(m)15691 49506 y(j)16566 46722 y Fd(\266)17913 48595 y Fl(\()p Ff(\241)p Fl(1\))20608 48047 y Fh(j)g Fi(+1)22297 46324 y Fd(!)23570 48595 y Fl(2)24220 48047 y Fh(n)25142 48595 y Fl(+)26992 46935 y Fh(m)26449 47333 y Fd(X)26637 50123 y Fh(t)p Fi(=2)28736 48595 y Fl(\()p Fk(t)295 b Fl(+)g(1\))32470 48047 y Fh(n)34022 46935 y(m)p Fe(\241)p Fi(1)34080 47333 y Fd(X)33687 50133 y Fh(j)51 b Fi(=)p Fh(t)p Fe(\241)p Fi(1)37351 46722 y Fd(\265)38329 47697 y Fk(m)38592 49506 y(j)39467 46722 y Fd(\266)41035 48595 y Fl(\()p Fk(b)42094 48794 y Fh(j)o(;t)p Fe(\241)p Fi(1)44627 48595 y Ff(\241)296 b Fk(b)46509 48794 y Fh(j)o(;t)47544 48595 y Fl(\))6750 52000 y(=)1107 b(\()p Ff(\241)p Fl(1\))11564 51451 y Fh(m)p Fi(+1)14023 52000 y Fl(2)14673 51451 y Fh(n)14072 55138 y Fl(+)15305 53478 y Fh(m)p Fe(\241)p Fi(1)15363 53877 y Fd(X)15551 56666 y Fh(t)p Fi(=2)17708 55138 y Fl(\()p Fk(t)295 b Fl(+)g(1\))21442 54590 y Fh(n)22994 53478 y(m)p Fe(\241)p Fi(1)23052 53877 y Fd(X)22658 56676 y Fh(j)51 b Fi(=)p Fh(t)p Fe(\241)p Fi(1)26323 53265 y Fd(\265)27301 54240 y Fk(m)27564 56050 y(j)28439 53265 y Fd(\266)30007 55138 y Fl(\()p Fk(b)31066 55337 y Fh(j)o(;t)p Fe(\241)p Fi(1)33599 55138 y Ff(\241)295 b Fk(b)35480 55337 y Fh(j)o(;t)36516 55138 y Fl(\))19274 58420 y(+)p Fk(m)369 b(b)22346 58619 y Fh(m)p Fe(\241)p Fi(1)p Fh(;m)p Fe(\241)p Fi(1)27100 58420 y Fl(\()p Fk(m)295 b Fl(+)g(1\))31502 57872 y Fh(n)32128 58420 y Fk(:)800 61353 y Fl(No)-36 b(w)434 b(Equations)g(\()p 0 1 0 0 TeXcolorcmyk(19)p (#equation.19) [[166 165 177 177] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)g(\()p 0 1 0 0 TeXcolorcmyk(21)p (#equation.19) [[194 165 205 177] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)g(\()p 0 1 0 0 TeXcolorcmyk(20)p (#equation.19) [[222 165 233 177] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))g(lead)g(to)10802 65489 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))1108 b(=)f Fk(b)19002 65688 y Fh(m;)p Fi(1)20622 65489 y Fl(2)21272 64940 y Fh(n)22193 65489 y Fl(+)23500 63828 y Fh(m)p Fe(\241)p Fi(1)23558 64227 y Fd(X)23746 67016 y Fh(t)p Fi(=2)26494 65489 y Fk(b)27047 65688 y Fh(m;t)28905 65489 y Fl(\()p Fk(t)294 b Fl(+)h(1\))32638 64940 y Fh(n)33560 65489 y Fl(+)g Fk(b)35420 65688 y Fh(m;m)37770 65489 y Fl(\()p Fk(m)g Fl(+)f(1\))42171 64940 y Fh(n)800 69584 y Fl(whic)-36 b(h)433 b(is)h(Equation)g(\()p 0 1 0 0 TeXcolorcmyk(22)p (#equation.22) [[180 91 191 103] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\).)579 b(This)434 b(completes)f(the)g(pro)36 b(of)435 b(b)-36 b(y)433 b(recurrence.)p 52170 69584 630 630 v Black 26475 74617 a(7)p Black eop %%Page: 8 8 8 7 bop Black 0 TeXcolorgray Black Black 2751 1424 a Fl(Replacing)684 b(the)f(Stirling)g(n)-36 b(um)g(b)36 b(ers)681 b(in)i(Equation)h(\()p 0 1 0 0 TeXcolorcmyk(17)p (#equation.17) [[342 704 354 716] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))f(with)g(their)g(expressions)h(from)f(Equa-)800 3029 y(tion)434 b(\()p 0 1 0 0 TeXcolorcmyk(11)p (#equation.11) [[108 690 120 702] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)g(w)-36 b(e)434 b(deriv)-36 b(e)433 b(the)g(more)h(explicit)h (form)-36 b(ula)13173 6259 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))1108 b(=)21363 4598 y Fh(m)20820 4997 y Fd(X)21018 7796 y Fh(i)p Fi(=1)23108 6259 y Fl(\()p Ff(\241)p Fl(1\))25803 5710 y Fh(m)p Fe(\241)p Fh(i)28481 6259 y Fk(i)28925 5710 y Fh(m)30946 4598 y(m)30402 4997 y Fd(X)30666 7796 y Fh(t)p Fi(=)p Fh(i)32911 4386 y Fd(\265)33889 5360 y Fk(t)33902 7170 y(i)34359 4386 y Fd(\266)35706 6259 y Fl(\()p Fk(t)294 b Fl(+)h(1\))39439 5710 y Fh(n)40066 6259 y Fk(:)p Black 10061 w Fl(\(24\))p Black 2751 9648 a(Another)474 b(reform)-36 b(ulation)475 b(is)f(obtained)h(b)-36 b(y)474 b(in)-36 b(tro)36 b(ducing)474 b(the)g(n)-36 b(um)g(b)36 b(er)473 b Ff(W)109 b Fl(\()p Fk(m;)221 b(k)45 b Fl(\))439 b(=)f Fk(k)45 b Fl(!)439 b Ff(S)100 b Fl(\()p Fk(m;)221 b(k)45 b Fl(\))474 b(of)800 11253 y(w)-36 b(eak)435 b(orders)e(with)h Fk(k)478 b Fl(classes)435 b(on)e(an)h Fk(m)p Fl(-elemen)-36 b(t)432 b(set:)14280 14150 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))1108 b(=)22470 12490 y Fh(m)21927 12889 y Fd(X)22115 15678 y Fh(t)p Fi(=1)24584 14150 y Fl(\()p Ff(\241)p Fl(1\))27279 13602 y Fh(m)p Fi(+)p Fh(t)29607 14150 y Ff(W)109 b Fl(\()p Fk(m;)221 b(t)p Fl(\))369 b(\()p Fk(t)295 b Fl(+)f(1\))38332 13602 y Fh(n)38959 14150 y Fk(:)p Black 11168 w Fl(\(25\))p Black 2751 17530 a(All)464 b(of)h(these)e(form)-36 b(ulas)464 b(for)g Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))465 b(are)f (alternating)f(sums.)668 b(W)-108 b(e)464 b(no)-36 b(w)464 b(turn)e(to)i(another)f(w)-36 b(a)g(y)464 b(of)800 19135 y(coun)-36 b(ting,)433 b(whic)-36 b(h)434 b(will)h(pro)-36 b(vide)433 b(us)g(with)h(a)g(sum)f(of)h(p)36 b(ositiv)-36 b(e)435 b(terms.)800 23466 y Fm(4)2152 b(A)717 b(Second)f(Explicit)h(F) -179 b(orm)-60 b(ula)800 26387 y Fl(In)319 b(view)i(of)f(the)e(prop)36 b(erties)319 b(collected)h(in)f(the)g(In)-36 b(tro)36 b(duction,)342 b(an)-36 b(y)319 b(biorder)g Fk(B)386 b Fl(from)320 b Fk(X)424 b Fl(to)320 b Fk(Y)608 b Fl(determines)800 27992 y(a)434 b(w)-36 b(eak)435 b(order)e Fk(B)9520 28191 y Fh(X)10852 27992 y Fl(on)g Fk(X)539 b Fl(and)433 b(a)h(w)-36 b(eak)434 b(order)g Fk(B)25525 28191 y Fh(Y)26768 27992 y Fl(on)f Fk(Y)289 b Fl(,)434 b(de\257ned)e(through)5756 30209 y Fk(x)369 b(B)7852 30408 y Fh(X)9119 30209 y Fk(x)9858 29661 y Fe(0)10907 30209 y Ff(\()-221 b(\))738 b Fk(B)67 b Fl(\()p Fk(x)p Fl(\))369 b Ff(\265)g Fk(B)67 b Fl(\()p Fk(x)20957 29661 y Fe(0)21268 30209 y Fl(\))p Fk(;)1522 b Fl(and)1300 b Fk(y)417 b(B)29092 30408 y Fh(Y)30271 30209 y Fk(y)30953 29661 y Fe(0)32001 30209 y Ff(\()-221 b(\))739 b Fk(B)36230 29661 y Fe(\241)p Fi(1)37488 30209 y Fl(\()p Fk(y)48 b Fl(\))368 b Ff(\265)h Fk(B)42007 29661 y Fe(\241)p Fi(1)43265 30209 y Fl(\()p Fk(y)44453 29661 y Fe(0)44763 30209 y Fl(\))p Fk(:)p Black 4858 w Fl(\(26\))p Black Black 800 32426 a Fb(Prop)42 b(osition)500 b(3)p Black 650 w Fa(Giv)-36 b(en)369 b(a)h(biorder)e Fk(B)437 b Fa(from)369 b Fk(X)474 b Fa(to)370 b Fk(Y)288 b Fa(,)383 b(the)368 b(t)-36 b(w)g(o)370 b(w)-36 b(eak)370 b(orders)f Fk(B)41293 32625 y Fh(X)42560 32426 y Fa(and)g Fk(B)46013 32625 y Fh(Y)47192 32426 y Fa(ha)-36 b(v)g(e)369 b(their)800 34032 y(n)-36 b(um)g(b)36 b(ers)388 b(of)i(equiv)-72 b(alence)390 b(classes)g(di\256ering)f(b)-36 b(y)389 b(at)g(most)g(one.)564 b(Con)-36 b(v)g(ersely)-108 b(,)399 b(an)-36 b(y)390 b(t)-36 b(w)g(o)389 b(w)-36 b(eak)390 b(orders)f(on)800 35637 y(resp)36 b(ectiv)-36 b(ely)419 b Fk(X)522 b Fa(and)418 b Fk(Y)706 b Fa(whic)-36 b(h)417 b(ha)-36 b(v)g(e)418 b(the)f(same)h(n)-36 b(um)g(b)36 b(er)417 b(of)h(equiv)-72 b(alence)419 b(classes)f(deriv)-36 b(e)418 b(in)g(this)f(w)-36 b(a)g(y)800 37242 y(from)463 b(exactly)g(t)-36 b(w)g(o)462 b(biorders)g(from)g Fk(X)567 b Fa(to)462 b Fk(Y)289 b Fa(.)664 b(Also,)470 b(if)463 b(t)-36 b(w)g(o)462 b(w)-36 b(eak)463 b(orders)f(on)g(resp)36 b(ectiv)-36 b(ely)463 b Fk(X)567 b Fa(and)461 b Fk(Y)800 38847 y Fa(ha)-36 b(v)g(e)476 b(their)e(n)-36 b(um)g(b)36 b(ers)474 b(of)i(equiv)-72 b(alence)477 b(classes)f(di\256ering)f(b)-36 b(y)475 b Fl(1)p Fa(,)486 b(then)475 b(they)g(deriv)-36 b(e)475 b(from)h(exactly)h(one)800 40452 y(biorder)433 b(from)h Fk(X)539 b Fa(to)433 b Fk(Y)289 b Fa(.)800 42789 y Fj(Pr)-66 b(o)g(of)p Fl(.)635 b(All)453 b(assertions)g(can)f(b)36 b(e)452 b(easily)i(c)-36 b(hec)g(k)g(ed)453 b(b)-36 b(y)452 b(considering)h(a)f(step-lik)-36 b(e)453 b(tableau)g(for)g(the)f(\(giv) -36 b(en)800 44394 y(or)434 b(to-b)36 b(e-constructed\))431 b(biorder)i Fk(B)67 b Fl(.)p 52170 44394 630 630 v 2751 46459 a(W)-108 b(e)420 b(no)-36 b(w)421 b(deriv)-36 b(e)420 b(a)h(second)f(explicit)h(form)-36 b(ula)421 b(for)g(the)f(n)-36 b(um)g(b)36 b(er)419 b(of)i(biorders)f(from)h Fk(X)525 b Fl(to)420 b Fk(Y)289 b Fl(,)423 b(whic)-36 b(h)800 48064 y(in)433 b(case)i Ff(j)p Fk(X)104 b Ff(j)369 b Fl(=)g Ff(j)p Fk(Y)289 b Ff(j)433 b Fl(w)-36 b(as)434 b(\257rst)f(obtained)g(b)-36 b(y)434 b(Destr)-36 b(\266)-614 b(ee)434 b([)p 0 1 0 0 TeXcolorcmyk(3)p (#cite.Destree1996) [[327 284 333 296] [1 1 1 [3 3]] [0 0 1]] pdfm Black(].)p Black 800 50690 a Fb(Prop)42 b(osition)500 b(4)p Black 650 w Fa(The)390 b(n)-36 b(um)g(b)36 b(er)387 b Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))391 b Fa(of)f(biorders)f (from)h Fk(X)494 b Fa(to)389 b Fk(Y)289 b Fa(,)399 b(where)389 b Ff(j)p Fk(X)104 b Ff(j)370 b Fl(=)e Fk(m)389 b Fa(and)g Ff(j)p Fk(Y)289 b Ff(j)369 b Fl(=)f Fk(n)p Fa(,)800 52296 y(equals)7013 55451 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))1109 b(=)15204 53791 y Fh(m)14660 54189 y Fd(X)14762 57018 y Fh(k)24 b Fi(=1)16800 55451 y Fk(k)45 b Fl(!)370 b(\()p Fk(k)340 b Ff(\241)295 b Fl(1\)!)370 b Ff(S)100 b Fl(\()p Fk(m;)221 b(k)45 b Fl(\))27715 54375 y Fd(\241)28323 55451 y Ff(S)100 b Fl(\()p Fk(n)296 b Fl(+)f(1)p Fk(;)221 b(k)45 b Fl(\))296 b(+)f Fk(k)266 b Ff(S)100 b Fl(\()p Fk(n)295 b Fl(+)g(1)p Fk(;)221 b(k)342 b Fl(+)294 b(1\))45616 54375 y Fd(\242)46225 55451 y Fk(:)p Black 3902 w Fl(\(27\))p Black 2751 58870 a(Remark)463 b(that,)468 b(con)-36 b(trary)462 b(to)g(Equation)g(\()p 0 1 0 0 TeXcolorcmyk(17)p (#equation.17) [[287 187 299 199] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)470 b(w)-36 b(e)462 b(ha)-36 b(v)g(e)462 b(here)f(a)h(sum)g (of)g(p)36 b(ositiv)-36 b(e)463 b(terms.)663 b(On)461 b(the)800 60475 y(other)433 b(hand,)g(there)g(are)h(more)g(summations)f (here,)g(b)36 b(ecause)434 b(eac)-36 b(h)433 b(Stirling)h(n)-36 b(um)g(b)36 b(er)432 b(requires)i(one.)800 62710 y Fj(Pr)-66 b(o)g(of)p Fl(.)578 b(>F)-108 b(rom)433 b(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 434 w(3)p (#theorem.4.3) [[214 153 220 165] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)434 b(w)-36 b(e)434 b(deriv)-36 b(e)5367 64927 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))1671 b(=)8125 66216 y Fh(m)7581 66615 y Fd(X)7683 69444 y Fh(k)24 b Fi(=1)9722 67877 y Fk(k)45 b Fl(!)221 b Ff(S)100 b Fl(\()p Fk(m;)221 b(k)45 b Fl(\))15603 66801 y Fd(\241)16213 67877 y Fl(\()p Fk(k)340 b Ff(\241)295 b Fl(1\)!)221 b Ff(S)100 b Fl(\()p Fk(n;)221 b(k)342 b Ff(\241)295 b Fl(1\))h(+)e(2)221 b Fk(k)45 b Fl(!)221 b Ff(S)100 b Fl(\()p Fk(n;)221 b(k)45 b Fl(\))298 b(+)d(\()p Fk(k)340 b Fl(+)295 b(1\)!)221 b Ff(S)100 b Fl(\()p Fk(n;)221 b(k)342 b Fl(+)294 b(1\))47262 66801 y Fd(\242)47871 67877 y Fk(:)800 71296 y Fl(Applying)434 b(Equation)g(\()p 0 1 0 0 TeXcolorcmyk(14)p (#equation.14) [[185 75 197 87] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)g(w)-36 b(e)434 b(get)g(Equation)f(\()p 0 1 0 0 TeXcolorcmyk(27)p (#equation.27) [[300 75 312 87] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\).)p 52170 71296 V Black 26475 74617 a(8)p Black eop %%Page: 9 9 9 8 bop Black 0 TeXcolorgray Black Black 2751 1424 a Fl(In)433 b(the)g(particular)h(case)g Fk(m)369 b Fl(=)f Fk(n)p Fl(,)435 b(w)-36 b(e)433 b(ha)-36 b(v)g(e)434 b([)p 0 1 0 0 TeXcolorcmyk(3)p (#cite.Destree1996) [[298 704 304 716] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])12563 5318 y Ff(B)40 b Fl(\()p Fk(m;)221 b(m)p Fl(\))1107 b(=)g(2)22355 3658 y Fh(m)21812 4057 y Fd(X)21913 6885 y Fh(k)24 b Fi(=1)24099 5318 y Fl(\()p Fk(k)45 b Fl(!\))26193 4770 y Fi(2)27088 5318 y Ff(S)100 b Fl(\()p Fk(m;)221 b(k)45 b Fl(\))369 b Ff(S)100 b Fl(\()p Fk(m)295 b Fl(+)g(1)p Fk(;)221 b(k)341 b Fl(+)295 b(1\))p Fk(:)p Black 9451 w Fl(\(28\))p Black 2751 9328 a(Returning)336 b(to)i(the)e(general)i(case,)357 b(w)-36 b(e)338 b(conclude)e(that)h (the)g(n)-36 b(um)g(b)36 b(er)335 b(of)j(biorders)f(b)36 b(oth)336 b(equals)i(either)800 10934 y(side)434 b(of)10454 12835 y Fh(m)9911 13234 y Fd(X)10099 16023 y Fh(t)p Fi(=1)12567 14496 y Fl(\()p Ff(\241)p Fl(1\))15262 13947 y Fh(m)p Fi(+)p Fh(t)17591 14496 y Fk(t)p Fl(!)369 b Ff(S)100 b Fl(\()p Fk(m;)221 b(t)p Fl(\))368 b(\()p Fk(t)295 b Fl(+)g(1\))26999 13947 y Fh(n)29295 14496 y Fl(=)12668 17113 y Fh(m)12125 17512 y Fd(X)12226 20341 y Fh(k)24 b Fi(=1)14265 18774 y Fk(k)45 b Fl(!)369 b(\()p Fk(k)340 b Ff(\241)295 b Fl(1\)!)370 b Ff(S)100 b Fl(\()p Fk(m;)221 b(k)45 b Fl(\))25179 17698 y Fd(\241)25788 18774 y Ff(S)100 b Fl(\()p Fk(n)295 b Fl(+)g(1)p Fk(;)221 b(k)45 b Fl(\))296 b(+)f Fk(k)266 b Ff(S)100 b Fl(\()p Fk(n)296 b Fl(+)e(1)p Fk(;)221 b(k)342 b Fl(+)295 b(1\))43081 17698 y Fd(\242)p Black 50488 18774 a Fl(\(29\))p Black 800 22784 a(and)433 b(is)h(the)f(solution)h(to)g(the)f(double)g(recurrence,)f(for)j Fk(m)368 b(>)h Fl(0)434 b(and)f Fk(n)369 b(>)g Fl(0,)14878 26794 y Ff(B)40 b Fl(\()p Fk(m;)221 b(n)p Fl(\))1109 b(=)22525 25133 y Fh(m)p Fe(\241)p Fi(1)22583 25532 y Fd(X)22726 28331 y Fh(j)51 b Fi(=0)25223 25133 y Fh(n)p Fe(\241)p Fi(1)25150 25532 y Fd(X)25252 28361 y Fh(k)24 b Fi(=0)28028 24921 y Fd(\265)29006 25895 y Fk(m)29269 27705 y(j)30144 24921 y Fd(\266)369 b(\265)32468 25895 y Fk(n)32496 27705 y(k)33245 24921 y Fd(\266)34592 26794 y Ff(B)40 b Fl(\()p Fk(j)r(;)221 b(k)45 b Fl(\))p Fk(;)p Black 11768 w Fl(\(30\))p Black 800 30946 a(with)434 b(initial)g(conditions)15171 33828 y Ff(B)40 b Fl(\()p Fk(m;)221 b Fl(0\))371 b(=)d Ff(B)40 b Fl(\(0)p Fk(;)221 b(n)p Fl(\))371 b(=)e(1)1107 b(and)g Ff(B)40 b Fl(\(0)p Fk(;)221 b Fl(0\))370 b(=)f(2)p Fk(:)p Black 12060 w Fl(\(31\))p Black 800 38258 a Fm(References)p Black 1450 41178 a Fl([1])p Black 652 w(J.-L.)607 b(Chandon,)650 b(J.)608 b(Lemaire,)652 b(and)606 b(J.)i(P)-36 b(ouget,)1139 b(D)-36 b(\266)-614 b(enom)-36 b(bremen)g(t)606 b(des)h(quasi-ordres)g (sur)g(un)3474 42783 y(ensem)-36 b(ble)433 b(\257ni,)576 b Fj(Math.)464 b(Sci.)g(Humaines)432 b Fb(62)i Fl(\(1978\),)h(61{80.)p Black 1450 45481 a([2])p Black 652 w(O.)e(Cogis,)578 b(On)433 b(the)g(Ferrers)g(dimension)g(of)i(a)f(digraph,)576 b Fj(Discr)-66 b(ete)463 b(Math.)433 b Fb(38)h Fl(\(1982\),)h(47{52.)p Black 1450 48178 a([3])p Black 652 w(L.)537 b(Destr)-36 b(\266)-614 b(ee,)913 b(Probl)-36 b(\265)-614 b(emes)538 b(algorithmiques)h(sur)e(les)h(biordres)f(et)h(mo)36 b(d)-36 b(\265)-614 b(eles)538 b(relationnels)g(appar-)3474 49783 y(en)-36 b(t)g(\266)-614 b(es,)382 b(Master's)297 b(thesis,)325 b(Univ)-36 b(ersit)g(\266)-614 b(e)298 b(Libre)f(de)h(Bruxelles,)325 b(D)-36 b(\266)-614 b(epartemen)-36 b(t)297 b(d'Informatique,)326 b(Brus-)3474 51388 y(sels,)434 b(Belgium,)g(1996.)p Black 1450 54086 a([4])p Black 652 w(J.-P)-108 b(.)367 b(Doignon,)383 b(A.)368 b(Ducamp,)381 b(and)368 b(J.-Cl.)g(F)-108 b(almagne,)484 b(On)367 b(realizable)i (biorders)f(and)f(the)h(biorder)3474 55691 y(dimension)433 b(of)h(a)g(relation,)578 b Fj(J.)464 b(Math.)g(Psych.)434 b Fb(28)g Fl(\(1984\),)h(73{109.)p Black 1450 58388 a([5])p Black 652 w(P)-108 b(.C.)434 b(Fish)-36 b(burn,)575 b Fj(Interval)463 b(Or)-66 b(ders)465 b(and)g(Interval)f(Gr)-66 b(aphs)p Fl(,)577 b(Wiley)-108 b(,)435 b(1985.)p Black 1450 61086 a([6])p Black 652 w(R.L.)397 b(Graham,)404 b(D.E.)397 b(Kn)-36 b(uth,)403 b(and)397 b(O.)f(P)-36 b(atashnik,)525 b Fj(Concr)-66 b(ete)429 b(Mathematics)p Fl(,)523 b(Addison)396 b(W)-108 b(esley)g(,)3474 62691 y(1986.)p Black 1450 65388 a([7])p Black 652 w(L.)563 b(Guttman,)996 b(A)563 b(basis)h(for)g(scaling)h(quan)-36 b(titativ)g(e)564 b(data,)997 b Fj(A)-33 b(meric)-66 b(an)582 b(So)-66 b(ciolo)g(gic)g(al)582 b(R)-66 b(eview)562 b Fb(9)3474 66993 y Fl(\(1944\),)434 b(139{150.)p Black 1450 69691 a([8])p Black 652 w(P)-108 b(.E.)521 b(Haxell,)545 b(J.J.)523 b(McDonald,)544 b(and)521 b(S.K.)h(Thomason,)861 b(Coun)-36 b(ting)521 b(in)-36 b(terv)-72 b(al)522 b(orders,)861 b Fj(Or)-66 b(der)521 b Fb(4)3474 71296 y Fl(\(1987\),)434 b(269{272.)p Black 26475 74617 a(9)p Black eop %%Page: 10 10 10 9 bop Black 0 TeXcolorgray Black Black Black 1450 1424 a Fl([9])p Black 652 w(B.)501 b(Monjardet,)794 b(Axiomatiques)502 b(et)f(propri)-36 b(\266)-614 b(et)-36 b(\266)-614 b(es)501 b(des)f(quasi-ordres,)794 b Fj(Math.)527 b(Sci.)e(Humaines)500 b Fb(63)3474 3029 y Fl(\(1978\),)434 b(51{82.)p Black 800 5741 a([10])p Black 652 w(J.)g(Riguet,)577 b(Les)433 b(relations)h(de)g(Ferrers,)576 b Fj(C.)464 b(R.)g(A)-66 b(c)g(ad.)464 b(Sci.)f(Paris)434 b Fb(232)g Fl(\(1951\),)h(1729{1730.)p Black 800 8453 a([11])p Black 652 w(N.J.A.)384 b(Sloane,)505 b Fj(The)419 b(On-line)e(Encyclop)-66 b(e)g(dia)417 b(of)i(Inte)-66 b(ger)416 b(Se)-66 b(quenc)g(es)p Fl(,)503 b(Published)382 b(electronically)3474 10058 y(at)433 b(h)-36 b(ttp://www.researc)g (h.att.com/)p Ff(\273)p Fl(njas/sequences/,)437 b(2003.)p Black 800 12770 a([12])p Black 652 w(M.)612 b(Y)-108 b(annak)-72 b(akis,)1156 b(The)612 b(complexit)-36 b(y)614 b(of)f(the)f(partial)h(order)f(dimension)g(problem,)1155 b Fj(SIAM)628 b(J.)3474 14376 y(A)-33 b(lgebr)-66 b(aic)462 b(Discr)-66 b(ete)463 b(Metho)-66 b(ds)434 b Fb(3)g Fl(\(1982\),)g (351{358.)p 800 17519 52000 45 v 800 19770 a(2000)h Fj(Mathematics)464 b(Subje)-66 b(ct)463 b(Classi\257c)-66 b(ation)p Fl(:)577 b(Primary)434 b(05A15)h(;)e(Secondary)h(06A06.)800 21375 y Fj(Keywor)-66 b(ds:)1250 b Fl(biorder,)434 b(Stirling)f(n)-36 b(um)g(b)36 b(er)432 b(of)i(the)g(second)f(kind.)p 800 23006 V 800 25331 a(\(Concerned)g(with)h(sequence)p 0 1 0 0 TeXcolorcmyk 433 w(A006531)p 16090 25543 4878 54 v [[217 489 261 501] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=A006531) pdfm Black 2 w(,)p 0 1 0 0 TeXcolorcmyk 434 w(A000108)p 21762 25543 V [[268 489 312 501] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=A000108) pdfm Black 2 w(,)p 0 1 0 0 TeXcolorcmyk 434 w(A022493)p 27434 25543 V [[319 489 363 501] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=A022493) pdfm Black 2 w(.\))p 800 27035 52000 45 v 800 30086 a(Receiv)-36 b(ed)430 b(F)-108 b(ebruary)428 b(17)i(2003;)i(revised)e(v)-36 b(ersion)429 b(receiv)-36 b(ed)430 b(Octob)36 b(er)428 b(27)i(2003.)578 b(Published)429 b(in)g Fj(Journal)800 31691 y(of)465 b(Inte)-66 b(ger)462 b(Se)-66 b(quenc)g(es)p Fl(,)432 b(Decem)-36 b(b)36 b(er)434 b(12)g(2003.)p 800 33322 V 800 35573 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 397 338 409] [1 1 1 [3 3]] [0 0 1]] (http://www.math.uwaterloo.ca/JIS/) pdfm Black(.)p Black 26150 74617 a(10)p Black eop %%Trailer end end