Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

順序の制約が多いほど並べ方は減る、と思いやすい。本稿は、点 $6$ 個の有向非巡回グラフを全部数え、並べ方の数が制約の本数では決まらないことを数える。新しい定理も法則も主張しない。

第一に、並べ方の数は両端では決まっている。辺が無ければ $720$ 通り、一本道なら $1$ 通りで、どちらも数え上げと一致した（第2節）。

第二に、これが本稿の芯である。同じ辺の本数でも、並べ方の数は大きく散らばる。辺 $5$ 本のグラフ $3003$ 個で、並べ方は $1$ 通りから $120$ 通りまで、$39$ 通りの値をとる（第2節）。

第三に、比べられる組の数で揃えても決まらない。推移で決まる組まで数えて $8$ 組に揃えても、並べ方は $14$ 通りから $48$ 通りまで、$\mathbf{3.428571}$ 倍動く（第3節）。

第四に、推移で決まる辺は並べ方を減らさない。一本道 $0\to1\to\dots\to5$ に辺 $0\to5$ を足しても $1$ 通りのまま、辺の本数だけが増える（第3節）。

第五に、並べ方の数は二通りに数えて一致した。置ける点を一つずつ足す数え方と、$720$ 通りの並べ替えを全部試す数え方が、無作為に選んだ $400$ 個で一致した（第2節）。

第六に、分離子は、辺の本数を数えるか、辺が残す答えの通り数を数えるかである。残りを比べて決める回数の下界は $\log_2$（並べ方の数）で、辺 $5$ 本でも $0$ から $\mathbf{6.906891}$ まで動く（第4節）。

キーワード：トポロジカルソート、有向非巡回グラフ、線形拡大、推移閉包、比べる回数の下界。

射程（何を示さないか）

新しい定理も法則も主張しない。有向非巡回グラフに矢印に逆らわない並べ方が在ること、その数（線形拡大の数）、推移で決まる辺が順序を変えないことは、いずれも既知である。算法の速さを論じない。並べ方の数を速く数える方法や、その難しさには入らない。実在の工程を扱わない。作業の段取りや講義の履修順は主題ではない。大きさを一般化しない。点 $7$ 個以上は数えていない。向きを番号の小さい側から大きい側に揃えたグラフだけを数えた。既刊との関係：論文843 は、比べる回数の下界が入力ではなく答えの通り数で決まることを示した。本稿はその隣に置く。あちらは答えの通り数を $n!$ として数えた。ここでは途中まで順序が分かったとき、残る答えの通り数が辺の本数では決まらないことを数える。加えたのは、$32768$ 個のグラフの並べ方を全部数えたこと、辺 $5$ 本で $39$ 通りの値に散らばると測ったこと、比べられる組の数で揃えても $3.428571$ 倍動くと測ったこと、分離子を「辺の本数か、残る答えの通り数か」に置いたことである。

1. 記法と問い

設定：点 $0,1,\dots,5$ の上に、番号の小さい点から大きい点へ向かう辺を好きなだけ引く。こうしてできる $2^{15}=32768$ 個のグラフはどれも有向非巡回グラフである。並べ方の数 $e(G)$ は、どの辺 $a\to b$ についても $a$ が $b$ より前に来る並べ方の個数である。

$$e(G)=\#\{\pi\in S_6:\ a\to b\in G\Rightarrow \pi^{-1}(a)<\pi^{-1}(b)\},\qquad
\text{比べる回数の下界}=\log_2 e(G)$$

並べ方の数は、すでに置いた点の集合を状態にして、前に置くべき点がすべて置かれた点を一つずつ足して数えた。比べられる組の数は、推移で決まる組まで含めた数（推移閉包の辺の数）である。

問い：辺の本数が同じなら、並べ方の数も同じくらいか。

2. 辺の本数ごとに数える

計算 2.1：辺の本数ごとに、並べ方の数の最小・最大・異なる値の個数を数えた。

観察 2.2　これが本稿の芯である。同じ辺の本数でも、並べ方の数は大きく散らばる。辺 $5$ 本では、一本道なら $1$ 通り、一つの点から残り五つへ辺を出せば $120$ 通りで、そのあいだに $39$ 通りの値がある。辺 $5$ 本から辺 $15$ 本まで、どの本数でも最小は $1$ 通りだった。辺を足すことで並べ方が決まり切るかどうかは、本数ではなく辺の置き方による。

観察 2.3　並べ方の数は二通りに数えて一致した。点を一つずつ足す数え方と、$720$ 通りの並べ替えを全部試す数え方を、無作為に選んだ $400$ 個で比べた。すべて一致した。辺が無いとき $720$ 通り、一本道のとき $1$ 通りも確かめた。

