×éºÏÊýѧÖг£¼ûµÄ¼ÆÊý·½·¨ ÏÂÔØ±¾ÎÄ

ÉòÑôÀí¹¤´óѧѧʿѧλÂÛÎÄ

1 Ð÷ ÂÛ

1.1×éºÏÊýѧµÄÑо¿±³¾°ºÍÒâÒå

ÏÖ´úÊýѧ¿ÉÒÔ·ÖΪÁ½´óÀࣺһÀàÊÇÑо¿Á¬Ðø¶ÔÏóµÄ£¬Èç·ÖÎö¡¢·½³ÌµÈ£¬ÁíÒ»Àà¾ÍÊÇÑо¿ÀëÉ¢¶ÔÏóµÄ×éºÏÊýѧ¡£×éºÏÊýѧ²»½öÔÚ»ù´¡ÊýѧÑо¿ÖоßÓм«ÆäÖØÒªµÄµØÎ»£¬ÔÚÆäËüµÄѧ¿ÆÖÐÒ²ÓÐÖØÒªµÄÓ¦Óã¬Èç¼ÆËã»ú¿ÆÑ§¡¢±àÂëºÍÃÜÂëѧ¡¢ÎïÀí¡¢»¯Ñ§¡¢ÉúÎïµÈѧ¿ÆÖоùÓÐÖØÒªÓ¦Óá£Î¢»ý·ÖºÍ½ü´úÊýѧµÄ·¢Õ¹Îª½ü´úµÄ¹¤Òµ¸ïÃüµì¶¨ÁË»ù´¡¡£¶ø×éºÏÊýѧµÄ·¢Õ¹ÔòÊǵ춨Á˱¾ÊÀ¼ÍµÄ¼ÆËã»ú¸ïÃüµÄ»ù´¡¡£¼ÆËã»úÖ®ËùÒÔ¿ÉÒÔ±»³ÆÎªµçÄÔ£¬¾ÍÊÇÒòΪ¼ÆËã»ú±»È˱àдÁ˳ÌÐò£¬¶ø³ÌÐò¾ÍÊÇËã·¨£¬ÔÚ¾ø´ó¶àÊýÇé¿öÏ£¬¼ÆËã»úµÄËã·¨ÊÇÕë¶ÔÀëÉ¢µÄ¶ÔÏ󣬶ø²»ÊÇÔÚ×÷ÊýÖµ¼ÆËã¡£ÕýÊÇÒòΪÓÐÁË×éºÏËã·¨²ÅʹÈ˸е½£¬¼ÆËã»úºÃÏñÊÇÓÐ˼άµÄ¡£

×éºÏÊýѧ²»½öÔÚÈí¼þ¼¼ÊõÖÐÓÐÖØÒªµÄÓ¦ÓüÛÖµ£¬ÔÚÆóÒµ¹ÜÀí£¬½»Í¨¹æ»®£¬Õ½ÕùÖ¸»Ó£¬½ðÈÚ·ÖÎöµÈÁìÓò¶¼ÓÐÖØÒªµÄÓ¦Óá£ÔÚÃÀ¹úÓÐÒ»¼ÒÓÃ×éºÏÊýѧÃüÃûµÄ¹«Ë¾£¬ËûÃÇÓÃ×éºÏÊýѧµÄ·½·¨À´Ìá¸ßÆóÒµ¹ÜÀíµÄÐ§Òæ£¬Õâ¼Ò¹«Ë¾°ìµÃ·Ç³£³É¹¦¡£´ËÍ⣬ÊÔÑéÉè¼ÆÒ²ÊǾßÓкܴóÓ¦ÓüÛÖµµÄѧ¿Æ£¬ËüµÄÊýѧԭÀí¾ÍÊÇ×éºÏÉè¼Æ¡£ÓÃ×éºÏÉè¼ÆµÄ·½·¨½â¾ö¹¤Òµ½çÖеÄÊÔÑéÉè¼ÆÎÊÌ⣬ÔÚÃÀ¹úÒÑÓÐרÃŵĹ«Ë¾¿ª·¢Õâ·½ÃæµÄÈí¼þ¡£

1.2¹úÄÚÍâÑо¿ÏÖ×´

