2021-05-29

n人から偶数人を選ぶ方法は2^{n-1}通り

命題

自然数 $n$ に対して以下が成立する．
$\displaystyle\sum_{k\geq 0}\binom{n}{2k}=2^{n-1}$ .

証明

$n$ 人の中から偶数人の参加者を選ぶ方法が $2^{n-1}$ 通りであることを言えばよい．
参加者を次のように決める：
一人目，二人目,..., $n-1$ 人目までは，参加／不参加を自由に決める．
最後の $n$ 人目は参加者の合計が偶数になるように，それまでの選び方に依存して決める．
よって，決め方は $2^{n-1}$ 通り．
（証明終わり）

補足

ここから， $n$ 人から奇数人を選ぶ方法も $2^{n-1}$ 通りであることがわかる．

2021-05-29

スターリング数の恒等式Σc(n,k)2^k=(n+1)!のシンプルな証明

スターリング数全単射的証明置換

前回の記事（第一種スターリング数の恒等式 Σc(n,k)2^k=(n+1)!の三通りの証明 - 数学の命題示しました）では、第一種スターリング数の恒等式
$\displaystyle\sum_{k=0}^nc(n,k)2^k=(n+1)!$
に二通りの全単射的証明をつけた。

今回は、
Amazon | Proofs that Really Count: The Art of Combinatorial Proof (Dolciani Mathematical Expositions) | Benjamin, Arthur T., Quinn, Jennifer J. | Logic
という本の106ページに、この恒等式のよりきれいな証明を見つけたので、紹介する。
まず、全単射の構成に必要な「標準サイクル記法」について説明する。

置換の標準サイクル記法

（サイクル記法を一意的に定める方法は目的によって色々あり，前の記事で紹介した「標準サイクル記法」と以下で述べるものは別であることに注意．）
置換をサイクルの積として書く書き方の中で

各サイクルの先頭要素は、そのサイクルの中の最大要素である。
サイクルは、先頭要素が小さい順に並んでいる。

をみたすものは一意的に定まり、標準サイクル記法という。
例えば、置換 $\sigma = (5)(364)(12)(78)$ の標準サイクル記法は $\sigma=(21)(5)(643)(87)$ である。

ちなみに、置換を標準サイクル記法により書いた場合、サイクルの区切りを表すカッコ「 $(,)$ 」は書かなくてもよくなる。
なぜなら、標準サイクル記法 $\sigma=(21)(5)(643)(87)$ において、サイクルの区切りは今までで最大の数が出現する場所として同定できるからである。
そのため、 $21564387$ と書いてもよい。
標準サイクル記法からカッコを除いてできるワードを置換のワード記法と見れば、これは $\mathfrak{S}_n$ から自身への全単射を定める。
詳しくは
Amazon | Enumerative Combinatorics (Cambridge Studies in Advanced Mathematics, Series Number 49) | Stanley, Richard P. | Pure Mathematics
に書いてある。

全単射的証明

示すべき等式をもう一度書いておく．
$\displaystyle\sum_{k=0}^nc(n,k)2^k=(n+1)!$

左辺は $n$ の置換を標準サイクル記法で書き、各サイクルごとに色 $\{赤、青\}$ を定めたものの集合の濃度である。式で書くと、 $\#\{(\sigma,f)\mid\sigma\in\mathfrak{S}_n,f\colon(\sigma{\rm のサイクルの集合})\to\{赤、青\}\}$ である。
右辺は、 $\mathfrak{S}_{n+1}$ の濃度である。

よって以下の全単射を作ればよい。
$\{(\sigma,f)\mid\sigma\in\mathfrak{S}_n,f\colon(\sigma{\rm のサイクル}の集合)\to\{赤、青\}\}\to \mathfrak{S}_{n+1}$

以下で全単射の構成を例を交えながら述べる：
まず左辺の元、例えば「(21)(5)(643)(87)」をとる。
赤いサイクルはそのまま残し、青いサイクルは並び順を保ったまま連結してひとつのサイクルにして先頭に「9」をつける。最後に色をなくす。
結果的に「(5)(643)(92187)」が得られる。
但し、すべてのサイクルが赤い場合は、単にサイクル「(9)」を加えて色をなくす。
この対応は可逆である。
（証明終わり）

恒等式の精密化

