組合わせ論の基礎 (1)：数えるということ

1. 1. はじめに
2. 2. 場合の数は数えられなくてはならない
3. 3. 漏れなく数えるということ
4. 4. 重複なく数えるということ
5. 5. 漏れや重複がなければそれでいいのか
6. 6. 樹形図を使う
7. 7. 出発点に戻ってみる
8. 8. 漏れや重複がない基準や規則性を使う
9. 9. 自然数という数の集まりとその特徴
10. 10. 積の法則で数え上げる
11. 11. 和の法則で数え上げる
12. 12. 分別棚の原理は何を教えるのか
13. 参考文献

1. はじめに

本稿では、中学や高校の数学で「場合の数（順列と組合せ）」のようなタイトルで単元とされている科目の基礎を解説します。大学では「組合せ論（combinatorics）」と呼ばれるため、本稿では組合せ論と呼びます。ここで「基礎」と言っているのは、大学での履修範囲に対して初等的な内容となっている、中学や高校の履修範囲という意味ではありません。大学の組合せ論においても通用する、理論的な基礎とか考え方の原則という意味です^*。したがって、中学生や高校生でも理解できる解説になってはいますが、大学に入れば再び学びなおさなくてはいけなくなるような暫定的で曖昧な話はしていません。僕が思うに、寧ろ初等的な議論を曖昧にするからこそ、多くの学生は煙に巻かれたような消化不良を起こすのだと思っています。そういう数学者や数学教育者の打算的で非論理的な議論の仕方に、僕も含めて数学を苦手だと思っている多くの人は不信感を抱いているとすら言えるでしょう。僕は数学の教員でもなければ数学者でもありませんが、こう言ってよければ「数学を不得手とする専門家」である自負があるため、そういう経験や観点で数学を苦手とする人々にも納得がゆく解説を書こうと思ったわけです。よって、自分は数学ができると（勘違いでもなんでも）思っている人は、本稿を読む必要はありません。あるいは、暇潰しに読みながら、こういうことを理解しないと計算すら始められない人々がいるのだと鼻で笑うのも結構でしょう。しかし、本稿での議論を実際に考えたことがないような人々は、どれほど複雑で高度な計算や証明ができようと、僕に言わせれば数学（数学的な思考）を理解しているとは言えないでしょうし、ましてや他人に教える資格などないと思います。

すでに学校で十分に勉強してきている経験から分かるように、数学とは「みかん1個とりんご1個で合計はいくつでしょうか」という具体的な問題を解くことが重要なのではなく、そういう問題を解くために与えられた状況を「1 + 1」という計算や証明といった形式的な手続きとか考え方に置き換えることの方が重要です。「1 + 1」という計算を、いつまでたっても「みかん1個とりんご1個の合計」だとしか理解できない人は、「鉛筆1本とボールペン1本の合計」の計算はできないままでしょう。あるいは、そういう人のために「A & A」という何か新しい記号で専用の表現を与えて、しかも彼が解答できる答えの表現（つまり「2」に該当する記号、たとえば「B」）も同時に与えたとしても、「1 + 1」と「A & A」が同じことであると理解しない限り、彼は与えられた文字という視覚的な刺激に生理的な反応をしているだけであって、計算しているとは言えないでしょう。事実、彼に「みかん1個とボールペン1本の合計は？」と尋ねてみても、彼には意味が分からない筈です。みかん1個は「1」と置き換えて、ボールペン1本は「A」と置き換えられても、品物が全部でいくつあるのかと言われた場合の「合計」が「+」のことなのか「&」のことなのか分からないからです。

僕が専攻している科学哲学という分野には、昔から “applicability of mathematics” というテーマがあります。これは、ユージン・ウイグナーという物理学者が1960年に書いた “The Unreasonable Effectiveness of Mathematics in the Natural Sciences” という論文で広く知られるようになりました。数学によって、物理をはじめとする数多くの分野で自然現象や物事の性質が記述できます。数学は、自然を記述するために非常に強力な道具ですが、このように色々な物事を記述するために有効であるのはどうしてなのでしょうか。おそらく一つの答えは、数学が無味乾燥で情け容赦のない抽象的かつ形式的な理屈だからだと言えます。数学も、もちろんほからなぬ人類が打ち立てた分野であり、そこで考えたり議論しているのも現実の人間ではありますが、扱っている概念や理論に感情や喜怒哀楽は何のかかわりもありません。数学は、本来はみかんがいくつあるとかボールペンが何本あるとか、そんなこととは関係なく議論できなくてはならないものです。そして、それゆえに幅広い分野やテーマで使える強力な道具なり手だてなり力となるわけです。

冒頭に戻る

2. 場合の数は数えられなくてはならない

僕が所持している高校数学の教科書では、まず次のように話が始まります。（ちなみに、僕が高校生のときに使っていた教科書ではありませんし、僕が高校生のときに使っていた教科書を改めて手に入れたわけでもありません。この二点を書かないと二重に誤解する人がいるので、敢えて注釈しています。）

数学の教員や数学者の多くは、ここで多くの人がひっかかる（しかし当人に強い自覚があるとは限らない）という事実に気づかないため、天下り式に話題を展開していることにも気づかないまま、組合せ論の議論を始めてしまいます。しかし、ここで立ち止まってみましょう。まず、最近は小学校で既に「場合の数（cases）」という単元を習っているようですから、場合の数が何のことなのかは分かっているものとします。念のために復習として説明すると、たとえば1個のサイコロを投げたときに出る目という場合の数は全部で 1, 2, 3, 4, 5, 6 の6通りあります。或る町から隣の或る町まで直に繋がる道が二本あるとき、双方の町を直に行き来する経路という場合の数は合計で2通りです。これだけのことですが、注意しておきたいことがあります。

場合の数について最初に注意したいのは、場合の数は数えられなくてはいけないということです。そんなことは、言われなくても当たり前だろうと思うかもしれませんが、専門用語では、こういう性質を「離散的（discrete）」とか「可算的（countable）」と言います。離散的であるとは、連続ではないという意味です（ここでは直後に後述する可算的な性質と同じく、自然数との対応関係をもつ値の集合として理解してください）。可算的であるとは、一つ、二つ、と数えられるという意味です（厳密には自然数とのあいだに全単射が存在する、つまり濃度が等しい集合のこと。なお、数えられるからといって有限とは限りません）。たとえば、整数は 1, 2, 3, ... などという数のことであり、実際には 1 と 2 のあいだに 1.5 とか 1.298475 といった無数の有理数なり実数があるのはご承知でしょう。よって、1, 2, 3, ... という、それらの間にある無数の数を考えずに飛び飛びの値だけで考えるときに離散的な値を扱っていると言ったりします（なお、離散的という性質は数そのものについて言っているわけではなく、数を何かの計算などの値として扱う場合の分布の話をしているので、「離散的な値」とは言いますが「離散的な数」という言い方は不正確なので、本稿では使いません）。また、連続していない離散的な値だけで議論する数学の分野を「離散数学（discrete mathematics）」と呼びます。原理的に実数を扱えないコンピュータのように（コンピュータで数を処理するときは全て近似値の計算です）、デジタルな 0 と 1 の組合せを原理とするような分野の基礎になっている数学であり、大学のコンピュータ・サイエンス学科へ進学すると、殆どの学生は離散数学に属している組合せ論やグラフ理論や集合論といった分野を学びます。ともかく、サイコロの目を事例として出したように、場合の数は一通りめ、二通りめ、… と一つずつ別々に数えられる「場合（case）」を数えた結果でなくてはなりません。サイコロの目に 2.8 などというものがないように、さきほど挙げた二つの町を行き来する経路についても、一通りめと二通りめしかないのであって、1.8通りめなんてものは考えられません。

