この記事は
日曜数学 Advent Calendar 2023
の
前日はコロちゃんぬさんの最大公約数と最小公倍数の分配法則についてでした。
この記事では、私にとって今一番熱い話題である「ドミノタイリング」について語りたいと思います。
今日の日付、12月10日にちなんだ1210とおりのドミノ数え上げパターン
ドミノタイリングというのは、図1 のようにしてドミノ(
ドミノタイリングの例
これに興味を持ったきっかけは濱中裕明@Ototo_さんから2023年7月23日にもらったこのリプライでした。
縦横の長さが自然数の長方形に、1x2のドミノを敷き詰める場合の数を求める式も、cosがバンバンでてきます。っていうか、このトピックの元の問題もそこからかな。>カステレイン行列
— 濱中裕明 (@Ototo_) July 22, 2023
これをきっかけにして、
さて、さきのリプライに出てきた式はこういうものでした。
いやあ、実に面白い式ですね!三角関数の
見た目もシンプルにまとまっていて実に美しいではありませんか!
私はこの式をどうしても理解したいと思い、「線形代数と数え上げ[増補版]」の本Tを買ってしまったのでした。
本を読んで、よくわからなかったところを自己流で補間することで、最終的にこの式を導出することに成功したのでした。
そして、その導出方法と、なぜその式でドミノタイリングの総数を計算できるかについて記事にまとめました。
前編記事ができたのが
≪リンク≫
ドミノタイリングの数え上げ公式の導出方法【前編~導出~】
≪リンク≫
ドミノタイリングの数え上げ公式の導出方法【後編~証明~】
式に出会ってから証明が完成するまで
ちょうど転勤して忙しくなり、平日は疲れ切って通勤時間も日曜数学活動はほとんどできていなかったこともあり、進捗は良くなかったと思います。
しかし、時間を気にしなくていいのが日曜数学のいいところでもありますね。
さて、証明記事が完成したとき、ふと「この方法を使えば、長方形でなくても、任意のポリオミノをドミノで埋め尽くす方法の総数を計算できるんじゃね?」と思いついたのでした……が。
実際にやってみると、計算が合わない場合が出てきてしまいました。
少し悩みましたが、「ポリオミノに穴が開いていたらそれも計算にいれなければいけない」ということを見落としていたことに気が付いたおかげで、少し修正することで、ほぼ同じ方法で任意のポリオミノバージョンも作ることができたのでした!
修正できたのは
この成果は、
その後、
#日曜数学会
— apu (@apu_yokai) October 29, 2023
ドミノ埋め尽くしの総数と行列式の不思議な関係
発表スライド
1~4 /12 pic.twitter.com/5B6upw5GEH
≪リンク≫ 任意のポリオミノをドミノで埋め尽くす方法の総数を行列式を使って求める方法(日曜数学会)
それから間もない
≪リンク≫
togetter:J.Koizumi氏による、平方剰余とドミノタイリングを結びつける公式を発見についての、中澤俊彦さんと神尾悠陽さんとの共著論文についての解説
≪リンク≫
arxiv:Quadratic residues and domino tilings
その内容を少し解説します。
一方で、奇数
ルジャンドル記号の式とこの式を見比べてみると、カッコ内の符号が逆になっているほかはまったく同じ形になっていることがわかりますね!
これがただの偶然ではないというのです。
J.Koizumi (sub)@J_Koizumi_233 さんのポストを元に少し解説します。
奇素数
このとき、全てのドミノタイリングにわたるスコアの合計が
さらに、
彼はまだ学部生ですが数学的才能に溢れており、今回もこの問題について相談した日の夜に完全な証明が送られてきて、大変驚かされました。一般の正整数m,nに対する(m-1)×(n-1)のドミノタイリングの場合は、mまたはnは奇数と仮定してよく、mが奇数である場合のスコアの合計は以下のようになります。 pic.twitter.com/7uuBncg7Vr
— J.Koizumi (sub) (@J_Koizumi_233) November 23, 2023
ここで左辺のD_(m-1,n-1)は(m-1)×(n-1)のドミノタイリング全体のなす集合です。右辺の(n/m)は平方剰余記号の拡張(Jacobi記号)であり、m=p_1×p_2×...と素因数分解して(n/p_i)を掛け合わせることで定義されます。
— J.Koizumi (sub) (@J_Koizumi_233) November 23, 2023
ちなみに、平方剰余の相互律(下式)は長方形の縦横を入れ替えることに対応しています。 pic.twitter.com/uKRem45f3k
ということで、
私はこの論文の内容をまだほとんど理解していないので、語れることはあまりないのですが、それでも少し気が付いたことがあります。
先のドミノタイリングの式を導出したときに、ドミノタイリングに対応するグラフの「タテの辺の重みを
そんなわけでパフィアンを計算するプログラムを作ろう……と思ったのですが、ググってもやり方がよくわからないので、chatGPT3.5と相談しながら作ることにしました。
chatGPT3.5が作ってくれたパフィアン計算プログラムは、致命的なバグが複数あり、そのままでは使えませんでしたが、骨格部分はできていたので、半日くらいかけて修正したらちゃんとパフィアンが計算できるようになりました。
とはいえ、もし私がchatGPTの力を借りなければ、今でもプログラムは完成していなかったことでしょう。今回、AIの恩恵・凄さというものを、最も感じた瞬間でした。
……おっと、脱線しすぎましたね。話を元に戻しましょう。
実際に計算した c++ のプログラムを以下に載せます。
このプログラムは、 forループで
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <complex>
#include <numeric>
#include <Eigen/Dense>
using namespace std;
using namespace Eigen;
typedef long long ll;
// 複素数型
using Complex = complex<double>;
// 複素行列型
using ComplexMatrix = vector<vector<Complex>>;
// ルジャンドル記号との関係を調べる
// ドミノタイリングのときのグラフの辺の重みを全部1にする
// 行列の中身を出力する関数
void printMatrix(const ComplexMatrix& matrix) {
for (const auto& row : matrix) {
for (const auto& element : row) {
cout << element << " ";
}
cout << endl;
}
}
// 交代行列を取得する関数
ComplexMatrix getSkewSymmetricMatrix(const ComplexMatrix& matrix) {
ComplexMatrix skewSymmetricMatrix = matrix;
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[i].size(); ++j) {
skewSymmetricMatrix[i][j] = -matrix[j][i];
}
}
return skewSymmetricMatrix;
}
// パフィアンの再帰的な計算
Complex recursivePfaffian(const ComplexMatrix& matrix, const vector<int>& indices) {
if (indices.size() == 2) {
return matrix[indices[0]][indices[1]];
}
Complex result = 0.0;
Complex s = Complex(1.0, 0);
for (size_t i = 1; i < indices.size(); i ++) {
if ( matrix[indices[0]][indices[i]] != 0.0){
vector<int> subIndices(indices.begin(), indices.end());
subIndices.erase(subIndices.begin() + 0);
subIndices.erase(subIndices.begin() + i - 1);
result += s * matrix[indices[0]][indices[i]] * recursivePfaffian(matrix, subIndices);
}
s = -s;
}
return result;
}
// パフィアンを計算
Complex calculatePfaffian(const ComplexMatrix& matrix) {
ComplexMatrix skewSymmetricMatrix = getSkewSymmetricMatrix(matrix);
//cout << "Original Matrix:" << endl;
//printMatrix(matrix);
//cout << "\nSkew Symmetric Matrix:" << endl;
//printMatrix(skewSymmetricMatrix);
vector<int> indices(matrix.size());
iota(indices.begin(), indices.end(), 0);
return recursivePfaffian(skewSymmetricMatrix, indices);
}
int main() {
// ドミノタイリングで水平ドミノの数をh(D)としたときのスコア(-1)^(h(D)/2)の総和
// by @apu_yokai
// double の精度で計算しているため、頂点数が多くなると誤差がでてきます。
for (int m = 2; m < 10; m += 2) {
cout << "[" << m+1 << "]" ;
for (int n = 1; n < 9; n++) {
vector<pair<ll, ll>> V={}; // 頂点を入れる配列
for(int jj = 1; jj <= n; jj++) {
for (int ii = m; ii >= 1; ii--) {
V.push_back(make_pair(m + 1 - ii, jj));
}
}
// 行列式計算のための複素行列の宣言
MatrixXcd complexMatrix(V.size(), V.size());
// パフィアン計算のための行列の宣言(同じ行列を作っており冗長 要改善)
ComplexMatrix copymatrix(V.size(),vector<Complex>(V.size()));
for (int ii = 0; ii < V.size(); ii++) {
for (int jj = 0; jj < V.size(); jj++) {
int i = V.at(ii).first;
int j = V.at(ii).second;
int k = V.at(jj).first;
int l = V.at(jj).second;
// ここから隣接行列の成分を作成
// parity が -1 のときは縦方向を -1倍にしている
if ( k == i && l == j - 1) { complexMatrix(ii, jj) = complex<double>(-1.0, 0.0);
copymatrix[ii][jj]=complex<double>(-1.0, 0.0);}
else if (k == i && l == j + 1) { complexMatrix(ii, jj) = complex<double>(1.0, 0.0);
copymatrix[ii][jj]=complex<double>(1.0, 0.0);}
else if (k == i + 1 && l == j) { complexMatrix(ii, jj) = complex<double>(1.0, 0.0);
copymatrix[ii][jj]=complex<double>(1.0, 0.0);}
else if (k == i - 1 && l == j) { complexMatrix(ii, jj) = complex<double>(-1.0, 0.0);
copymatrix[ii][jj]=complex<double>(-1.0, 0.0);}
else { complexMatrix(ii, jj) = complex<double>(0.0, 0.0);
copymatrix[ii][jj]=complex<double>(0.0, 0.0);
}
}
}
// 行列式を計算し、実部を取り出す(虚部はゼロになる)
double det = complexMatrix.determinant().real();
// パフィアンを計算し、実部を取り出す(虚部はゼロになる)
Complex pf = calculatePfaffian(copymatrix);
// 出力の精度を設定
cout << setprecision(15); // 15桁の精度
// 結果を出力
//cout << "パフィアンの値(実部・虚部): " << pf << endl;
//cout << "パフィアンの値(実部): " << pf.real() << endl;
//cout << "行列式の値: " << det << endl;
cout << pf.real() << " ";
}
cout << endl;
}
return 0;
}
このプログラム、出力しないのに行列式も計算しているのは、いろいろ実験して遊ぶことを想定しているからです。
行列式計算部分を削除すればもっと短く、軽くすることもできますのでいろいろアレンジしてもらえればと思います。
それを含めてかなり冗長な処理になってしまっていると思いますが、素人がchatGPT3.5と相談しながら作ったプログラムということで大目に見ていただければと思います。
パフィアンを計算するアルゴリズムを簡単に説明します。
計算には、パフィアンの次の性質を使っています。
これは行列式における余因子展開にあたる公式で、これを再帰的に適用することでパフィアンを求めることができるというわけです。
なお、
さておき、出力結果はつぎのようになりました。
[ ]は
各行は左から
[3]1 0 -1 -1 0 1 1 0
[5]1 -1 -1 0 -1 -1 1 1
[7]1 -1 1 -1 -1 0 1 1
[9]1 0 1 1 0 1 1 0
この表が Wikipedia のヤコビ記号の表と一致するのかどうか見比べてみると・・・
(Wikipedia のヤコビ記号の表をもとに作成)
3 | -1 | 0 | 1 | -1 | 0 | 1 | -1 | 0 |
5 | -1 | -1 | 1 | 0 | 1 | -1 | -1 | 1 |
7 | 1 | -1 | 1 | -1 | -1 | 0 | 1 | 1 |
9 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
……あれ?少し違いますね?
……と思って見直してみると
ですから、
「
ということでした。
少しややこしいですが、これにあわせて表をこんな風に修正してみると……
3 | 1 | 0 | -1 | -1 | 0 | 1 | 1 | 0 |
5 | 1 | -1 | -1 | 0 | -1 | -1 | 1 | 1 |
7 | 1 | -1 | 1 | -1 | -1 | 0 | 1 | 1 |
9 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
プログラムが出力した表と確かに一致していることが確認できました!
さて、時が少し戻って
ブラウザ上で動作するようにしてみました!
— Tatt(たっと) (@tatt61880) October 27, 2023
現時点では、幅と高さを6に固定しています。
“ドミノ数え上げ” https://t.co/cQHPWsBW70 pic.twitter.com/0OqGFtzjvw
ドミノ数え上げゲーム
自由にタイルを配置して、すぐにドミノ配置パターンが何通りあるかわかり、しかも、見つけたパターン数をコレクションできる楽しいゲームです。
遊んでいると時間が溶けてしまう危険なゲームです。
ここから、意外な方向へ話が転がっていきます。
このドミノ数え上げゲームでステージの大きさを無限にしたら全ての自然数のパターンを網羅できるかどうかについてポストしたところ……
apu_yokaiの11月18日のポスト
X(旧Twitter)apu_yokai:ドミノ数え上げゲーム、ステージの大きさを無限にしたら全ての自然数のパターンを網羅できるだろうか?
このポストのリプライにあるように、suisen(@_su1sen)さん、べーたTCM-β(@tcmbeta)さん、
Tatt(たっと)(@tatt61880) さんが任意の自然数とおりを構成できるパターンを色々と構成してみせてくれました。
つまり、ステージの広さが無限であれば、任意の数のパターンが構成可能なのです!
自分で考えたい人もいると思いますので、具体的な構成例は↓に隠しておきます。
というわけで、↑のパターンを見れば、「高さ
次に、「高さ
さすがに、高さ
べーたTCM-β@tcmbeta さんの11月30日のポスト
X(旧Twitter)tcmbeta:手計算を諦め、プログラムにより4桁の素数は全部可能と判明しました。大きな素数でも、例えば100003を構成することができました↓
100003とおりのパターン
なんと、少なくとも
この記事を書いている
というわけで、
私は普段、こんな感じでX(旧Twitter)上で情報交換しながら日曜数学活動をしています。一人ではたどりつけない世界でも、みんなで議論しながらなら垣間見ることができるのがこのスタイルのいいところですね。
これでこの記事はおしまいですが、ドミノタイリングにはまだまだ面白い話題がかくれていそうです。
みなさんもドミノタイリングで遊んでみてください!
それでは明日のアドベントカレンダーは kiguro_masanao さんの「書籍『笑わない数学』裏話」ですね!
それでは~。