Solutions Manual to accompany Combinatorial Reasoning: An Introduction to the Art of Counting E-Book

Duane DeTemple

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

Seitenzahl: 246

Veröffentlichungsjahr: 2014

Beschreibung

COMBINATORIAL REASONING

Showcases the interdisciplinary aspects of combinatorics and illustrates how to problem solve with a multitude of exercises

Written by two well-known scholars in the field, Combinatorial Reasoning: An Introduction to the Art of Counting presents a clear and comprehensive introduction to the concepts and methodology of beginning combinatorics. Focusing on modern techniques and applications, the book develops a variety of effective approaches to solving counting problems.

Balancing abstract ideas with specific topical coverage, the book utilizes real-world examples with problems ranging from basic calculations that are designed to develop fundamental concepts to more challenging exercises that allow for a deeper exploration of complex combinatorial situations. Simple cases are treated first before moving on to general and more advanced cases. Additional features of the book include:

• Approximately 700 carefully structured problems designed for readers at multiple levels, many with hints and/or short answers
• Numerous examples that illustrate problem solving using both combinatorial reasoning and sophisticated algorithmic methods
• A novel approach to the study of recurrence sequences, which simplifies many proofs and calculations
• Concrete examples and diagrams interspersed throughout to further aid comprehension of abstract concepts
• A chapter-by-chapter review to clarify the most crucial concepts covered

Combinatorial Reasoning: An Introduction to the Art of Counting is an excellent textbook for upper-undergraduate and beginning graduate-level courses on introductory combinatorics and discrete mathematics.

Leseprobe

SOLUTIONS MANUAL TO ACCOMPANY COMBINATORIAL REASONING

An Introduction to the Art of Counting

DUANE DeTEMPLE WILLIAM WEBB

Department of Mathematics Washington State University Pullman, WA

Copyright © 2014 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 representations 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 or for technical support, 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 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:

DeTemple, Duane W.     Solutions manual to accompany combinatorial reasoning : an introduction to the art        of counting / Duane DeTemple, William Webb.         pages    cm     ISBN 978-1-118-83078-9 (pbk.)    1. Combinatorial analysis–Textbooks.    2. Mathematical analysis–Textbooks.    I. Webb,    William,    1944-    II. Title.     QA164.D48 2013     511′.6–dc23

2013035522

CONTENTS

PREFACE

How to Use this Manual

Tips for Solving Combinatorial Problems

PART I THE BASICS OF ENUMERATIVE COMBINATORICS

1 Initial EnCOUNTers with Combinatorial Reasoning

Problem Set 1.2

Problem Set 1.3

Problem Set 1.4

Problem Set 1.5

Problem Set 1.6

Section 1.7

2 Selections, Arrangements, and Distributions

Problems Set 2.2

Problem Set 2.3

Problem Set 2.4

Problem Set 2.5

Problem Set 2.6

Problem Set 2.7

3 Binomial Series and Generating Functions

Problem Set 3.2

Problem Set 3.3

Problem Set 3.4

Problem Set 3.5

Problem Set 3.6

4 Alternating Sums, Inclusion-Exclusion Principle, Rook Polynomials, and Fibonacci Nim

Problem Set 4.2

Problem Set 4.3

Problem Set 4.4

Problem Set 4.5

Problem Set 4.6

5 Recurrence Relations

Problem Set 5.2

Problem Set 5.3

Problem Set 5.4

Problem Set 5.5

Problem Set 5.6

Problem Set 5.7

6 Special Numbers

Problem Set 6.2

Problem Set 6.3

Problem Set 6.4

Problem Set 6.5

Problem Set 6.6

Problem Set 6.7

Problem Set 6.8

PART II TWO ADDITIONAL TOPICS IN ENUMERATION

7 Linear Spaces and Recurrence Sequences

Problem Set 7.2

Problem Set 7.3

Problem Set 7.4

Section 7.5

8 Counting with Symmetries

Problem Set 8.2

Problem Set 8.3

Problem Set 8.4

Problem Set 8.5

End User License Agreement

Guide

Cover

Table of Contents

Preface

Pages

vii

viii

1

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

159

161

162

163

164

165

166

167

168

169

170

171

172

173

175

176

177

178

179

180

181

182

183

184

185

186

PREFACE

This manual provides the statements and complete solutions to all of the odd numbered problems in the textbook Combinatorial Reasoning: An Introduction to the Art of Counting. The definitions, theorems, figures, and other problems referenced in the solutions contained in this manual are to that book.

HOW TO USE THIS MANUAL

The most important thing to remember is that you should not turn to any solution in this manual without first attempting to solve the problem on your own. Many of the problems are subtle or complex and therefore require considerable thought—and time!—before you can expect to find a correct method of solution. You will learn best by trying to solve a problem on your own, even if you are unsuccessful. We hope that most often you will consult this manual simply to confirm your own answer. Often your answer will be the same as ours, but sometimes you may have found a different method of solution that is not only correct, but may even be better than ours (if so, please send us your alternative solution at the address below). If the answer to a problem eludes you even after a good effort, then take a look at the solution offered here. Even in this case, it is best only to read the beginning of the solution and see if you can continue to solve the problem on your own.

TIPS FOR SOLVING COMBINATORIAL PROBLEMS

Many students wonder how to go about attacking nonroutine problems. We have listed some suggestions below that may be helpful for solving combinatorial problems and more generally for solving problems in any branch of mathematics.

Try small cases and look for patterns

Separate a problem into cases

Draw a figure

Make a table of values

Look for a similar or related problem, one you already know how to solve

For combinatorial problems, apply one of the strategies explored in the textbook: use the addition and multiplication principles; identify the problem as a permutation, combination, or distribution; find and solve a recurrence relation; use a generating function; use the principle of inclusion/exclusion; restate the problem to relate it to a problem answered by well known numbers such as binomial coefficients, Fibonacci numbers, Stirling numbers, partition numbers, Catalan numbers, and so on.

For a more complete discussion of mathematical problem solving, you are encouraged to consult How to Solve It, the classic, but still useful, book of George Pólya.

DUANE DETEMPLE

WILLIAM WEBB

Washington State University, Pullman, WA

[email protected] and [email protected]

PART ITHE BASICS OF ENUMERATIVE COMBINATORICS