Please use this identifier to cite or link to this item: https://ah.nccu.edu.tw/handle/140.119/32561


Title: 兩個組合數學的主題: Hadamard 矩陣的建構及有關森林的研究
Two Combinatorial Topics: Constructions of Hadamard Matrices and Studies of Forests
Authors: 施耀振
Shih,Yaio-Zhern
Contributors: 陳永秋
李陽明

施耀振
Shih,Yaio-Zhern
Keywords: Kronecker乘積
Sylvester-Hadamard矩陣
J_m-Hadamard矩陣
正交對
Weighing矩陣
最小指數
平面森林
Catalan數
Motzkin數
Riordan數
Narayana數
Dyck路徑
Motzkin路徑
Chung-Feller定理
優美標法
拉丁方陣
J_m-classes
n-Caterpillars
Date: 2006
Issue Date: 2009-09-17 13:45:12 (UTC+8)
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的優美標法。
Reference: [1] S.S. Agayan, Hadamard matrices and their applications, Lecture notes in mathematics, Vol. 1168, Springer-Verlag, Berlin, 1985.
[2] R.E.L. Aldred and B.D. McKay, Graceful and harmonious labellings of trees, Bull. Inst. Combin. Appl. 23 (1998), 69-72.
[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.
[4] M.D. Atkinson and J.R. Sack, Generating binary trees at random, Inform. Process. Lett. 41 (1) (1992), 21-23.
[5] J.C. Bermond and D. Sotteau, Graph decompositions and G-design, Proc. 5th British Combinatorics Conference, 1975, Congressus Numerantium XV (1976),53-72.
[6] J.C. Bermond, Graceful graphs, radio antennae and
French windmills, Graph Theory and Combinatorics, Pitman, London (1979), 18-37.
[7] F.R. Bernhart, Catalan, Motzkin, Riordan numbers, Discrete Math. 204 (1999), 73-112.
[8] V. Bhat-Nayak and U. Deshmukh, New families of graceful banana trees,
Proc. Indian Acad. Sci. Math. Sci. 106 (1996), 201-216.
[9] C.P. Bonnington and J. Siran, Bipartite labelling of trees with maximum degree three, J. Graph Theory 31 (1999), 7-15.
[10] L. Brankovic, A. Rosa, and J. Siran, Labelling of trees with maximum degree three and improved bound, preprint.
[11] H.J. Broersma and C. Hoede, Another equivalent of the graceful tree
conjecture, Ars Combinatoria 51 (1999), 183-192.
[12] M. Burzio and G. Ferrarese, The subdivision graph of a graceful tree is a graceful tree, Discrete Math. 181 (1998), 275-281.
[13] A. Caley, A theorem on trees, Quart. J. Pure Appl. Math. 23 (1889), 376-378.
[The Collected Mathematical Papers of Arthur Caley, Vol. \textrm{XIII}
(Cambrige University Press, 1897), 26-28.]
[14] D. Callan, A combinatorial derivation of the number of labelled forests, J. Integer
Sequences Vol. 6 (2003), Article 03.4.7
[15] W.-C. Chen, H.-I. Lu, and Y.-N. Yeh, Operations of interlaced trees and graceful
trees, Southeast Asian Bulletin of Math. 21 (1997), 337-348.
[16] Y.-M. Chen and Y.-Z. Shih, On enumeration of plane forests, preprint.
[17] Y.-M. Chen, The Chung-Feller Theorem revisited, submitted.
[18] Y.-M. Chen and Y.-Z. Shih, 2-Caterpillars are graceful, submitted.
[19] K. L. Chung and W. Feller, On fluctuations in coin-tossing, Proc. Nat. Acad. Sci.
USA 35 (1949), 605-608.
[20] R. Craigen, Constructing Hadamard matrices with orthogonal pairs, Ars Combinatoria 33 (1992), 57-64.
[21] R. Craigen, J. Seberry and Xian-Mo Zhang, Product of four Hadamard matrices, J. Combin. Theory Series A 59 (1992), 318-320.
[22] W. de Launey, A product for twelve Hadamard matrices, Australasian J. of Combin. 7 (1993), 123-127.
[23] N. Dershowitz and S. Zaks, Enumerations of ordered trees, Discrete Math. 31 (1980), 9-28.
[24] N. Dershowitz and S. Zaks, The cycle lemma and some applications, European J. Combinatorics 11 (1990), 35-40.
[25] E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999), 167-202.
[26] J.H. Dinitz and D.R. Stinson, Contemporary Design Theory: A Collection of Surveys, John Wiley and Sons, Inc., 1992.
[27] R. Donaghey and L.W. Shapiro, Motzkin numbers, J. Combin. Theory Series A 23 (1977), 291-301.
[28] T. Doslic, Morgan trees and Dyck paths, Croatica Chemica Acta CCACAA 75
(4) (2002), 881-889.
[29] S.-P. Eu, On the Quadratic Algebric Generating Functions
and Combinatorial Structrues , Ph. D. thesis, Department of Mathematics, National Taiwan Normal University, 2003.
[30] S.-P. Eu, T.-S. Fu, and Y.-N. Yeh, Refined Chung-Feller Theorems
for lattice paths, J. Combin. Theory Series A 112 (2005), 143-162.
[31] S.-P. Eu, S.-C. Liu and Y.-N. Yeh, Taylor expansions for Catalan and Motzkin
numbers, Advances in Applied Math. 29 (2002), 345-357.
[32] S.-P. Eu, S.-C. Liu, and Y.-N. Yeh, Dyck paths with
peaks avoiding or restricted to a given set, Studies in Applied Math. 111 (2003), 453-465.
[33] S.-P. Eu, S.-C. Liu, and Y.-N. Yeh, Odd or even on plane trees,
Discrete Math. 281 (2004), 189-196.
[34] J.A. Gallian, A dynamic survey of graph labelling, Electronic J. Combinatorics 5 (2005), #DS6.
[35] I. Gessel, Counting forests by descents and leaves, Electronic J. Combinatorics 3 (2) (1996), #R8.
[36] S.W. Golomb, How to number a graph, in Graph Theory and Computing, R. C. Read,
ed., Academic Press, New York (1972), 23-37.
[37] J. Hadamard, Resolution d'une question relative aux determinants,
Bull. des Sci. Math. 17 (1893), 240-246.
[38] S.M. Hegde and S. Shetty, On graceful trees, Applied Mathematics
E-Notes 2 (2002), 192-197.
[39] P. Hrnciar and A. Haviar, All trees of diameter five are graceful, Discrete Math. 233 (2001), 133-150.
[40] C. Huang, A. Kotzig and A. Rosa, Further results on tree labellings, {\it Utilitas
Math. 21c (1982), 31-48.
[41] H. Izbicki, Uber Unterbaume eines Baumes, Monatshefte f. Math. 74
(1970), 56-62.
[42] K.M. Koh, D.G. Rogers, and T. Tan, On graceful
trees, Nanta Math. 10 (1977), 27-31.
[43] K.M. Koh, D.G. Rogers, and T. Tan, A graceful
arboretum: A survey of graceful trees, in Proceedings of Franco-Southeast
Asian Conference, Singapore, May 1979, 2 278-287.
[44] J. Labelle and Y.-N. Yeh, Dyck paths of knight moves,
Discrete Appl. Math. 24 (1989), 213-221.
[45] J. Labelle and Y.-N. Yeh, Generalized Dyck paths, Discrete Math.
82 (1990), 1-6.
[46] O. Marrero, Une caracterisation des matrices de Hadamard,
Expositiones Mathematicae 17 (1999), 283-288.
[47] D. Mishra and P. Panigrahi, Graceful lobsters obtained by partitioning and component moving of branches
of diameter four trees, Computers and Mathematics with Applications 50
(2005), 367-380.
[48] D. Morgan, Gracefully labelled trees from Skolem sequences, Congressus
Numerantium 142 (2000), 41-48.
[49] D. Morgan, All lobsters with perfect matchings are graceful, Electronic Notes in Discrete Math. 11 (2002), 503-508.
[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.
[51] T.V. Narayana, Cyclic permutation of lattice paths and the Chung-Feller Theorem, Skandinavisk Aktuarietidskrift (1967), 23-30.
[52] T.V. Narayana, Lattice path combinatorics with statistical applications, Mathematical Expositions No. 23, University of Toronto Press, Toronto, 1979.
[53] H.K. Ng, Gracefulness of a class of lobsters, Notices AMS 7 (1986), 825-05-294.
[54] A.M. Pastel and H. Raynaud, Numerotation gracieuse des oliviers, Colloq.
Grenoble, Publications Universite de Grenoble (1978), 218-223.
[55] G. Ringel, Problem 25, in Theory of Graphs and its Applications, Proceedings of Symposium in Smolenice 1963}, Prague (1964), 162.
[56] J. Riordan, Forests of labelled trees, J. Graph Theory 5 (1968), 90-103.
[57] J. Riordan, A note on Catalan parentheses, Amer. Math. Monthly 80
(1973), 904-906.
[58] J. Riordan, Forests of label-increasing trees, J. Graph Theory 3
(1979), 127-133.
[59] F.S. Roberts, Applied Combinatorics, Prentice-Hall, Inc., Englewood Cliffs, New
Jersey 07632, 1984.
[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),
349-355.
[61] A. Rosa, Labelling snakes, Ars Combinatoria 3 (1977), 67-74.
[62] A. Rosa and J. Siran, Bipartite labellings of trees and the gracesize,
J. Graph Theory 19 (1995), 201-215.
[63] S. Seo, A pairing of the vertices of ordered trees, Discrete Math., 241 (2001), 471-477.
[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.
[65] L.W. Shapiro, Problem 10753, Amer. Math. Monthly 106 (1999), 777.
[66] L.W. Shapiro, The higher you go, the older it gets, Congressus Numerantium
138 (1999), 93-96.
[67] L.W. Shapiro, The higher you go, the older it gets, Congressus Numerantium
138 (1999), 93-96.
[68] L.W. Shapiro, Some open questions about random walks
, involutions, limiting distributions, and generating functions, Advances
in Applied Math. 27 (2001), 585-596.
[69] Y.-Z. Shih and E.-T. Tan, On Jm-Hadamard matrices, Expositiones Mathematicae
23 (2005), 81-88.
[70] Y.-Z. Shih and E.-T. Tan, On Marrero's Jm-Hadamard matrices, to appear in Taiwanese J. Math..
[71] Y.-Z. Shih and E.-T. Tan, On Craigen-de Launey's constructions of Hadamard matrices, preprint.
[72] N.J. Sloane, A Library of Hadamard Matrices, \\http://www.research.att.com/~njas/hadamard/.
[73] R.P. Stanley, Enumerative Combinatorics Volume 1, Cambridge University Press,
1986.
[74] R.P. Stanley, Enumerative Combinatorics Volume 2, Cambridge University Press,
1999.
[75] D. Stanton and D. White, Constructive
Combinatorics, Springer-Veerlag New York Inc. 1986.
[76] R. Stanton and C. Zarnke, Labelling of balanced trees, Proc. 4th Southeast Conference of Comb., Graph Theory, Computing (1973), 479-495.
[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. 34
(1867), 461-475.
[78] . Takacs, Counting forests, Discrete Math. 84 (1990), 323-326.
[79] J. Touchard, Sur certaines equations fonctionnelles, Proc. Int. Math.
Congress, Toronto (1924), Vol. 1, p.465, (1928).
[80] F. van Bussel, Relaxed graceful labellings of trees, Electronic J.
Combinatorics 9 (2002), #R4.
[81] J.H. van Lint and R.M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.
[82] J.-G. Wang, D.J. Jin, X.-G. Lu and D. Zhang, The gracefulness of a class
of lobster trees, Mathematical Computer Modelling 20 (1994), 105-110.
[83] W. Woan, Uniform partitions of lattice paths and Chung-Feller
generalizations, Amer. Math. Monthly 108 (2001), 556-559.
[84] D.B. West, Introduction to Graph Theory, Prentice-Hall, Inc. 1996.
[85] W.-C. Wu, Graceful labellings of 4-caterpillars, Master Thesis,
Department of Mathematical Sciences, National Chengchi University, 2006.
[86] S.L. Zhao, All trees of diameter four are graceful, Annals New York Academy of Sciences (1986), 700-706.
Description: 博士
國立政治大學
應用數學研究所
89751501
95
Source URI: http://thesis.lib.nccu.edu.tw/record/#G0089751501
Data Type: thesis
Appears in Collections:[應用數學系] 學位論文

Files in This Item:

File Description SizeFormat
75150101.pdf190KbAdobe PDF673View/Open
75150102.pdf338KbAdobe PDF765View/Open
75150103.pdf184KbAdobe PDF746View/Open
75150104.pdf84KbAdobe PDF1043View/Open
75150105.pdf148KbAdobe PDF714View/Open
75150106.pdf252KbAdobe PDF878View/Open
75150107.pdf430KbAdobe PDF1379View/Open
75150108.pdf438KbAdobe PDF852View/Open
75150109.pdf534KbAdobe PDF872View/Open
75150110.pdf672KbAdobe PDF845View/Open
75150111.pdf693KbAdobe PDF874View/Open
75150112.pdf1442KbAdobe PDF939View/Open
75150113.pdf80KbAdobe PDF740View/Open
75150114.pdf303KbAdobe PDF910View/Open


All items in 學術集成 are protected by copyright, with all rights reserved.


社群 sharing