第13章数列、確率、数え上げSequences, Probability, and Counting Theory

A new company sells customizable cases for tablets and smartphones. Each case comes in a variety of colors and can be personalized for an additional fee with images or a monogram. A customer can choose not to personalize or could choose to have one, two, or three images or a monogram. The customer can choose the order of the images and the letters in the monogram. The company is working with an agency to develop a marketing campaign with a focus on the huge number of options they offer. Counting the possibilities is challenging!

ある新しい会社が、板状端末と多機能携帯電話のあつらえの覆いを売る。各覆いはさまざまな色があり、追加の料金で画像や組み合わせ文字を入れて個人向けにできる。客は個人向けにしないことも、一つ、二つ、三つの画像や組み合わせ文字を入れることも選べる。客は画像の順序と組み合わせ文字の並びも選べる。この会社は、提供する選択肢の膨大な数に絞った宣伝を作るため、代理店と組んでいる。可能性を数えるのは骨が折れる。

We encounter a wide variety of counting problems every day. There is a branch of mathematics devoted to the study of counting problems such as this one. Other applications of counting include secure passwords, horse racing outcomes, and college scheduling choices. We will examine this type of mathematics in this section.

日々、実にさまざまな数え上げの問題に出会う。この種の数え上げの問題を研究する数学の分野がある。数え上げのほかの応用には、安全な合言葉、競馬の結果、大学の時間割の選び方がある。この節ではこの種の数学を調べる。

The company that sells customizable cases offers cases for tablets and smartphones. There are 3 supported tablet models and 5 supported smartphone models. The Addition Principle tells us that we can add the number of tablet options to the number of smartphone options to find the total number of options. By the Addition Principle, there are 8 total options, as we can see in Figure 1.

あつらえの覆いを売るこの会社は、板状端末と多機能携帯電話の覆いを提供する。対応する板状端末は3型、対応する多機能携帯電話は5型ある。和の原理によれば、板状端末の選択肢の数に多機能携帯電話の選択肢の数を足せば、選択肢の総数が求まる。図1に見るとおり、和の原理により選択肢は全部で8つある。

The Multiplication Principle applies when we are making more than one selection. Suppose we are choosing an appetizer, an entrée, and a dessert. If there are 2 appetizer options, 3 entrée options, and 2 dessert options on a fixed-price dinner menu, there are a total of 12 possible choices of one each as shown in the tree diagram in Figure 2.

積の原理は、二つ以上の選択をするときに当てはまる。前菜、主菜、甘味を選ぶとしよう。定額の夕食の献立に前菜が2つ、主菜が3つ、甘味が2つあるなら、図2の樹形図に示すとおり、それぞれ一つずつ選ぶしかたは全部で12通りある。

The possible choices are:

ありうる選び方は次である。

We can also find the total number of possible dinners by multiplying.

掛け算でも夕食のありうる総数が求まる。

We could also conclude that there are 12 possible dinner choices simply by applying the Multiplication Principle.

積の原理を使うだけでも、夕食の選び方が12通りあると結論できる。

The Multiplication Principle can be used to solve a variety of problem types. One type of problem involves placing objects in order. We arrange letters into words and digits into numbers, line up for photographs, decorate rooms, and more. An ordering of objects is called a permutation.

積の原理はさまざまな型の問題を解くのに使える。一つの型は、物を順に並べることである。文字を並べて語にし、数字を並べて数にし、写真のために並び、部屋を飾る、といった具合である。物の並べ方を順列という。

To solve permutation problems, it is often helpful to draw line segments for each option. That enables us to determine the number of each option so we can multiply. For instance, suppose we have four paintings, and we want to find the number of ways we can hang three of the paintings in order on the wall. We can draw three lines to represent the three places on the wall.

順列の問題を解くには、選択肢ごとに線分を描くとしばしば役立つ。そうすれば各選択肢の数が決められ、掛け算ができる。たとえば、絵が四枚あり、そのうち三枚を順に壁に掛けるしかたの数を求めたいとしよう。壁の三か所を表す三本の線が描ける。

There are four options for the first place, so we write a 4 on the first line.

最初の場所には四つの選択肢があるので、一本目の線の上に4と書く。

After the first place has been filled, there are three options for the second place so we write a 3 on the second line.

最初の場所が埋まったあと、二番目の場所には三つの選択肢があるので、二本目の線の上に3と書く。

After the second place has been filled, there are two options for the third place so we write a 2 on the third line. Finally, we find the product.

二番目の場所が埋まったあと、三番目の場所には二つの選択肢があるので、三本目の線の上に2と書く。最後に積を求める。

There are 24 possible permutations of the paintings.

絵の順列は24通りありうる。

A family of five is having portraits taken. Use the Multiplication Principle to find the following.