上で構成した全単射は、以下の恒等式の証明にもなっている。
$\displaystyle\sum_{k=0}^nc(n,k)\binom{k}{r}=c(n+1,r+1)$ .

これは、左辺で赤いサイクルが $r$ 個ならば、右辺ではサイクルが $r+1$ 個になることから分かる。
この式の両辺を $r$ について和を取れば、最初に述べた恒等式を得る。

2021-05-27

第一種スターリング数の恒等式 Σc(n,k)2^k=(n+1)!の三通りの証明

スターリング数置換全単射的証明

追記：よりシンプルな証明を本で見つけたので、記事にしました。
iwalion.hatenablog.com

ツイッターで「スターリング数」で検索してみると、次のようなツイートを見かけた。

第1種スターリング数（n個の数をkこの巡回列に分解する方法の場合の数）のこの性質、1つ目は直感的に理解できるんだけど2つ目のこれどうやっても直感的に理解できない pic.twitter.com/tqqum01I2Q
— さかな (@Enjapma_kyopro) 2019年9月22日

消えたときのためにもう一度書いておくと
命題１
$\displaystyle\sum_{k=0}^n2^kc(n,k)=(n+1)!$

をどう示すか、という問題である。（上記の $c(n,k)$ は第一種スターリング数。）

この記事では、この式について代数的証明、全単射的証明その１、全単射的証明その２をつける。
命題１を直感的に理解したいという元のツイートの趣旨を、全単射的証明により叶えられたらよいと思っている。

全単射的証明その２では第一種スターリング数 $c(n,k)$ を「 $n$ の置換でサイクル数 $k$ なものの数」として理解するのではなく、「0-1タブロー」と呼ばれるオブジェクトとして扱う。
（見方を変えただけでやっていることは全単射的証明その１と一緒な気はする。）

代数的証明

第一種スターリング数の定義は色々あるが、例えば
(式０)： $\displaystyle x(x+1)\cdots(x+n-1)=\sum_{k=0}^n c(n,k)x^k$
を満たす数 $c(n,k)$ と定義される。
つまり、左辺 $\prod_{i=0}^{n-1}(x+i)$ を展開したときの $x^k$ の係数が第一種スターリング数 $c(n,k)$ である。
（例えばWikipediaを参照: スターリング数 - Wikipedia）
式０に $x=2$ を入れれば、命題１が示される。（証明終わり）

全単射的証明その１

以下のことを示す。
(式１)： $\displaystyle(n+1)\sum_{k=0}^{n-1}c(n-1,k)2^k=\sum_{k=0}^nc(n,k)2^k$ .
式１が示せれば、帰納法により命題１が示される。
式１を全単射的に示すために、「色付き置換」というオブジェクトを考える。
（これについては、以前の記事で述べたものと同じであるがもう一度書いておく。）
「色付き置換」の集合 $\mathcal{S}_n$ を
$\displaystyle\mathcal{S}_n\triangleq\left\{(\sigma,f)\mid \sigma\in\mathfrak{S}_n,\ f\colon (\sigma {\rm のサイクルの集合}) \to \{0,1\}\right\}$
と定める。つまり色付き置換とは、置換をサイクル分解してサイクルごとに色 $\{0,1\}$ を決めたものである。
式１を示すには、以下のような全単射 $\varphi$ を構成すればよい。
$\varphi\colon \{0,\ldots,n\}\times \mathcal{S}_{n-1}\to\mathcal{S}_{n}$ .

全単射 $\varphi$ は次のように構成できる。
$(\sigma,f)\in\mathcal{S}_{n-1}$ と $i\in\{0,\ldots,n\}$ とをとったとき、 $\mathcal{S}_n$ の元を次のように定める。

$i=0,1$ のとき、色 $i$ をもつ新しいサイクル $(n)$ を色付き置換 $(\sigma,f)$ に追加する。
$i=2,\ldots,n$ のとき、色付き置換 $(\sigma,f)$ には要素 $i-1$ を含むサイクルが存在する。要素 $i-1$ の前に要素 $n$ を追加する。

この対応は全単射的である。
（証明終わり）

全単射的証明その２

この証明ではまず、置換を全単射的に「0-1タブロー」というオブジェクトにに変換する。