次に、上記の引用では「ある事柄が起こる場合の数を知るには」と不正確な書き方をしていますが、厳密には「ある事柄が起こる全ての場合の数を知るには」と書かなくてはなりません。そうでなくては、そのあとに続く二つの条件を必要とする理由がなくなってしまうからです。こう考えると、その次に「すべての場合をもれなくかつ重複もなく数える必要がある」と書かれているのは奇妙に思えるかもしれません。なぜなら、「すべての場合が目の前にあって数えられるなら、その人にはすべての場合が既に目の前に並べられていて全貌が分かってるんじゃないのか。ただ単に数えるだけでいいのに、それがいったい数学の問題と言えるのか」と思えるからです。トランプのカードを机に全て広げ並べて、「さぁカードは何枚あるでしょうか」と言われたような状況だと考えてみてください。でも、場合の数という数学の議論や理論は、単に目の前にある物を指さしながら数える話ではないはずです。よって、この文で言う「すべての場合」は、数えようとしている目の前にある何らかの具体的な対象を「～を」という言葉で指しているわけではなく、もれなくかつ重複もなく数えることによって、すべての場合を数えることになるのだと言っているわけですね。しかし、そんな現代文の解釈をしなくてはならないほど複雑なことを言う必要があるのでしょうか。上に述べたような奇妙さは、単に教科書の書き方が日本語として稚拙だから起きる印象でしかないと思います。僕が彼ら著者に代わって数学の教科書を作るなら、上記の引用文は次のようになるでしょう。

高校生くらいになれば、“certain” の意味で使う「或る」とか「しかるべき」という日本語くらいは慣れるようにしたいものです。数学で国語を教える必要も義務もありませんが、そのていどの素養を求めておいて文章を書いても傲慢ではないでしょう。最初の文節で「全ての場合」と書いた理由は既に述べました。後の節については段落を替えて説明しますが、やや確率の意味合いが含まれているように読めるので、適切な表現かどうかは確信がありません。しかし、最初の教科書から引用した文よりも正確で的確に意味がつかめるという自負はあります。

では次に、全ての場合を数えるとは言っても、どのように数えるべきなのでしょうか。その条件として、漏れなく数えるということと、重複せずに数えることという二つの条件が示されています。そして、これらの条件を両方とも満たすのが全ての場合を数えたときであるため、最初に引用した「ある事柄が起こる場合の数を知る」などという不正確な表現をしてはいけないわけです。

ところで、すぐに幾つかの問いが出てくると思います。そして、たいていの数学の教科書や参考書では素通りしてしまっているでしょうから、本稿では丁寧に議論しておきます。少なくとも、次の三つの問いが考えられます^*。

• 漏れなく数えたことになると言えるには、何が根拠や保証になるのか。
• 数え方が重複するとはどういうことをいうのか。
• 漏れなく、重複せずに数えたら、本当に全ての場合を数えたことになるのか。

冒頭に戻る

3. 漏れなく数えるということ

では、最初の問いを考えてみます。与えられた条件において起きうることがらを「場合」として数えていくときに、漏れなく数えたことになると言えるには、どういう条件が満たされたらよいでしょうか。もちろん、「漏れなく」という言葉のとおり、取りこぼしがないということでしょう。サイコロの目であれば、数えていない目がないということですし、二つの町を直に結ぶ道という経路を調べているなら、数えていない道があってはいけません^*。すると、他に漏れがないかどうかを知るには、どうすればいいでしょうか。

それは、「前提や条件による」という答えが最も適切です。しばしば「数学は国語である」などと冗談でも言われますが、設問の内容を正確に読むことが重要です。サイコロの目と言われたら、サイコロという物体の目を数えることしかやることはありません。そして、特別な説明がない限り常識的には6つの目があるサイコロを想定していいはずです。もちろん、テーブル・ゲームを楽しむ人なら、12面体や20面体や4面体のサイコロがあることはご承知かと思いますが、説明もなくそんな特殊なサイコロを当然のように想定し、設問に「サイコロ」と書くような人が出題する大学に進む必要はありませんし、そんな問題文のテキストは即座に窓から捨ててしまいましょう（ちなみに、僕は中学時代に定期試験で似たような事例に出会い、「このサイコロを仮に4面体だと仮定すると…」と条件を想定して問題を解き、先生から「想定している解答とは違うが、解き方は正しい」と、いくらかの点数をもらったことがあります）。いずれにしても、漏れがないと言えるための根拠は、設問で与えられる前提や条件に見出すしかありません。そして、その前提を理解するときには、問題を作ったり解いたりする僕たち自身の常識も含まれます。そうした前提や条件とは関係なく、どこかに漏れがないと保証してくれる客観的な根拠や基準があるというものでもないわけです。

冒頭に戻る

4. 重複なく数えるということ

しかし、漏れなく数えられたらいいかというと、それだけでは不十分です。したがって、次の条件として重複せずに数えることが求められます。このとき、「重複しない」とはどういう意味でしょうか。いちばん簡単な事例は、やはりサイコロの目でしょう。「1, 2, 3, 4, 4, 5, 6」と数えたら、4 の目が重複しています。「1, 1, 2, 3, 4, 5」と数えたら、6という（場合の数を数えた結果としての）数としては正しくても、数え方としては正しくないと言えます。解答する方法が数を単に記入するだけなら正解になるかもしれませんが、このような人は別の問題を解くときに間違う可能性があります。経路の問題を解いているときも同じことです。A 町と B 町を直に結ぶ道を数えているときに、A から B への道を数えた後に B から A への道を数えて、道が二つあると考えるような人は、経路を重複して数えていることになります。

考えている対象としての物事が重複しているかどうかは、もちろん目で見て分かるという場合が圧倒的に多いでしょう。「1, 4, 7, 2, 5, 6, 4, 3, 0, 2, 4, 1」という数字の集まりで1や2や4という数字が重複していることは、見れば分かります。そして、現実に数学の試験問題とか会社で何事かを設計したり分析しているときも、結局は目で見て同じものがあるかどうかを確かめているわけであって、ここには数学的に厳密な理論とか基準なんて、実はないのです。重複せずに数えるためには、何か大層な数学理論とか概念とか、あるいは予備校で名物講師が教える秘訣なんてものはありません。一つ例を出しましょう。

• sfQhAIdDiFQEy9iWpmHT2Az3wCp16fat3ferDaqtklgE6pwf
• SlE9YeOR2r3rcJWzyCbZMTlhuov4aVA1hS50vJPzeNtBZZMm
• LQP0cOJtslyYMcAFu0VcJXxTlA4IYUd70hwJM2WgxRV0TLy9

上の文字列三行の全体にわたって、重複している英小文字を全て挙げてみてください^*。ふつうは、これを1分以内で解答するのは非常に難しいと思います（ちなみに、僕は解答する速さなんてどうでもいいと思ってるので、試してもいません。そして小学校のときに受けた知能指数のテストでも同じことをやって、知能指数37というスコアをもらって逆に教師に怒られたことがあります。でも、知能指数37の科学哲学者がいて何がいけないのでしょうか。知能指数が高いと評判の人たちだって、その大半がたいしたことない企業の社長や特段の業績も上げていない大学教授、それに生産性のないテレビ・タレントではありませんか）。つまり、重複しているかどうかを目で見て確かめられるていどの問題しか、重複しているかどうかを確認することが解答するために重要な手続きとなるような事例はないとすら言えます。実際に、受験数学では明らかな事例がたくさん見つかる筈ですが、「A, B, C, D から二文字ずつ取り出して云々」といった設問のように、重複する可能性をまったく心配しなくてもよい問題は、最初から設問で考察する対象が重複していないことが分かるようになっています。そして逆に、重複する可能性が解答するにあたっての鍵となるような設問なら、わざわざ「A, B, B, C, A という文字があって云々」などと、視覚的に重複している対象があると丁寧に知らせてくれた上で、解答するための条件を示しています。よって、或る前提なり条件が与えられている状況で、起こりうる可能な結果を全て列挙した中に重複があるかどうかを心配するべきかどうかは、設問を読んだ時点で分かるようになっている筈なのです。そして設問を読んで起こりうる結果が重複する可能性があると分かれば、逆にどういうときに重複するのかを注意すれば正しい解答を導けるということも分かるようになっています。

冒頭に戻る

5. 漏れや重複がなければそれでいいのか

では最後に、漏れがないということと、重複がないということという、これら二つの条件さえ満たしていれば（他に条件がないとして）求めるべき全ての場合の数を数えたと言えるのでしょうか。この問いへ答えるために、場合の数を数えていると判断できるための必要条件と十分条件を考えてみることにしましょう。目標は、求めるべき全ての場合の数を数え上げることでした。このことを記号で ^^S^^ と略記します。そして、

