Section 4.2 Counting
257
and fourth are different, there are 10 # 9 # 1 # 8 ways this can happen. If the first two
digits are alike and the last two are also alike but different from the first two, there are
10 # 1 # 9 # 1 such numbers. Obviously, there are many other possibilities.
Instead, we solve the problem by noting that numbers with repetitions and
numbers with no repetitions are disjoint sets whose union equals all four-digit
numbers. By Example 31 we can find the number with repetitions by subtracting
the number with no repetitions (5040, according to Example 26) from the total
number (10,000, according to Example 25). Therefore, there are 4960 numbers
with repetitions.
example 38
A computer (or tablet, or camera, or cell phone) that wishes to connect to the Internet must have an IP (Internet Protocol) address assigned to it. This allows the
device to be “found” over the Internet, much as a postal address allows a building
to be “found” via regular mail. The version of IP known as IPv4 uses an address
that is a 32-bit, or 4-byte, number (1 byte equals 8 bits). The first part of the address, called the netid, identifies the network that the machine is part of and the
rest, called the hostid, identifies the machine itself. Note that this is a hierarchical
addressing scheme. A router trying to decide where to send a data packet looks at
the netid to determine the network. The hostid bytes need never be consulted until
the data packet has reached the correct network. U.S. postal addresses are hierarchical in the opposite order, with the most specific information first.
How many different IPv4 addresses are there? Each of the 32 bits can be set to
0 or 1, so by the multiplication principle, there are 2 # 2 # 2 # c # 2 = 2
32
different
bit patterns. Looking at a more abstract view, assume that a particular IP address
uses 16 bits for the netid and 16 bits for the hostid. Again using the multiplication
principle, this would give 2
16 # 2
16
= (again) 2
32
unique IP addresses. This number
is roughly 4.3 billion, which seems large enough to satisfy the world’s needs. But
no − the pool of IPv4 addresses allotted to some regions of the world began to run
out in 2011 and more would do so in another year or two. Hence the switch to IPv6.
An IPv6 address is 128 bits, divided into 64 bits for the network prefix that
identifies a particular network and the last 64 bits for the interface ID that identifies
the unique node on the network. While the gross structure of an IPv6 address therefore sounds just like an IPv4 address only bigger, there are details that make the
IPv6 scheme more efficient. And exactly how big is the pool of IPv6 addresses?
Using the same reasoning as before, there are 2
128
unique addresses. This number
is roughly 3.4 × 10
38
, or 340 trillion trillion trillion, enough, it is said, for every
star in the known universe to have the equivalent of its very own IPv4 internet.
The World IPv6 Launch occurred on June 6, 2012, but it was not like turning
on a switch. Many major companies already supported IPv6 and IPv4 will continue to be supported over a few years of transition.
decision trees
Trees such as those in Figures 4.3 and 4.4 illustrate the number of outcomes of an
event based on a series of possible choices. Such trees are called decision trees.
We will see in Chapter 6 how decision trees are used in analyzing algorithms,
but for now we use them to solve additional counting problems. The trees of
Figures 4.3 and 4.4 led to the multiplication principle because the number of
257
and fourth are different, there are 10 # 9 # 1 # 8 ways this can happen. If the first two
digits are alike and the last two are also alike but different from the first two, there are
10 # 1 # 9 # 1 such numbers. Obviously, there are many other possibilities.
Instead, we solve the problem by noting that numbers with repetitions and
numbers with no repetitions are disjoint sets whose union equals all four-digit
numbers. By Example 31 we can find the number with repetitions by subtracting
the number with no repetitions (5040, according to Example 26) from the total
number (10,000, according to Example 25). Therefore, there are 4960 numbers
with repetitions.
example 38
A computer (or tablet, or camera, or cell phone) that wishes to connect to the Internet must have an IP (Internet Protocol) address assigned to it. This allows the
device to be “found” over the Internet, much as a postal address allows a building
to be “found” via regular mail. The version of IP known as IPv4 uses an address
that is a 32-bit, or 4-byte, number (1 byte equals 8 bits). The first part of the address, called the netid, identifies the network that the machine is part of and the
rest, called the hostid, identifies the machine itself. Note that this is a hierarchical
addressing scheme. A router trying to decide where to send a data packet looks at
the netid to determine the network. The hostid bytes need never be consulted until
the data packet has reached the correct network. U.S. postal addresses are hierarchical in the opposite order, with the most specific information first.
How many different IPv4 addresses are there? Each of the 32 bits can be set to
0 or 1, so by the multiplication principle, there are 2 # 2 # 2 # c # 2 = 2
32
different
bit patterns. Looking at a more abstract view, assume that a particular IP address
uses 16 bits for the netid and 16 bits for the hostid. Again using the multiplication
principle, this would give 2
16 # 2
16
= (again) 2
32
unique IP addresses. This number
is roughly 4.3 billion, which seems large enough to satisfy the world’s needs. But
no − the pool of IPv4 addresses allotted to some regions of the world began to run
out in 2011 and more would do so in another year or two. Hence the switch to IPv6.
An IPv6 address is 128 bits, divided into 64 bits for the network prefix that
identifies a particular network and the last 64 bits for the interface ID that identifies
the unique node on the network. While the gross structure of an IPv6 address therefore sounds just like an IPv4 address only bigger, there are details that make the
IPv6 scheme more efficient. And exactly how big is the pool of IPv6 addresses?
Using the same reasoning as before, there are 2
128
unique addresses. This number
is roughly 3.4 × 10
38
, or 340 trillion trillion trillion, enough, it is said, for every
star in the known universe to have the equivalent of its very own IPv4 internet.
The World IPv6 Launch occurred on June 6, 2012, but it was not like turning
on a switch. Many major companies already supported IPv6 and IPv4 will continue to be supported over a few years of transition.
decision trees
Trees such as those in Figures 4.3 and 4.4 illustrate the number of outcomes of an
event based on a series of possible choices. Such trees are called decision trees.
We will see in Chapter 6 how decision trees are used in analyzing algorithms,
but for now we use them to solve additional counting problems. The trees of
Figures 4.3 and 4.4 led to the multiplication principle because the number of