包邮离散数学

CHAPTER 1 Counting1.1 Basic CountingThe Sum PrincipleAbstractionSumming Consecutive IntegersThe Product PrincipleTwo-Element SubsetsImportant Concepts, Formulas, and TheoremsProblems1.2 Counting Lists, Permutations, and SubsetsUsing the Sum and Product PrinciplesLists and FunctionsThe Bijection Principlek-Element Permutations of a SetCounting Subsets of a SetImportant Concepts, Formulas, and TheoremsProblems1.3 Binomial CoefficientsPascal s TriangleA Proof Using the Sum PrincipleThe Binomial TheoremLabeling and Trinomial CoefficientsImportant Concepts, Formulas, and TheoremsProblems1.4 RelationsWhat Is a Relation？Functions as RelationsProperties of RelationsEquivalence RelationsPartial and Total OrdersImportant Concepts, Formulas, and TheoremsProblems1.5 Using Equivalence Relations in CountingThe Symmetry PrincipleEquivalence RelationsThe Quotient PrincipleEquivalence Class CountingMultisetsThe Bookcase Arrangement ProblemThe Number of k-Element Multisetsof an n-Element SetUsing the Quotient Principle to Explain a QuotientImportant Concepts, Formulas, and TheoremsProblemsCHAPTER 2 Cryptography and Number Theory2.1 Cryptography and Modular ArithmeticIntroduction to CryptographyPrivate-Key CryptographyPublic-Key CryptosystemsArithmetic Modulo nCryptography Using Addition mod nCryptography Using Multiplication mod nImportant Concepts, Formulas, and TheoremsProblems2.2 Inverses and Greatest Common DivisorsSolutions to Equations and Inverses mod nInverses mod nConverting Modular Equations to Normal EquationsGreatest Common DivisorsEuclid s Division TheoremEuclid s GCD AlgorithmExtended GCD AlgorithmComputing InversesImportant Concepts, Formulas, and TheoremsProblems2.3 The RSA CryptosystemExponentiation mod nThe Rules of ExponentsFermat s Little TheoremThe RSA CryptosystemThe Chinese Remainder TheoremImportant Concepts, Formulas, and TheoremsProblems2.4 Details of the RSA CryptosystemPractical Aspects of Exponentiation mod nHow Long Does It Take to Use the RSA Algorithm？How Hard Is Factoring？Finding Large PrimesImportant Concepts, Formulas, and TheoremsProblemsCHAPTER 3 Reflections on Logic and Proof3.1 Equivalence and ImplicationEquivalence of StatementsTruth TablesDeMorgan s LawsImplicationIf and Only IfImportant Concepts, Formulas, and TheoremsProblems3.2 Variables and QuantifiersVariables and UniversesQuantifiersStandard Notation for QuantificationStatements about VariablesRewriting Statements to Encompass Larger UniversesProving Quantified Statements True or FalseNegation of Quantified StatementsImplicit QuantificationProof of Quantified StatementsImportant Concepts, Formulas, and TheoremsProblems3.3 InferenceDirect Inference （Modus Ponens） and ProofsRules of Inference for Direct ProofsContrapositive Rule of InferenceProof by ContradictionImportant Concepts, Formulas, and TheoremsProblemsCHAPTER 4 Induction, Recursion, and Recurrences4.1 Mathematical InductionSmallest CounterexamplesThe Principle of Mathematical InductionStrong InductionInduction in GeneralA Recursive View of InductionStructural InductionImportant Concepts, Formulas, and TheoremsProblems4.2 Recursion, Recurrences, and InductionRecursionExamples of First-Order Linear RecurrencesIterating a RecurrenceGeometric SeriesFirst-Order Linear RecurrencesImportant Concepts, Formulas, and TheoremsProblems4.3 Growth Rates of Solutions to RecurrencesDivide and Conquer AlgorithmsRecursion TreesThree Different BehaviorsImportant Concepts, Formulas, and TheoremsProblems4.4 The Master TheoremMaster TheoremSolving More General Kinds of RecurrencesExtending the Master TheoremImportant Concepts, Formulas, and TheoremsProblems4.5 More General Kinds of RecurrencesRecurrence InequalitiesThe Master Theorem for InequalitiesA Wrinkle with InductionFurther Wrinkles in Induction ProofsDealing with Functions Other Than ncImportant Concepts, Formulas, and TheoremsProblems4.6 Recurrences and SelectionThe Idea of SelectionA Recursive Selection AlgorithmSelection without Knowing the Median