• 漏れなく場合の数を数えている： ^^C^^
• 重複なく場合の数を数えている： ^^M^^

としておくと、「漏れなく場合の数を数えていることが、全ての場合の数を数えることにとって必要条件になっている」ということを ^^S \implies C^^ として表記できます。このような記号を使うと、考えるべき条件どうしの関係という組合せ（これを場合の数として課題にしてもいいわけですが）を次のように簡単に列挙できます。ここで複数の条件が共に満たされることを「 ^^\land^^ 」という記号で表記すると、僕たちが問題にしているのは、 ^^C \land M^^ つまり「^^C^^ と ^^M^^ の両方が条件として満たされていること」が、^^S^^ であることにとって必要かつ十分な条件になっているかどうかです。必要かつ十分であるということは、必要条件でもあり十分条件にもなっているということですから、記号で表すと次のようになるでしょう。

• (^^C \land M \implies S^^) ^^\land^^ (^^S \implies C \land M^^)... 5.1

論理学では、これを ^^C \land M \iff S^^ のように表記します。もちろん、ここでは論理学の解説をしたいわけでもなく、あるいは記号をむやみに使って話を（場合によっては）ややこしくしたいわけでもありません。あくまでも、議論している状況とか議論する話題を目で見て単純な表記として見通しよくするための技巧を採用しただけのことです（式 5.1 を日本語で言い換えてみてください）。内容や意味を正確に理解せずに記号を単に並べるだけなら、どれほどエレガントな記号を格好よく並べてみたところで、僕ら哲学者に言わせればクズみたいな茶飲み話でしかありません。

では、式 5.1 が正しいのかどうかを吟味しましょう。前半の ^^C \land M \implies S^^ は、漏れなく重複なく数えることが、全ての場合の数を数えることにとって、十分条件になっていると言っています。これはつまり、^^C \land M^^ が真である状況で ^^S^^ が偽となる状況はないという意味です。漏れなく、重複もしていないのに、数えていない場合が一つでもあれば、それは場合の数を全て数えていることにならないのは当たり前でしょう。しかし、果たしてそんなことがあるのでしょうか。なぜなら、既に僕たちは漏れなく数えている（^^C^^）筈だからです。そこに重複があれば数えすぎにはなりますが、漏れなく数えているのに全てを数えていないなんてことは、矛盾しています。すると、漏れなく数えてはいても、そこには数えすぎているかどうかが分からないという問題が残るだけとなります。よって、数えすぎてはいない、つまり重複がないということも同時に満たされなくてはならないわけです。こうして、^^C \land M \implies S^^ は正しいと言えます。

次に、^^S \implies C \land M^^ を考えます。この表現は、漏れなく重複なく数えることが、全ての場合の数を数えることにとって、必要条件になっているという意味になります。先の事例と同じように、これはつまり、^^S^^ が真であるためには ^^C \land M^^ が偽であってはならないという意味です。実は論理学の議論として言えば、^^S^^ が偽であり ^^C \land M^^ が偽であっても、^^S \implies C \land M^^ という式は真であると評価されます。しかし、前提も結論も偽になっているような状況で、場合の数を本当にちゃんと数えているかどうかを議論する意味はないでしょう。僕たちが関心を持っているのは、もちろん正しい前提や真となる条件であって、間違いや誤りを仮定したり前提にした、出来損ないの SF や陰謀論のような議論を延々と続ける価値はありません。よって、前提である ^^S^^ が真であるなら（「求めるべき全ての場合の数を数えている」という、本来の目的を表す条件が偽であると仮定するのは、そもそも変ですよね）、^^S \implies C \land M^^ という式が真だと評価されるためには ^^C \land M^^ が真となっている必要があります。そしてもちろん、必要とされる全ての場合の数を数えているという状況において、漏れなく数えていなかったり、数え方が重複していたりするなんてことはないでしょうから、^^S \implies C \land M^^ も正しいと言えます。

以上の議論から、^^C \land M \implies S^^ と ^^S \implies C \land M^^ はどちらも正しいので、これらを合わせた式 5.1 も正しいと言えます。こう言っては身も蓋もありませんが、「必要とされる全ての場合の数を数える」ということがどういうことなのかは、寧ろ漏れなく数えたり、重複なく数えるということでしか正確に説明したり定義できないことだと思います。

冒頭に戻る

6. 樹形図を使う

必要とされる全ての場合の数を求めるときには、上の例題にあるような「樹形図（tree diagram）」を使うと分かりやすくなることが多々あります^*。とは言っても、求めたい場合の数が、或る物体とか状況を説明する図などで漏れなく重複せずに描かれていたり示されていて、その数を単に数えたらいいだけなら、樹形図を使う必要はありません。6面体のサイコロの目という場合の数が全部でいくつあるか（正確に設問を表現すると、こういう回りくどい書き方になります）は、単にサイコロの目を数えたらいいだけであって、1, 2, 3, 4, 5, 6 などと樹形図を描く必要はないでしょう。樹形図は、求めたい場合の数が複数もしくは複合的な条件や前提をもつときに効果があります。ただし、樹形図を描くこと自体が大変な作業になるほどの複雑な条件ではいけません。なぜなら、樹形図を間違って描くと、樹形図こそがミスや勘違いの原因になってしまうからです。

さて、上に紹介した例題は樹形図を描いて場合の数を求めよと述べています。したがって、樹形図を描くだけで何時間もかかるような作業を要求する問題ではないということが明らかです（大学で学ぶ数学の勉強では、そんなことは誰も保証してくれませんが）。そして、樹形図が複数あるいは複合的な条件や前提をもつときに効果があると説明したように、上記の例題も、五つの数があるということ、それらの数を使って3桁の整数を作るという二つの条件があります。もちろん、これらはどちらも、全ての場合の数を数えようとするに当たっては「場合」の一つであるために満たされなくてはならない条件です。0, 0, 1, 1, 2 という五つの数は使っていても2桁や4桁の整数は求めるべき「場合」の一つに該当しませんし、3桁の整数とは言っても前提にある五つの数とは違う数を使って568なんて整数を「場合」に含めてはいけません。そして、設問に書かれていないからと言って忘れてしまってはならないのが、これは求めるべき全ての場合の数を数える問題だということです。つまり、与えられた数で3桁の整数を作ればいいだけではなく、それは場合の数である以上、これまで説明したように漏れがあってはいけませんし、重複があってもいけません。

上の図は、与えられた五つの数を単純に三つ並べたときの樹形図です。ただちに分かるように、この樹形図には「3桁の整数」という条件を満たしていない並べ方があるため、答えには使えません。3桁の整数であるためには、先頭つまり百の位が0ではいけないからです。012は12という整数です。よって、先頭が0になっている並べ方は、数える対象から除外すべきです。

次に、先頭が1になる並べ方は重複しているため、ここでもどちらかの並べ方（上の図では赤くなっている方）を取り除かなくてはなりません。場合の数として数えるために求められる条件の一つは、重複があってはいけないということでした。

そして、先頭の桁が1か2である並べ方だけを重複なしに取り出せました。もともとの樹形図が並べられる数を全て並べた樹形図だったので、ひとまずそこでは漏れがないという条件は満たしていたわけです。しかし、それだけでは他の条件を満たしていないため、ここでは条件にしたがって対象を絞っています。対象を絞って並べ方の数が単純に少なくなったからといって、漏れがあるかのように考えるのは錯覚です。しかし、まだ上から二桁目や三桁目にも重複があるため、これらを除外していかなくてはなりません。上の図では百の位が1の場合について、重複している並べ方を赤く示してあります。百の位が2の場合はどうなるか、これはみなさんが考えてみてください。こうして条件を満たす並べ方だけを選んでゆくと、結果として求めるべき全ての場合の数は11通りであるという答えが出ます。

冒頭に戻る

7. 出発点に戻ってみる

