Search
- Filter Results
- Location
- Classification
- Include attachments
- https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/zz%3A_Back_Matter/22%3A_Appendix_B%3A_Mathematical_InductionThere is a variant of one of the bijections we used to prove the Pascal Equation that comes up in counting the subsets of a set. In the next problem, it will help us compute the total number of subsets...There is a variant of one of the bijections we used to prove the Pascal Equation that comes up in counting the subsets of a set. In the next problem, it will help us compute the total number of subsets of a set, regardless of their size. Our main goal in this problem, however, is to introduce some ideas that will lead us to one of the most powerful proof techniques in combinatorics (and many other branches of mathematics), the principle of mathematical induction.
- https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/06%3A_Groups_Acting_on_SetsUntil now we have thought of permutations mostly as ways of listing the elements of a set. In this chapter, we will find it very useful to think of permutations as functions. This will help us in usin...Until now we have thought of permutations mostly as ways of listing the elements of a set. In this chapter, we will find it very useful to think of permutations as functions. This will help us in using permutations to solve enumeration problems that cannot be solved by the quotient principle because they involve counting the blocks of a partition in which the blocks don’t have the same size.
- https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/04%3A_Generating_Functions/4.01%3A_The_Idea_of_Generating_FunctionsIn the theory of generating functions, we associate variables or polynomials or even power series with members of a set. There is no standard language describing how we associate variables with member...In the theory of generating functions, we associate variables or polynomials or even power series with members of a set. There is no standard language describing how we associate variables with members of a set, so we shall invent some. By a picture of a member of a set we will mean a variable, or perhaps a product of powers of variables (or even a sum of products of powers of variables). A function that assigns a picture P(s) to each member s of a set S will be called a picture function.
- https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/06%3A_Groups_Acting_on_Sets/6.02%3A_Groups_Acting_on_SetsWe have seen that the fact that we have defined a permutation group as the permutations of some specific set doesn’t preclude us from thinking of the elements of that group as permuting the elements o...We have seen that the fact that we have defined a permutation group as the permutations of some specific set doesn’t preclude us from thinking of the elements of that group as permuting the elements of some other set as well.
- https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/03%3A_Distribution_ProblemsThumbnail: The 15 partitions of a 4-element set ordered in a Hasse diagram There are S(4,1),...,S(4,4) = 1,7,6,1 partitions containing 1,2,3,4 sets. (CC BY-3.0; Watchduck). Contributors and Attributio...Thumbnail: The 15 partitions of a 4-element set ordered in a Hasse diagram There are S(4,1),...,S(4,4) = 1,7,6,1 partitions containing 1,2,3,4 sets. (CC BY-3.0; Watchduck). Contributors and Attributions Kenneth P. Bogart (Dartmouth)
- https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/03%3A_Distribution_Problems/3.01%3A_The_Idea_of_DistributionIt is helpful to have more than one way to think of solutions to problems. In the case of distribution problems, another popular model for distributions is to think of putting balls in boxes rather th...It is helpful to have more than one way to think of solutions to problems. In the case of distribution problems, another popular model for distributions is to think of putting balls in boxes rather than distributing objects to recipients. Passing out identical objects is modeled by putting identical balls into boxes. Passing out distinct objects is modeled by putting distinct balls into boxes.
- https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/05%3A_The_Principle_of_Inclusion_and_Exclusion/5.01%3A_The_Size_of_a_Union_of_SetsOne of our very first counting principles was the sum principle which says that the size of a union of disjoint sets is the sum of their sizes. Computing the size of overlapping sets requires, quite n...One of our very first counting principles was the sum principle which says that the size of a union of disjoint sets is the sum of their sizes. Computing the size of overlapping sets requires, quite naturally, information about how they overlap. Taking such information into account will allow us to develop a powerful extension of the sum principle known as the “principle of inclusion and exclusion.”
- https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/05%3A_The_Principle_of_Inclusion_and_Exclusion/5.02%3A_Applications_of_Inclusion_and_ExclusionWe defined a graph to consist of set V of elements called vertices and a set E of elements called edges such that each edge joins two vertices. A coloring of a graph by the elements of a set C (...We defined a graph to consist of set V of elements called vertices and a set E of elements called edges such that each edge joins two vertices. A coloring of a graph by the elements of a set C (of colors) is an assignment of an element of C to each vertex of the graph; that is, a function from the vertex set V of the graph to C. A coloring is called proper if for each edge joining two distinct vertices, the two vertices it joins have different colors.
- https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/01%3A_What_is_Combinatorics/1.01%3A_About_These_NotesThese notes are based on the philosophy that you learn the most about a subject when you are figuring it out directly for yourself, and learn the least when you are trying to figure out what someone e...These notes are based on the philosophy that you learn the most about a subject when you are figuring it out directly for yourself, and learn the least when you are trying to figure out what someone else is saying about it. What we are going to try to do is to give you a chance to discover many of the interesting examples that usually appear as textbook examples and discover the principles that appear as textbook theorems.
- https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/04%3A_Generating_Functions/4.03%3A_Generating_Functions_and_Recurrence_RelationsAlgebraic manipulations with generating functions can sometimes reveal the solutions to a recurrence relation.
- https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/05%3A_The_Principle_of_Inclusion_and_Exclusion/5.03%3A_Deletion-Contraction_and_the_Chromatic_PolynomialIn Chapter 2 we introduced the deletion-contraction recurrence for counting spanning trees of a graph. In this section, we will use the deletion-contraction recurrence to reduce the computation of the...In Chapter 2 we introduced the deletion-contraction recurrence for counting spanning trees of a graph. In this section, we will use the deletion-contraction recurrence to reduce the computation of the chromatic polynomial of a graph (exemplified by Figure 5.3.1) to the computation of chromatic polynomials that can easily be computed.