「0-1タブロー」はLeroux [1]により導入されたオブジェクトで、ここでは次のように定義する。
分割 $\lambda=(\lambda_1\geq\lambda_2\geq\ldots\geq\lambda_r\geq0)$ は次の条件を満たすとする。

$\lambda_1=n$ である。
転置をとった分割 $\lambda'$ は要素がすべて異なる、つまり $\lambda'=(\lambda_1'\gt\lambda_2'\gt\cdots)$ を満たす。

このような分割 $\lambda$ のヤング図形の各列に一個づつ $1$ を入れ、残りの場所に $0$ を入れたものを「0-1タブロー」といい、その集合を ${\rm Td}(r,n)$ とかく。
例：
f:id:iwalion:20210527132423j:plain

以下に見るように、この「0-1タブロー」を使って第一種スターリング数を表すことができる。
補題
下式が成立する。
$\#{\rm Td}(n-1,n-k)=c(n,k)$ .

補題を証明する前に、置換の「標準サイクル記法」について説明する。
標準サイクル記法とは、置換をサイクル分解したあと、各サイクルを先頭が最も小さい巡回置換として書き、それらの巡回置換を先頭要素が小さい順に一列に並べたものである。
つまり、置換
$\sigma=(65)(8)(47213)$
の標準サイクル記法は
$\sigma=(13472)(56)(8)$
である。

補題の証明
この証明はde Médicis [2]から引用している。
$n$ 文字の置換でサイクル数 $k$ のものと、集合 ${\rm Td}(n-1,n-k)$ との間に全単射 $\varphi$ を作ることができる。
全単射は以下のように帰納的に構成する。
まず、1文字の置換 $\sigma=(1)$ は、空の0-1タブローに対応するとする。
つまり、 $\varphi( (1) )\triangleq\emptyset$ .
次に置換 $\sigma$ が $n$ 文字の置換であるとき、文字 $n$ を抜いて $n-1$ 文字の置換 $\sigma'$ を作る。
置換 $\sigma'$ に対しては、0-1タブロー $T$ がもうすでに構成されているとする。
その上で、

文字 $n$ が置換 $\sigma$ において、サイクル $(n)$ に含まれるとき：

$\varphi(\sigma)\triangleq T$ とする。

文字 $n$ が置換 $\sigma$ において、 $(n)$ でないあるサイクルに含まれるとき：

置換 $\sigma$ の標準サイクル記法において、文字 $n$ が左から $i$ 番目にあるとする。
このとき、タブロー $T$ の先頭の列に $n-1$ 個の箱を追加し、上から $i-1$ 番目の箱に「1」を入れ、他の箱には「0」を入れる。
こうして構成された0-1タブローを $\varphi(\sigma)$ の値とする。

この対応は全単射的である。
（証明終わり）

対応の例：
f:id:iwalion:20210527132517j:plain

対応の例（順を追ってタブローを構成する様子）：
f:id:iwalion:20210527132555j:plain

以上の準備により、命題１を示すための全単射を構成できる。
命題２
以下の全単射 $\psi$ が構成できる。
$\displaystyle \psi\colon\bigsqcup_{k=0}^{n}{\rm Td}(n-1,n-k)\times\{0,1\}^k\to {\rm Td}(n+1,n+1)$ .

ここから直ちに、
$\displaystyle \sum_{k=0}^nc(n,k)2^k=c(n+2,1)=(n+1)!$
が成立し、命題１が導かれる。

命題２の証明
下図の通り。（証明終わり）
f:id:iwalion:20210527132610j:plain

補足：この全単射と同じノリで、式０に $x=r+1$ を入れてできる式
$\displaystyle (n+1)!=r!\sum_{k=0}^n(r+1)^kc(n-r+1,k)$
も全単射的に示すことができる。

参考文献

[1]
www.sciencedirect.com

[2]
www.sciencedirect.com

2021-05-27

第一種，第二種スターリング数を対称多項式で表す

スターリング数

本記事の結論

時間がない人のために結論だけ書くと，以下が成立する (cf. [2])．
$c(n,k)=e_{n-k}(1,2,\ldots,n-1)$ ,
$S(n,k)=h_{n-k}(1,2,\ldots,k)$ .

$c$ と $S$ はそれぞれ第一種，第二種スターリング数で，右辺は基本，完全対称式である．
この $1,2,\ldots$ を $[1]_q,[2]_q,\ldots$ に変えると，
標準的な $q-$ スターリング数と呼ばれているものが得られる．

