Enumeration ~ and Design — - Edlfedby David M. Jackson Scott A.Vanstone ‘ ENUMERATION AND DESIGN Academic Press Rapid ManuscriptReproduction ENUMERATION AND DESIGN Edited by DAVID M. JACKSON SCOTT A. VANSTONE Department of Combinatorics and Optimization UniversityofWaterloo Waterloo, Ontario, Canada 1984 ACADEMIC PRESS (HarcourtBraceJovanovich, Publishers) TORONIO ORLANDO SANDIEGO SANFRANCISCO NEWYORK LONDON MONTREAL SYDNEY TOKYO 8A0PAULO COPYRIGHT« I984.avACADEMICPREssCANADA ALLRIGHTSRESERVED. NoPAR'I'orTHISPUBLICATIONMAvREREPRODUCED0R TRANSMITTEDINANFORM0RavANvMEANs.ELECTRONIC ORMECHANICAL.INCLUDINGPHO‘IOCOPV.RECORDING.ORANv INIORMATIONSTORAGEANDRETRIEVALsvs'rEM.WITHOUT PERMISSIONINWRITINGFROMTHEWINNER. ACADEMICPRESSCANADA 55BarberGreeneRoad.DonMills.Ontario MIC2A1 UnitedSumsEdiu‘anpublishedby ACADEMIC PRESS. INC. Orlando.Florida32887 UnitedKingdomEllilionpublishedh_I ACADEMICPRESS INC (LONDON)LTD. 24I28OvalRoad.LondonNWI 7DX CanadianCataloguinginPublicationData Mainentryundertitle: Enumerationanddesign PapersfromaportionoftheSilverJubilee ConferenceonCombinatorics.UniversityofWaterloo. June l4-July2. I982. ISBN0-l2-379I20-0 .Combinatorialdesignsandconfigurations-— b . 2 c nrial mm.9. LI Congresses. 3. Combinatorialanalysis—Congresses. I. Jackson.D. M.(DavidMartin) I942- II. Vanstone.S.A.(ScottAlexander). I947- III. SilverJubileeConferenceonCombinatorics (I982: UniversityofWaterloo) QAI643.E58 I984 SII162 C84099285-8 LibraryofCongressCataloginginPublicationData Mainentryundertitle: Enumerationanddesign. BasedinpartontheproceedingsoftheSilver JubileeConferenceonCombinatorics heldatthe UniversityofWaterloo June I4toJuly2 I982. I C L. mi miunpr 2. Combinatorialdesignsandconfigurations—Congre§ses. I. Jackson David M. II. Vanstone ScottA. III. Silver JubileeConferenceonCombinatorics(I982:Univelsityof Waterloo) IV. UniversityofWaterloo QAI64.8.E58 I984 SH'.6 8448435 ISBN0-l2-379I20-0(alk.paper) PKINIFI)INCANADA 8485868798765432I CONTENTS Contributors vIl Preface Acknowledgments An Introduction toCombinatorialCommutativeAlgebra RichardP. Stanley OntheTheory oft-Designs RichardM. Wilson Useand ExtensionofFrobenius‘ Representationof Partitions SI George E. Andrews Orthogonal PolynomialsOld and New. and SomeCombinatorial Connections 67 RichardAskey Strongly RegularGraphsand PartialGeometries 85 A. E. BrouwerandJ. H. Van Lint Combinatorics ofLaguerre Polynomials l23 Dominique Foamand VolkerStrehl BaerSubplanes in a Finite Projective Planeand Kirkman Cubes I4] Ryoh Fuji-Ham Combinatorial ProofsofCongruences 157 Ira M. Gessel On Variance-Balanced Block Designswithb= v SanpeiKageyama A Characterization ofPartialGeometric Lattices of Rank4 2l5 Renu LaskarandAlan P. Sprague vi CONTENTS Asymptotics for0- l Matriceswith Prescribed Line Sums 225 Brendan D. McKay Balanced lncomplete Block Designswith k =6 and A = l 239 W. H. Mills On the ExistenceofSome Extremal Self-DualCodes 245 Vera Pless ExistenceofLongCycles in RandomCubicGraphs 25l R. W. Robinson andN. C. Wormald Group Divisible DifferenceSets 27l Di/en K. Ray-Chaudhuri lndeterminates and Set lntersections 285 H. J. Ryser TheNumberofColorCyclic Factorizations ofaGraph 297 AllenJ. Srhwenk ThreeNew Orthogonal Diagonal LatinSquares 313 W. D. Wallis CONTRIBUTORS Numbersinparenthesesindicatethepagesonwhichtheauthors’contributions begin. George E. Andrews (5|), Department ofMathematics. PennsylvaniaState Uni- versity, University Park, Pennsylvania [6802. U.S.A. Richard Askey (67), Department of Mathematics, University of Wisconsin. Madison. Wisconsin53706, U.S.A. A. E. Brouwer(85), MathemattscheCentrum, DepartmentofPureMathematics, 2e Boerhaavestraat, 49 Amsterdam, The Netherlands Dominique Foata (123), De’partement de Mathe'matiques, Universite’de Stras- bourg. 7rue René-Descartes, F67084Strasbourg, France Ryoh Fuji-Hara(l4l). InstituteofSocio-Economic Planning, The University of Tsukuba, Sakura. Ibaraki305, Japan Ira M. Gessel (l57). Department of Mathematics. Massachusetts Institute of Technology. Cambridge, Massachusetts02139, U.S.A. Sanpei Kageyama (I99), Department of Mathematics. Faculty of Education, Hiroshima University, [-33 Shinonome3-chome, Minami-ku. Hiroshima734. Japan Renu Laskar(2l5). DepartmentofMathematics, Clemson University. Clemson. South Carolina2965], USA. J. H.vanLint(85). TechnicalUniversityQfEindhoven. P.0. Box5]3, Eindhoven. The Netherlands Brendan D. McKay (225). Computer Science Department. Australian National University. P.0. Box4. Canberra, ACT. 2600, Australia W. H. Mills(239). Institute/0r DefenceAnalysis, Thane! Road. Princeton, New Jersey08540, USA. Vera Pless(245), DepartmentofMathematics, Box4348. UniversityofIllinoisat Chicago Circle. Chicago, Illinois60680, USA. Dijen K. Ray-Chaudhuri (27]), Department ofMathematics. The Ohio State University, Columbus, Ohio432/0, U.S.A. vii viii CONTRIBUTORS R. W. Robinson(25]), DepartmentofMathematics,SouthernIllinoisUniversity. Carbondale, Illinois6290]. U.S.A. H.J.Ryser(285),DepartmentofMathematics.CaliforniaInstituteofTechnology, Pasadena. California9l125. U.S.A. Allen J. Schwenk (297). United States Naval Academy, Annapolis, Maryland 21402. USA. Alan P. Sprague (2l5), Department of Computer Science, The Ohio State University, Columbus, Ohio432l0, U.S.A. Richard P. Stanley (3), Department ofMathematics. Massachusetts Instituteof Technology. Cambridge, Massachusetts02/39, U.S.A. VolkerStrehl(123), Informatik I, Universiliit Erlangen-Nurnberg. Martenstrasse 3, 0-8520Erlangen. FederalRepublicofGermany W.D.Wallis(3l3),DepartmentofMathematics,StatisticsandComputerScience, The UniversityofNewcastle. NewSouth Wales2308. Australia Richard M. Wilson (l9) Department ofMathematics. California Institute of Technology, Pasadena, California9]I25 U.S.A. N. C. Wormald (25]), Department of Mathematics, Statistics and Computer Science, The UniversityofNewcastle. NewSouth Wales2308. Australia