ヨーキョクデイ

多趣味で器用貧乏なブログ(j は虚数単位)

ゲリマンダーを作ってみた

ja.wikipedia.org
数学的に公民を見るシリーズができた。前回は、

ということだろう。

概要

二大政党制を想定し、支持者の数で不利であろう A 党がそうでない B 党に勝つための選挙区の区分けを行いたい。

選挙のルールと勝敗

地区
各地区は A 党の支持者と B 党の支持者からなる。
選挙区
いくつかある地区をいくつかに区切って選挙区を作る。このとき、おのおのの選挙区は飛び地を持たないようにする。
各選挙区について、それに属する地区の各党の支持者数を党ごとに合算する。
選挙
選挙区ごとに、より多くの支持者数がいる党がその選挙区を獲得する。最終的に他党より多くの選挙区を獲得できた党が選挙において勝利する。
そんな小選挙区制のイメージ。
ja.wikipedia.org

ゲリマンダリングのシミュレーション

方法

あり得る区分けを列挙し、それぞれについて勝敗を評価する。

また、それについてはグラフ理論を用いるが、あまり一般的ではないかもしれない用語を定義したい。

グラフの分割連結分割
グラフ  G の頂点集合  V(G) の分割  \{V_j\} を考える。このとき、 \{V_j\} によって得られる  G の誘導部分グラフの集合  \{G[V_j]\} G分割 (partition) と呼ぶ。
とくに、分割  \{G[V_j]\} のすべての元が連結であるとき、連結分割 (connected partition) と呼ぶ。

連結分割は仮想的に適当な辺を除去することで仮想的な連結成分を作るイメージ。

グラフ理論の基本的なところは以下参照。
www.momoyama-usagi.com
www.momoyama-usagi.com

区分け

地区を頂点とし、地区どうしの隣接関係を辺としたグラフ  G(V) を作り、そのグラフを  N 個に連結分割した  \{G[V_j]\} を考える。 |\{j\}| = N である。この連結分割の各元に選挙区を紐付けることで  N 個の選挙区を得る。

勝敗

地区のスコア
各地区について A 党の支持者数から B 党の支持者数を引いた数をスコアと呼ぶことにし、各頂点  v_i \in V にスコア  S(v_i) を紐付ける。
選挙区の勝ち点

 G[V_j] に属する頂点のスコアの和  S_j を求める。すなわち、

\displaystyle  S_j = \sum_{v_i \in V_j} S(v_i)

である。さらに、これに基づいてそれぞれの選挙区  j勝ち点  P_j を次のように割り振ることにする。

 P_j =  \begin{cases}
1 & (S_j > 0) \\
0 & (S_j = 0) \\
 -1 & (S_j < 0)
 \end{cases}

選挙の勝敗
選挙区ごとの勝ち点の総和  \sum_j P_j が正であれば A 党の勝利とする。

具体例

15 個の地区を用意した。次のグラフに示す。

f:id:electrolysis:20210131234951p:plain
縦 3、横 5 の格子状に連なった地区

各頂点  v_i には地区の番号とスコアが  (i, S(v_i)) という対として記載されており、赤い頂点は  S(v_i) < 0、青い頂点は  S(v_i) > 0 であること示している。各頂点のスコアは番号順に、

\begin{align} \{S(v_i)\} =& -15, 21, -35, -31, -43, \\
& 26, -27, 15, 11, -48, \\
& 39, -12, 2, -10, -28
\end{align}

となっており、その和は  -135 である。また、赤い頂点は 9 個、青い頂点は 6 個である。すなわち、

  • 全体で見ると A 党の支持者数は B 党を下回っている
  • A 党支持者の多い地区のほうが B 党支持者の多い地区より少ない

という A 党劣勢を覆していくのが目的。

今回は選挙区を 3 つ設けたい。そういったグラフの分割方法は 5368 通りあるらしい。勝ち点の和ごとの内訳を次の表に示す。

勝ち点の和 分割方法の数
1 621
0 25
-1 3411
-2 42
-3 1269
5368

ゲリマンダーが成功する組合せが 621 通りあることを示している。

成功例
f:id:electrolysis:20210202202227p:plain
ゲリマンダー成功な区分け例

濃い色の辺で結ばれている部分グラフが選挙区に対応していると思ってほしい。

この例は地区の番号の分割が、

\displaystyle \{\{0, 5, 10, 11, 12, 13\}, \{1, 6, 7\}, \{2, 3, 4, 8, 9, 14\}\}

である場合である。すなわち、

\displaystyle (V_0, V_1, V_2) = (\{v_0, v_5, v_{10}, v_{11}, v_{12}, v_{13}\}, \{v_1, v_6, v_7\}, \{v_2, v_3, v_4, v_8, v_9, v_{14}\})

によるグラフの分割  \{G[V_0], G[V_1], G[V_2]\} を考えている。このとき、選挙区ごとのスコアの和は、

\displaystyle (S_0, S_1, S_2) = (30, -174, 9)

となり、勝ち点は

\displaystyle (P_0, P_1, P_2) = (1, -1, 1)

である。よって、勝ち点の和  P_0 + P_1 + P_2 1 であるから、A 党が大逆転勝利を遂げる。

また、次に図示する区分けは自明な成功例といえる。

f:id:electrolysis:20210202204004p:plain
自明な成功例

互いに隣接する有利な地区のみからなる勝ち点  1 が必然な選挙区の数が過半数を占めた時点で勝利する、トリビアルな区分けである。今回は一票の格差やらの平等性を無視したので、こういうのもアリ。