ここで、改めて議論を初めの段階に戻してみましょう。これまでに、漏れなく数えること、重複なく数えること、という二つの要件で、或る条件のもとで数え上げるべき全ての場合の数を正しく数えていることになるのかどうかを考えてきました。樹形図を使って描けるような、最初から答えとして想定できる場合の数が少なく見積れるとか、あるいは樹形図を誤って描いてしまう恐れのなさそうな見込みがあってこそ、つまり数学の問題になりそうな状況こそ、漏れなく重複なしに樹形図を描いて解けるというわけです。要するに、ひょっとすると数学の教員も文科省の官僚も予備校の講師も即座に答えが出せないかもしれない、場合の数として合計がどれだけの数になるのか直観的には分からず、複雑で条件がはっきりしない現実の状況なんて扱いません。そういう現実の圧倒的な実例とは違って、数学という教育科目の中でうまく扱えるようにお膳立てされた事例が、「場合の数」として教えられたり取り組まれている単元の例題や試験問題なのです。現実は厳しいですねぇ。勉強もまた一つの現実ではありますが。

こうした事情があるために、皆さんも中学生や高校生の頃に感じたことがあるかもしれませんが、教科書や参考書や問題集に出てくる設問に描かれた状況は、それを考える必要がどこにあるのか、いまの自分には分からず、僕らの生活や人生と殆ど関係のない、どうでもいいことであるかのようです。椅子が円形に6つ並んでいて云々と言われても、座りたいなら隣の人を押しのけて座ればいいと思う人がいたり、しかじかの中からこれこれを幾つ取り出して持参しようなんて考えなくても、最初から全部持って行って求められたものだけ相手に渡せばいいのだと感じたりします。そこに、数えなくてはいけないとか選ばなくてはいけないという事情や強い理由がないなら、いちいち物を数えたり該当する物を拾い上げるという作業そのものが手順として非効率となる原因になるかもしれませんし、或る種の形骸化した儀式のようなものとして自分たちの暮らしとは縁遠いことだという印象を植え付けるかもしれません。もちろん、数学的な思考の効用とか強みとか便利さは、例題で描かれた状況が自分にとって親しみやすいかどうかとは関係がありません。繰り返しますが、数学が強力な道具として使える理由の一つは、敢えて言えば数学が無味乾燥で形式的であり、みなさんの生活とは関係ないからなのです。みなさんが「あーつまんねーなー」と感じるところ、それこそが逆に数学がもつ特性なのであり、道具として有効に使えるかどうかは、皆さん自身が数学をどう使うかにかかっているのです。しかし、そのことを丁寧に教えたり説明しない限り、教科書や授業で教えられるとおりに覚えて実行せよと言われても、なかなか納得はできないでしょう。簡単に言ってしまえば、人は勉強や学問をしなくても生きていけるのです。教育者の多くは、近代国家で採用され大多数の子供が参加させられている「学校教育」という行政システムに安住してしまい、このことを忘れてしまっていると思います。

中学生や高校生が学んで当たり前のこととして「場合の数」という単元を教えられているのとは違って、少なくとも大学で教えられている数学という分野では、組合せ論を学ぶべき理由や効用や魅力を説明したりアピールする必要があります。大学もしょせんは高等教育という行政システムの一つであるため、大学の研究者は特殊な場合を除けば研究だけしていればいいというわけにはいかず、本人の得手不得手や好き嫌いとは関係なく学生を教える職責があるからです（教員としての評価には色々と言えることはあるにしても、不完全性定理を証明したクルト・ゲーデルという人物ですら学生を教える教員として過ごしていました）。したがって、これまでの各節で解説してきた問いについても、大学の数学として精密に展開するというだけではなく、その根拠や基礎となっているアイデアについても議論されており、その中には数学的な思考の力や効用あるいは魅力を説明するために有効な内容が数多くあります。

そこで、次のように考えてみましょう。漏れがないかどうかとか、重複していないかどうかを、与えられた条件の中だけで確かめようとすると、既に述べたように「サイコロ」と言われたら6面体だと想定しようとか、僕たちの常識が正しいとか、設問（出題者）が想定する常識の範囲や理解度は誰でも似たようなものだと、仮定していなくてはならないようです。しかし、本当に漏れがないのかどうかは、与えられている条件や状況を僕らがその常識の範囲でどう理解するかに依存するため、明確にこういうことが分かれば漏れがないのだと言えるような、どういう状況にでも当てはめられる基準はないかもしれません。そしてこのような話は、実は人工知能の理論を研究している人々のあいだで昔から難しいと評価されている「フレーム問題（frame problem）」と呼ばれるテーマと同じ話なのです。人工知能をプログラミングして何か与えられた課題を実行して解答を出力するということは、つまりそれを有限時間で解決できるようなアルゴリズムがあると想定しているのと同じです。アルゴリズムというのは、一つずつ手順を追って処理すると答えが導けるという手続きのことであり、コンピュータに実行させる（まともな）プログラムは、アルゴリズムの典型的な事例です。しかし、或る問題を解決するために必要な条件がどれだけあるのか分からなければ、当然ですが有限時間内に処理が終わるのかどうかは決められませんし分かりません^*。しかし、数がどれだけあるのか分からないという状況だけではなく、そもそも何が条件として必要なのか分からないという状況もあります。或る問題を解決するために必要な条件の一式を決めている範囲を「フレーム」と言います。“frame of reference”（参照枠）という言い方で、何かを考えるときに必要とされる（必要十分かどうかは分からない）関連情報とか背景知識のことを意味することがあるため、見聞きしたことがある方もいるでしょう。

フレーム問題を説明するために使われる典型的な事例は、たとえば人工知能（を搭載したロボット）に買い物をさせることです。或るベンチャー企業が開発した人工知能を搭載するロボット、「ソンマサヨシ君」に買い物を頼んでみましょう。

1. 僕「ドン・キホーテで、『胡散臭いチョコレート』を何枚か買ってきてくれないか。」
2. ソンマサヨシ君「ピピピピ…（ドン・キホーテの店舗を検索している）…『胡散臭いチョコレート』とは何ですか。」
3. 僕「菓子類のコーナーにある、タイで製造された安物のチョコレートだよ。」
4. ソンマサヨシ君「ピピピピ…『安物』とは幾らのことですか。」
5. 僕「税別で100円以下のチョコレートだね。」
6. ソンマサヨシ君「ピピピピ…『何枚か』とは何枚のことですか。」
7. 僕「チャージしてるお金をいくら持ってるのか知らないけど、２枚から４枚のあいだで、買えるだけ買ってきたらいいよ。」
8. ソンマサヨシ君「ピピピピ…了解しました。行ってきます。」
9. 僕「頼んだよ。」

残念ながら、ソンマサヨシ君は帰ってきません。なぜなら、ドン・キホーテの店舗を検索して、最初にヒットした「MEGAドン・キホーテ新川店」（北海道札幌市北区）へ行ってしまったからです。そこまで行く途中に、どこかの山中で電池切れで停止してしまいました。僕はソンマサヨシ君に、「ここから一番近い店舗で買ってきてくれ」と教えなくてはならなかったわけです。みなさんは、「そんなの当たり前だろう」と突っ込むかもしれませんが、その「当たり前」という判断の基準を人工知能にどうやってアルゴリズムとしてプログラミングすればいいのか、実は世界中の人工知能の研究者が50年以上も研究していながら、誰も良いアイデアを思いついていません^*。

このようなわけで、「物事を数える問題なら何でも解決できる完璧なルールというものはありません。しかし、さまざまな場面で何度も扱う多くの問題は、物事を数える幾つかの重要な技巧とルールを使って解けます」 [Rosen, 2000:115]。離散数学は工学と密接な関係にあるため、こうした技巧や手続きを工夫して多くの問題を解いています。一つの公式で何でも解けるというわけにはいきませんが、どういう状況でどういう考え方を当てはめられそうかと考えることも、数学的な思考の一部と言えるでしょう。

冒頭に戻る

8. 漏れや重複がない事柄や規則性を使う

では、漏れや重複なしに物事を全て数え上げるという課題には、教科書や参考書で紹介されている図や公式が当てはまるかどうかという基準しかないのでしょうか。もちろん、どういう状況でも使える決定版の基準というものがないということは十分に説明してきましたが、他に基準がないかと言えば、学術研究の分野である組合せ論には他の基準もあります。それは、見出しに述べているように、漏れや重複がないと（定義によって）分かっている事柄や規則性に照らしてみて確かめるという基準です。その基準を理解するために欠かせないのが、高校の数学でも取り上げられている「集合（set）」というアイデアです。

