Combinatorics E-Book

Theodore G. Faticoni

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 401

Veröffentlichungsjahr: 2014

Beschreibung

Bridges combinatorics and probability and uniquely includes detailed formulas and proofs to promote mathematical thinking

Combinatorics: An Introduction introduces readers to counting combinatorics, offers examples that feature unique approaches and ideas, and presents case-by-case methods for solving problems.

Detailing how combinatorial problems arise in many areas of pure mathematics, most notably in algebra, probability theory, topology, and geometry, this book provides discussion on logic and paradoxes; sets and set notations; power sets and their cardinality; Venn diagrams; the multiplication principal; and permutations, combinations, and problems combining the multiplication principal. Additional features of this enlightening introduction include:

• Worked examples, proofs, and exercises in every chapter
• Detailed explanations of formulas to promote fundamental understanding
• Promotion of mathematical thinking by examining presented ideas and seeing proofs before reaching conclusions
• Elementary applications that do not advance beyond the use of Venn diagrams, the inclusion/exclusion formula, the multiplication principal, permutations, and combinations

Combinatorics: An Introduction is an excellent book for discrete and finite mathematics courses at the upper-undergraduate level. This book is also ideal for readers who wish to better understand the various applications of elementary combinatorics.

Leseprobe

Contents

Preface

Chapter 1: Logic

1.1 Formal Logic

1.2 Basic Logical Strategies

1.3 The Direct Argument

1.4 More Argument Forms

1.5 Proof by Contradiction

1.6 Exercises

Chapter 2: Sets

2.1 Set Notation

2.2 Predicates

2.3 Subsets

2.4 Union and Intersection

2.5 Exercises

Chapter 3: Venn Diagrams

3.1 Inclusion/Exclusion Principle

3.2 Two-Circle Venn Diagrams

3.3 Three-Square Venn Diagrams

3.4 Exercises

Chapter 4: Multiplication Principle

4.1 What Is the Principle?

4.2 Exercises

Chapter 5: Permutations

5.1 Some Special Numbers

5.2 Permutations Problems

5.3 Exercises

Chapter 6: Combinations

6.1 Some Special Numbers

6.2 Combination Problems

6.3 Exercises

Chapter 7: Problems Combining Techniques

7.1 Significant Order

7.2 Order Not Significant

7.3 Exercises

Chapter 8: Arrangement Problems

8.1 Examples of Arrangements

8.2 Exercises

Chapter 9: At Least, At Most, and Or

9.1 Counting with Or

9.2 At Least, At Most

9.3 Exercises

Chapter 10: Complement Counting

10.1 The Complement Formula

10.2 A New View of “At Least”

10.3 Exercises

Chapter 11: Advanced Permutations

11.1 Venn Diagrams and Permutations

11.2 Exercises

Chapter 12: Advanced Combinations

12.1 Venn Diagrams and Combinations

12.2 Exercises

Chapter 13: Poker and Counting

13.1 Warm-Up Problems

13.2 Poker Hands

13.3 Jacks or Better

13.4 Exercises

Chapter 14: Advanced Counting

14.1 Indistinguishable Objects

14.2 Circular Permutations

14.3 Bracelets

14.4 Exercises

Chapter 15: Algebra and Counting

15.1 The Binomial Theorem

15.2 Identities

15.3 Exercises

Chapter 16: Derangements

16.1 Mathematical Induction

16.2 Fixed-Point Theorems

16.3 His Own Coat

16.4 Inclusion/Exclusion for Many Sets

16.5 A Common Miscount

16.6 Exercises

Chapter 17: Probability Vocabulary

17.1 Vocabulary

Chapter 18: Equally Likely Outcomes

18.1 Outcomes in Experiments

18.2 Exercises

Chapter 19: Probability Trees

19.1 Tree Diagrams

19.2 Exercises

Chapter 20: Independent Events

20.1 Independence

20.2 Logical Consequences of Influence

20.3 Exercises

Chapter 21: Sequences and Probability

21.1 Sequences of Events

21.2 Exercises

Chapter 22: Conditlonal Probability

22.1 What Does Conditional Mean?

22.2 Exercises

Chapter 23: Bayes’ Theorem

23.1 The Theorem

23.2 Exercises

Chapter 24: Statistics

24.1 Introduction

24.2 Probability Is Not Statistics

24.3 Conversational Probability

24.4 Conditional Statistics

24.5 The Mean

24.6 Median

24.7 Randomness

Chapter 25: Linear Programming

25.1 Continuous Variables

25.2 Discrete Variables

25.3 Incorrectly Applied Rules

Chapter 26: Subjective Truth

26.1 The Absolute Truth of Axioms

Bibliography

Index

Cover Design: John Wiley & Sons, Inc.Cover Illustration: courtesy of Theodore G. Faticoni

Copyright © 2013 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representation or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your Situation. You should consult with a Professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print, however, may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Faticoni, Theodore G. (Theodore Gerard), 1954–Combinatorics : an introduction / Theodore G. Faticoni, Department of Mathematics, FordhamUniversity, Bronx, NY.pages cmIncludes bibliographical references and index.ISBN 978-1-118-40436-2 (hardback)1. Combinatorial analysis. I. Title.QA164.F38 2012511’.6—dc23

2012025751

To our mother, Margaret Faticoni.My sisters and I are one for our Mom ‘s efforts.

Preface