3. 比べられる組の数で揃える

計算 3.1：推移で決まる組まで数えた「比べられる組」の数ごとに、並べ方の数を数えた。

観察 3.2　比べられる組の数で揃えても、並べ方の数は決まらない。組を $8$ に揃えても $14$ 通りから $48$ 通りまで、$3.428571$ 倍動く。辺の本数よりは散らばりが小さいが、同じ数の組を知っていても、どの組を知っているかで残る並べ方は違う。

観察 3.3　推移で決まる辺は並べ方を減らさない。一本道 $0\to1\to2\to3\to4\to5$ に辺 $0\to5$ を足しても $1$ 通りのままだった。辺の本数は $5$ から $6$ に増えるが、新しい順序は何も加わっていない。辺の本数が並べ方を決めない理由の一つである。

4. 分離子

観察 4.1　分離子は、辺の本数を数えるか、辺が残す答えの通り数を数えるかである。並べ方の数は、辺を知ったあとに残る答えの通り数である。残りを比べて並べ終えるのに要る回数の下界は $\log_2$（並べ方の数）で、辺が無いとき $9.491853$、辺 $5$ 本では $0$ から $6.906891$ まで動く。何本の辺を知ったかでは、あと何回比べればよいかは決まらない。

観察 4.2　論文843 の隣に置く。843 は、比べる回数の下界が入力ではなく答えの通り数で決まることを示した。あちらの答えの通り数は $n!$ だった。ここでは途中まで順序が分かったときに残る答えの通り数を数え、それが辺の本数でも比べられる組の数でも決まらないことを示した。

観察 4.3　言わないこと。並べ方の数を速く数える方法も、実在の工程表も、点 $7$ 個以上も扱わない。示したのは、並べ方の数が辺の本数では決まらないということである。

5. 点呼と結び

1. 並べ方の数 $e(G)$（第1節）：矢印に逆らわない並べ方。
2. 辺が無ければ $720$ 通り（計算 2.1）：$6!$。
3. 一本道なら $1$ 通り（計算 2.1）：決まり切る。
4. 辺 $5$ 本で $1$ から $120$ 通り（計算 2.1）：本稿の芯。
5. 辺 $5$ 本で $39$ 通りの値（計算 2.1）：散らばり。
6. 組 $8$ で $\mathbf{3.428571}$ 倍（計算 3.1）：揃えても決まらない。
7. 推移で決まる辺は変えない（観察 3.3）：$1$ 通りのまま。
8. 二通りの数え方が一致（観察 2.3）：$400$ 個。
9. 下界は $0$ から $\mathbf{6.906891}$（観察 4.1）：辺 $5$ 本。
10. 辺の本数か、残る答えの通り数か（観察 4.1）：分離子・論文843。

結び：並べ方の数は、辺の本数でも、比べられる組の数でも決まらない。点 $6$ 個の有向非巡回グラフで、辺が $5$ 本のものだけでも並べ方は $1$ 通りから $120$ 通りまで $39$ 通りの値をとる。一本道のように順序を決め切る置き方と、一つの点からだけ出す置き方とで、残る並べ方がまるで違うからである。推移で決まる組まで数えて $8$ 組に揃えても $14$ 通りから $48$ 通りまで $3.428571$ 倍動き、推移で決まる辺を足しても並べ方は減らない。残りを比べる回数の下界 $\log_2$（並べ方の数）は、辺 $5$ 本で $0$ から $6.906891$ まで動く。既刊との位置：論文843 の「下界は答えの通り数で決まる」の隣に、途中まで順序が分かったときの答えの通り数を置いた。正直に言えば、数えたのは点 $6$ 個、向きを番号順に揃えたグラフだけである。

参考文献

1. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
2. Stanley, R. P. (2011). Enumerative Combinatorics, Volume 1 (2nd ed.). Cambridge University Press.
3. 山岸勇輝 (2026). 『比べる回数の下界は、入力ではなく答えの通り数で決まる』[論文843]. YOI: https://www.yamagishiyuuki.com/yoi/843

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「並べ方の数は、辺の本数でも、比べられる組の数でも決まらない」［論文869］. YOI: https://www.yamagishiyuuki.com/yoi/869

@misc{yamagishi2026yoi869,
  author = {Yamagishi, Yuuki},
  title = {The Number of Orderings Is Set Neither by the Number of Edges Nor by the Number of Comparable Pairs},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/869},
  note = {Preprint, edition 1}
}