ここで、あなたが図書館から借りた本を一冊だけ手に取っていると想像してください。あなたは本を開いて、読みたい文章が書かれているページを目次から見つけて、そのページを開きます。23ページだとしましょう。そこから27ページまで、論文とかエッセイが、ともかくひとまとまりの文章として続いています。とても役に立つ内容で、後から何度でも読む必要があると思ったあなたは、このひとまとまりの文章を近くのコンビニエンス・ストアでコピーすることにしました。その本は見開きでコピーできる判型ですから、1枚で2ページ分をコピーできます。1枚のコピー料金は税込みで10円だとして、全部で幾らの料金がかかるでしょうか。ここまでは、中学生や高校生でなくても「30円」だと分かる問題でしょう。ちなみに、コピーしたいページが全部で奇数だけあるなら、左ページから始まっても右ページから始まっても答えは同じです（ここで考えている例題なら、23ページから27ページまで5ページ分あります。引き算した4は答えではありませんよ。偶数だと、左右どちらのページから数えるかによって、見開きのコピーを取るために必要な枚数が違ってきます）。そして、ここで説明したいのは、このような問題が簡単に解けるのは、書籍のページ番号（業界用語で「ノンブル」と言います。なお、序文などローマ数字で印刷されるページや表紙、あるいは白紙などは別の扱いとなっています。また、DTP のデータでは設定されていても、必ず印刷されるとは限りません）の並びが、或るページから別の或るページまで、漏れなく、重複なしに一ページずつ数えられるからなのです。そして、このような規則性があると分かっていれば、その本を持っていない人にも同じ文章が何ページから何ページまであって、コピーすれば幾らになるかを教えられるでしょう。しかし、もしその本にミスがあって、27ページに「26」と印刷されていたら、「26」と印刷されたページが重複することになります。そして、その次のページ（正しくは28ページの筈）に「27」と印刷されていたら、その本を持っていない人にコピーするべきページを伝えるには、少し複雑な説明をしなくてはならなくなるでしょう。あるいは、もしその本にミスがあって、「25」と印刷するべきページに番号が印刷されておらず（つまり漏れがあるということです）、次のページに「25」と印刷されて後が続いていた場合も、その本を持っていない人には面倒な補足説明が必要となります。たいていの出版物には、こういう編集のミスがないという信頼があってこそ、僕たちは一ページずつ数え上げなくても、必要なページ数（つまりはコピーするべき枚数）を計算できるわけです。では、僕らがこうあるべきだと期待したり想定しているページの並び方とは、どういう性質や特徴をもっているのでしょうか。

これまでに見てきたような、さまざまな状況を仮定した問い、つまり「～であるような～は、全部で幾つあるのか」という問いに答える手法は、大きく二つのタイプに分類できます [Mazur, 2010: 1]。一つは「列挙（enumeration）」と呼ばれていて、これは樹形図などが典型であるように、条件を満たす事柄を全て書き並べることです。そしてもう一つが「数え上げ（counting）」と呼ばれるわけですが、この言い方には「数え上げる」という手続き的な意味合いがあるため、どうしても列挙と混同させてしまう不適切な印象を受けますし、日本の数学では “enumerative combinatorics” を「数え上げ組合せ論」と呼ぶ伝統があるため、更に混乱が生じてしまいます。かといって “counting” と英語で書いたところで、やはり「カウントする」という表現には物事を一つずつ指折り数えたり、あるいはボクシングで倒れた選手がノック・ダウンされたかどうか審判がコールしてゆくといった印象があるため、「具体的に一つずつ数えるわけではなく計算して個数を導き出す」という意味合いが薄れてしまうかもしれません。ともかく、二つの違いは明らかでしょう。「1から10までの自然数から3で割り切れる数は幾つあるのか」という問題への答えは、3, 6, 9 といったように一つずつ数えて答えを出せます。大多数の中学生以上の人にとっては、4や8が3で割り切れるかどうかを計算して確かめる必要などないでしょう。しかし、「アルファベットを10個だけ重複を認めて並べるなら、全部で何通りになるか」と問われた場合に、AAAAAAAAAA から始めて ZZZZZZZZZZ まで一つずつ書き出すよりも、^^26 ^{10} = 141,167,095,653,376^^ と電卓やコンピュータで計算するでしょう（ちなみに、僕は PHP というプログラミング言語で php -r "echo pow( 26, 10 );" と打ち込んで計算しました）。

以上のように、列挙するだけで答えられるとは限らない問題がいくらでもあります。条件が少しでも変わると、途端に指折り数えるわけにはいかなくなる事例がたくさんあるということが想像できるでしょう。そこで、与えられた条件から全ての場合の数を数え上げる（ここでは「算出する」という意味）手法が必要になります。もちろん、高校の数学を勉強した方であれば、既に積の法則とか和の法則とか ^^{}_n P_r^^ や ^^{}_n C_r^^ と表現する階乗を使った計算はご存じかと思います。しかし、それらの法則を使えば、漏れなく重複もない数え方で全ての場合の数を数えたことになる数を算出しているのだと言えるための証明を、学校や予備校の授業で見聞きした方は少ないと思います。そこで、そうした法則や計算に根拠があることを納得するためにも、漏れがなく、重複もない、そういう要素から作られている基準を使ってみましょう。そして、強力な一つの基準として知られているのが、「自然数（natural numbers）」と呼ばれている数の集合です。

冒頭に戻る

9. 自然数という数の集まりとその特徴

では、自然数について、漏れがなくて重複もない物事の基準として使えるのかどうか考えてみましょう。なんでいちいち「考える」のかというと、直感的には使えそうであっても、直感的には正しいかどうか分からないほど多くの数にも当てはまるかどうかは、やはり証明という手続きに訴えるしか納得できる理由がないからです^*。ひょっとすると、僕らが自然数について正しいと思っている特徴は、僕らが見聞きできる範囲の小さな数にしか当てはまらないかもしれません。さてそうすると、まず自然数とはどういうものなのかを正確に知っておく必要があります。これはつまり、自然数という数についてではなく、自然数と呼ばれることになるような数だけがもつ規則性や特徴の話をすることになります。そして、こういう規則性や特徴をもつ数だけを考えるために、数学では「集合（sets）」というアイデアを使います。1とか5とか3398といった、個々の数についてではなく、それらが「自然数」であるための特徴について議論するのに有効なアイデアです。個々の数についてしか議論できないなら、既に述べたように僕らは自分が知っている8とか256とか98748729といった具体的な数についてしか議論していない可能性（つまりリスクや懸念）が残ってしまうからです。自然数であれば何であっても言えるような特徴について議論すれば、僕らが生活で扱ったことがない他の全ての自然数にも、同じように当てはまる議論をしていると言えるでしょう。

では、自然数をもう少し正確に理解してみましょう（大学で学ぶ公理的集合論のように順序数論を仮定するほど厳密ではありませんが）。第一に、自然数と呼ばれる数には順序があります。これは、二つの自然数 ^^x^^, ^^y^^ を自由に選ぶと、^^x^^ と ^^y^^ には次の三つの関係のどれかが必ず成立するということでもあります^*。

• ^^x > y^^,
• ^^x < y^^,
• ^^x = y^^

次に、自然数どうしを足したり掛けても答えは自然数です。そして、加法（足し算）と乗法（掛け算）には、よく知られている次のような規則性があります。

• ^^a + b = b + a^^... 加法の交換法則
• ^^( a + b ) + c = a + ( b + c )^^... 加法の結合法則
• ^^a \times b = b \times a^^... 乗法の交換法則
• ^^( a \times b ) \times c = a \times ( b \times c )^^... 乗法の結合法則
• ^^( a + b ) \times c = a \times c + b \times c ^^... 分配法則

冒頭に戻る

10. 積の法則で数え上げる

ここで、場合の数で扱われる例題の条件を一つだけ考えてみましょう。みなさんも、何かオンラインのサービスを使おうとしたり、あるいはゲームにユーザ登録するときに「パスワード」を設定する筈です。パスワードというのは、サービスごとに使える文字の種類が違っていますが、どこのサービスでも数字や英文字（小文字と大文字）くらいはパスワードの文字として使えるようになっている筈です。そこで、24桁のパスワードを設定することにしました（なお、企業で情報セキュリティの部長をやっている立場から、パスワードは桁数が多いものを設定してもらいたいとは思うので、いくら最小限で6桁や8桁のパスワードでも構わないサービスだからといって、そんな小さい桁数でパスワードを設定するのはお勧めしません）。では、パスワードとして設定できる文字の並び方は、全部で幾つあるでしょうか。