第一種，第二種スターリング数

定義 (第一種，第二種スターリング数)
非負整数 $n,k$ に対して第一種スターリング数 $c(n,k)$ ，第二種スターリング数 $S(n,k)$ をそれぞれ
$x(x-1)\cdots(x-n+1)=\sum_{k=0}^n(-1)^{n-k}c(n,k)\cdot x^k$ ,
$x^n=\sum_{k=0}^nS(n,k)\cdot x(x-1)\cdots(x-k+1)$
を満たす実数として定義する．

スターリング数は実は非負整数になり，以下のような組合せ論的な意味をもつ．

定理１ (第一種スターリング数の組合せ論的意味づけ，cf. [1])
任意の非負整数 $n,k$ について，第一種スターリング数 $c(n,k)$ は，
$n$ 文字の置換のうちサイクル数 $k$ であるものの個数に等しい．

定理２ (第二種スターリング数の組合せ論的意味づけ，cf. [1])
任意の非負整数 $n,k$ について，第二種スターリング数 $S(n,k)$ は，
$n$ 点集合の $k$ 部分への分割の個数に等しい．

上記二つの性質の説明は，本ブログの記事
第一種，第二種スターリング数 - 数学の命題示しました
でも述べた．
また，スターリング数は以下の漸化式を満たすことが知られている．

定理３ (スターリング数の満たす漸化式．cf. [2])
$c(n+1,k)=n\cdot c(n,k)+c(n,k-1)$ ,
$S(n+1,k)=k\cdot S(n,k)+S(n,k-1)$ ,

上記の漸化式についての証明は，Wikipediaの記事が見やすいかもしれない．

本記事では，対称多項式を使ってスターリング数を表す方法について述べる．

基本対称式や完全対称式を使ってスターリング数を表す

基本対称式 $e_k(x_1,\cdots,x_n)$ と完全対称式 $h_k(x_1,\cdots,x_n)$ の定義は
色々な方法があるが，ここでは以下のように定義する．

定義 (基本対称式，完全対称式)
変数 $x_1,\ldots,x_n$ についての多項式 $e_k(x_1,\ldots,x_n)$ と $h_k(x_1,\ldots,x_n)$
とを，それぞれ以下を満たす式として定義する．
$\sum_{k\geq 0}e_k(x_1,\ldots,x_n)t^k=\prod_{i=1}^n(1+tx_i)$ ,
$\sum_{k\geq 0}h_k(x_1,\ldots,x_n)t^k=\prod_{i=1}^n\frac{1}{1-tx_i}$ .

これを使って，第一種，第二種スターリング数は以下の通り表される．

定理４ (スターリング数の対称多項式を使った表示．cf. [2])
$c(n,k)=e_{n-k}(1,2,\ldots,n-1)$ ,
$S(n,k)=h_{n-k}(1,2,\ldots,k)$ .

定理４の証明の概略

基本対称式と完全対称式はそれぞれ，以下の漸化式を満たす．

定理５ (基本対称式，完全対称式の満たす漸化式)
$e_m(z_1,\ldots,z_n,z_{n+1})=z_{n+1}e_{m-1}(z_1,\ldots,z_n)+e_m(z_1,\ldots,z_n)$ ,
$h_m(z_1,\ldots,z_n,z_{n+1})=z_{n+1}h_{m-1}(z_1,\ldots,z_n,z_{n+1})+h_m(z_1,\ldots,z_n)$ .

この漸化式については，上は[3]，下は[4]を参照せよ．

この漸化式に
$(z_1,z_2,\ldots):=(1,2,\ldots)$
を入れれば，例えば $e_{n-k}(1,2,\ldots,n-1)$ と $c(n,k)$ とは
定理３にある漸化式をともに満たすことが分かる．
$S(n,k)$ についても同様である．

引用文献

[1]
A Course in Enumeration | Martin Aigner | Springer

[2]
Reduced matrices and q-log-concavity properties of q-Stirling numbers - ScienceDirect

[3]
Elementary Symmetric Function/Examples/Recursion - ProofWiki

[4]
Determinants Involving the Numbers of the Stirling-Type

2021-03-31

平行六角形の内接楕円の公式

高校数学

