数学の話：箸を並べてつまんで拭いたら、カタラン数が出てきた話
投稿日：2025年8月3日
目次
イントロダクション
お疲れ様です、東です。
実家で洗い物をしていているときに、ある数学の問題が頭をよぎりました。
その時私は、洗い終わった箸を、布巾で拭いて、箸入れに戻していました。
全部いっぺんに拭くと、箸全体を拭き切ることが出来ないので、2本ずつ拭いていたのですが、
同じ人の箸同士で2本選ばないと、ちょっと拭きにくいです。
（私の箸、父の箸、母の箸、……、それぞれ長さが違うので）
そのため、バーっと1列に並べた後、なるべく同じ人の箸同士を摘んで、拭いてました。
隣り合っていると、一発でまとめて摘みやすいので、隣り合った同じ組の箸を摘んで進めよう！ ということです。
ですが、この手順は、いつも上手くいくとは限りません。
上手くいかない例：
箸が「私 父 父 母 私 母」の順に並んでいる場合
→父の箸を拭いた後、「私 母 私 母」の順で箸が残る
上手くいく例：
箸が「私 父 母 母 父 私」の順に並んでいるとき
→「母 →父 →私」の順に拭くことで、全ての箸を拭ける
こうしてみると、「ランダムに箸を並べたときに、大体どのくらいの箸を拭けるのか」というのが気になります。
この疑問を、正確に問題文として書き起こしてみると、以下のようになります。
今回の問題：箸を並べてつまんで拭く
nを自然数とする。
n組の箸（1組目〜n組目）、計2n本を、ランダムに一列に並べる。
この時、以下のアルゴリズムを考える。操作１：同じ組の箸が隣り合っている場合、その組の箸を2本とも取り除く。
操作２：操作１が行えなくなるまで、操作１を繰り返す。操作２は、隣り合う同じ組の箸が無くなった時、または、全ての箸が取り除かれた場合に停止する。
上記のアルゴリズムを行った際、「取り除かれた箸の組数」の期待値E_nは、nを用いてどのように表されるか。
※上記アルゴリズムは、「手順は一意に定めない」ですが「取り除かれた箸の組数は一意に定める」ので、（取り除かれた箸の組数は）well-definedです。きちんと証明するには、帰納法を用いることになりますが、割愛します。
観察
実験：大人数の箸を拭くと、1膳くらいしかつまめないらしい
nが小さいときに手計算してみると、以下のようになっています。
- E_0 = 0
- E_1 = 1
- E_2 = 4/3
- E_3 = 4/3
また、100膳の箸を100万回ランダムに並び替えて上記アルゴリズムを実施して、実験的に観察してみると、
- n→∞ で E_n→1 に収束
となることがわかりました。
100人家族の方は、ぜひ100万回ランダムに洗い物をしてみると良いでしょう。
（私はpythonを使いました）
「収束先が1」となると、何かキチンとした表示が得られるのではないか、と期待が出てきますね。
（それはそれとして、大人数の箸を拭くと、1膳くらいしかつまめないというのは、直観に反するような気もします。
面白いですね）
問題のシンプル化：自分の箸（特定の箸）だけ拭けばOK
さて、確率変数X_kを、
- 箸 k が取り除かれる場合→ X_k=1
- その他の場合→ X_k=0
で定めます。すると、
E_n = E(X_1 + …… + X_n)
= E(X_1)+…… +E(X_n) （期待値の線形性により）
=n * E(X_1) （箸のラベルの対称性より）
=n * p
となります。
（ただし最後のpは、「特定の箸（例えば箸1）が取り除かれる確率」とします）
このように、特定の箸に着目すれば、最終的に期待値が求められることがわかります。
特定の箸に着目：取り除かれる箸の組の間には、ちょうど k 組の箸が入る（so what?）
i 組目の箸（以下、箸 i ）が取り除かれるには、その間が全て取り除かれることが必要十分です。
更に考えてみると、箸 i が取り除かれることは、「箸 i の間にちょうど k 組（k：n 以下の自然数）の箸が入り、これらが全て取り除かれること」が必要十分条件になります。
※奇数本の場合は、明らかに箸 i たちの間に、最後に箸が残ってしまいます。
また、偶数本であっても、箸 i たちの間に片方しか間に入ってない箸がある場合は、
その箸が残ってしまいます。
よって、箸 i が取り除かれるには、箸 i の間にちょうど k 組の箸が入ることが必要です。
十分性は明らかです。
……さて、ここまで観察してきて、「箸 i の間にちょうど k 組の箸が入り、これらが全て取り除かれる場合の数」が求められればOK、ということはわかりました。
が、「So what? 」とならないでしょうか。
実際にこれを求めるには、骨が折れる計算をするか、上手い対応に気付く必要があります。
箸 = 括弧 （箸で数学をして、括弧で飯を食う）
さて、突然ですが、箸 = 括弧 であることに気付けるでしょうか。
箸も括弧も1列に並べますし、2つ1組ですし、形も似ている（真っ直ぐか曲がってるかくらいの違いです）ので、まあ似たようなものですね。
実際、箸 = 括弧 であることは、以下のような双方向の対応を見ることで、確認できます。
箸→括弧 の対応（箸で数学をする）
箸 i が取り除かれるとき、その間にある k 組の箸それぞれについて
- 左側にある箸を ( 開きカッコ に置き換える
- 右側にある箸を ) 閉じカッコ に置き換える
ことで、（適切な）括弧列に対応させることができます。
例：箸1の間に、2 4 4 3 5 5 3 2 と箸が並んでいる場合
括弧列 ( ( ) ( ( ) ) ) に対応。
※ここで、「適切な」括弧列とは、
「左から順に、開きカッコ・閉じカッコそれぞれをカウントしたときに、
閉じカッコの個数が開きカッコの個数を超過しない」ことです。
※箸 i の間の k 組の箸が全て取り除けることが、本質的に重要です。
（例えば、1 3 2 3 1 2 は、上記のルールだと ((( ))) に対応しますが、
後述の 括弧 → 箸 の対応で戻すと、
i j k k j i に戻り、（ラベリングの任意性を考慮しても）元の箸の並びに戻りません）
括弧→箸 の対応（括弧で飯を食う）
逆に、k 組の括弧からなる（適切な）括弧列に対して、
- ( 開きカッコ を、登場した順に、箸の番号に対応させる
※ここの対応（ラベリング）は任意性あり - ) 閉じカッコ を、対応する ( 開きカッコ と同じ箸の番号に対応させる
ことで、（箸のラベリングの違いを除いて一意に）箸の並びを対応させることが出来ます。
例：上記例で得た括弧列 ( ( ) ( ( ) ) ) に対して、
箸の並び i j j k l l k i が対応。ただし、
各ラベル i 〜 l に対して、箸2〜5を適当に並び替えて対応させるものとする。
（例えば、i : 2 j : 4 k : 3 l : 5 なら、元の箸の並びに対応し、
i : 2 j : 3 k : 4 l : 5 なら、別の箸の並びに対応する。
この意味で、箸のラベリングの違いを除いて一意に、箸の並びが対応している）
このように、箸の並び → 括弧列 、 括弧列 → 箸の並び の、互いに逆の対応を得ることができます。
これにより、「箸の並びの場合の数」と「括弧列の場合の数」を対応させることができます。
括弧と同様、箸もカタラン数で数えられる
カタラン数 C_k = 1/(k+1) * COMBIN(2k, k)
※ただし、COMBINは組み合わせ関数
再び突然ですが、k 組の括弧列の並べ方は、カタラン数 C_k 通りあります。
よって、箸の並びも、カタラン数 C_k によって数え上げることが出来ます。
（今回、括弧列の並べ方がカタラン数通りであることの証明は割愛しますが、
「カタラン数 証明」で検索すると、色々と証明が見つかります）
ここまで来たら、あとは計算するのみです。
期待値の計算（駆け足）
（ここまで具体的な計算になると、普段のHP編集機能だと、数式の書き込みに限界があるため、概要だけ駆け足で書きます）
- 箸 i の間に入る k 組の箸をfixしたとき、その並び替えの場合の数は、以下のように表されます。
k ! * C_k （C_k：カタラン数） - 箸 i の間隔が 2k になる確率は、以下のように表されます。
2(2n – 2k – 1) / 2n(2n-1) - 箸i の間に入る k 組の箸の選び方の場合の数は、組み合わせ関数COMBINを用いて、以下のように表されます。
COMBIN ( n-1 , k ) - 外側に残る m ( = n – 1 – k ) 組の並びの場合の数は、以下のように表されます。
(2m)! / (2^m) - 「箸 i の左端 〜 右端」を、全体のどこに配置するかの場合の数は、m を用いて、以下のように表されます。
2m + 1 - 全ての並び替えの場合の数は、以下のように表されます。
(2n) ! / (2^n) - 以上をもとに、 箸 i の間に k 組入る並べ方の場合の数を計算し、k = 0からn-1まで場合の数を足し合わせて、全ての並び替えの場合の数で割ることで、箸 i が取り除かれる確率 p が求められます。
- p * n により期待値が求められます。その後、式を整理すると、以下のような表示になります。
E_n = n!/(2n)! * 2^n * (Σ(t=0からn-1) (2t)!/(2^t * t!) * (2t +1) * C_(n-1-t) )
※最後に、t = n-1-k で変数変換しています。
上記の期待値の表示を、n= 0 , 1 , 2 , 3 で計算してみると、最初に手計算で求めた値に一致し、n = 4以降での値も、pythonで実験的に求めた値に近いことが確かめられました。
また、大きい値で計算してみたところ、極限も1になるっぽいことが確認できました。（カタラン数の極限を基に、厳密に極限を求めることも出来ると思いますが、ここまでで丸2日の休日を費やしたので、この辺りで切り上げました）
以上により、今回求めたかった、E_n の表示を得ることが出来ました。
これで、安心して箸を拭くことが出来ますね。
最後に：
日頃生活していて、頭によぎる疑問も、場合によっては数学の問題に帰着させることができるのは、面白いです。
他にも、色々なことが疑問になるかと思います。
皆さんも、日々の疑問を問題として解いてみてはいかがでしょうか。
例題：（毎朝通勤のたびに頭をよぎること）
エスカレーターの右側を歩くのと、左側に立っているのとでは、どちらの方が効率が良いか。
立っている時の前後の間隔（人の距離）を a 、歩いている時の前後の間隔をb、
歩くスピードを v 、エスカレーターのスピードを w としたときに、
歩く方が効率が良くなる条件を考えよ。
（そもそも、上記a, b, v, w の設定は、十分かつ妥当か）
さて、本文中に登場した「カタラン数」ですが、私が最初に出会ったのは高校生の時でした。
某・数学ボーイミーツガール物のシリーズ第1巻が、高校の図書室に置いてあって、「こんな概念もあるものなんだなあ」と感じたのを覚えています。
（最近、このシリーズの最終巻の発売が発表されました。いち読者として、勝手に感慨深いと感じています）
社会人になって、ふと出会った疑問が、高校生のときに出会った概念と結び付いたのも、面白いです。
サポート行政書士法人では、流石にここまで数学的な話を使うことは無いですが、ごくたまに、数学的な知識があってよかったな、となるシーンもあります。
数学に限らず、「面白いけど、いつ・何の役に立つんだ？」と思っている話が、時折顔を覗かせることもあります。
色々な話・知識に興味を持って、身につけて、いつか必要になったそのときに使えるようにしておくことは、どの分野・業種でも、変わらず大切ですね。
（カタラン数も、いつかは行政書士法人の業務で活きてくることが、あるかもしれないですしね！）