まず、1桁目から24桁目までを自然数の順番で24と数えることはできそうです。例題の条件で「24桁」と明示されているわけですから、そもそもこの例題に「20桁目は本当はない」とか「15桁目は重複している」などという隠れた前提があると、そんなことは誰も「聞いてないよぉ！…」としか言いようがないでしょう。問題を解きようがなくなるからです。そして、そんな問題に答えようとする必要なんてありません。人が出題すれば、そういうバカげた前提も可能になりますが、それこそ「自然」にそういうバカげた前提などない（と仮定するのが科学であり数学である）からです。次に、各桁で使える文字の種類を数えてみると、数字は10個、英文字は小文字と大文字がそれぞれ26個ですから、^^10 + 26 + 26 = 62^^ です。そして、先に述べたとおり自然数の加法には交換法則があるので、これを ^^26 + 26 + 10^^ と計算しても同じことですし、^^26 \times 2 + 10^^ と計算しても同じです（ただし、奇妙な新興宗教を信じている学校教師がいて、これを「^^2 \times 26 + 10^^」と書いたら誤りだと喚き始めますから、注意しましょう）。なお、括弧は使っていませんが、標準的な解釈では乗法の計算が加法の計算に優先しますから、「^^26 \times 2 + 10^^」は「^^(26 \times 2) + 10^^」という意味になります。

このように準備してから1桁目を考えると、まず桁が一つだけなので、使える文字の数は全部で62となります。もし例題が1桁のパスワードなんていうバカげたものを求めているなら、62通りのパスワードがありますというのが答えになるわけですが、現実には62通りしかないパスワードなんて怖くて使えませんね。さて、桁を2桁目に進めると、2桁目にどういう文字を選ぶかは、もちろん1桁目にどういう文字を選んだかとは関係がありません。しばしば、パスワードの強度を測定するサービスというのがあって、そういうサービスでは同じ文字が連続しないように並び方を検査していますが、ここではそんな必要はありません。全ての桁が同じ文字になってしまうとしても、ここではそういうパスワードが現実に危険であるかどうかの議論をしたいわけではなく、全部でどれだけの文字の並びがあるのかという話だけをしているからです。よって、2桁目でも選べる文字は62通りあります。すると、1桁目で何か選んだ文字があり、そして次に2桁目で文字を選ぶことが1桁目で選んだ文字と関係がないのであれば、パスワードが2桁として求められている場合に、全部でどれだけの並び方があるのでしょうか。考え方としては、1桁目に何か文字を選んだとして、それの後に2桁目として続く文字が常に62通り（1桁目にどの文字を選んだかは関係ないのですから）あるわけなので、全部で ^^62 \times 62^^ と考えるのが正しいですね。これは、前の節で説明したような樹形図を描いてみたら、視覚的にも分かるでしょう。1桁目に（パスワードは整数ではないので、1桁目に0があっても構いません）「0」を選ぶと、0に対して2桁目にも0を選ぶ、次に0に対して2桁目に1を選ぶ、そして0に対して2桁目に2を選ぶ・・・とやっていくと、1桁目に選んだ文字1文字ごとに2桁目に文字を全部で62だけ選べるということが分かる筈です。しかし、このやりかたは桁が多くなればすぐに作業として難しくなります。いま「描いてみたら」と気軽に書きましたが、実は2桁だけでも全部で1,612通りの並び方になり、3桁では10万通り以上、4桁になると600万通り以上、そして5桁では4億通り近くを紙に書き出さなくてはならなくなります。前節でも述べた通り、条件が少しでも変わると手作業では難しくなるような列挙や樹形図という方法では限界があるのは明らかです。ここで役に立つのが、以下のような「積の法則（rule of product or multiplication principle）」です。

ここで考えているパスワードの文字については、各段階で選べる選択肢の数は常に62ですから、上記の積の法則を使うと、^^62^{24} = 141167095653376^^ という答えが出せます。では、積の法則を使っても漏れや重複がないと言える理由はなんでしょうか。

それは、まず初めに各段階で選ぶという手続きが独立しているという特徴に求められます。他の段階で行う選択とは関係がないという意味ですから、ここで考えている例題でも言えるように、1桁目で何の文字や数字を選ぼうと、そのことが8桁目や23桁目でどういう文字や数字を選ぶかとは何の関係もないということです。それぞれの桁で文字や数字を選ぶという操作は、他の桁で何かを選ぶという結果とは独立しているというわけです。この性質により、まず各桁で選ぶという操作や手続きには重複がないという特徴が保証されます。もし重複していれば、17桁目で選ぶという処理や手順が再び繰り返されることになるので、その結果が同じであろうと違っていようと、どちらが正しいのかという問題が起きます。そして、もちろんどちらかが間違っているわけですから、そのような選択を行う手続きには間違いがあるということになります。

次に、漏れがないとはどういうことなのかを考えてみると、それはつまり自然数の一部と比較したときに対応関係があるということです。自然数は無限個あるわけですが、その一部を「部分集合」として取り出せます。たとえば0から100までの自然数からなる部分集合とか（数学には0を自然数に含めるかどうかで「流派」が分かれると言います。僕は数学者ではありませんから、職業プログラマとして扱い慣れている配列の添え字として、0から始まる数字の列を自然数として仮定しておきます。というか、それぞれ議論するときに前提として明記すればいいだけの話ですから、あまり流派は気にしていませんし、本稿での議論を左右するような事ではないと思っています）、51から398までの自然数の部分集合とか、いくらでも好き勝手に部分集合は作れます。しかし、その集合に属している数が自然数であることと、特別な条件がない限りは一定の数が属している部分集合に欠落した数、つまり漏れはないということが保証されます。単に45から867までの自然数を集めたというだけの部分集合なのに、何の根拠や追加の前提もなしに実は76が欠けていますとか、あるいは143はありませんとか、そんなことはありえないというわけです。これもまた、順序という概念を正確に導入しなければ議論できない点ではありますが、ひとまず一定の個数を開始の数から終りの数まで含んでいる自然数の部分集合に欠落した数はないという前提で進めてください。

すると、パスワードを設定するという例題では、各桁で使える文字として数字とアルファベットで合計が62個だという数に、重複も漏れもないという前提が成り立ちます。10個の数字は特別な仮定がない限りは、10個の自然数からなる部分集合と対応していますし、それぞれの数は独立しているからです。同じくアルファベットの大文字と小文字についても特別な仮定がありませんから、それぞれの文字は独立しているので、合計は26文字と26文字で52文字です。よって、数字と英文字から合計した62文字にも同じ性質が言えるというわけです。そうして、それぞれが或る桁においてパスワードに使える文字としてどれでも自由に、前後の桁でどういう文字を選んだかとは関係なく選べるという点で、それぞれの桁は独立しています。また、それぞれの桁は1桁目から24桁目まで欠落した桁はないということが例題の条件から明らかでしたので、桁についても重複や漏れはないとわかります。あとは、1桁目から手続きを始めてゆき、62個の中から或る数字か文字を選んだという場合に、次の2桁目でも62個の中から或る数字か文字を選ぶという場合が続き、これを24桁目まで繰り返すということは、^^62^{24}^^ という計算をすることでしかないと分かるでしょう。ただし、漏れや重複がなくても別の条件や規則性を使って異なる結果を計算できますから、漏れも重複もないということは積の法則で計算できることに対して、十分条件ではなく必要条件です。よって、積の法則が当てはめられるなら漏れも重複もないと言えますが、その逆は必ずしも言えません。

冒頭に戻る

11. 和の法則で数え上げる

もちろん、自然数の部分集合に属している数は、特別な追加の条件がない限りは順番どおりに並んでいます。1から5までの自然数という部分集合を考えるときに、{1, 2, 3, 4, 5} とは違う他の特徴をもった集合を考えなくてはいけない理由というのは、ありません。{1, 2, 2, 4, 5}（重複している）とか、{1, 3, 4, 5} とか（漏れがある）とか、そういう集合でありえるなどと考えたり心配する必要はないのです。そこで、また別の例題を取り上げてみましょう。或る町 A から別の或る町 B まで、直に接続している道路が2本あるとします。そして、二つの町を直に結んでいる鉄道の路線が1本あります。すると、これら二つの町を直に行き来する経路は合計で幾つあるのでしょうか。