×éºÏÊýѧÔÚ¹úÍâÔçÒѳÉΪʮ·ÖÖØÒªµÄѧ¿Æ£¬ÉõÖÁ¿ÉÒÔ˵ÊǼÆËã»ú¿ÆÑ§µÄ»ù´¡¡£Ò»Ð©´ó¹«Ë¾£¬ÈçIBM£¬AT&T¶¼ÓÐÈ«ÊÀ½ç×îÇ¿µÄ×éºÏÑо¿ÖÐÐÄ¡£Microsoft µÄBill Gates½üÀ´Ò²ÔÚÌᳫºÍÖ§³Ö¼ÆËã»ú¿ÆÑ§µÄ»ù´¡Ñо¿¡£ÀýÈ磬BellʵÑéÊÒµÄÓйØÏßÐԹ滮Ëã·¨µÄʵÏÖ£¬ÒÔ¼°ÓйؼÆËã»úÍøÂçµÄËã·¨£¬ÓÉÓÚÓÐÃ÷ÏÔµÄÉÌÒµ¼ÛÖµ£¬ÏÔÈ»ÊÇûÓжÔÍ⹫¿ªµÄ¡£ÃÀ¹úÒѾ­ÓÐÒ»ÖÖÇ÷ÊÆ£¬¾ÍÊÇÓëеÄËã·¨ÓйصÄÈí¼þÊÇ¿ÉÒÔÉêÇëרÀûµÄ¡£Èç¹ûÕÕÕâÖÖÇ÷ÊÆ·¢Õ¹£¬ÊÀ½ç¸÷¹ú¶Ô×éºÏÊýѧºÍ¼ÆËã»úËã·¨µÄͶÈëºÍ¾ºÕù±ØÈ»ÈÕÇ÷¼¤ÁÒ¡£ÃÀ¹úÕþ¸®Ò²³ÉÁ¢ÁËÀëÉ¢Êýѧ¼°ÀíÂÛ¼ÆËã»ú¿ÆÑ§ÖÐÐÄDIMACS£¨ÓëPrinceton´óѧ£¬Rutgers´óѧ£¬AT&T ÁªºÏ´´°ìµÄ£¬ÉèÔÚRutgers´óѧ£©£¬¸ÃÖÐÐÄÒÑÊÇ×éºÏÊýѧÀíÂÛ¼ÆËã»ú¿ÆÑ§µÄÖØÒªÑо¿Õ󵨡£ÃÀ¹ú¹ú¼ÒÊýѧ¿ÆÑ§Ñо¿Ëù£¨Mathematical Sciences Research Institute£¬ÓɳÂÊ¡ÉíÏÈÉú´´Á¢£©ÔÚ1997ÄêÑ¡ÔñÁË×éºÏÊýѧ×÷ΪÑо¿×¨Ì⣬×éÖ¯ÁËΪÆÚÒ»ÄêµÄÑо¿»î¶¯¡£ÈÕ±¾µÄNEC¹«Ë¾»¹ÔÚÃÀ¹úµÄÉèÁ¢ÁËÑо¿ÖÐÐÄ£¬ÀíÂÛ¼ÆËã»ú¿ÆÑ§ºÍ×éºÏÊýѧÒÑÊÇËûÃÇÖØÒªµÄÑо¿¿ÎÌ⣬¸ÃÖÐÐÄÖ÷ÈÎR. Tarjan¼´ÊÇ×éºÏÊýѧµÄȨÍþ¡£ÃÀ¹úÖØÒªµÄ¹ú¼Òʵ¼ÊÊÒ£¨Los Alamos¹ú¼ÒʵÑéÊÒ£¬ÒÔÔì³öµÚÒ»¿ÅÔ­×Óµ¯Öø³ÆÓÚÊÀ£©£¬´ÓÂü¹þ¶Ù¼Æ»®ÒÔÀ´Ò»Ö±ÖØÊÓÓ¦ÓÃÊýѧµÄÑо¿£¬

1

ÉòÑôÀí¹¤´óѧѧʿѧλÂÛÎÄ