As I read the current textbooks on finite or linear mathematics, I am struck by the superficial way that counting problems or combi- natorics are handled. Counting is treated as a methodical or me- chanical thing. The student is asked to memorize a few important but unenlightening algorithms that will always teil us the number of ways that someone can choose and arrange her outfits for the week.

Furthermore, the examples that are given use so much of reality that the Student has more to learn about electronic components, failed tests, and card games than they do about counting in mathematics. Whatever happened to problems that emphasized their mathematical content and left a knowledge of Science and gaming to other departments? I understand that, to some, mathematics is best when it is used in applications. But why are we giving up on teaching mathematical content in favor of these other subjects?

Moreover, the why of it all, the justification, the beauty of proof has left these courses entirely. There is no explanation as to how the fundamental formulas are derived, and there is no rationalization as to how certain formulas are formed. The exercises that are given in modern texts are just slight variations on the examples worked out in the chapter. And in my opinion, the chapter examples are mostly uninspiring.

This book is aimed at College students, teaching assistants, ad- junct instructors, or anyone who wants to learn a little more el- ementary combinatorics than the usual text contains. This book might also-be used as a Supplement to the existing text for a finite mathematics course or to Supplement a discrete mathematics course, which several curriculums require.

The purpose of this book is to give a treatment of counting combinatorics that allows for some discussion beyond what is seen in today’s texts. We will discuss and justify our formulas at every turn. Our examples will include, after the most elementary of appli- cations, some ideas that do not occur in other texts on the market at this time. The applications never get beyond the use of Venn diagrams, the inclusion/exclusion formula, the multiplication prin- cipal, permutations, and combinations. But their uses are clever and at times inspiring.

For example, we do some poker hand problems that are not seen in modern texts, we count the number of bracelets that can be made with n > 1 different colored beads, and we count the number of derangements of {1, …, n}. We do this without any more than the elementary tools for counting. We then consider some probability problems by doing some elementary counting. But we show some very surprising, mathematically precise consequences of a trained approach to the subject.

A second theme within this book is that the case-by-case method for solving problems is emphasized. Of course we use a formula when needed, but when it comes time to derive a formula, we have decided to consistently give the case-by-case approach to the Problem. In this way we are asking the Student/reader to think mathematically and in exactly the same way from problem to problem throughout the book. Perhaps this is what the students will take with them when they leave the course. They will misremember the applications for the permutation formula, but they might remember how to break a problem into pieces in order to solve it.

The book is a series of short chapters that cover no more than one topic each. We cover such topics as logic and paradoxes, sets and set notation, power sets and their cardinality, Venn diagrams, the multiplication principal, permutations, combinations, problems combining the multiplication principal, problems combining permutations and combinations, problems involving the complement rule, at least, and at most. We cover derangements, elementary probability, conditional probability, independent probability, and Bayes' Theorem. We close with a discussion of two dimensional geometric simplex algorithm problems, showing that the traditional geometric method breaks down in the case where the variables take on only integer values. In other words, the method breaks down in every example done in the modern finite mathematics texts.

There are plenty of worked examples, as I want to do the work for the reader, and there is a short list of homework exercises. The examples given can also be used by an instructor or a teaching assis- tant to gain a higher level of understanding of the subject than the current texts offer, thus providing the instructor with an overview of the subject that the Student does not possess. This can aid the classroom Situation since, as I believe, we do a better job of teaching when we teach from a higher point of view in the delivered subject. The instructor then has a Professional confidence that (s)he can solve any problem that comes up in dass.

The fact that the book is salted with explanations as to why cer- tain formulas exist helps the Student and the instructor understand what they are doing. This is different from the rote memorization that many texts on this subject require. In this book the justifica- tion for the formulas is also there.

With this approach to the subject and to my readers, I believe I have found a gradual, understandable path that will bring a College student to a discussion of a subject on combinatorics and probability that is more advanced than any of the topics covered in the current texts on finite mathematics.

Theodore G. FaticoniDepartment of MathematicsFordham UniversityBronx, New York [email protected]

Chapter 1

Logic

There are several kinds of logic in mathematics. The one based in the construction of Truth tables is called formal logic. This is the logic used in Computer science to design and construct the guts of your Computer. And then there is Aristotle’s logic. This is the logic used to make arguments in court or when arguing informally with another person. This is the logic used to prove that something is, or to prove that something is not. This is the logic used to examine combinations of any of the mathematical ideas encountered in this text. While we will examine formal logic and the logic of sets and functions, we will be most interested in Aristotle’s logic of the argument in this chapter and throughout the rest of the text.

Oh, and there will be no need for a calculator in this book. I have made an effort to emphasize the important mathematical content in this book, not the superfluous, tedious practice of arithmetic. Arithmetic is important when you work with money, but in more challenging mathematical problems it only gets in the way. So cradle your electronic toy if you need to, but there will be almost no use for it as we do our counting.

1.1 Formal Logic

Formal logic is just a series of tables describing how the words and, or, not are defined. There is nothing illuminating with this approach, but it does match the operations of the inner workings of your Computer. We will minimally justify the tables used here. We will just write them down and show how they agree with your use of the words in your language.

These tables define logic. Not just in English, the language that this book is being written in, but they describe logic in every language on earth. If you are reading a Mandarin Chinese translation of this book, then the logic presented here will still be the logic of your language. It is also the binary language in which the Software in your Computer is written. Take time to savor that thought. Logic as it is applied to languages and Computers is universal. Logic is thus common to all forms of communication, analogue or digital.