実数 $a,b,c,p,q$ $(a\lt b\lt p)$ , $(-c\lt q\lt c)$ をとり，
点 $(a,c),(b,c),(p,q),(-a,-c),(-b,-c),(-p,-q),(a,c)$ をこの順番に線分で結んでできる有界領域を「平行六角形」と呼ぶことにする．

つまり，以下の図みたいなやつのことである．
f:id:iwalion:20210331125545j:plain

平行六角形には上の図に赤い点線で描いたような内接楕円が存在するように見える．
ここでいう内接楕円とは，平行六角形の六辺全てに接する楕円のことをいう．
本記事ではその式を求める．

内接楕円を求める

本当に示したいのは以下のことなのだが，
予想
任意の平行六角形には内接楕円が存在する．

ここではそれより弱い次のことを示した．
命題
任意の平行六角形に対して，その六辺を延長した直線全てに接する二次曲線が存在する．
（ここでいう二次曲線は必ずしも実曲線とは限らない．）

証明
原点に関して点対称な二次曲線で，条件に合うものを探すことにする．
二次曲線 $E$ を
$E\colon(x+y\tan\theta)^2/A^2+(-x\tan\theta+y)^2/B^2=1$
とおく．

点 $(a,c),(b,c)$ を通る直線は $\ell_1\colon y=c$ ,
点 $(b,c),(p,q)$ を通る直線は $\ell_2\colon y-c=(q-c)(x-b)/(p-b)$ ,
点 $(a,c),(-p,-q)$ を通る直線は $\ell_3\colon y-c=(-q-c)(x-a)/(-p-a)$
である．

以下，二次曲線 $E$ が直線 $\ell_1,\ell_2,\ell_3$ に接するように $A^2,B^2,\tan\theta$ を決める．

二次曲線 $E$ と直線 $\ell_1$ が接するので， $E,\ell_1$ から $y$ を消去してできる
$x$ の二次方程式において判別式 $=0$ である．これを整理すると：
(式1)
$\tan^2\theta \cdot A^2+B^2-c^2(\tan^2\theta+1)^2=0$
を得る．

次に $E$ と直線 $\ell_2$ が接するので， $y$ を消去して判別式 $=0$ より
(式2)
$((b-p)\tan\theta-c+q)^2A^2+((c-q)\tan\theta+b-p)^2B^2-(\tan^2\theta+1)^2(bq-cp)^2=0$
を得る．

また $E$ と直線 $\ell_3$ が接するので， $y$ を消去して判別式 $=0$ より
(式3)
$((p+a)\tan\theta-c-q)^2A^2+((q+c)\tan\theta+a+p)^2B^2-(\tan^2\theta+1)^2(aq-cp)^2=0$
を得る．

(式1)と(式2)を連立すると，以下の通り $A^2,B^2$ を $\tan\theta$ で表す式が得られる．
(式4)
$A^2=(c(c-q)\tan\theta+bc-2pc+bq)(\tan^2\theta+1)(c\tan\theta+b)$
　　 $\div((c-q)\tan^2\theta+2(b-p)\tan\theta-(c-q) )$ ,
(式5)
$B^2=( (bc-2pc+bq)\tan\theta-c(c-q) ) (\tan^2\theta+1)(b\tan\theta-c)$
　　 $\div( (c-q)\tan^2\theta+2(b-p)\tan\theta-(c-q) )$ .

また(式1)と(式3)を連立すると，同じく $A^2,B^2$ を $\tan\theta$ で表す式が得られる．
(式6)
$A^2=(c(c+q)\tan\theta+ac+2pc-aq)(tan^2\theta+1)(c\tan\theta+a)$
　　 $\div( (c+q)\tan^2\theta+2(a+p)\tan\theta-c(c+q) )$ ,
(式7)
$B^2=((ac+2pc-aq)\tan\theta-c(c+q) )(tan^2\theta+1)(b\tan\theta-c)$
　　 $\div( (c+q)\tan^2\theta+2(a+p)\tan\theta-c(c+q) )$ .

二次曲線が存在するためには，(式4)，(式5)，(式6)，(式7)を同時に満たす $\tan\theta$ が存在しなければならない．
それは実際存在することが以下のように分かる．
(式4)と(式6)より， $A^2$ を消去して $\tan\theta$ の方程式として解くと
$S\triangleq ac-aq+bc+bq\neq 0,$ (これは最初の条件より成立する)
$T\triangleq -ab+ap-bp+c^2$ とすると
$\tan\theta=\pm i, (T\pm\sqrt{T^2+S^2})/S$
を得る．

