駆け足で読む『離散体積計算による組合せ数学入門』第６章 魔方陣

• 魔方陣と半魔方陣
  • 魔方陣はが縦・横・対角線の和が同じになるようににならべられたもの
  • 半魔方陣は非負整数成分を並べて、行・列の和が等しいもの
• 半魔方陣の制約は多面体とその格子点に対応させることができて、その場合の数は、多項式で表せる
  • Birkhoff-von Nuemann 多面体と呼ばれる
  • 行・列の和が等しい(１とすることもできる)ので、確率論でよく使われる。二重確率行列(doubly stochastic matrix)と言う(Wikiはこちら)
• 魔方陣の場合は、半魔方陣の制約に対角成分の制約を加えたものである
  • それは、整数線形方程式・不等式で表せる(条件が増えた)ので、有理多面体の格子点列挙問題となる
  • modによる場合分けが必要で、それが、数え上げにも反映される