ぶっちゃけ、こんな手の込んだイラストをわざわざ作って見せるまでもない話でしょう。或るやり方が二通りあって、別のやり方が一通りあるなら、それらがお互いに依存関係になければ、単純に合わせて考えて三通りだとすぐに分かる筈です。これを「和の法則（rule of sum or addition principle）」として、もう少し正確に表現しておくと、次のようになるでしょう。

「二つの事柄は同時に起きない」という条件は、町どうしの経路という事例で言えば、A町からB町へ行くのに道路と鉄道を同時に使う行き方とか、道路を二本とも通る順路というものがないという意味になります。集合の用語を使うなら、^^m^^ 通りの仕方を集めた集合 ^^M^^ と、^^n^^ 通りの仕方を集めた集合 ^^N^^ については、^^M \cap N = \varnothing^^（互いに素である）であると表現できます。和の法則は、これが成り立つという条件が明らかであれば、特に詳しい解説をする必要もないほど自明であるように思えます。よって、大学で使う組合せ論の教科書でも、和の法則を割愛している本があります（目次に掲げて一つの単元として教えていないというだけではなく、そもそも積の法則とは別に和の法則というものがあるということすら書いていない教科書もあります）。しかし、ここではこうした法則がどうして物事を漏れなく重複なしに数えるために有効だと言えるのかという議論をしているわけですから、自明だからといって無視したり軽視してよい筈がありません。和の法則を使えばいいという条件があってこそ、公式に当てはめて計算したり、あるいは単純に足せばいいだけだと即座に答えられるわけです。そういう保証や見込みがない限り、足せばいいだけだと侮っていると、もちろん受験でも仕事でも間違った答えを出してしまう可能性があります。

もちろん、和の法則を使う状況においても、設問が与えている条件から見て判断できます。つまり、A町とB町を結ぶ経路について、道路が二本あるとか鉄道路線が一本あると簡単に書いていますが、道路のどちらかを通るとか、あるいは鉄道を利用するということが独立しているという前提がない限り、和の法則は成り立ちません。したがって、上記で和の法則を述べていますが、「或る事が ^^m^^ 通りの仕方で起き得て」とか「別の或る事が ^^n^^ 通りの仕方で起き得る」という表現で、それぞれ ^^m^^ 通りの事柄や ^^n^^ 通りの事柄は独立して起き得る事柄であると仮定していると見做さなくてはなりません。そしてそれゆえに、全ての場合の数を数え上げるときに和の法則が使えると判断するにあたっては、数えようとしている事柄が独立している、つまり重複がないと想定しているわけです。そして、漏れがないということについては、^^m^^ とか ^^n^^ のような自然数で表されている特徴をそのまま信用して使うことで保証されると言えるでしょう。そもそも、或る仕方で ^^m^^ 通りあると設問で言っているのに、その数え方が間違っているかもしれないなどと想定して問題を解くのはナンセンスだからです。このようなわけで、和の法則についても、漏れも重複もないということは和の法則で計算できることに対して設問で想定されたり定義されている範囲で必要条件であると言えます。

冒頭に戻る

12. 分別棚の原理は何を教えるのか

或る場合の数を数え上げるにあたって、漏れがないとか、重複がないという条件を支えるための一つの基準が、自然数の部分集合と比較するというものでした。ここで、漏れがあるということと、重複しているということが、二つの集合を比較した場合にどちらかが多かったり少なかったりする話と同じだと分かれば、漏れがないということと重複していないということを一つの理屈で確かめられると期待できます。そして、そういう期待に応える一つの考え方が、俗に「鳩の巣原理（pigeonhole principle）」と呼ばれている規則性です。ただし、この “pigeonhole” という言葉は、鳩の巣箱という意味でもありますが、ここでは物を分類したり分別する小さな箱や引き出しが並んだラックとか棚のことなので、本稿では「分別棚の原理」と呼びます（この原理を1834年に紹介したディリクレという数学者にちなんで「ディリクレの原理（Dirichlet principle）」と呼ばれることもあります。また、この原理を一般化したものとされている「ラムジーの定理（Ramsey's thorem, Ramsey theory）」の一部として紹介されることもあります）。以下の具体的な議論の展開は、[Bóna, 2017] を主に参照しています。

Wikimedia Commons contributors, "File:Pigeon-hole messagebox 2.jpg," Wikimedia Commons, the free media repository, https://commons.wikimedia.org/w/index.php?title=File:Pigeon-hole_messagebox_2.jpg&oldid=453634161 (accessed November 8, 2022).

分別棚の原理は、言っていることだけを見れば当たり前のように思えるでしょう。典型的な表現だと、次のようになります [Bóna, 2017: 1]。

箱の数よりもボールの数が多いと仮定しているわけですから、ボールの数が最低でも一つだけ多いなら、箱の数が一つだとボールは二つなので、その箱に二つのボールが入っていなくてはなりません。こんなのは当たり前のように思えますね。しかし、これをしっかり証明することによって、箱の数から見ればボールは重複して入ることになりますし、ボールの数から見れば箱の数には漏れがあると言えるので、分別棚の原理が想定する状況は、これまで考察してきた二つの条件とかかわりがあると分かるでしょう。

この原理は次のような背理法で証明できます。上記のような条件があったとして、重複してボールが入った箱が一つもないと仮定しましょう（「そんなこと、ありえないだろう」と思うかもしれませんが、背理法というスタイルの証明は、その「ありえない」ということを示す方法なのです）。すると、それぞれの箱にはボールがぜんぜん入っていないか、あるいは1個だけ入っていると言えます。ボールが全く入っていない箱の数を ^^m^^ 個とすれば、明らかに ^^m \geqq 0^^ です。すると、ボールが1個だけ入っている箱の数は（もともと箱の数は全部で ^^k^^ 個だったので）、^^k - m^^ 個となります。しかし、それはつまり ^^k^^ 個の箱に入れたボールの合計が ^^k - m^^ 個であるということですから、これは ^^n^^ 個のボールを ^^k^^ 個の箱に全て入れるという前提に対して、^^k - m \leqq k < n^^ だと言っていることになります。ボールの合計数よりも、ボールが1個だけ入っている箱の合計数が少ない（それ以外の箱にはボールが入っていない）と言っているのですから、これは矛盾しています。

このように、主張も証明も大して複雑だったり難解ではありませんが、分別箱の原理は非常に応用範囲が広い強力なアイデアだと評価されています。このことを説明するには、上記のように表現した分別棚の原理を、以下のとおり集合論のアイデアを使って更に一般化して表現しなおす必要があります。

ここで「関数」とは集合 ^^A, B^^ の要素（例えば ^^a \in A, b \in B^^）を順番どおりに並べて作った対（ペア、正確には「順序対」と言う）、^^< a, b >^^ などを集めた集合のことです。高校の数学やプログラミングでは、或る値から別の値への変換装置とか工場の処理施設みたいなものを想像するかと思いますが、高等教育で学ぶ数学（集合論）では、個々の要素で作ったペアという集合を集めた集合のうち、^^A^^ の各要素に ^^B^^ の要素が一つだけ対応しているペアを集めた集合 ^^f^^ を、^^A^^ から ^^B^^ への関数と言います。これだけだと、^^A^^ の二つ以上の要素が ^^B^^ の同じ値に対応してもいいことになるので（^^a_1 \rightarrow b, a_2 \rightarrow b^^ と、^^A^^ の二つ以上の要素が ^^B^^ の或る一つの要素へ対応してもよい）、^^B^^ の要素すべてについて、^^A^^ の要素が一つだけ対応しているような関数を「一対一関数」（一対一写像、または単射とも言います。英語では “one-to-one” とか “1-1” とか色々な書き方がありますが、意味はおおよそ分かる筈です））と言います。なお注意しておくと、^^B^^ の要素で ^^A^^ に対応する要素がないものもあります。一対一関数は、あくまでも ^^A^^ の要素が ^^B^^ の何らかの要素に重複なく対応しているという性質（injective）だけを言っています。それから、上記で ^^| A |^^ のように書いているのは ^^A^^ の要素の個数を表すためで、集合論では「濃度」と言います。というわけで、上記のように少しばかり抽象的に書いてはいますが、言っていることは同じです。A の要素の数が B の要素の数よりも多いなら、A の全ての要素に重複なく B の要素が対応するなんてことはありえない（必ず A の要素が余る）と言っているだけだからです。

