n次元ビンゴにおける可能なビンゴ列の本数

複数マスから成るビンゴシート（各辺\(m\)マス、\(n\)次元）において可能なビンゴ列の本数\(\#_b(m,n)\)は、次の式で与えられる（2025-08-22加筆）：$$ \sout{\#_b(m, n) = \frac{1}{2} \sum_{i=0}^{n-1} (2^{n-i} - 1) 2^{n-i} {}_n C_i (m-2)^i} $$$$ \#_b(m, n) = \frac{1}{2} ((m+2)^n - m^n) $$\(2 \le m \le 9, 1 \le n \le 8\)における\(\#_b(m,n)\)の値は次の通り：

導出

通常のビンゴシートは、5×5の正方形をしています。これは、各辺を 5 マスに割った 2 次元超立方体です。このように、各辺が\(m\)マスになっている\(n\)次元超立方体を使ったビンゴを考え、これを\(m^n\)ビンゴと呼ぶことにします。例えば、通常のビンゴは「 5² ビンゴ」を用いています。また\(m\)の値に拘らず、\(m^n\)ビンゴを\(n\)次元ビンゴと呼ぶことにします。
ここで、\(m^n\)ビンゴにおいて、ビンゴとして成立しうるマスの並びがいくつあるかということを考えます。例えば、 5² ビンゴでは縦5本、横5本、斜め2本の合計12本が最大値です。他の次元を例に取ると、 5¹ ビンゴでは1本、 5³ ビンゴでは109本です。

方針

ビンゴ列にはファセット*上のマスが必ずちょうど2つ含まれるので、ファセット上のマスから伸びるビンゴ列の数を合計すれば、その半分が求めたい値になっています。
*\(n\)次元超多面体におけるそれを囲む\(n-1\)次元の面を言う。線分に対する（端）点、多角形に対する辺、多面体に対する面。例えば 5¹ ビンゴでは2マス、 5² ビンゴでは16マス、 5³ ビンゴでは98マスがファセットに属する（下図で橙色に塗った部分）。

ところで、\(m=1\)と\(n=0\)のときは、もう一方の変数の値に拘らず、ビンゴシートが 1 マスのみから成ることになります。\(m=1\)の場合、「ビンゴ列にはファセット上のマスが必ずちょうど2つ含まれる」が成り立ちません。また\(n=0\)の場合は、 1 次元以上のビンゴシートにあるような通常の意味でのビンゴ「列」が存在しません。よって、以下これらの場合は除外して、ビンゴシートが複数マスからなる、一辺 2 マス以上、 1 次元以上の場合（\(m \geq 2, n \geq 1\)）を考えることとします。

ファセット上の一マスから伸びるビンゴ列の数

マスの位置によって、そこから伸びるビンゴ列の数は異なります。 3³ ビンゴを例に取って考えましょう。以降、説明のために手前左上のマスを原点として左右方向にx軸、上下方向にy軸、前後方向にz軸を導入します。

立方体の頂点にあたるマスからは、縦横奥行の3方向、表面上を斜めに3方向、反対側の点にかけての1方向がありますが、これは①\(x,y,z\)のいずれか1つが変化するもの：\([(0,0,0),(1,0,0),(2,0,0)]\)
\([(0,0,0),(0,1,0),(0,2,0)]\)
\([(0,0,0),(0,0,1),(0,0,2)]\)、②\(x,y,z\)のいずれか2つが変化するもの：\([(0,0,0),(1,1,0),(2,2,0)]\)
\([(0,0,0),(0,1,1),(0,2,2)]\)
\([(0,0,0),(1,0,1),(2,0,2)]\)、③\(x,y,z\)のいずれか3つ（＝全て）が変化するもの：\([(0,0,0),(1,1,1),(2,2,2)]\)、として解釈できます（座標はマス\((0,0,0)\)からの例）。立方体の辺上（除頂点）にあるマスからは、①：\([(1,0,0),(1,1,0),(1,2,0)]\)
\([(1,0,0),(1,0,1),(1,0,2)]\)と②：\([(1,0,0),(1,1,1),(1,2,2)]\)だけが、立方体の面上（除辺上）にあるマスからは、①：\([(1,1,0),(1,1,1),(1,1,2)]\)だけがあります。

このように、\(n\)次元ビンゴにおけるファセット上のマスには、その位置に応じて、利用可能な成分が 1 個から\(n\)個あります。また、特に\(N\)個の成分が利用可能な場合に、そこから（ビンゴ列を伸ばす方向を指定するために）実際に利用する成分を選ぶ方法は\(\sum_{k=1}^N {}_N C_k\)通り、すなわち$$ 2^N - 1 $$通りあります。

ファセット上のマスの数

さて、前節で、特定のマスから引けるビンゴ列の数は分かりました。次は、それらのマス自体の数を数えます。前述の通り、ファセット上のマスはビンゴ列を伸ばす方向として利用可能な成分の数で\(n\)通りに分類できます。ここで、\(N\)個の成分が利用可能なマスは、特に余次元\(N\)の面上にあります。 3³ ビンゴでは次のようになっています：

ここで、\(n\)次元多面体における余次元\(N\)の面、\(ν = n - N\)として\(ν\)次元面の個数は次の式で与えられます：$$ 2^{n-ν} {}_n C_{ν} $$これは、\(ν\)次元面を構成する成分の選び方が\({}_n C_{ν}\)通りあり、また面は面を構成しない成分のそれぞれ両側に配置される*ので、同じ成分からなる面がそれぞれ\(2^{n-ν}\)個あるためです。
* 3次元の立体を例に取ると、xyからなる面は前後の2箇所（z軸の両側）にあり、xからなる辺は上下と前後の組み合わせによる4箇所（y軸とz軸の両側）にあり、頂点は左右・上下・前後の組み合わせによる8箇所（x軸とy軸とz軸の両側）にある。

次に、ある一つの面に属するマスの個数を考えます。ただし、本来求めたいのは\(ν\)次元面に属するマスの個数というよりも、\(ν\)次元面に属し、\(ν\)以下の次元の面に属さないマスの個数です。同じ\(ν\)次元面に属していても、\(ν\)以下の次元の面に属するマスから引けるビンゴ列の本数は、\(ν\)以下の次元の面に属さないマスから引けるビンゴ列の本数よりも多くなるためです。よってその面のファセットに属するマスを除いて数える必要がありますが、これは一辺のマス数から両端分を除いた値に面の次元を乗じた$$ (m-2)^{ν} $$で済みます（\(m \ge 2\)であることを確認してください）。問題になりそうなのは「両端」が存在しない\(ν=0\)（頂点）の場合ですが、「\(ν\)以下の次元」が存在しないため\(ν\)次元面に属するマスの個数である 1 を得られればよく、実際常に 1 を返すため都合よく行きます。

したがって、\(n\)個の成分が利用可能なマスの個数は、\(ν = n - N\)を用いて$$ 2^{n-ν} {}_n C_{ν} (m-2)^{ν} $$で与えられます。

可能なビンゴ列の本数

前二節での議論から、\(n\)個の成分が利用可能なマスから引かれるビンゴ列の本数は、ビンゴシート全体で$$ (2^{n-ν} - 1) 2^{n-ν} {}_n C_{ν} (m-2)^{ν} $$として得られます（\(2^N - 1\)を\(N = n - ν\)で置換しています）。よってこれのビンゴ列に利用可能な成分の数（＝余次元）\(N = 1,\ldots,n\)での総和、すなわち面の次元\(ν = 0,\ldots,n-1\)での総和を取った値がファセット上の全てのマスから引けるビンゴ列の本数の合計です：$$ \sum_{ν=0}^{n-1} (2^{n-ν} - 1) 2^{n-ν} {}_n C_{ν} (m-2)^{ν} $$これは各ビンゴ列を2回ずつ数えているので、この半分が求めるべきものです。

以上のことから、\(m^n\)ビンゴにおいて可能なビンゴ列の本数は$$ \frac{1}{2} \sum_{i=0}^{n-1} (2^{n-i} - 1) 2^{n-i} {}_n C_i (m-2)^i $$によって求まります。

除外したケースについて

冒頭で「 1 マスビンゴ」になってしまう\(m=1\)と\(n=0\)の場合を除外しました。これらにおけるビンゴ列（？）の本数を考えるならば、唯一のマスが開いた 1 本であるということになるでしょう。しかし、上で得た式に\(m=1\)を代入すると\(0,1,4,13,40, \cdots (n \ge 0)\)となり、\(n=0\)を代入すると常に 0 が得られます。これらの場合にも対応させるならば、$$ \#_b(m,n) = \left\{ \begin{array}{ll} 1 & (m=1 \lor n=0)\\ \frac{1}{2} \sum_{i=1}^{n-1} (2^{n-i} - 1) 2^{n-i} {}_n C_i (m-2)^i & (m > 1 \land n > 0) \end{array} \right. $$としてもいいかもしれません。

式を簡単にする（2025-08-22追記）

この記事を書いたあと、私は別の記事でLLMの助けを借りて式を簡単にする経験をしました。いま前掲の式を見てみたときに、より簡単な表現ができそうな気配を感じたので、実行してみました。

まず、式を二つの項に分解します。$$ \begin{align*} \#_b(m, n) &= \frac{1}{2} \sum_{i=0}^{n-1} (2^{n-i} - 1) 2^{n-i} \binom{n}{i} (m-2)^i \\ &= \frac{1}{2} \sum_{i=0}^{n-1} ((2^{n-i})^2 - 2^{n-i}) \binom{n}{i} (m-2)^i \\ &= \frac{1}{2} (\sum_{i=0}^{n-1} 4^{n-i} \binom{n}{i} (m-2)^i - \sum_{i=0}^{n-1} 2^{n-i} \binom{n}{i} (m-2)^i) \\ \end{align*} $$ここで\(S_1 = \sum_{i=0}^{n-1} 4^{n-i} \binom{n}{i} (m-2)^i, S_2 = \sum_{i=0}^{n-1} 2^{n-i} \binom{n}{i} (m-2)^i\)と置くと、二項定理から$$ \begin{align*} S_1 &= \sum_{i=0}^{n} \binom{n}{i} 4^{n-i} (m-2)^i - \binom{n}{n} 4^{n-n} (m-2)^n \\ &= (4+(m-2))^n - (m-2)^i \\ &= (m+2)^n - (m-2)^i \\ \end{align*} $$$$ \begin{align*} S_2 &= \sum_{i=0}^{n} \binom{n}{i} 2^{n-i} (m-2)^i - \binom{n}{n} 2^{n-n} (m-2)^n\\ &= (2+(m-2))^n - (m-2)^i \\ &= m^n - (m-2)^i \end{align*} $$と簡単にできます。従って$$ \begin{align*} \#_b(m, n) &= \frac{1}{2} (S_1 - S_2) \\ &= \frac{1}{2} ((m+2)^n - m^n) \\ \end{align*} $$ということになります。実際この式に基づいて計算した結果は最初に載せた表と一致しました。なるほど言われてみれば二項定理っぽい香りが漂ってますね。ありがとう Gemini 2.5 Pro。