失敗例
f:id:electrolysis:20210202202322p:plain
ゲリマンダー失敗な区分け例

また、

\displaystyle  (V_0, V_1, V_2) = (\{v_0, v_1, v_2, v_3, v_5\}, \{v_4, v_6, v_7, v_8, v_9, v_{14}\}, \{v_{10}, v_{11}, v_{12}, v_{13}\})

による分割では、選挙区ごとのスコアの和は、

\displaystyle (S_0, S_1, S_2) = (-120, -34, 19)

となり、勝ち点は

\displaystyle (P_0, P_1, P_2) = (-1, -1, 1)

であるから、勝ち点の和が  -1 であり、A 党が敗北したのでゲリマンダー失敗である。

コード

今回のシミュレーションで使った SageMath のコード。与えるグラフが大きかったりすると終わらない。

def connected_partition_iterator(G, k):
    """
    Partition G into `k` connected induced subgraphs.
    """

    if G.order() == 0 or k > G.order():
        return

    root = G.vertices()[0]

    for csg_with_root in filter(
        lambda sg: root in sg,
        G.connected_subgraph_iterator(k=G.order() - k + 1),
    ):
        sg_opposite = G.subgraph(set(G) - set(csg_with_root))
        m = sg_opposite.connected_components_number()
        if m == k - 1:
            yield [csg_with_root] + [
                G.subgraph(cc) for cc in sg_opposite.connected_components(sort=False)
            ]
        elif m < k - 1:
            for parts in connected_partition_iterator(sg_opposite, k - 1):
                yield [csg_with_root] + [G.subgraph(part) for part in parts]


def custom_show(G, supergraph=None):
    excluded_edges = set(supergraph.edges()) - set(G.edges()) if supergraph else {}
    g = supergraph or G
    g.show(
        fig_tight=False,
        figsize=[5, 3],
        vertex_size=2200,
        vertex_colors={
            "white": list(filter(lambda v: v[1] == 0, g)),
            "lightblue": list(filter(lambda v: v[1] > 0, g)),
            "lightpink": list(filter(lambda v: v[1] < 0, g)),
        },
        edge_colors={"gainsboro": excluded_edges},
    )


def show_partition(partition, supergraph):
    custom_show(
        supergraph.subgraph(
            edges=set.union(*[set(part.edges()) for part in partition])
        ),
        supergraph,
    )


g = graphs.Grid2dGraph(3, 5)
scores = [-15, 21, -35, -31, -43, 26, -27, 15, 11, -48, 39, -12, 2, -10, -28]
assert g.order() == len(scores)
g.relabel(enumerate(scores))

n = 3

stats = {}
custom_show(g)

partitions = [*connected_partition_iterator(g, n)]

# show_partition(partitions[5152], g)

for i, partition in enumerate(partitions):
    assert len(partition) == n
    scores_by_part = [sum([v[1] for v in part]) for part in partition]
    result = sum(sgn(s) for s in scores_by_part)

    if not result in stats:
        stats[result] = []

    stats[result].append(
        (
            sorted(
                [sorted({v[0] for v in part}) for part in partition], key=lambda a: a[0]
            ),
            scores_by_part,
            i,
        )
    )

print("Stats:", [(k, len(stats[k])) for k in sorted(stats.keys(), reverse=True)])
print("Details: <partition> <scores> <points> <#>")
for k in sorted(stats.keys(), reverse=True):
    for p, s, i in stats[k]:
        print(p, s, k, "#%d" % i)

ハノイの塔の「和」に関する数列の一般化

前回の問題を一般化することにした。
e10s.hateblo.jp

問題・改