この原理を当てはめられる事例は、組合せ論の本をどれでも開けば色々と紹介されています。その多くが突拍子もない結論をもたらすものだったりするわけですが、ここではそういう些事にとらわれず（既にこのようなページを読んでいるのですから、組合せ論について「親しみ」や「分かりやすさ」を強調する文章を期待するようなレベルの方ではないと思いますので）、もともとのテーマであった数え方（counting）の議論を進めましょう。すると、分別棚の原理を使うことで、^^A^^ が ^^B^^ よりも個数が多いとか数が大きいということは、すなわち ^^B^^ の要素を数える基準に照らして ^^A^^ の要素を数えると、^^A^^ の要素が必ず余ると言えます。逆に、^^A^^ の要素を数える基準で ^^B^^ の要素を数えると、必ず漏れが生じるということでもあります。これが ^^A^^ と ^^B^^ とを比較して、どちらが「多い」とか「少ない」ということの正確な意味と言えるでしょう。

ここで、和の法則という話題で取り上げたA町とB町の経路という事例に戻ってみましょう。道路が二本あり、鉄道の路線が一本ありました。この状況でA町からB町へ何かの重要な式典へ参加するために VIP がどれかの経路を独占的に使うとしましょう。VIP が四人いたら、分別棚の原理によれば少なくとも一本の経路において複数人の VIP が移動経路の取り合いになります。あたりまえですよね。このときは、移動経路を数えるという基準で導いた数と、移動する VIP の人数という数とで比べており、もちろん VIP を数える基準に照らせば移動経路の数には漏れ（不足）があり、移動経路を数える基準に照らせば VIP の人数がどこかの移動経路で重複するとも言えます。そして、和の法則を紹介したときに強調したように、実は和の法則を使った計算そのものはただの足し算にすぎず、このアイデアで本当に重要なのは、互いに独立している場合の数を数えているのかどうかという点にありました。

これに対して、積の法則で紹介したパスワードを作る事例では、1桁目に或る文字や数字を選んだという前提のもとで2桁目にどんな文字や数字を選び、そして3桁目、4桁目と数えていくかが場合の数を全て数えるためのヒントになっていました。この事例では、それぞれの桁については選べる場合が独立しているため、どの桁であっても選べるのは62通りです。仮に1桁しかないパスワードを作ると仮定すれば、話は和の法則と変わりません。しかし複数の桁でパスワードを作るとなると、1桁目に或る文字や数字を選んだという前提のもとで次の桁で何を選ぶかという複数の結果を、お互いに依存関係がある状況で組み合わせていきます。そこでは、或る桁で選べる文字や数字の個数に対して、次の桁で選べる文字や数字の個数が（パスワードの場合は各桁で選べる文字の数が減ったり増えたりしないので）同じように対応している必要があります。“j” を選んだときだけ次の桁では “3” が選べないとか、そんな条件はありませんね。したがって、1桁目である62個の文字や数字について、2桁目でも62個の文字が場合として選べるため、全ての場合の数は ^^62 \times 62 = 3844^^ となります。この考え方を24桁まで押し進めた結果が、^^62 \times 62 \times 62 \times ... \times 62 = 62^{24} = 141167095653376^^ ということになるわけです。もし、各桁で計算する文字（選べる文字）が少なかったり多かったとすればどうでしょうか。世の中にはパスワードを生成するプログラムとか、パスワードの強度を測定するプログラムというのがあり、1桁目に数字を使うのは良くないとされています（パスワードを暗号化する処理が先頭つまり左側から1桁ずつ文字を扱うからです）。よって、ここで1桁目に数字は使えないというルールを追加しましょう。すると、1桁目に使える文字という場合の数が全部で幾つあるのかは、もちろん和の法則などといちいち言わなくても英文字（大文字と小文字）だけなので52個だと分かります。数字が使えた状況と比較すれば、数字が使えた状況で作ったパスワードのうち、数字が使えない状況で作ったパスワードとは一致しないパスワードが少なくとも一つはあるというのが、分別棚の原理が教える結論であり、もちろんこれは証明の必要なく分かる話でしょう。

冒頭に戻る

冒頭に戻る

参考文献

Beeler, Robert A.

2015

How to Count: An Introduction to Combinatorics and Its Applications. Springer, 2015.

Bóna, Miklós

2017

A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. 4th edn., World Scientific Publishing, 2017 (1st edn., 2002).

Burgess, John P.

2022

Set Theory. Cambridge University Press (Elements in Philosophy and Logic), 2022.

Cameron, Peter J.

1994

Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, 1994.

2017

Notes on Counting: An Introduction to Enumerative Combinatorics. Cambridge University Press (Australian Mathematical Society Lecture Series, 26), 2017 .

Cioabǎ Sebastian M. and M. Ram Murty

2022

A First Course in Graph: Theory and Combinatorics. 2nd edn., Hindustan Book Agency with Springer (Texts and Readings in Mathematics, vol.55), 2022 (1st edn., 2009).

Cunningham, Daniel W.

2016

Set Theory: A First Course. Cambridge University Press, 2016.

Dasgupta, Abhijit

2014

“Chapter 4 Postscript I: What Exactly Are the Natural Numbers?" in Set Theory: With an Introduction to Real Point Sets. Springer, 2014, pp.67-72.

Enderton, Herbert B.

1977

Elements of Set Theory. Academic Press, 1977.

深瀬幹雄, et. al.

2014

『Aクラスブックス 場合の数と確率』, 昇龍堂出版, 2014.

Harris, John M.; Jeffry L. Hirst, and Michael J. Mossinghoff

2000

Combinatorics and Graph Theory. Springer (Undergraduate Texts in Mathematics), 2000 (2nd edn., 2008).

なお、本書は2008年に第2版が出ていて、他の内容ともども pigeonhole principle の解説も大半が書き換えられている。そして、僕は初版だけにあった記述内容を参考にしているため、本稿では敢えて初版を優先して掲載している。典拠表記は研究や論説の作成にあたって実際に参照して得るものがあった文献を掲載するものであり、最新の出版物を紹介するカタログではないからだ。

Jacobson, Nathan

2009

Basic Algebra I. 2nd edn., Dover Publications, 2009 (originally publicated in 1985 by W. H. Freeman, 1st edn., 1974).

嘉田 勝

2008

『論理と集合から始める数学の基礎』, 日本評論社, 2008.

Mazur, David R.

2010

Combinatorics: A Guided Tour. The Mathematical Association of America (MAA Textbooks), 2010.

Moschovakis, Yiannis

2006

Notes on Set Theory. 2nd edn., Springer, 2006 (1st edn., 1994).

成嶋 弘

2003

『数え上げ組合せ論入門』, 改訂版, 日本評論社（日評数学選書）, 2003 (1st edn., 1996).

「[...] パラメータの具体値が与えられていて場合分けの規則が明確で，場合分けの木（または森）を人間が視覚的に認識できる範囲で描くことができる問題に対しては，実際に場合分けの木を描くことによってその答えを求めることができる．また，人間の手に余るときはコンピュータの助けをかりることもできる．しかし，場合分けの規則が明確である（すなわち求めるものを数え上げるアルゴリズムがある）が，個数関数が定まっていないで，数え上げる対象がパラメータに関し指数関数的に増大するとき，パラメータ値がある程度大きくなると，コンピュータでも手に負えなくなる．」 (p.10f.)

大矢雅則, et. al.

2014

『新編 数学I』, 数研出版, 2014（2011年3月9日、文部科学省検定済）.

2015

『新編 数学A』, 数研出版, 2015（2011年3月16日、文部科学省検定済）.

Stillwell, John

2013

The Real Numbers: An Introduction to Set Theory and Analysis. Springer, 2013.

田中尚夫

1982

『公理的集合論』, 培風館（現代数学レクチャーズ B-10）, 1982.

冒頭に戻る