Combinatorial Methods

ISBN-13: 9780387900278 / Angielski / Miękka / 1971 / 194 str.

Jerome K. Percus

Opis

It is not a large overstatement to claim that mathematics has traditionally arisen from attempts to understand quite concrete events in the physical world. The accelerated sophistication of the mathematical community has perhaps obscured this fact, especially during the present century, with the abstract becoming the hallmark of much of respectable mathematics. As a result of the inaccessibility of such work, practicing scientists have often been compelled to fashion their own mathematical tools, blissfully unaware of their prior existence in far too elegant and far too general form. But the mathematical sophistication of scientists has grown rapidly too, as has the scientific sophistication of many mathematicians, and the real worl- suitably defined - is once more serving its traditional role. One of the fields most enriched by this infusion has been that of combinatorics. This book has been written in a way as a tribute to those natural scientists whose breadth of vision has inparted a new vitality to a dormant giant. The present text arose out of a course in Combinatorial Methods given by the writer at the Courant Institute during 1967-68. Its structure has been determined by an attempt to reach an informed but heterogeneous group of students in mathematics, physics, and chemistry. Its lucidity has been enhanced immeasurably by the need to satisfy a very resolute critic, Professor Ora E. Percus, who is responsible for the original lecture notes as well as for their major modifications.

Spis treści

I. Counting and Enumeration on a Set.- A. Introduction.- 1. Set Generating Functions.- 2. Numerical Generating Functions.- Examples.- Fibonacci Numbers.- B. Counting with Restrictions — Techniques.- 1. Inclusion - Exclusion Principle.- The Euler Function.- Rencontres, Derangement or Montmort Problem.- The Menage Problem.- 2. Permutations with Restricted Position. The Master Theorem.- Exercises.- Example.- Rencontre Problem.- Menage Problem.- 3. Extension of the Master Theorem.- C. Partitions, Compositions and Decompositions.- 1. Permutation Counting as a Partition Problem.- a) Counting with allowed transitions.- b) Counting with prohibited transitions.- 2. Classification of Partitions.- a) Distribution of unlabeled objects: Compositions.- b) Distribution of unlabeled objects: Partitions.- 3. Ramsey’s Theorem.- Example.- 4. Distribution of Labeled Objects.- a) Distinguishable boxes.- b) Collections of pairs — graph theory.- c) Indistinguishable boxes (and labeled objects).- d) Partially labeled graphs — The Polya Theorem.- Examples.- Proof of Polya’s Theorem.- Examples.- Exercises.- e) Counting unrooted (free) unlabeled graphs.- Dissimilarity Theorem.- Example.- II. Counting and Enumeration on a Regular Lattice.- A. Random Walk on Lattices.- 1. Regular Cubic Lattices.- Examples.- 2. General Lattices.- i) Nearest neighbor random walk on a face centered cubic lattice.- ii) Nearest neighbor random walk on a body centered cubic lattice.- B. One Dimensional Lattices.- 1. The Ballot Problem.- Example.- 2. One Dimensional Lattice Gas.- C. Two Dimensional Lattices.- 1. Counting Figures on a Lattice, General Algebraic Approach.- 2. The Dimer Problem — Transfer Matrix Method.- Exercises.- 3. The Dimer Problem — Pfaffian Method.- Exercises.- 4. The Dimer Problem — First Permanent Method.- 5. The Dimer Problem — Second Permanent Method.- D. Counting Patterns on Two Dimensional Lattices.- 1. The Ice Problem — Introduction.- 2. Square Ice — The Transfer Matrix Method.- 3. Square Ice — Exact Solution.- 4. Other Hydrogen Bonded Models — Dimer Solution.- E. The Ising Model.- 1. Introduction.- 2. Estimates of the Curie Temperature.- 3. Combinatorial Solution of the Ising Model.- 4. Other Combinatorial Solutions.- 5. Spin Correlations.