五人家族が肖像写真を撮ってもらう。積の原理を使って次を求めよ。

For some permutation problems, it is inconvenient to use the Multiplication Principle because there are so many numbers to multiply. Fortunately, we can solve these problems using a formula. Before we learn the formula, let’s look at two common notations for permutations. If we have a set of $n$ objects and we want to choose $r$ objects from the set in order, we write $P(n,r).$ Another way to write this is $n{P}_r,$ a notation commonly seen on computers and calculators. To calculate $P(n,r),$ we begin by finding $n!,$ the number of ways to line up all $n$ objects. We then divide by $\left(n-r\right)!$ to cancel out the $\left(n-r\right)$ items that we do not wish to line up.

順列の問題によっては、掛ける数が多すぎるので積の原理を使うのが不便である。幸い、この問題は公式を使えば解ける。公式を学ぶ前に、順列のよくある二つの表記を見よう。$n$ 個の物の集合があり、その集合から $r$ 個を順に選びたいとき、$P(n,r)$ と書く。もう一つの表記は $n{P}_r$ であり、これは計算機や電卓でよく見られる。$P(n,r)$ を計算するには、まず $n!$、すなわち $n$ 個すべてを並べるしかたの数を求める。そして、並べたくない $\left(n-r\right)$ 個を打ち消すために $\left(n-r\right)!$ で割る。

Let’s see how this works with a simple example. Imagine a club of six people. They need to elect a president, a vice president, and a treasurer. Six people can be elected president, any one of the five remaining people can be elected vice president, and any of the remaining four people could be elected treasurer. The number of ways this may be done is $6\times 5\times 4=120.$ Using factorials, we get the same result.

簡単な例でこれがどうはたらくか見よう。六人の会を思い浮かべよ。会長、副会長、会計を選ぶ必要がある。六人が会長に選ばれうる。残り五人の誰でも副会長に選ばれうる。残り四人の誰でも会計に選ばれうる。このしかたの数は $6\times 5\times 4=120.$ である。階乗を使うと同じ結果になる。

There are 120 ways to select 3 officers in order from a club with 6 members. We refer to this as a permutation of 6 taken 3 at a time. The general formula is as follows.

6人の会員の会から3人の役員を順に選ぶしかたは120通りある。これを6個から3個ずつ取る順列という。一般の公式は次である。

Note that the formula stills works if we are choosing underlineallend underline $n$ objects and placing them in order. In that case we would be dividing by $\left(n-n\right)!$ or $0!,$ which we said earlier is equal to 1. So the number of permutations of $n$ objects taken $n$ at a time is $\frac{n!}{1}$ or just $n!\text{.}$

$n$ 個「すべて」を選んで順に並べるときも、この公式は成り立つことに注意せよ。その場合は $\left(n-n\right)!$ すなわち $0!$ で割ることになり、これは先に述べたとおり1に等しい。よって $n$ 個から $n$ 個ずつ取る順列の数は $\frac{n!}{1}$、すなわち単に $n!$ である。

A play has a cast of 7 actors preparing to make their curtain call. Use the permutation formula to find the following.

ある芝居で、7人の役者がカーテンコールの用意をしている。順列の公式を使って次を求めよ。

So far, we have looked at problems asking us to put objects in order. There are many problems in which we want to select a few objects from a group of objects, but we do not care about the order. When we are selecting objects and the order does not matter, we are dealing with combinations. A selection of $r$ objects from a set of $n$ objects where the order does not matter can be written as $C(n,r).$ Just as with permutations, $\text{C}(n,r)$ can also be written as ${}_n{C}_r.$ In this case, the general formula is as follows.

ここまで、物を順に並べる問題を見てきた。物の群からいくつかを選びたいが、順序は気にしないという問題も多い。物を選ぶのに順序が効かないときは、組合せを扱っていることになる。$n$ 個の物の集合から、順序を気にせず $r$ 個を選ぶことは $C(n,r)$ と書ける。順列と同じく、$\text{C}(n,r)$ は ${}_n{C}_r$ とも書ける。この場合、一般の公式は次である。

An earlier problem considered choosing 3 of 4 possible paintings to hang on a wall. We found that there were 24 ways to select 3 of the 4 paintings in order. But what if we did not care about the order? We would expect a smaller number because selecting paintings 1, 2, 3 would be the same as selecting paintings 2, 3, 1. To find the number of ways to select 3 of the 4 paintings, disregarding the order of the paintings, divide the number of permutations by the number of ways to order 3 paintings. There are $3!=3·2·1=6$ ways to order 3 paintings. There are $\frac{24}{6},$ or 4 ways to select 3 of the 4 paintings. This number makes sense because every time we are selecting 3 paintings, we are not selecting 1 painting. There are 4 paintings we could choose not to select, so there are 4 ways to select 3 of the 4 paintings.