°üÀ¨×éºÏÊýѧµÄÑо¿¡£²»½öÈç´Ë£¬¸ÃʵÑéÊÒ×î½ü»¹ÔÚ»ý¼«³äʵ×éºÏÊýѧ·½ÃæµÄÑо¿ÊµÁ¦¡£ÃÀ¹úÁíÍâÒ»¸öÖØÒªµÄ¹ú¼ÒʵÑéÊÒSandia¹ú¼ÒʵÑéÊÒÓÐÒ»¸öרÃÅÑо¿×éºÏÊýѧºÍ¼ÆËã»ú¿ÆÑ§µÄ»ú¹¹£¬Ö÷Òª´ÓÊÂ×éºÏ±àÂëÀíÂÛºÍÃÜÂëѧµÄÑо¿£¬ÔÚÃÀ¹úÕþ¸®ÒÔ¼°¹ú¼ÊѧÊõ½ç¶¼¾ßÓкܸߵĵØÎ»¡£

ÓÉÓÚÉúÎïѧÖеÄDNAµÄ½á¹¹ºÍÉúÎïÏÖÏóÓë×éºÏÊýѧÓÐÃÜÇеÄÁªÏµ£¬¸÷¹ú¶ÔÉúÎïÐÅϢѧµÄÑо¿¶¼ºÜÖØÊÓ£¬ÕâÒ²ÊÇ×éºÏÊýѧ¿ÉÒÔ·¢»Ó×÷ÓõÄÒ»¸öÖØÒªÁìÓò¡£ÓÉÓÚDNA¾ÍÊÇ×éºÏÊýѧÖеÄÒ»¸öÐòÁнṹ£¬ÃÀ¹ú¿ÆÑ§ÔºÔºÊ¿£¬½ü´ú×éºÏÊýѧµÄµì»ùÈËRota½ÌÊÚÔ¤ÑÔ£¬ÉúÎïѧÖеÄ×éºÏÎÊÌ⽫³ÉΪ×éºÏÊýѧµÄÒ»¸öÇ°ÑØÁìÓò¡£

´«Í³µÄ¼ÆËã»úËã·¨¿ÉÒÔ·ÖΪÁ½´óÀ࣬һÀàÊÇ×éºÏËã·¨£¬Ò»ÀàÊÇÊýÖµËã·¨£¨°üÀ¨¼ÆËãÊýѧºÍÓë´¦Àí¸÷ÖÖÐÅÏ¢Êý¾ÝÓйصÄÐÅϢѧ£©¡£½üÄêÀ´¼ÆËã»úËã·¨ÓÖ¶àÁËÒ»ÀࣺÄǾÍÊÇ·ûºÅ¼ÆËãËã·¨¡£ÎâÎÄ¿¡ÔºÊ¿¿ª´´µÄ»úÆ÷Ö¤Ã÷·½·¨¾ÍÊôÓÚ·ûºÅ¼ÆË㣬ÒýÆðÁ˹ú¼ÊÉÏµÄ¸ß¶ÈÆÀ¼Û£¬±»³ÆÎªÎâ·½·¨¡£¶ø¹ú¼ÊÉÏ»¹ÓÐרÃŵķûºÅ¼ÆËãÔÓÖ¾¡£·ûºÅËã·¨ºÍÎâ·½·¨¸ú´úÊý×éºÏѧҲÓÐÊ®·ÖÃÜÇеÄÁªÏµ¡£×éºÏÊýѧ£¬ÊýÖµ¼ÆË㣨°üÀ¨¼ÆËãÊýѧ£¬¿ÆÑ§¼ÆË㣬·ÇÏßÐÔ¿ÆÑ§£¬ºÍÓë´¦Àí¸÷ÖÖÐÅÏ¢Êý¾ÝÓйصÄÐÅϢѧ£©ºÍͳ¼ÆÑ§¿ÉÄÜÊÇÓ¦ÓÃ×î¹ãµÄÊýѧ·ÖÖ§£¬¶ø×éºÏÊýѧµÄ¼ÛÖµÉõÖÁ²»ÑÇÓÚͳ¼ÆÑ§ºÍÊýÖµ¼ÆËã¡£ÓÉÓÚÊýѧ»úе»¯½üÄêÀ´µÄ·¢Õ¹ºÍÔÚ¼ÆËã»ú¿ÆÑ§ÖеÄÖØÒªÐÔ£¬°ÑÊýѧ»úе»¯£¬¿ÆÑ§¼ÆËãºÍ×éºÏÊýѧ×éºÏÆðÀ´£¬¾Í¿ÉÒÔ˵ÊÇÖйúÐÅÏ¢²úÒµµÄ»ù´¡¡£×éºÏÊýѧ¼ÒH. WilfºÍD. Zeilberger1998ÒòΪÔÚ×éºÏºãµÈʽµÄ»úе»¯Ö¤Ã÷·½ÃæµÄ³É¹û£¬»ñµÃ1998ÄêÃÀ¹úÊýѧ»áµÄSteele½±¡£