前回の問題と同様の最短手順で  n 段のハノイの塔を攻略するとき、

  •  k 番目に小さい円盤を k とする(最小の円盤が  1、最大の円盤が  n
  • 各手順について、円盤 k の移動先の柱に点数  f(k) が加算される
  • 最初の段階で各柱の点数は  0 である

という条件のもとで攻略終了時の柱  A, B, C の点数をそれぞれ  a_n, b_n, c_n として、それらを求めよ。

つまり、加算される点数が  k ではなく、 f(k) になった。

方針・改

ステップ 2 では  C f(n) 点加算されることに注意。すなわち、

 \begin{cases}
\displaystyle a_n = a_{n-1}+b_{n-1} \\
\displaystyle b_n = a_{n-1}+c_{n-1} \\
\displaystyle c_n = b_{n-1}+c_{n-1}+f(n)
\end{cases}

という連立漸化式を解く。前回と同様、 a_0 = b_0 = c_0 = 0 である。

解・改

z 変換

先の連立漸化式の辺々を z 変換すると、

 \begin{cases}
A(z) = z^{-1} A(z) + z^{-1} B(z) \\
B(z) = z^{-1} A(z) + z^{-1} C(z) \\
C(z) = z^{-1} B(z) + z^{-1} C(z) + \mathcal{Z}[f(n)]
\end{cases}

である。これを変形すると、

 \begin{cases}
\displaystyle A(z) = \frac{1}{z-1} B(z) \\
\displaystyle B(z) = \frac{z}{(z+1) (z-2)} \mathcal{Z}[f(n)] \\
\displaystyle C(z) = A(z) + \frac{z}{z-1} \mathcal{Z}[f(n)]
\end{cases}

が得られる。ここまでは前回と同様のアプローチ。さらに整理して、右辺を  z \mathcal{Z}[f(n)] で表すと、

 \begin{cases}
\displaystyle A(z) = \frac{z}{(z+1)(z-1)(z-2)} \mathcal{Z}[f(n)] \\
\displaystyle B(z) = \frac{z}{(z+1)(z-2)} \mathcal{Z}[f(n)] \\
\displaystyle C(z) = \left[ \frac{z}{(z+1)(z-1)(z-2)} + \frac{z}{z-1} \right] \mathcal{Z}[f(n)]
\end{cases}

となる。部分分数分解しておくと、

 \begin{cases}
\displaystyle A(z) = \frac{1}{6} \left[ \frac{z}{z+1} - \frac{3z}{z-1} + \frac{2z}{z-2} \right] \mathcal{Z}[f(n)] \\
\displaystyle B(z) = \frac{1}{3} \left[ -\frac{z}{z+1} + \frac{z}{z-2} \right] \mathcal{Z}[f(n)] \\
\displaystyle C(z) = \frac{1}{6} \left[ \frac{z}{z+1} + \frac{3z}{z-1} + \frac{2z}{z-2} \right] \mathcal{Z}[f(n)]
\end{cases}

が得られる。

逆 z 変換

 \mathcal{Z}[f(n)] の係数に注目したい。

 A(z), B(z), C(z) それぞれについて  \mathcal{Z}[f(n)] の係数の逆 z 変換を  a'_n, b'_n, c'_n とすると、

 \begin{cases}
\displaystyle a'_n = \frac{1}{6} \left[ (-1)^n - 3 + 2^{n+1} \right] = \frac{1}{6} \left[ 2^{n+1} - (-1)^{n+1} - 3 \right] \\
\displaystyle b'_n = \frac{1}{3} \left[ -(-1)^n+ 2^n \right] = \frac{1}{3} \left[ 2^n - (-1)^n \right] \\
\displaystyle c'_n = \frac{1}{6} \left[ (-1)^n + 3 + 2^{n+1} \right] = \frac{1}{6} \left[ 2^{n+1} - (-1)^{n+1} + 3 \right]
\end{cases}

Jacobsthal 数

Jacobsthal 数  J_n は以下で表される数列らしい。

\displaystyle  J_n = \frac{1}{3} \left[ 2^n - (-1)^n \right]

en.wikipedia.org
まさに  b'_n = J_n である。さらに  a'_n, c'_n J_n で表すことができて、

 \begin{cases}
\displaystyle a'_n = \frac{1}{2} (J_{n+1} - 1) \\
\displaystyle b'_n = J_n \\
\displaystyle c'_n = \frac{1}{2} (J_{n+1} + 1)
\end{cases}

となる。

続・逆 z 変換

これまでの結果から、

 \begin{cases}
\displaystyle A(z) = \mathcal{Z}[a'_n] \mathcal{Z}[f(n)] \\
\displaystyle B(z) = \mathcal{Z}[b'_n] \mathcal{Z}[f(n)] \\
\displaystyle C(z) = \mathcal{Z}[c'_n] \mathcal{Z}[f(n)]
\end{cases}

の辺々を逆 z 変換することで、

 \begin{cases}
\displaystyle a_n = a'_n * f(n) = \frac{1}{2} (J_{n+1} - 1) * f(n) \\
\displaystyle b_n =b'_n * f(n) = J_n * f(n) \\
\displaystyle c_n = c'_n * f(n) = \frac{1}{2} (J_{n+1} + 1) * f(n)
\end{cases}

となることがわかる。

例題

 n 段のハノイの塔の最短手順が  2^n-1 回であることを確かめよ。

 f(n) = u(n-1) = \begin{cases}
1 & (n \geq 1) \\
0 & (otherwise) \\
\end{cases}

としたときの、 a_n+b_n+c_n を求めればよい。

\begin{align}a_n+b_n+c_n
&= \frac{1}{2} (J_{n+1} - 1) * u(n-1) + J_n * u(n-1) + \frac{1}{2} (J_{n+1} + 1) * u(n-1) \\
&= (J_{n+1} + J_n) * u(n-1) \\
&= 2^n * u(n-1) \\
&= \sum_{m=0}^\infty 2^m u(n-m-1) \\
&= \sum_{m=0}^{n-1} 2^m \\
&= 2^n-1
\end{align}

おわり。

所感

前回よりも sophisticated な理論展開ができた気がする。

ハノイの塔の「和」に関する数列

f:id:electrolysis:20210102232450p:plain

ハノイの塔というパズルゲームがある。これは 3 本の柱  A,B,C と穴の開いた  n 枚の円盤から構成される。ゲーム開始状態では柱  A にすべての円盤が刺さっている。これらのすべての円盤を以下のルールに従って、柱  C に移動させるとゲームは完了する。

  • 開始状態から一貫して、どの柱についても任意の円盤の上にはそれよりも小さい円盤だけがある
  • 1 回の手順ではいずれかの柱の最上部の円盤 1 つを別のいずれかの柱に移動させる

これに従ってゲームを進めるとき、最短手順は  2^n-1 回であることが知られている。

また、この最短手順で攻略するための再帰的なアルゴリズムが知られている。

  1.  A の 上部  n-1 段を柱  B に移動する
  2.  A に残った円盤  n を柱  C に移動する
  3.  B n-1 段を柱  C に移動する

これを下に図示する。

f:id:electrolysis:20210102232217p:plain
ハノイの塔の再帰的解法

ja.wikipedia.org

問題

上記の最短手順で  n 段のハノイの塔を攻略するとき、

  •  k 番目に小さい円盤を k とする(最小の円盤が  1、最大の円盤が  n
  • 各手順について、円盤 k の移動先の柱に点数  k が加算される
  • 最初の段階で各柱の点数は  0 である

という条件のもとで攻略終了時の柱  A, B, C の点数をそれぞれ  a_n, b_n, c_n として、それらを求めよ。

方針

  1.  A の 上部  n-1 段を柱  B に移動する
  2.  A に残った円盤  n を柱  C に移動する
  3.  B n-1 段を柱  C に移動する

以上の 3 段階に分割して考える。

ステップ 1 では、柱  B と柱  C の役割が入れ替わっているので、 A a_{n-1} 点、 B c_{n-1} 点、 C b_{n-1} 点、それぞれ加算される。

ステップ 2 では  C n 点加算される。

ステップ 3 では、柱  A と柱  B の役割が入れ替わっているので、 A b_{n-1} 点、 B a_{n-1} 点、 C c_{n-1} 点、それぞれ加算される。

これらを合算すると、

 \begin{cases}
\displaystyle a_n = a_{n-1}+b_{n-1} \\
\displaystyle b_n = a_{n-1}+c_{n-1} \\
\displaystyle c_n = b_{n-1}+c_{n-1}+n
\end{cases}

という連立漸化式が得られる。また、 a_0 = b_0 = c_0 = 0 である。これを解けばよい。

z 変換

ja.wikipedia.org
 \mathcal{Z}[x_n] = X(z) に対して、 \mathcal{Z}[x_{n-1}] = z^{-1} X(z) であることを利用して、先の連立漸化式の辺々を z 変換すると、

 \begin{cases}
A(z) = z^{-1} A(z) + z^{-1} B(z)  \\
B(z) = z^{-1} A(z) + z^{-1} C(z) \\
C(z) = z^{-1} B(z) + z^{-1} C(z) + \mathcal{Z}[n]
\end{cases}

である。これを変形すると、

 \begin{cases}
\displaystyle A(z) = \frac{1}{z-1} B(z)  \\
\displaystyle B(z) = \frac{z}{(z+1) (z-2)} \mathcal{Z}[n] = \frac{z^2}{(z-1)^2 (z+1) (z-2)} \\
\displaystyle C(z) = A(z) + \frac{z}{z-1} \mathcal{Z}[n]
\end{cases}

が得られる。

逆 z 変換

 B(z) の式の最右辺を部分分数分解してみる。

\begin{align} B(z)
&= \frac{z^2}{(z-1)^2 (z+1) (z-2)} \\
&= z \left[ \frac{z}{(z-1)^2 (z+1) (z-2)} \right] \\
&= z \left[ -\frac{1}{2} \frac{1}{(z-1)^2} -\frac{3}{4} \frac{1}{z-1} + \frac{1}{12}\frac{1}{z+1} + \frac{2}{3}\frac{1}{z-2} \right] \\
&= -\frac{1}{2} \frac{z}{(z-1)^2} -\frac{3}{4} \frac{z}{z-1} + \frac{1}{12}\frac{z}{z+1} + \frac{2}{3}\frac{z}{z-2}\ \\
\end{align}

この両辺を逆 z 変換する。

\begin{align} \mathcal{Z}^{-1}[B(z)]
&= \mathcal{Z}^{-1} \left [-\frac{1}{2} \frac{z}{(z-1)^2} -\frac{3}{4} \frac{z}{z-1} + \frac{1}{12} \frac{z}{z+1} + \frac{2}{3} \frac{z}{z-2} \right] \\
&= -\frac{1}{2} n -\frac{3}{4} 1^n + \frac{1}{12} (-1)^n + \frac{2}{3} 2^n
\end{align}

これが  b_n に等しいので、

\displaystyle b_n = \frac{1}{12} \left( -6n-9+(-1)^n+2^{n+3} \right)

となる。また、

\displaystyle A(z) = \frac{1}{z-1} B(z)

の両辺を逆 z 変換する。

 u(n) は単位ステップ関数とすると、

\displaystyle \frac{z}{z-1} = \mathcal{Z}[u(n)]

であり、

\displaystyle \frac{1}{z-1} = z^{-1} \mathcal{Z}[u(n)] = \mathcal{Z}[u(n-1)]

であることを考慮すると、畳み込みを直接計算することで、

\begin{align} a_n
&= \mathcal{Z}^{-1} \left[ \frac{1}{z-1} B(z) \right] \\
&= \mathcal{Z}^{-1} \left[ \frac{1}{z-1} \right] * \mathcal{Z}^{-1}[B(z)] \\
&= u(n-1) * b_n \\
&= \sum_{m=0}^\infty u(m-1) b_{n-m} \\
&= \sum_{m=1}^{n-1} b_{n-m} \\
&= \sum_{k=1}^{n-1} b_k \\
&= \frac{1}{12} \sum_{k=1}^{n-1} \left( -6k-9+(-1)^k+2^{k+3} \right) \\
&= \frac{1}{24} \left( -6n^2-12n-15-(-1)^n+2^{n+4} \right)
\end{align}

である。また、 C(z) の逆変換について、

\begin{align} c_n
&= a_n + \mathcal{Z}^{-1} \left[ \mathcal{Z}[u(n)] \mathcal{Z}[n]\right] \\
&= a_n + u(n)*n \\
&= a_n + \sum_{m=0}^\infty u(m) (n-m) u (n-m) \\
&= a_n + \sum_{k=1}^n k \\
&= a_n + \frac{1}{2}n(n+1) \\
&= \frac{1}{24} \left( -6n^2-12n-15-(-1)^n+2^{n+4} \right) + \frac{1}{2}n(n+1) \\
&= \frac{1}{24} \left( 6n^2-15-(-1)^n+2^{n+4} \right)
\end{align}

となる。

以上をまとめると、

 \begin{cases}
\displaystyle a_n = \frac{1}{24} \left( -6n^2-12n-15-(-1)^n+2^{n+4} \right) \\
\displaystyle b_n = \frac{1}{12} \left( -6n-9+(-1)^n+2^{n+3} \right) \\
\displaystyle c_n = \frac{1}{24} \left( 6n^2-15-(-1)^n+2^{n+4} \right)
\end{cases}

が解である。

別解

連立漸化式の行列表記

先の連立漸化式

 \begin{cases}
\displaystyle a_n = a_{n-1}+b_{n-1} \\
\displaystyle b_n = a_{n-1}+c_{n-1} \\
\displaystyle c_n = b_{n-1}+c_{n-1}+n
\end{cases}

を行列を用いて表すことにすると、

 
\begin{bmatrix}
a_n \\
b_n \\
c_n 
\end{bmatrix}
=
\begin{bmatrix}
1&1&0 \\
1&0&1 \\
0&1&1
\end{bmatrix}
\begin{bmatrix}
a_{n-1} \\
b_{n-1} \\
c_{n-1} 
\end{bmatrix}
+
\begin{bmatrix}
0 \\
0 \\
n
\end{bmatrix}

となる。ここで、

 
\boldsymbol{x}_n=\begin{bmatrix}
a_n \\
b_n \\
c_n 
\end{bmatrix},
M=\begin{bmatrix}
1&1&0 \\
1&0&1 \\
0&1&1
\end{bmatrix},
\boldsymbol{y}_n=\begin{bmatrix}
0 \\
0 \\
n 
\end{bmatrix}

とおくと、

 \boldsymbol{x}_n = M \boldsymbol{x}_{n-1} + \boldsymbol{y}_n,  \boldsymbol{x}_0 =  \boldsymbol{0}

という漸化式になる。

漸化式の展開

 \left\{\begin{align}
\boldsymbol{x}_1 &= M \boldsymbol{x}_{0} + \boldsymbol{y}_1 \\
&= \boldsymbol{y}_1 \\
\boldsymbol{x}_2 &= M \boldsymbol{x}_{1} + \boldsymbol{y}_2 \\
&= M \boldsymbol{y}_1 + \boldsymbol{y}_2 \\
\boldsymbol{x}_3 &= M \boldsymbol{x}_{2} + \boldsymbol{y}_3 \\
&= M (M \boldsymbol{y}_1 + \boldsymbol{y}_2)  + \boldsymbol{y}_3 \\
&= M^2 \boldsymbol{y}_1 + M \boldsymbol{y}_2  + \boldsymbol{y}_3 \\
&\vdots \\
\boldsymbol{x}_n &= M \boldsymbol{x}_{n-1} + \boldsymbol{y}_n \\
&= M (M \boldsymbol{x}_{n-2} + \boldsymbol{y}_{n-1})  + \boldsymbol{y}_n \\
&= M (M (M \boldsymbol{x}_{n-3} + \boldsymbol{y}_{n-2}) + \boldsymbol{y}_{n-1})  + \boldsymbol{y}_n \\
&= \cdots \\
&= M^{n-1} \boldsymbol{y}_{1} + M^{n-2} \boldsymbol{y}_{2} + M^2 \boldsymbol{y}_{n-2} + M \boldsymbol{y}_{n-1}  + \boldsymbol{y}_n \\
&= \sum_{k=1}^n M^{n-k} \boldsymbol{y}_k 
\end{align} \right .

ここで、 M^n k 列目を  \boldsymbol{m}^{(n)}_k と書くことにすると、

\begin{align}
M^{n-k} \boldsymbol{y}_k
&= \begin{bmatrix}
\boldsymbol{m}^{(n-k)}_1 & \boldsymbol{m}^{(n-k)}_2 & \boldsymbol{m}^{(n-k)}_3
\end{bmatrix}
\begin{bmatrix}
0 \\
0 \\
k 
\end{bmatrix} \\
&= k  \boldsymbol{m}^{(n-k)}_3
\end{align}

となるから、

\displaystyle \boldsymbol{x}_n = \sum_{k=1}^n  k \boldsymbol{m}^{(n-k)}_3

となる。

対角化

 M を対角化することにより、 M^n を求める。

例えば、

\displaystyle
D=\begin{bmatrix}
 -1&0&0 \\
0&1&0 \\
0&0&2
\end{bmatrix},
P=\begin{bmatrix}
1&1&1 \\
 -2&0&1 \\
 -1&-1&1
\end{bmatrix},
P^{-1}= \frac{1}{6} \begin{bmatrix}
1&-2&1 \\
3&0&-3 \\
2&2&2
\end{bmatrix}

が得られ、

\begin{align} M^n
&= P D^n P^{-1} \\
&= \frac{1}{6} \begin{bmatrix}
1&1&1 \\
 -2&0&1 \\
 -1&-1&1
\end{bmatrix}
\begin{bmatrix}
(-1)^n&0&0 \\
0&1&0 \\
0&0&2^n
\end{bmatrix}
\begin{bmatrix}
1&-2&1 \\
3&0&-3 \\
2&2&2
\end{bmatrix} \\
&=\frac{1}{6} \begin{bmatrix}
\cdot&\cdot&-3+(-1)^n+2^{n+1} \\
\cdot&\cdot&-2(-1)^n+2^{n+1} \\
\cdot&\cdot&3+(-1)^n+2^{n+1}
\end{bmatrix}
\end{align}

となる。これにより、

\begin{align} \boldsymbol{x}_n 
&= \sum_{k=1}^n  k  \boldsymbol{m}^{(n-k)}_3 \\
&= \frac{1}{6} \sum_{k=1}^n  k \begin{bmatrix}
 -3+(-1)^{n-k}+2^{n-k+1} \\
 -2(-1)^{n-k}+2^{n-k+1} \\
 3+(-1)^{n-k}+2^{n-k+1}
\end{bmatrix} \\
&= \frac{1}{6} \sum_{k=1}^n  \begin{bmatrix}
 -3k+(-1)^n k (-1)^k+2^{n+1} k \left( \frac{1}{2} \right)^k \\
 2(-1)^{n+1} k (-1)^k +2^{n+1} k \left( \frac{1}{2} \right)^k \\
 3k+(-1)^n k (-1)^k+2^{n+1} k \left( \frac{1}{2} \right)^k \\
\end{bmatrix} \\
&= \frac{1}{6} \left( \begin{bmatrix}
 -3 \\
 0 \\
 3
\end{bmatrix} \sum_{k=1}^n k +
\begin{bmatrix}
(-1)^n \\
 2(-1)^{n+1} \\
(-1)^n
\end{bmatrix} \sum_{k=1}^n k (-1)^k +
\begin{bmatrix}
2^{n+1} \\
2^{n+1} \\
2^{n+1}
\end{bmatrix} \sum_{k=1}^n k \left( \frac{1}{2} \right)^k
\right)
\end{align}

となる。

等差×等比タイプの和

 r \ne 1 のとき、

\displaystyle S_n = \sum_{k=1}^n k r^k


とおくと、

 \left\{\begin{align}
S_n &= r + 2r^2 + 3r^3 + \cdots + n r^n \\
r S_n &= r^2 + 2r^3 + 3r^4 + \cdots + (n-1) r^n + n r^{n+1}
\end{align} \right .

より、

\begin{align} (1-r) S_n
&= r + r^2 + r^3 + \cdots +  r^n - n r^{n+1} \\
&= \frac{r(1-r^n)}{1-r} - n r^{n+1}
\end{align}

だから、

\displaystyle S_n = \frac{r(1-r^n)}{(1-r)^2} - \frac{n r^{n+1}}{1-r}


となる。

これにより、

\displaystyle \sum_{k=1}^n k(-1)^k = \frac{-1+(-1)^n}{4} - \frac{n (-1)^{n+1}}{2}


また、

\displaystyle \sum_{k=1}^n k \left(\frac{1}{2} \right)^k = 2 \left(1-\frac{1}{2^n} \right) - \frac{n}{2^n}


となる。

これらを利用して整理すると、

\displaystyle \boldsymbol{x}_n = \begin{bmatrix}
\frac{1}{24} \left( -6n^2-12n-15-(-1)^n+2^{n+4} \right) \\
\frac{1}{12} \left( -6n-9+(-1)^n+2^{n+3} \right) \\
\frac{1}{24} \left( 6n^2-15-(-1)^n+2^{n+4} \right)
\end{bmatrix}

という同様の解が得られる。

点数表

n a_n b_n c_n
0 0 0 0
1 0 0 1
2 0 1 3
3 1 3 7
4 4 8 14
5 12 18 27
6 30 39 51
7 69 81 97
8 150 166 186
9 316 336 361
10 652 677 707
11 1329 1359 1395
12 2688 2724 2766
13 5412 5454 5503
14 10866 10915 10971
15 21781 21837 21901
16 43618 43682 43754
17 87300 87372 87453
18 174672 174753 174843
19 349425 349515 349615
20 698940 699040 699150
21 1397980 1398090 1398211
22 2796070 2796191 2796323
23 5592261 5592393 5592537

所感

別解はロジックはエレガントなものの、いざやってみると手計算がつらすぎるので実用的ではない気がした。また、ハノイの塔が門松の竹柱と鏡餅のセットに似ている気がするので、縁起のよい正月遊びとして推していきたい。

マウス新調

2 年半ぶりにチャタリングがひどいので、新調。今まではロジクールの M336 を使っていたが、今回は M337 をチョイス。前と同じで赤。モノとしては同じで、差は配色だけかと思っていたが、パッケージが前者は紙箱なのに対してこっちはブリスターなのね。

e10s.hateblo.jp

三角関数のラプラス変換の「証明」でたまに見かけるインチキについて考えてみた

Laplace 変換

 f(t)Laplace 変換  \mathcal{L} [f(t)](s) は次の式で表される。

\displaystyle \mathcal{L} [f(t)] = \int_0^{\infty} f(t) e^{-st} dt

 s複素数とする。

指数関数の Laplace 変換

まずは  e^{at}Laplace 変換を考えたい。ここで、 a \in \mathbb{C} とする。

\begin{align} \mathcal{L} \left[ e^{at} \right]
&= \int_0^{\infty} e^{at} e^{-st} dt \\
&= \int_0^{\infty} e^{(a-s)t} dt \\
&= \left[ \frac{e^{(a-s)t}}{a-s} \right]_0^{\infty} \\
&= \lim_{t \to \infty} \frac{e^{(a-s)t} - e^0}{a-s}
\end{align}

これは  \mathrm{Re}\,(a-s) < 0 すなわち  \mathrm{Re}\,s > \mathrm{Re}\,a で収束して、

\begin{align} \mathcal{L} \left[ e^{at}\right]
&= \frac{0-1}{a-s} \\
&= \frac{1}{s-a}
\end{align}

となる。収束域は  \mathrm{Re}\,s > \mathrm{Re}\,a である。

三角関数Laplace 変換

ここでは、三角関数を指数関数で表記し、上記の結果を用いて計算することで煩雑な部分積分を回避する。以下、  b \in \mathbb{R} とする。

指数関数の Laplace 変換の結果から、

\displaystyle \mathcal{L} \left[ e^{\pm jbt} \right] = \frac{1}{s-\mp jb}

であって、収束域は  \mathrm{Re}\,s > \mathrm{Re}\,\pm jb = 0 である。複号同順。

余弦関数の Laplace 変換

\begin{align} \mathcal{L} \left[ \cos bt \right]
&= \mathcal{L} \left[ \frac{e^{jbt} + e^{-jbt}}{2} \right] \\
&= \frac{1}{2} \left( \mathcal{L} \left[ e^{jbt} \right] + \mathcal{L} \left[ e^{-jbt} \right] \right) \\
&= \frac{1}{2} \left( \frac{1}{s-jb} + \frac{1}{s+jb} \right) \\
&= \frac{1}{2} \cdot \frac{s+jb+s-jb}{s^2 + b^2} \\
&= \frac{s}{s^2 + b^2} 
\end{align}

となり、途中で現れた指数関数の Laplace 変換部分の収束域がともに  \mathrm{Re}\,s > 0 であるから、全体としてこの変換の収束域は  \mathrm{Re}\,s > 0 である。

正弦関数の Laplace 変換

同様に、

\begin{align} \mathcal{L} \left[ \sin bt \right]
&= \mathcal{L} \left[ \frac{e^{jbt} - e^{-jbt}}{j2} \right] \\
&= \frac{1}{j2} \left( \mathcal{L} \left[ e^{jbt} \right] - \mathcal{L} \left[ e^{-jbt} \right] \right) \\
&= \frac{1}{j2} \left( \frac{1}{s-jb} - \frac{1}{s+jb} \right) \\
&= \frac{1}{j2} \cdot \frac{s+jb-(s-jb)}{s^2 + b^2} \\
&= \frac{b}{s^2 + b^2} 
\end{align}

となり、収束域は  \mathrm{Re}\,s > 0 である。

これらが真っ当な証明であろう。

三角関数Laplace 変換におけるインチキ

ここからが本題。

オイラーの公式から、 e^{jbt} = \cos bt + j \sin bt であるから、この両辺を Laplace 変換すると、

\displaystyle \mathcal{L} \left[ e^{jbt} \right] = \mathcal{L} \left[ \cos bt \right] + j \mathcal{L} \left[ \sin bt \right]

であるが、左辺の Laplace 変換を具体的に計算し、右辺のような形に変形することで、正弦関数と余弦関数の Laplace 変換を一挙両得で導こうというインチキがはびこりがちなので紹介する。

上に示した結果から、

\begin{align} \mathcal{L} \left[ e^{jbt} \right]
&= \frac{1}{s-jb} \\
&= \frac{s+jb}{s^2+b^2} \\
&= \frac{s}{s^2+b^2} + j \frac{b}{s^2+b^2} 
\end{align}

と変形できるわけで、ここまでは問題ない。

ここからインチキが始まって、2 つの形で表した  \mathcal{L} \left[ e^{jbt} \right] の「実部」と「虚部」をそれぞれ比較してみようという話になる。

「実部」 \mathrm{Re?}\, \mathcal{L} \left[ e^{jbt} \right] について、

\begin{align}
 \mathrm{Re?}\left(  \mathcal{L} \left[ \cos bt \right] + j \mathcal{L} \left[ \sin bt \right] \right) &= \mathrm{Re?}\left( \frac{s}{s^2+b^2} + j \frac{b}{s^2+b^2}  \right) \\
 \mathcal{L} \left[ \cos bt \right] &= \frac{s}{s^2+b^2}
\end{align}

また、「虚部」 \mathrm{Im?}\, \mathcal{L} \left[ e^{jbt} \right] について、

\begin{align}
 \mathrm{Im?}\left(  \mathcal{L} \left[ \cos bt \right] + j \mathcal{L} \left[ \sin bt \right] \right) &= \mathrm{Im?}\left( \frac{s}{s^2+b^2} + j \frac{b}{s^2+b^2}  \right) \\
 \mathcal{L} \left[ \sin bt \right] &= \frac{b}{s^2+b^2}
\end{align}

というインチキによって、所望の式が得られたように見える。わざわざカギカッコやハテナを付けた部分にインチキがある。

そもそも最初に書いたとおり、 s複素数であるので、それが絡んだ分数式の部分も複素数である。 u,v,z \in \mathbb{C} として、 z=u+jv と表せても、一般には  \mathrm{Re}\,z \ne u であり、 \mathrm{Im}\,z \ne v である。それゆえ、今回のような「実部」と「虚部」のような考え方は一般には正しくない。

 \mathcal{L} \left[ \cos bt \right]  \mathcal{L} \left[ \sin bt \right]  を知っているときに、 \mathcal{L} \left[ e^{jbt} \right] を計算するために、

\begin{align} \mathcal{L} \left[ e^{jbt} \right]
&= \mathcal{L} \left[ \cos bt \right] + j \mathcal{L} \left[ \sin bt \right] \\
&= \frac{s}{s^2+b^2} + j \frac{b}{s^2+b^2} \\
&= \frac{1}{s-jb}
\end{align}

と順に変形していくのは妥当だが、その逆順をたどるのはいかがわしいという話である。

フォロー

この実部・虚部比較は  s複素数としたときの証明としては不正確だが、 s を実数とするケースがあるらしく、その場合は正当な方法であろう。そうでなくても、変換公式を忘れていたときに手元で導出するために使う分には有用なトリックだろう。

地方自治法の定めるリコールに必要な署名数についての要件を調べてみた

いきさつはこのツイーヨ。

リコールについては若かりし時分に習った気がするのだが、何分の何みたいなのは覚えていなかったので調べることにした。

ja.wikipedia.org

どうやら、首長・議員・役員の解職、議会の解散のいずれも同等の署名数で定められているようだが、ちょっと表記がややこしいことになっている。そもそも自分が中学の公民を聞いていた時代とは数が変わっていないか。

代表して、都道府県知事および市町村長のリコールについて定めた、地方自治法 81 条の 1 項を抜き出してみる。

選挙権を有する者は、政令の定めるところにより、その総数の三分の一その総数が四十万を超え八十万以下の場合にあつてはその四十万を超える数に六分の一を乗じて得た数と四十万に三分の一を乗じて得た数とを合算して得た数その総数が八十万を超える場合にあつてはその八十万を超える数に八分の一を乗じて得た数と四十万に六分の一を乗じて得た数と四十万に三分の一を乗じて得た数とを合算して得た数)以上の者の連署をもつて、その代表者から、普通地方公共団体選挙管理委員会に対し、当該普通地方公共団体の長の解職の請求をすることができる。

e-Gov法令検索

何やら有権者数に関して条件が 3 つあって、それぞれのケースにおいて必要な署名の数が異なるようだが、ぱっと見でそれがどういう計算によるのかがわかりにくい。そこで、これらを数式に書き下す。つまり、「選挙権を有する者は、(中略)その総数を正整数として  p としたとき、 n(p) なる実数が存在して、この数以上の者の連署をもって(以下略)」ということにする。そして  n(p) とはどう書き表されるかという問題である。

まず、めんどくさいので  K = 400000 とおく。すると、上記の条文で示された数はそれぞれ次のように書き直される。

i) 「その総数の三分の一

\displaystyle \frac{p}{3}

ii) 「その総数が四十万を超え八十万以下の場合にあつてはその四十万を超える数に六分の一を乗じて得た数と四十万に三分の一を乗じて得た数とを合算して得た数

\displaystyle \frac{1}{6}(p-K)+\frac{1}{3}K

iii) 「その総数が八十万を超える場合にあつてはその八十万を超える数に八分の一を乗じて得た数と四十万に六分の一を乗じて得た数と四十万に三分の一を乗じて得た数とを合算して得た数

\displaystyle \frac{1}{8}(p-2K)+\frac{1}{6}K+\frac{1}{3}K

ふざけるなという感想しか出ないが、何かしらの意図があってこういう書き方をしたのだろう。さらに、式を整理して、まとめて書くと、

 n(p)=
\begin{cases}
\displaystyle \frac{p}{3} & (p \leq K) \\
\displaystyle \frac{1}{6} (p+K) & (K < p \leq 2K) \\
\displaystyle \frac{1}{8} (p+2K) & (2K < p)
\end{cases}

となり、これが所望の式である。

蛇足だが、i) が元来あったもので、これが全  p に適用されていて、自分が習ったのはこのバージョンのようだ。また、平成 14 年法律第 4 号とやらにより、要件が緩和されたようなのだが、それが ii) であり、  p > K に対して適用されていたらしい。さらに、平成 24 年法律第 72 号とやらにより、さらに緩和され、それが現行のバージョンであり、iii) が追加されたという流れのようだ。

