We use combinatorial reasoning to prove identities.
1 Combinatorial Identities
example 1 Use combinatorial reasoning to establish the identity We will use bijective
reasoning, i.e., we will show a one-to-one correspondence between objects to conclude
that they must be equal in number. Suppose a group of people is split into two
groups. If the first group consists of people, then the second group must consist of
people and vice versa. Hence groups of size and taken from a group of size must be
equal in number. Thus
example 2 Use combinatorial reasoning to establish Pascal’s Identity: This identity is
the basis for creating Pascal’s triangle.
To establish the identity we will use a double counting argument. That is we will pose a counting problem and reason its solution two different ways- one which yields the left hand side of the identity and the other which yields the right hand side. For the identity above, we begin with the right hand side since it is simpler. The quantity counts the number of committees of people that can be selected from a group of people. Hence, we must find another way of counting this same thing which yields the left hand side. Reason as follows. Regard one of the people as special. Then the committee either contains the special person or it does not. The number of committees which contain the special person is since other committee members must be selected from the other people. Then, the number of committees which do not contain the special person is since then entire person committee members must be selected from the other people. The total number of possible committees is thus Since we have two different forms for the solution to the same problem, they must be equal: and the identity is established.
To establish the identity we will use a double counting argument. That is we will pose a counting problem and reason its solution two different ways- one which yields the left hand side of the identity and the other which yields the right hand side. For the identity above, we begin with the right hand side since it is simpler. The quantity counts the number of committees of people that can be selected from a group of people. Hence, we must find another way of counting this same thing which yields the left hand side. Reason as follows. Regard one of the people as special. Then the committee either contains the special person or it does not. The number of committees which contain the special person is since other committee members must be selected from the other people. Then, the number of committees which do not contain the special person is since then entire person committee members must be selected from the other people. The total number of possible committees is thus Since we have two different forms for the solution to the same problem, they must be equal: and the identity is established.
example 3 Use combinatorial reasoning to establish the identity The left hand side
represents the number of ways to select a committee of people from a group of
people times the number of ways to select one member from that committee to be the
chair. The right hand side represents the number of ways to select one person from
the group of to be the chair of a committee times the number of ways to select other
committee members from the remaining people. In either case, we are counting the
number of ways to select a chaired committee of people from a group of
people.
example 4 Use combinatorial reasoning to establish the identity Let . The number of
subsets of can be counted in two different ways. First, we can use the Fundamental
Principle of Counting element by element. In a given subset, an element is either in
it or not in it, giving 2 choices. Creating the subset requires making this
decision for each of the elements in the set. The number of subsets that can
be created (including the empty set) is where there are factors of in the
product. Hence the number of possible subsets is . On the other hand, we
can create all of the possible subsets of by partitioning them into groups
of the same size. The number of subsets of of size is since we have to
choose items from a set of items without regard to the order of selection.
Thus the total number of possible subsets is obtained by summing over all
possible values of : This double counting argument establishes the identity
example 5 Use combinatorial reasoning to establish the Hockey Stick Identity:
The right hand side counts the number of ways to form a committee of
people from a group of people. To establish this identity we will double count
this by assigning each of the people a unique integer from to and then
partitioning the committees according to the largest number assigned among its
members. Since there are members on the committee, the largest number
assigned among the members in a particular committee ranges from to . The
number of committees that can be formed having largest number among
its members is since we must choose members from those numbered to
in addition to the member numbered . Since ranges from to we have
that the total number of possible committees is By double counting, we
have established the identity This is called the hockey stick identity due to
the shape of the binomial coefficients involved when highlighted in Pascal’s
Triangle.
(problem 2) Use combinatorial reasoning to establish the identity
(problem 3) Use combinatorial reasoning to establish the identity
2024-09-27 14:05:02