Thomson Science¹«Ë¾´´¿¯µÄÒ»·Ýµç×Ó¿¯Îï¡¶ÀëÉ¢ÊýѧºÍÀíÂÛ¼ÆËã»ú¿ÆÑ§¡·¼´ÊÇÒ»¸öºÜºÃµÄ˵Ã÷¡£ËüµÄÄÚÈÝÉæ¼°ÀëÉ¢ÊýѧºÍ¼ÆËã»ú¿ÆÑ§µÄÖÚ¶à·½Ãæ¡£ÓÉÓÚ¼ÆËã»úÈí¼þµÄ´Ù½øºÍÐèÇó£¬×éºÏÊýѧÒѳÉΪһÃżȹ㲩ÓÖÉî°ÂµÄѧ¿Æ£¬ÐèÒªºÜÉîµÄÊýѧ»ù´¡£¬Öð½¥³ÉΪÁËÊýѧµÄÖ÷Á÷·ÖÖ§¡£

³ýÉÏÊöÒÔÍ⣬ŷÖÞÒ²ÔÚ»ý¼«·¢Õ¹×éºÏÊýѧ£¬Ó¢¹ú¡¢·¨¹ú¡¢µÂ¹ú¡¢ºÉÀ¼¡¢µ¤Â󡢰µØÀû¡¢Èðµä¡¢Òâ´óÀû¡¢Î÷°àÑÀµÈ¹ú¼Ò¶¼½¨Á¢Á˸÷ÖÖÐÎʽµÄ×éºÏÊýѧÑо¿ÖÐÐÄ¡£½ü¼¸Ä꣬ÄÏÃÀ¹ú¼ÒÒ²ÔÚ»ý¼«Íƶ¯×éºÏÊýѧµÄÑо¿¡£°Ä´óÀûÑÇ£¬ÐÂÎ÷À¼Ò²×齨Á˺ÜÇ¿µÄ×éºÏÊýѧÑо¿»ú¹¹¡£ÖµµÃÒ»ÌáµÄÊÇÑÇÖ޵ķ¢´ï¹ú¼ÒҲʮ·ÖÖØÊÓ×éºÏÊýѧµÄÑо¿¡£ÈÕ±¾ÓÐ×éºÏÊýѧÑо¿ÖÐÐÄ£¬²¢ÇÒ´ÓÃÀ¹úÒý½øÈ˲ţ¬²»½öÖ§³ÖÈÕ±¾¹úÄÚµÄÑо¿£¬»¹³ö×ÊÖ§³ÖÃÀ¹úµÄÓйؿÎÌâµÄÑо¿£¬ÕâÑùʹÈÕ±¾µÄ×éºÏÊýѧÕ⼸ÄêµÄ·¢Õ¹¼«ÎªÑ¸ËÙ¡£Ì¨Íå¡¢Ïã¸ÛÁ½µØÒ²´ÓÃÀ¹úÒý½øÈ˲ţ¬´óÁ¦·¢Õ¹×éºÏÊýѧ¡£ÐÂ¼ÓÆÂ£¬º«¹ú£¬ÂíÀ´Î÷ÑÇÒ²ÔÚ»ý¼«Íƶ¯×éºÏÊýѧµÄÑо¿ºÍÈ˲ÅÅàÑø¡£Ì¨ÍåµÄÊýѧÑо¿ÖÐÐÄÒ²ÕýÔÚ¿¼ÂǰÑ×éºÏÊýѧ×÷ÎªÖØµã·½ÏòÀ´·¢Õ¹¡£

2

ÉòÑôÀí¹¤´óѧѧʿѧλÂÛÎÄ

2 CatalanÊý

2.1 Catalan²úÉúµÄÀúÊ·