また，(式5)と(式7)からは
$\tan\theta=0,\pm i, (T\pm\sqrt{T^2+S^2})/S$
が得られる．

結局， $\tan\theta$ が実数になる
$\tan\theta = (T\pm\sqrt{T^2+S^2})/S$
の方をとればよい．

(証明終わり．)

楕円の存在を言うためにはこの $\tan\theta$ をとったときに $A^2,B^2$ が正になることを確かめないといけないのだが，少し考えたがよく分からなかったので示せていない．
$a,b,c,p,q$ を最初の条件の通り与えれば，楕円以外の双曲線になることはない気がしているのだが．
そう思う根拠は，平行六角形を図形的に見ると，六辺に接するように円錐曲線 (楕円，放物線，双曲線)を引く方法は楕円にするしかない気がするから．

上記の証明中で $\tan\theta$ が $\pm$ の二つ出てきたが，これらの二つはどちらも同じ楕円を与えるような気がしていて，
内接楕円の唯一性も言える気がしている．

内接楕円の公式

分かったことを公式として書いておこうと思う．

内接楕円の公式

実数 $a,b,c,p,q$ $(a\lt b\lt p)$ , $(-c\lt q\lt c)$ が与えられているとする．
点 $(a,c),(b,c),(p,q),(-a,-c),(-b,-c),(-p,-q)$ を時計回りにこの順に頂点として持つ平行六角形の内接楕円は

$S\triangleq ac-aq+bc+bq,$
$T\triangleq -ab+ap-bp+c^2,$
$\tan\theta \triangleq (T\pm\sqrt{T^2+S^2})/S,$
$A^2\triangleq(c(c-q)\tan\theta+bc-2pc+bq)(\tan^2\theta+1)(c\tan\theta+b)$
　　 $\div((c-q)\tan^2\theta+2(b-p)\tan\theta-(c-q) ),$
$B^2\triangleq( (bc-2pc+bq)\tan\theta-c(c-q) ) (\tan^2\theta+1)(b\tan\theta-c)$
　　 $\div( (c-q)\tan^2\theta+2(b-p)\tan\theta-(c-q) )$
により

$E\colon(x+y\tan\theta)^2/A^2+(-x\tan\theta+y)^2/B^2=1$
と書かれる．（と思う．もしかしたら楕円にならないかもしれないので．）

図示

作った楕円を図示してみる．
$(a,b,c,p,q)\triangleq(-4,4,3,7,-1)$
ととる．すると平行六角形と楕円は以下のようになる．
直線どうしの交点 (の一部)が平行六角形の頂点を表している．
f:id:iwalion:20210331151104p:plain

平行六角形にならないような点のとり方をした場合

本記事では最初から平行六角形ができるように $(a,b,c,d,q)$ に条件をつけて考えたが，
この条件を外しても，上で求めた曲線は意味を持つ．
それについて図示してみると，双曲線とかになるっぽかった．（下図）
f:id:iwalion:20210331151451p:plain

図形的に気になったこと

(式1)，(式2)，(式3)は三平方の定理の形をしている．
何かしら図形的な解釈によってこの式を導くことができるのかもしれない．

2021-03-19

六角形をつないだ領域のひし形タイル張り

タイル張り

三角格子上の平行六角形は，大きさに関わらずひし形タイル張りができることが知られている [1]．
例えば，下図左の赤で示された領域は右のようなひし形タイル張りが可能である．

なので当然，任意の平行六角形に含まれる上向きの三角形△の数と下向きの三角形▽の数は等しい．

本記事では，平行六角形と別の領域とを辺でつなぎ合わせて作った領域のひし形タイル張りの数がどうなるかを二通り考え，それをもとに具体例を紹介する．

補題１

平行六角形 $H$ の一辺（の一部）と別の領域 $X$ をつなぎ合わせた領域のひし形タイル張りの数は， $H$ のタイル張りの数と $X$ のタイル張りの数の積に等しい．

考えているのは例えば下図のような状況である．

証明

