Please use this identifier to cite or link to this item: https://ah.lib.nccu.edu.tw/handle/140.119/32561
DC FieldValueLanguage
dc.contributor.advisor陳永秋<br>李陽明zh_TW
dc.contributor.author施耀振zh_TW
dc.contributor.authorShih,Yaio-Zhernen_US
dc.creator施耀振zh_TW
dc.creatorShih,Yaio-Zhernen_US
dc.date2006en_US
dc.date.accessioned2009-09-17T05:45:12Z-
dc.date.available2009-09-17T05:45:12Z-
dc.date.issued2009-09-17T05:45:12Z-
dc.identifierG0089751501en_US
dc.identifier.urihttps://nccur.lib.nccu.edu.tw/handle/140.119/32561-
dc.description博士zh_TW
dc.description國立政治大學zh_TW
dc.description應用數學研究所zh_TW
dc.description89751501zh_TW
dc.description95zh_TW
dc.description.abstract在這篇論文,我們主要探討兩個獨立的組合數學主題:一個是Hadamard矩陣的建構,一個是有關森林的研究。在第一個主題,所得者又分為二,其一,我們從一個已知的Hadamard矩陣,利用Sylvester的方法去建構名為Jm-Hadamard矩陣。從這個矩陣裡,藉由在Sm上適當的排列,可以獲致其他2mm!-1個Hadamard矩陣。另外,我們引進Jm-class的概念, 將之寫成CJm,並探討當n整除n`時,CJn`是否包含於CJn。關於這個問題,我們得到最初的結論是CJ8 CJ4 CJ2。其二,在已知的t個階數分別是4m1,4m2,…,4mt的Hadamard矩陣,希望獲得一個階數是2km1m2… mt的Hadamard矩陣,使得k值愈小愈好。我們可以找到最小指數的上界,這個數稍好於Craigen及de Launey所得到的值。在第二個主題裡,我們致力於三個目標,首先,我們將平面樹上的一些結果,推廣到平面森林上,諸如Shapiro的結果,葉子的偶數、奇數問題,Catalan數與類似數之間的恒等式。其二,我們用了一個很簡潔的方法去證明Chung-Feller定理,也獲致相關的結果及應用。最後,我們以研究數種n-caterpillars的優美標法,作為本文的結束,最特別的是我們可藉用拉丁方陣去建構2n-caterpillars的優美標法。zh_TW
dc.description.tableofcontentsAbstract\n中文摘要\nIntroduction\nI Constructions of Hadamard Matrices\n1 On Jm-Hadamard Matrices\n 1.1 Jm-Hadamard Matrices\n 1.2 Counterexamples\n2 Further Results on Jm-Hadamard Matrices\n 2.1 Some Properties of Jm-Hadamard Matrices\n 2.2 Hadamard Matrices in Jm-classes\n3 On Craigen-de Launey’s Constructions of Hadamard Matrices\n 3.1 Generalizations of Craigen’s Theorem and Craigen-Seberry-Zhang’s Theorem\n 3.2 Minimum Exponent of Hadamard Matrices Resulting from t Hadamard Matrices\nII Studies of Forests \n4 On Enumeration of Plane Forests\n4.1 A Catalan Identity \n4.2 Some Results of Leaves\n4.3 Generalizations of Motzkin-Catalan Identity\n4.4 Some Riordan Families\n5 The Chung-Feller Theorem Revisited\n5.1 A Simple Proof of Chumg-Feller Theorem\n5.2 Bi-color Plane Forests\n5.3 Semiatandard Tableaux and Noncrossing Semiordered Pairs\n5.4 Motzkin Paths with Flaws and a Labelled Minimum\n6. Graceful Labellings of Some n-Caterpillars\n6.1 Graceful Labellings of 2-Caterpillars\n6.2 Graceful Labellings of (r,m,n)-Caterpillars\n6.3 n-Partition with Parameter k\n6.4 Latin Squares and Graceful Labellings of 2n-Caterpillars\nConcluding Remarks\nBibliograghyzh_TW
dc.format.extent194858 bytes-
dc.format.extent346804 bytes-
dc.format.extent188983 bytes-
dc.format.extent86347 bytes-
dc.format.extent152254 bytes-
dc.format.extent259009 bytes-
dc.format.extent440568 bytes-
dc.format.extent448542 bytes-
dc.format.extent547616 bytes-
dc.format.extent688867 bytes-
dc.format.extent710593 bytes-
dc.format.extent1476861 bytes-
dc.format.extent82700 bytes-
dc.format.extent311275 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.language.isoen_US-
dc.source.urihttp://thesis.lib.nccu.edu.tw/record/#G0089751501en_US
dc.subjectKronecker乘積zh_TW
dc.subjectSylvester-Hadamard矩陣zh_TW
dc.subjectJ_m-Hadamard矩陣zh_TW
dc.subject正交對zh_TW
dc.subjectWeighing矩陣zh_TW
dc.subject最小指數zh_TW
dc.subject平面森林zh_TW
dc.subjectCatalan數zh_TW
dc.subjectMotzkin數zh_TW
dc.subjectRiordan數zh_TW
dc.subjectNarayana數zh_TW
dc.subjectDyck路徑zh_TW
dc.subjectMotzkin路徑zh_TW
dc.subjectChung-Feller定理zh_TW
dc.subject優美標法zh_TW
dc.subject拉丁方陣zh_TW
dc.subjectJ_m-classesen_US
dc.subjectn-Caterpillarsen_US
dc.title兩個組合數學的主題: Hadamard 矩陣的建構及有關森林的研究zh_TW
dc.titleTwo Combinatorial Topics: Constructions of Hadamard Matrices and Studies of Forestsen_US
dc.typethesisen
dc.relation.reference[1] S.S. Agayan, Hadamard matrices and their applications, Lecture notes in mathematics, Vol. 1168, Springer-Verlag, Berlin, 1985.zh_TW
dc.relation.reference[2] R.E.L. Aldred and B.D. McKay, Graceful and harmonious labellings of trees, Bull. Inst. Combin. Appl. 23 (1998), 69-72.zh_TW
dc.relation.reference[3] R.E.L. Aldred, J. Siran and M. Siran, A note on the number of graceful labellings of paths, Discrete Math. 261 (2003), 27-30.zh_TW
dc.relation.reference[4] M.D. Atkinson and J.R. Sack, Generating binary trees at random, Inform. Process. Lett. 41 (1) (1992), 21-23.zh_TW
dc.relation.reference[5] J.C. Bermond and D. Sotteau, Graph decompositions and G-design, Proc. 5th British Combinatorics Conference, 1975, Congressus Numerantium XV (1976),53-72.zh_TW
dc.relation.reference[6] J.C. Bermond, Graceful graphs, radio antennae andzh_TW
dc.relation.referenceFrench windmills, Graph Theory and Combinatorics, Pitman, London (1979), 18-37.zh_TW
dc.relation.reference[7] F.R. Bernhart, Catalan, Motzkin, Riordan numbers, Discrete Math. 204 (1999), 73-112.zh_TW
dc.relation.reference[8] V. Bhat-Nayak and U. Deshmukh, New families of graceful banana trees,zh_TW
dc.relation.referenceProc. Indian Acad. Sci. Math. Sci. 106 (1996), 201-216.zh_TW
dc.relation.reference[9] C.P. Bonnington and J. Siran, Bipartite labelling of trees with maximum degree three, J. Graph Theory 31 (1999), 7-15.zh_TW
dc.relation.reference[10] L. Brankovic, A. Rosa, and J. Siran, Labelling of trees with maximum degree three and improved bound, preprint.zh_TW
dc.relation.reference[11] H.J. Broersma and C. Hoede, Another equivalent of the graceful treezh_TW
dc.relation.referenceconjecture, Ars Combinatoria 51 (1999), 183-192.zh_TW
dc.relation.reference[12] M. Burzio and G. Ferrarese, The subdivision graph of a graceful tree is a graceful tree, Discrete Math. 181 (1998), 275-281.zh_TW
dc.relation.reference[13] A. Caley, A theorem on trees, Quart. J. Pure Appl. Math. 23 (1889), 376-378.zh_TW
dc.relation.reference[The Collected Mathematical Papers of Arthur Caley, Vol. \\textrm{XIII}zh_TW
dc.relation.reference(Cambrige University Press, 1897), 26-28.]zh_TW
dc.relation.reference[14] D. Callan, A combinatorial derivation of the number of labelled forests, J. Integerzh_TW
dc.relation.referenceSequences Vol. 6 (2003), Article 03.4.7zh_TW
dc.relation.reference[15] W.-C. Chen, H.-I. Lu, and Y.-N. Yeh, Operations of interlaced trees and gracefulzh_TW
dc.relation.referencetrees, Southeast Asian Bulletin of Math. 21 (1997), 337-348.zh_TW
dc.relation.reference[16] Y.-M. Chen and Y.-Z. Shih, On enumeration of plane forests, preprint.zh_TW
dc.relation.reference[17] Y.-M. Chen, The Chung-Feller Theorem revisited, submitted.zh_TW
dc.relation.reference[18] Y.-M. Chen and Y.-Z. Shih, 2-Caterpillars are graceful, submitted.zh_TW
dc.relation.reference[19] K. L. Chung and W. Feller, On fluctuations in coin-tossing, Proc. Nat. Acad. Sci.zh_TW
dc.relation.referenceUSA 35 (1949), 605-608.zh_TW
dc.relation.reference[20] R. Craigen, Constructing Hadamard matrices with orthogonal pairs, Ars Combinatoria 33 (1992), 57-64.zh_TW
dc.relation.reference[21] R. Craigen, J. Seberry and Xian-Mo Zhang, Product of four Hadamard matrices, J. Combin. Theory Series A 59 (1992), 318-320.zh_TW
dc.relation.reference[22] W. de Launey, A product for twelve Hadamard matrices, Australasian J. of Combin. 7 (1993), 123-127.zh_TW
dc.relation.reference[23] N. Dershowitz and S. Zaks, Enumerations of ordered trees, Discrete Math. 31 (1980), 9-28.zh_TW
dc.relation.reference[24] N. Dershowitz and S. Zaks, The cycle lemma and some applications, European J. Combinatorics 11 (1990), 35-40.zh_TW
dc.relation.reference[25] E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999), 167-202.zh_TW
dc.relation.reference[26] J.H. Dinitz and D.R. Stinson, Contemporary Design Theory: A Collection of Surveys, John Wiley and Sons, Inc., 1992.zh_TW
dc.relation.reference[27] R. Donaghey and L.W. Shapiro, Motzkin numbers, J. Combin. Theory Series A 23 (1977), 291-301.zh_TW
dc.relation.reference[28] T. Doslic, Morgan trees and Dyck paths, Croatica Chemica Acta CCACAA 75zh_TW
dc.relation.reference(4) (2002), 881-889.zh_TW
dc.relation.reference[29] S.-P. Eu, On the Quadratic Algebric Generating Functionszh_TW
dc.relation.referenceand Combinatorial Structrues , Ph. D. thesis, Department of Mathematics, National Taiwan Normal University, 2003.zh_TW
dc.relation.reference[30] S.-P. Eu, T.-S. Fu, and Y.-N. Yeh, Refined Chung-Feller Theoremszh_TW
dc.relation.referencefor lattice paths, J. Combin. Theory Series A 112 (2005), 143-162.zh_TW
dc.relation.reference[31] S.-P. Eu, S.-C. Liu and Y.-N. Yeh, Taylor expansions for Catalan and Motzkinzh_TW
dc.relation.referencenumbers, Advances in Applied Math. 29 (2002), 345-357.zh_TW
dc.relation.reference[32] S.-P. Eu, S.-C. Liu, and Y.-N. Yeh, Dyck paths withzh_TW
dc.relation.referencepeaks avoiding or restricted to a given set, Studies in Applied Math. 111 (2003), 453-465.zh_TW
dc.relation.reference[33] S.-P. Eu, S.-C. Liu, and Y.-N. Yeh, Odd or even on plane trees,zh_TW
dc.relation.referenceDiscrete Math. 281 (2004), 189-196.zh_TW
dc.relation.reference[34] J.A. Gallian, A dynamic survey of graph labelling, Electronic J. Combinatorics 5 (2005), #DS6.zh_TW
dc.relation.reference[35] I. Gessel, Counting forests by descents and leaves, Electronic J. Combinatorics 3 (2) (1996), #R8.zh_TW
dc.relation.reference[36] S.W. Golomb, How to number a graph, in Graph Theory and Computing, R. C. Read,zh_TW
dc.relation.referenceed., Academic Press, New York (1972), 23-37.zh_TW
dc.relation.reference[37] J. Hadamard, Resolution d`une question relative aux determinants,zh_TW
dc.relation.referenceBull. des Sci. Math. 17 (1893), 240-246.zh_TW
dc.relation.reference[38] S.M. Hegde and S. Shetty, On graceful trees, Applied Mathematicszh_TW
dc.relation.referenceE-Notes 2 (2002), 192-197.zh_TW
dc.relation.reference[39] P. Hrnciar and A. Haviar, All trees of diameter five are graceful, Discrete Math. 233 (2001), 133-150.zh_TW
dc.relation.reference[40] C. Huang, A. Kotzig and A. Rosa, Further results on tree labellings, {\\it Utilitaszh_TW
dc.relation.referenceMath. 21c (1982), 31-48.zh_TW
dc.relation.reference[41] H. Izbicki, Uber Unterbaume eines Baumes, Monatshefte f. Math. 74zh_TW
dc.relation.reference(1970), 56-62.zh_TW
dc.relation.reference[42] K.M. Koh, D.G. Rogers, and T. Tan, On gracefulzh_TW
dc.relation.referencetrees, Nanta Math. 10 (1977), 27-31.zh_TW
dc.relation.reference[43] K.M. Koh, D.G. Rogers, and T. Tan, A gracefulzh_TW
dc.relation.referencearboretum: A survey of graceful trees, in Proceedings of Franco-Southeastzh_TW
dc.relation.referenceAsian Conference, Singapore, May 1979, 2 278-287.zh_TW
dc.relation.reference[44] J. Labelle and Y.-N. Yeh, Dyck paths of knight moves,zh_TW
dc.relation.referenceDiscrete Appl. Math. 24 (1989), 213-221.zh_TW
dc.relation.reference[45] J. Labelle and Y.-N. Yeh, Generalized Dyck paths, Discrete Math.zh_TW
dc.relation.reference82 (1990), 1-6.zh_TW
dc.relation.reference[46] O. Marrero, Une caracterisation des matrices de Hadamard,zh_TW
dc.relation.referenceExpositiones Mathematicae 17 (1999), 283-288.zh_TW
dc.relation.reference[47] D. Mishra and P. Panigrahi, Graceful lobsters obtained by partitioning and component moving of brancheszh_TW
dc.relation.referenceof diameter four trees, Computers and Mathematics with Applications 50zh_TW
dc.relation.reference(2005), 367-380.zh_TW
dc.relation.reference[48] D. Morgan, Gracefully labelled trees from Skolem sequences, Congressuszh_TW
dc.relation.referenceNumerantium 142 (2000), 41-48.zh_TW
dc.relation.reference[49] D. Morgan, All lobsters with perfect matchings are graceful, Electronic Notes in Discrete Math. 11 (2002), 503-508.zh_TW
dc.relation.reference[50] D. Morgan and R. Rees, Using Skolem and Hooked-Skolem sequences to generate graceful trees, J. Combin. Math. and Combin. Computing 44 (2003), 47-63.zh_TW
dc.relation.reference[51] T.V. Narayana, Cyclic permutation of lattice paths and the Chung-Feller Theorem, Skandinavisk Aktuarietidskrift (1967), 23-30.zh_TW
dc.relation.reference[52] T.V. Narayana, Lattice path combinatorics with statistical applications, Mathematical Expositions No. 23, University of Toronto Press, Toronto, 1979.zh_TW
dc.relation.reference[53] H.K. Ng, Gracefulness of a class of lobsters, Notices AMS 7 (1986), 825-05-294.zh_TW
dc.relation.reference[54] A.M. Pastel and H. Raynaud, Numerotation gracieuse des oliviers, Colloq.zh_TW
dc.relation.referenceGrenoble, Publications Universite de Grenoble (1978), 218-223.zh_TW
dc.relation.reference[55] G. Ringel, Problem 25, in Theory of Graphs and its Applications, Proceedings of Symposium in Smolenice 1963}, Prague (1964), 162.zh_TW
dc.relation.reference[56] J. Riordan, Forests of labelled trees, J. Graph Theory 5 (1968), 90-103.zh_TW
dc.relation.reference[57] J. Riordan, A note on Catalan parentheses, Amer. Math. Monthly 80zh_TW
dc.relation.reference(1973), 904-906.zh_TW
dc.relation.reference[58] J. Riordan, Forests of label-increasing trees, J. Graph Theory 3zh_TW
dc.relation.reference(1979), 127-133.zh_TW
dc.relation.reference[59] F.S. Roberts, Applied Combinatorics, Prentice-Hall, Inc., Englewood Cliffs, Newzh_TW
dc.relation.referenceJersey 07632, 1984.zh_TW
dc.relation.reference[60] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (International Symposium, Rome, July 1966), Gordon and Breach, N.Y. and Dunod Paris (1967),zh_TW
dc.relation.reference349-355.zh_TW
dc.relation.reference[61] A. Rosa, Labelling snakes, Ars Combinatoria 3 (1977), 67-74.zh_TW
dc.relation.reference[62] A. Rosa and J. Siran, Bipartite labellings of trees and the gracesize,zh_TW
dc.relation.referenceJ. Graph Theory 19 (1995), 201-215.zh_TW
dc.relation.reference[63] S. Seo, A pairing of the vertices of ordered trees, Discrete Math., 241 (2001), 471-477.zh_TW
dc.relation.reference[64] L.W. Shapiro, A short proof of an identity of Touchard`s concerning Catalan numbers, J. Combin. Theory Series A 20 (1976), 375-376.zh_TW
dc.relation.reference[65] L.W. Shapiro, Problem 10753, Amer. Math. Monthly 106 (1999), 777.zh_TW
dc.relation.reference[66] L.W. Shapiro, The higher you go, the older it gets, Congressus Numerantiumzh_TW
dc.relation.reference138 (1999), 93-96.zh_TW
dc.relation.reference[67] L.W. Shapiro, The higher you go, the older it gets, Congressus Numerantiumzh_TW
dc.relation.reference138 (1999), 93-96.zh_TW
dc.relation.reference[68] L.W. Shapiro, Some open questions about random walkszh_TW
dc.relation.reference, involutions, limiting distributions, and generating functions, Advanceszh_TW
dc.relation.referencein Applied Math. 27 (2001), 585-596.zh_TW
dc.relation.reference[69] Y.-Z. Shih and E.-T. Tan, On Jm-Hadamard matrices, Expositiones Mathematicaezh_TW
dc.relation.reference23 (2005), 81-88.zh_TW
dc.relation.reference[70] Y.-Z. Shih and E.-T. Tan, On Marrero`s Jm-Hadamard matrices, to appear in Taiwanese J. Math..zh_TW
dc.relation.reference[71] Y.-Z. Shih and E.-T. Tan, On Craigen-de Launey`s constructions of Hadamard matrices, preprint.zh_TW
dc.relation.reference[72] N.J. Sloane, A Library of Hadamard Matrices, \\\\http://www.research.att.com/~njas/hadamard/.zh_TW
dc.relation.reference[73] R.P. Stanley, Enumerative Combinatorics Volume 1, Cambridge University Press,zh_TW
dc.relation.reference1986.zh_TW
dc.relation.reference[74] R.P. Stanley, Enumerative Combinatorics Volume 2, Cambridge University Press,zh_TW
dc.relation.reference1999.zh_TW
dc.relation.reference[75] D. Stanton and D. White, Constructivezh_TW
dc.relation.referenceCombinatorics, Springer-Veerlag New York Inc. 1986.zh_TW
dc.relation.reference[76] R. Stanton and C. Zarnke, Labelling of balanced trees, Proc. 4th Southeast Conference of Comb., Graph Theory, Computing (1973), 479-495.zh_TW
dc.relation.reference[77] J.J. Sylvester, Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colors, with applications to Newton`s Rule, ornamental tile-work, and the theory of numbers, Phil. Mag. 34zh_TW
dc.relation.reference(1867), 461-475.zh_TW
dc.relation.reference[78] . Takacs, Counting forests, Discrete Math. 84 (1990), 323-326.zh_TW
dc.relation.reference[79] J. Touchard, Sur certaines equations fonctionnelles, Proc. Int. Math.zh_TW
dc.relation.referenceCongress, Toronto (1924), Vol. 1, p.465, (1928).zh_TW
dc.relation.reference[80] F. van Bussel, Relaxed graceful labellings of trees, Electronic J.zh_TW
dc.relation.referenceCombinatorics 9 (2002), #R4.zh_TW
dc.relation.reference[81] J.H. van Lint and R.M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.zh_TW
dc.relation.reference[82] J.-G. Wang, D.J. Jin, X.-G. Lu and D. Zhang, The gracefulness of a classzh_TW
dc.relation.referenceof lobster trees, Mathematical Computer Modelling 20 (1994), 105-110.zh_TW
dc.relation.reference[83] W. Woan, Uniform partitions of lattice paths and Chung-Fellerzh_TW
dc.relation.referencegeneralizations, Amer. Math. Monthly 108 (2001), 556-559.zh_TW
dc.relation.reference[84] D.B. West, Introduction to Graph Theory, Prentice-Hall, Inc. 1996.zh_TW
dc.relation.reference[85] W.-C. Wu, Graceful labellings of 4-caterpillars, Master Thesis,zh_TW
dc.relation.referenceDepartment of Mathematical Sciences, National Chengchi University, 2006.zh_TW
dc.relation.reference[86] S.L. Zhao, All trees of diameter four are graceful, Annals New York Academy of Sciences (1986), 700-706.zh_TW
item.openairecristypehttp://purl.org/coar/resource_type/c_46ec-
item.grantfulltextopen-
item.languageiso639-1en_US-
item.cerifentitytypePublications-
item.fulltextWith Fulltext-
item.openairetypethesis-
Appears in Collections:學位論文
Files in This Item:
File Description SizeFormat
75150101.pdf190.29 kBAdobe PDF2View/Open
75150102.pdf338.68 kBAdobe PDF2View/Open
75150103.pdf184.55 kBAdobe PDF2View/Open
75150104.pdf84.32 kBAdobe PDF2View/Open
75150105.pdf148.69 kBAdobe PDF2View/Open
75150106.pdf252.94 kBAdobe PDF2View/Open
75150107.pdf430.24 kBAdobe PDF2View/Open
75150108.pdf438.03 kBAdobe PDF2View/Open
75150109.pdf534.78 kBAdobe PDF2View/Open
75150110.pdf672.72 kBAdobe PDF2View/Open
75150111.pdf693.94 kBAdobe PDF2View/Open
75150112.pdf1.44 MBAdobe PDF2View/Open
75150113.pdf80.76 kBAdobe PDF2View/Open
75150114.pdf303.98 kBAdobe PDF2View/Open
Show simple item record

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.