前の問題では、壁に掛ける絵を4枚のうち3枚選ぶことを考えた。4枚のうち3枚を順に選ぶしかたは24通りだと分かった。だが順序を気にしないならどうか。絵1、2、3を選ぶのと絵2、3、1を選ぶのが同じになるので、もっと小さい数になるはずである。絵の順序を無視して4枚のうち3枚を選ぶしかたの数を求めるには、順列の数を、3枚の絵を並べるしかたの数で割る。3枚の絵を並べるしかたは $3!=3·2·1=6$ 通りある。4枚のうち3枚を選ぶしかたは $\frac{24}{6}$ すなわち4通りある。この数は理にかなう。3枚を選ぶときはいつも、1枚を選ばないからである。選ばないでおける絵が4枚あるので、4枚のうち3枚を選ぶしかたは4通りある。

We have looked only at combination problems in which we chose exactly $r$ objects. In some problems, we want to consider choosing every possible number of objects. Consider, for example, a pizza restaurant that offers 5 toppings. Any number of toppings can be ordered. How many different pizzas are possible?

ちょうど $r$ 個を選ぶ組合せの問題だけを見てきた。問題によっては、ありうるすべての個数の選び方を考えたい。たとえば、具を5種類出すピザの店を考えよ。具はいくつ注文してもよい。ピザは何通りありうるか。

To answer this question, we need to consider pizzas with any number of toppings. There is $C(5,0)=1$ way to order a pizza with no toppings. There are $C(5,1)=5$ ways to order a pizza with exactly one topping. If we continue this process, we get

この問いに答えるには、どの個数の具のピザも考える必要がある。具の無いピザの注文のしかたは $C(5,0)=1$ 通りある。具がちょうど一つのピザの注文のしかたは $C(5,1)=5$ 通りある。この手順を続けると、次を得る。

There are 32 possible pizzas. This result is equal to $2^5.$

ピザは32通りありうる。この結果は $2^5$ に等しい。

We are presented with a sequence of choices. For each of the $n$ objects we have two choices: include it in the subset or not. So for the whole subset we have made $n$ choices, each with two options. So there are a total of $2·2·2·\dots ·2$ possible resulting subsets, all the way from the empty subset, which we obtain when we say “no” each time, to the original set itself, which we obtain when we say “yes” each time.

選び方の連なりが与えられている。$n$ 個の物それぞれについて、部分集合に入れるか入れないかの二通りの選び方がある。よって部分集合全体では $n$ 回の選び方をし、それぞれに二つの選択肢がある。よってできる部分集合は全部で $2·2·2·\dots ·2$ 通りありうる。毎回「入れない」と言って得られる空の部分集合から、毎回「入れる」と言って得られる元の集合そのものまでである。

We have studied permutations where all of the objects involved were distinct. What happens if some of the objects are indistinguishable? For example, suppose there is a sheet of 12 stickers. If all of the stickers were distinct, there would be $12!$ ways to order the stickers. However, 4 of the stickers are identical stars, and 3 are identical moons. Because all of the objects are not distinct, many of the $12!$ permutations we counted are duplicates. The general formula for this situation is as follows.

かかわる物がすべて異なる順列を学んできた。物のいくつかが見分けられないときはどうなるか。たとえば、12枚のシールの一枚紙があるとしよう。シールがすべて異なるなら、シールを並べるしかたは $12!$ 通りある。だが、シールのうち4枚は同じ星、3枚は同じ月である。物がすべて異なるわけではないので、数えた $12!$ 通りの順列の多くが重複である。この場合の一般の公式は次である。

In this example, we need to divide by the number of ways to order the 4 stars and the ways to order the 3 moons to find the number of unique permutations of the stickers. There are $4!$ ways to order the stars and $3!$ ways to order the moon.

この例では、シールの重複しない順列の数を求めるため、4つの星を並べるしかたの数と、3つの月を並べるしかたの数で割る必要がある。星を並べるしかたは $4!$ 通り、月を並べるしかたは $3!$ 通りある。

There are 3,326,400 ways to order the sheet of stickers.

シールの一枚紙を並べるしかたは3,326,400通りある。

For the following exercises, determine whether to use the Addition Principle or the Multiplication Principle. Then perform the calculations.

次の各問について、和の原理と積の原理のどちらを使うかを決めよ。そして計算を行え。

For the following exercises, compute the value of the expression.

次の各問について、この式の値を計算せよ。

For the following exercises, find the number of subsets in each given set.

次の各問について、与えられた各集合の部分集合の数を求めよ。

For the following exercises, find the distinct number of arrangements.

次の各問について、異なる並べ方の数を求めよ。