$H$ と $X$ にまたがって貼られるひし形が無いことを言えばよい．
タイルのある貼り方において， $H$ と $X$ にまたがるひし形を全て取り除き，残ったひし形たちからなる領域を考える，
その領域と $H$ の共通部分はひし形で覆えるはずであるが，もし， $H$ と $X$ にまたがるひし形が一つでも存在するならば，共通部分は上向き三角形よりも下向き三角形が少なくなるので，ひし形で覆うことは不可能となる．
（証明終わり）

下図は，補題１の証明の状況を描いた図である．
$H$ と $X$ にまたがって張られるひし形は， $H$ の「下向き三角形」と， $X$ の「上向き三角形」をくっつけたものであることがわかるだろう．（図中の青いひし形を見よ．）

補題２

平行六角形 $H$ の頂点を時計回りに $H_1,H_2,\ldots,H_6$ とする．辺 $H_1H_2$ に別の領域 $X$ をつなぎ，辺 $H_3H_4$ に別の領域 $Y$ をつないで新しい領域を作る．
この領域のひし形タイル張りの数は，領域 $H,X,Y$ のタイル張りの数の積に等しい．

証明

補題１と殆ど同じである．
$H$ と $X$ ， $H$ と $Y$ にまたがるひし形タイルが置けないことを言えばよい．
そのようなタイルは $H$ の下向き三角形▽だけを使うことになるので， $H$ の残った部分は上向きと下向きの数が合わず，ひし形で覆うことができない．
（証明終わり）

下図左は，補題２の状況を示す図で，右は証明の状況を示す図である．（領域 $X$ と $Y$ は下の方で繋がっていても良い．）

応用例

以下では，領域 $X$ のひし形タイル張りの数を $M(X)$ とかく．

例１

証明

補題１を使う．

（証明終わり）

例２

証明

補題２を使う．

（証明終わり）

参考文献
[1]
www.sciencedirect.com

2021-03-16

菱形タイル張り　その１

タイル張り

上向きの正三角形△と下向きの正三角形▽をつなぎ合わせて作る，下図の赤い部分で表される領域を考える．
f:id:iwalion:20210316202632p:plain:h300
この領域は，
△▽△▽△▽△▽△▽△▽△
▽△▽△▽△▽△▽△▽△▽
みたいなやつを縦に積み重ねたものである．そこで，「底辺」に含まれる下向き三角形▽の数を $n$ ，積み重ねた段の数を $c$ として，
この領域を $R(n,c)$ と書くことにする．
図の領域は $R(7,4)$ である．

これから領域 $R(n,c)$ の菱形タイル張りの方法の数を考える．
菱形タイル張りとは，単位正三角形２つを辺でつなぎ合わせて作る「菱形のタイル」で領域を埋め尽くすことである．
例えば，次の図は $R(7,4)$ の菱形タイル張りの例である．
f:id:iwalion:20210316202749p:plain:h300

上の例は，タイルのやや特殊な貼り方に見えるが，実はそうではない．領域 $R(n,c)$ には，上図のような貼り方しかないというのが今日示すことである．

命題

領域 $R(n,c)$ を菱形タイル張りする方法の数は， $n^c$ 通りである．

これを示すために，２つの補題を示す．

補題１

領域 $R(n,c)$ の菱形タイル張りにおいて，「層と層にまたがる位置」に，縦向きの菱形を置くことはできない．

つまり言いたいことは，下図の状況がありえないということである．
f:id:iwalion:20210316202821p:plain:h300

補題１の証明

領域 $R(n,c)$ を菱形タイルで埋め尽くしたとき，「層と層にまたがる位置」に，縦向きの菱形があったとする．
そのような縦向きの菱形のうち，一番下にあるものを $H$ とする．

$H$ の四辺のうち，右下の辺を $v_1$ とする．辺 $v_1$ に接している $H$ でない方の菱形を $H^{(右)}_1$ とし，辺 $v_1$ の対辺を $v_2$ とする．
同様にして辺 $v_{i+1}$ に接して置かれている $H^{(右)}_{i}$ でない方の菱形を $H^{(右)}_{i+1}$ とし，辺 $v_{i+1}$ の対辺を $v_{i+2}$ とすることを繰り返すと，ある辺 $v_{I}$ は領域 $R(n,c)$ の境界の一部となる．
また， $H$ は一番下にあるということから，その辺 $v_{I}$ は，菱形 $H^{(右)}_{1}$ と同じ「層」にある事がわかる．