Global Representation with Service and Distribution Centers Worldwide.

David Santos

Description

• capacity flange barrel arbor hole drive pin
• ulbrich
• flat wire round wire
• radius nitinol strip
• flat wire
• custom products with top notch service
• variety of medical applications
• precision
• products

Sujets

• Westminster
• Target
• Custom
• Médecine
• Variety
• Précision

Informations

• Publié par: zeap
• Nombre de lectures: 59
• Langue: English

Extrait

David A. SANTOS
[e-mail]
July 3, 2006 REVISION
Discrete
Discrete Mathematics
Discrete Mathematics
Notes Discrete Mathematics
t i t t ti
No es D scre e Ma hema cs
Mathematics Notes Discrete Mathematics Notes
Mathematics Notes Discrete Mathematics Notes
Notes Discrete Mathematics Notes Discrete
Notes Discrete Mathematics Notes Discrete
Discrete Mathematics Notes Discrete
Discrete Mathematics Notes Discrete Mathematics
Discrete Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics Notes
Mathematics Notes Discrete Mathematics Notes
Notes Discrete Mathematics Notes Discrete
Notes Discrete Mathematics Notes Discrete
Discrete Mathematics Notes Discrete Mathematics
Discrete Mathematics Notes Discrete Mathematics
Discrete Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics Notes
Mathematics Notes Discrete Mathematics Notes
Mathematics Notes Discrete Mathematics Notes Discrete
Notes Discrete Mathematics Notes Discrete
Discrete Mathematics Notes Discrete
Discrete Mathematics Notes Discrete Mathematics
Discrete Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics Notes
Mathematics Notes Discrete Mathematics Notes
Notes Discrete Mathematics Notes Discrete
Notes Discrete Mathematics Notes Discrete
Discrete Mathematics Notes Discrete
Discrete Mathematics Notes Discrete Mathematics
Discrete Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics Notes
Mathematics Notes Discrete Mathematics Notes
Notes Discrete Mathematics Notes Discrete
Notes Discrete Mathematics Notes Discrete
Discrete Mathematics Notes Discrete Mathematics
Discrete Mathematics Notes Discrete Mathematics
Discrete Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics Notes
Mathematics Notes Discrete Mathematics Notes
Mathematic Note Di c ete Mathematic Note Di c ete
s s s r s s s r
Notes Discrete Mathematics Notes Discrete
Discrete Mathematics Notes Discrete
Discrete Mathematics Notes Discrete Mathematics
Discrete Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics
Mathematics Notes Discrete Mathematics Notes
Mathematics Notes Discrete Mathematics Notes
Notes Discrete Mathematics Notes Discrete
Notes Discrete Mathematics Notes Discrete
Discrete Mathematics Notes Discreteii
Contents
Preface iii 5 Number Theory 44
5.1 Division Algorithm . . . . . . . . . . . . . . . . . . 44
5.2 Greatest Common Divisor . . . . . . . . . . . . . . 461 Pseudocode 1
5.3 Non-decimal Scales . . . . . . . . . . . . . . . . . . 481.1 Operators . . . . . . . . . . . . . . . . . . . . . . . 1
5.4 Congruences . . . . . . . . . . . . . . . . . . . . . 491.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . 2
5.5 Divisibility Criteria . . . . . . . . . . . . . . . . . . 51
1.3 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . 3
Homework . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.4 If-then-else Statements . . . . . . . . . . . . . 4 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.5 Thefor loop . . . . . . . . . . . . . . . . . . . . . 5
6 Enumeration 571.6 Thewhile loop . . . . . . . . . . . . . . . . . . . 8
6.1 The Multiplication and Sum Rules . . . . . . . . . . 57Homework . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.2 Combinatorial Methods . . . . . . . . . . . . . . . . 59Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
6.2.1 Permutations without Repetitions . . . . . . 60
6.2.2 Permutations with Repetitions . . . . . . . . 622 Proof Methods 14
6.2.3 Combinations without Repetitions . . . . . . 64
2.1 Proofs: Direct Proofs . . . . . . . . . . . . . . . . . 14
6.2.4 Combinations with Repetitions . . . . . . . . 66
2.2 Proofs: Mathematical Induction . . . . . . . . . . . 15 6.3 Inclusion-Exclusion . . . . . . . . . . . . . . . . . . 67
2.3 Proofs: Reductio ad Absurdum . . . . . . . . . . . . 17 Homework . . . . . . . . . . . . . . . . . . . . . . . . . . 72
2.4 Proofs: Pigeonhole Principle . . . . . . . . . . . . . 19 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Homework . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7 Sums and Recursions 78
Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
7.1 Famous Sums . . . . . . . . . . . . . . . . . . . . . 78
7.2 First Order Recursions . . . . . . . . . . . . . . . . 82
3 Logic, Sets, and Boolean Algebra 26
7.3 Second Order Recursions . . . . . . . . . . . . . . . 85
3.1 Logic . . . . . . . . . . . . . . . . . . . . . . . . . 26 7.4 Applications of Recursions . . . . . . . . . . . . . . 86
3.2 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Homework . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.3 Boolean Algebras and Boolean Operations . . . . . . 31 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.4 Sum of Products and Products of Sums . . . . . . . . 33
8 Graph Theory 893.5 Logic Puzzles . . . . . . . . . . . . . . . . . . . . . 34
8.1 Simple Graphs . . . . . . . . . . . . . . . . . . . . 89
Homework . . . . . . . . . . . . . . . . . . . . . . . . . . 36
8.2 Graphic Sequences . . . . . . . . . . . . . . . . . . 92
Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 8.3 Connectivity . . . . . . . . . . . . . . . . . . . . . 93
8.4 Traversability . . . . . . . . . . . . . . . . . . . . . 93
4 Relations and Functions 38 8.5 Planarity . . . . . . . . . . . . . . . . . . . . . . . . 95
4.1 Partitions and Equivalence Relations . . . . . . . . . 38 Homework . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.2 Functions . . . . . . . . . . . . . . . . . . . . . . . 40 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . 97Preface
These notes started in the Spring of 2004, but contain material that I have used in previous years.
I would appreciate any comments, suggestions, corrections, etc., which can be addressed at the email below.
David A. Santos
[e-mail]
Things to do:
• Weave functions into counting, a la twelfold way. . .`
iiiLegal Notice
This material may be distributed only subject to the terms and conditions set forth in the Open Publication License, version 1.0
or later (the latest version is presently available at http://www.opencontent.org/openpub/
THIS WORK IS LICENSED AND PROVIDED “AS IS” WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IM-
PLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
FOR A PARTICULAR PURPOSE OR A WARRANTY OF NON-INFRINGEMENT.
THIS DOCUMENT MAY NOT BE SOLD FOR PROFIT OR INCORPORATED INTO COMMERCIAL DOCUMENTS
WITHOUT EXPRESS PERMISSION FROM THE AUTHOR(S). THIS DOCUMENT MAY BE FREELY DISTRIBUTED
PROVIDED THE NAME OF THE ORIGINAL AUTHOR(S) IS(ARE) KEPT AND ANY CHANGES TO IT NOTED.
ivChapter1
Pseudocode
In this chapter we study pseudocode, which will allow us to mimic computer language in writing algorithms.
1.1 Operators
1 Definition (Operator) An operator is a character, or string of characters, used to perform an action on some entities. These
entities are called the operands.
2 Definition (Unary Operators) A unary operator is an operator acting on a single operand.
Common arithmetical unary operators are+ (plus) which indicates a positive number, and− (minus) which indicates a negative
number.
3 Definition (Binary Operators) A binary operator is an operator acting on two operands.
Common arithmetical binary operators that we will use are + (plus) to indicate the sum of two numbers and− (minus) to
indicate a difference of two numbers. We will also use∗ (asterisk) to denote multiplication and/ (slash) to denote division.
There is a further arithmetical binary operator that we will use.
4 Definition (mod Operator) The operator mod is defined as follows: for a≥ 0, b> 0,
a mod b
is the integral non-negative remainder when a is divided by b. Observe that this remainder is one of the b numbers
0, 1, 2, ..., b− 1.
In the case when at least one of a or b is negative, we will leave a mod b undefined.
5 Example We have
38 mod 15= 8,
15 mod 38= 15,
1961 mod 37= 0,
and
1966 mod 37= 5,
for example.
1
È
È
È
‹
2 Chapter 1
6 Definition (Precedence of Operators) The priority or precedence of an operator is the order by which it is applied to its
operands. Parentheses ( ) are usually used to coerce precedence among operators. When two or more operators of the same
precedence are in an expression, we define the associativity to be the order which determines which of the operators will be
executed first. Left-associative operators are executed from left to right and right-associative operators are executed from right
to left.
Recall from algebra that multiplication and division have the same precedence, and their precedence is higher than addition and
subtraction. The mod operator has the same precedence as multiplicati