CatalanÊý:1,1,2,5,14,42,132,¡­ÊÇ×éºÏÊýѧÖÐÓ¦Óù㷺µÄÖØÒª¼ÆÊýº¯Êý,±¾ÎļÇ×÷

Cn¡£±ÈÀûʱÊýѧ¼ÒE.C.Catalan(1814-1894),ÔÚ1838Äê·¢±íµÄһƪÂÛÎÄÖÐÌÖÂÛÁ˶ûºóËù³ÆµÄCatalanÎÊÌâ:n¸ö²»Í¬Òò×Ó¼äÁ¬Ðø×÷³Ë·¨,ÈçºÎÈ·¶¨²»Í¬µÄÇó»ý·½·¨Êý?Ëû»ñµÃCatalanÊýµÄ¼ÆÊý¹«Ê½:

Cn?1?2n???,(n?0). (2.1) ??n?1?n?Ëü±íʾËãÊýÈý½ÇÐΡ°Öд¹Ïß¡±ÉϵÄÊýµÝ´Î³ýÒÔ×ÔÈ»ÊýºóËùµÃµÄÊýÁС£

ÏÖ´ú×éºÏÊý¶ÔCatalanÊýµÄÉîÈëÑо¿,·¢ÏÖÁËÐí¶à¾ßÓÐ×éºÏÒâÒåµÄÓ¦ÓÃʵÀý,ÓÐÈ˹À¼Æ²»ÉÙÓÚ50ÖÖ¡£

ÆäÖÐ,ÌØ±ðÊÇÐí¶àÎ÷·½Êýѧ¼Ò²»Á˽âÖйúÀúÊ·É϶ÔCatalanÊýµÄÑо¿³É¹û,Çå´úÊýѧ¼ÒÃ÷°²Í¼(Ô¼1692?-1763?)ÊÇCatalanÊýµÄÊ×´´Õß,ÏÖÔÚÒÑÖð²½±»¹úÄÚÍâÊýѧ½ç³ÐÈÏ.Ã÷°²Í¼Ö®ºó,»¹Óм¸Î»Çå´úÊýѧ¼Ò¶Ô´ËÒ²ÓÐÑо¿,¾ùÔÚ1838Äê֮ǰ,´ó¶àÏÊΪÈËÖª¡£

¾­µäCatalanÊýµÄ²úÉú Newton¶þÏîʽ¶¨Àí

k?1??1?k(?1)2?z?1??2k?1Ck?1Zk(Z?1)¡£ (2.2) (1?z)?????K?0?k?K?1212?µ±Ö¸Êý??1ʱ,Newton¶þÏîʽ¶¨ÀíÕ¹¿ªÊ½±ØÈ»¿ÉÒÔ±íʾ³ÉCatalanÊý×÷ϵÊýµÄÃÝ

2¼¶Êý¡£µ«ÊÇ,Newton²¢Ã»ÓаÑϵÊýд³ÉCatalanÊýµÄÐÎʽ¡£

Ã÷°²Í¼ÊÇCatalanÊýµÄÊ×´´Õß

×îÔç·¢ÏÖCatalanÊýµÄÊÇÎÒ¹úÇå´úÊýѧ¼ÒÃ÷°²Í¼¡£17ÊÀ¼Í30Äê´úËûÔÚÑо¿ÎÞÇî¼¶ÊýʱµÃµ½¸ÃÊýµÄ3ÖÖËã·¨,²¢¶à´Î½«ËüÓ¦ÓÃÓÚÔËËãÖÐ.ÆäÖÐ,Á½ÖÖËã·¨¹«Ê½ÊÇÏÖ½ñ×éºÏÊýѧÊé¼®¡¢ÂÛÎÄÖж¼Î´ÖªµÄ.ËûµÄÓйسɹûÏêÔØÓÚÒÅÖø¡¶¸îÔ²ÃÜÂʽݷ¨¡·ÖÐ,ÓɺóÈËÕûÀí³ö°æ¡£

CatalanÊýµÄ¾í»ýÐ͵ÝÍÆ¹«Ê½Cn??Cn?kCk,(n?2).Ã÷°²Í¼ÔÚ¼ÆËãÎÞÇî¼¶ÊýʱÊ×

k?1n?1ÏÈ·¢ÏÖÁËÕâÒ»¹æÂÉ,²¢ÔÚ¼ÆËãÖÐÁ½´ÎÔËÓá£