例として、最初に挙げたツイートのように、横浜市長をクビにしたいと思った場合を考えよう。

www.city.yokohama.lg.jp

上記に横浜市有権者数がまとめられているが、2019 年 9 月 1 日付けのデータでは、 p=3114475 である。これは 300 万強であって 80 万を超えるので、

\displaystyle n(p)=\frac{p+2K}{8}

に代入することにより、

\displaystyle n(3114475)=\frac{3114475+800000}{8}=\frac{3914475}{8}=489309.375

が得られる。すなわち、この数以上の署名が必要であるということなので、小数部分を切り上げて、最低でも 48 万 9310 人分の署名が必要ということがわかる。大変よね。

最後にグラフを載せる。実線部が今回求めた現行の法律に基づく  n(p) であって、横軸に有権者数、縦軸に必要な署名数をとってある。点線部は改正前のイメージであり、どう緩和されてきたかを視覚化した。

f:id:electrolysis:20191209211125p:plain
有権者数に対する、リコールに必要な署名数

東京遠征

現実逃避のために、21 日から 3 日間東京で神社巡りをしてきた。なんとなく拠点を秋葉原に設定。

22 日は即位礼正殿の儀だったわけだが、そっちのけで明治神宮靖国神社を参拝した。非国民の中の愛国者であるところのチョイスである。明治神宮では即位礼当日祭がまさに執り行われていたのが、それと同時に樽酒を振る舞っていたので、令和の御代を祝して午前中から顔を真っ赤にしてきたのだ。いずれも初参拝であり、よい記念になった。

台風の影響による雨風で、雨男スキルが発揮されたのを強く感じる日であった。

いっぽう、翌日は晴れて暑い日であった。この日は東京大神宮から神保町、小川町あたりの行ってみたかった店を巡りつつ神田明神を参拝。いずれも願掛けに来た参拝客が多い印象であった。前者は初であるが、後者は去年の遠征で夏越の大祓以来。

もうちょっと回りたいところはあったけど、まあ。