Ã÷°²Í¼Ò»ÏîÖØÒªµÄ¹¤×÷ÊÇ»ñµÃÁËCatalanÊýµÄ×éºÏµÝÍÆ¹«Ê½

3

ÉòÑôÀí¹¤´óѧѧʿѧλÂÛÎÄ

Cn?1?n?k???(?1)??k?1??Cn?k,(n?2)¡£ (2.3) k?0??k³õʼÌõ¼þÊÇC1=1,C2=1¡£´ËʽΪÊÀ½çÊ×´´,Çø±ðÓÚÎ÷·½ÔÚÀúÊ·ÉϺÍÏÖ´úÇóCatalanÊýµÄËùÓз½·¨¡£³ýÁËËûµÄËã·¨Ö®Íâ,Æù½ñûÓÐÏÖ´úµÄÖ¤Ã÷¡£Ê½(2.3)µ±n?5ʱÓÐC2=C1=2,C3=2C2=2,

?3??2??C4??C??1?3??2??C2?5, ?????4??3??C5??C??1?4??2??C3?14, ?????5??4??3????C6??C?C??1?5?2?4??3??C3?42¡£ ??????Ã÷°²Í¼ÔÚÑо¿ÎÞÇî¼¶ÊýÕ¹¿ªÊ½¹ý³ÌÖжà´ÎÓõ½Ê½(2.3),˵Ã÷Cn?1¿É±íʾΪËüǰ±ßÈô¸ÉÏîÓëËãÊýÈý½ÇÐÎÖеÚnÌõбÏßÉÏÈô¸É×éºÏÊý³Ë»ýµÄ´úÊýºÍ¡£

Ã÷°²Í¼½¨Á¢ÁË3¸ö¼¸ºÎÄ£ÐÍ,ͨ¹ý¸´Ôӵļ¸ºÎ¡¢´úÊý¡¢¼¶ÊýÔËËã,´ÓÆäÖÐÁ½¸ö»ñµÃʽ(2.3),Ò»¸ö»ñµÃʽ(2.5),(2.6) ¡£ºóÕßÊÇ´ÓÔ­ÎÄÖо­³éÏ󽍯ðµÄÒ»¸öÆæÌØµÄ¼ÆÊý½á¹¹¡£

ÉèM1?(1),M2?(0,1);ÒÔϵÄËã·¨²½ÖèΪ

M3?(2M1?M2)M2?[2(1)?(0,1)](0,1)?(2,1)(0,1)?(0,0,2,1), M4?[2(M1?M2)?M3]M3?(2,2,2,1)(0,0,2,1)?(0,0,0,4,6,6,4,1),

M5?[2(M1?M2?M3)?M4]M4?(0,0,0,8,20,40,68,94,114,116,94,60,28,8,1)

Mn?1?(2?Mk?Mn)Mn (2.4) MCn??Mk?(1,1,2,5,14,42,132,?,Cn) (2.5)

k?1nk?1n-1ÕâÖÖËã·¨Ï൱ÓÚ½¨Á¢ÁËÒ»ÖÖÉú³Éº¯Êý,Ó¢¹úÊýѧ¼ÒP.J.Larcombe¸ø³öÁËÒ»¸öÏÖ´úÖ¤Ã÷¡£

Ã÷°²Í¼Ó¦ÓÃÖйú´«Í³Êýѧ·½·¨¡ª¸îÔ²Á¬±ÈÀý·¨µÃµ½¶þ±¶½ÇÕýÏÒµÄÎÞÇî¼¶ÊýÕ¹¿ªÊ½:

sin2¦Á?2sin¦Á??Cnsin2n?1?/4n-1 (2.6)

n?1?ËüµÄϵÊýÊÇCatalanÊý¡£Ê½(2.6)ΪÊÀ½çÊýѧʷÉÏÊ×´´,ÆäÕýÈ·ÐÔ¿ÉÓɶþÏîʽ¶¨ÀíµÃµ½Ö¤Ã÷¡£Ëû½ø¶øÑо¿ÁËËı¶½ÇÕýÏÒµÄÎÞÇî¼¶ÊýÕ¹¿ªÊ½,ËüµÄϵÊýͬÑù¿É±íʾΪCatalanÊýµÄ

4