たくさん玉を入れ替えた後の確率を sympy で求めてみる

[清水団(@dannchu)さん](https://twitter.com/dannchu)の[「たくさん玉を入れ替えた後の確率」の問題](https://zenn.dev/dannchu/articles/db5f441c16bfa4)が面白そうでしたので，sympy を使って調べてみました。

https://twitter.com/dannchu/status/1542137511790915584

# 問題

はじめ，袋Aには白玉10個，袋Bには赤玉10個入っている。

＜操作＞
Aから1つBに入れ，Bをよくかき混ぜ，Bから1つAに戻しかき混ぜる。

この＜操作＞をたくさん繰り返すと…

* 問題1. 「袋Aに白玉が5個，赤玉が5個入っている」状態に近づくと言えるか？
* 問題2. この＜操作＞をたくさん繰り返したのちに，袋Aから玉を1個取り出すとき，それが白玉である確率は，1/2に近づくか？

# 漸化式を立てる

$n$ 回の試行後に，袋Aに白玉 $k$ 個，赤玉 $10-k$ 個が入っている確率を $p_{n,k}\ (n\geqq 0, 0\leqq k\leqq 10)$ とおきます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/41739/7256471f-6d98-2ab1-f0aa-0003716dbfdf.png" width="50%">


$n$ 回目から $n+1$ 回目への推移を考えます。

$n+1$ 回目の試行後に袋Aに白玉 $k$ 個が入っている状況は，$n$ 回目の試行後からの推移として，次の4通りが考えられます。

1. $n$回目の試行後には袋Aに白玉 $k-1$ 個が入っていて，$n+1$ 回目の試行においては，袋Aから赤，袋Bから白を引く。
1. $n$回目の試行後には袋Aに白玉 $k$ 個が入っていて，$n+1$ 回目の試行においては，袋Aから白，袋Bから白を引く。
1. $n$回目の試行後には袋Aに白玉 $k$ 個が入っていて，$n+1$ 回目の試行においては，袋Aから赤，袋Bから赤を引く。
1. $n$回目の試行後には袋Aに白玉 $k+1$ 個が入っていて，$n+1$ 回目の試行においては，袋Aから白，袋Bから赤を引く。

* パターン1. の確率：$p_{n,k-1}\times \frac{11-k}{10}\times \frac{11-k}{11}$
* パターン2. の確率：$p_{n,k}\times \frac{k}{10}\times \frac{11-k}{11}$
* パターン3. の確率：$p_{n,k}\times \frac{10-k}{10}\times \frac{k+1}{11}$
* パターン4. の確率：$p_{n,k+1}\times \frac{k+1}{10}\times \frac{k+1}{11}$

よって，次の連立漸化式が成り立つことになります。$(n\geqq 0, 0\leqq k\leqq 10)$

```math
p_{n+1,k} = \frac{(11-k)^2}{110}p_{n,k-1}+\frac{k(11-k)+(10-k)(k+1)}{110}p_{n,k} + \frac{(k+1)^2}{110}p_{n,k+1}
```

（ただし $k=-1,11$のときは $p_{n,k}=0$ と見なします。）

# 連立漸化式の行列表示

この連立漸化式を行列表示すると次のようになります。

```math
\begin{pmatrix}
p_{n+1,0}\\
p_{n+1,1}\\
p_{n+1,2}\\
p_{n+1,3}\\
p_{n+1,4}\\
p_{n+1,5}\\
p_{n+1,6}\\
p_{n+1,7}\\
p_{n+1,8}\\
p_{n+1,9}\\
p_{n+1,10}
\end{pmatrix}
=\frac{1}{110}
\left(\begin{array}{ccccccccccc}
10 & 1^2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
10^2 & 28 & 2^2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 9^2 & 42 & 3^2 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 8^2 & 52 & 4^2 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 7^2 & 58 & 5^2 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 6^2 & 60 & 6^2 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 5^2 & 58 & 7^2 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 4^2 & 52 & 8^2 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 3^2 & 42 & 9^2 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2^1 & 28 & 10^2 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1^2 & 10
\end{array}\right)
\begin{pmatrix}
p_{n,0}\\
p_{n,1}\\
p_{n,2}\\
p_{n,3}\\
p_{n,4}\\
p_{n,5}\\
p_{n,6}\\
p_{n,7}\\
p_{n,8}\\
p_{n,9}\\
p_{n,10}
\end{pmatrix}
```

この11次正方行列部分を$A$とおき，

```math
\boldsymbol{v}_n = \begin{pmatrix}p_{n,0}\\\vdots\\p_{n,10}\end{pmatrix}
```

とおけば，推移は

```math
\boldsymbol{v}_{n+1} = \frac{1}{110} A\boldsymbol{v}_{n}
```

と表せることになります。ただし，初期値（0回目の試行後）は白玉が袋Aに10個入っている確率が1であることから，

```math
\boldsymbol{v}_0 = \begin{pmatrix}0\\\vdots\\0\\1\end{pmatrix}
```

となります。

よって，$n$回の試行後の確率分布は

```math
\boldsymbol{v}_{n} = \frac{1}{110^n} A^n \boldsymbol{v}_{0}
```

と表せるので，行列の累乗 $A^n$ を求めることが目標となります。

ここから先は手計算でやる気は起きないので，sympyで進めます。

# sympy の環境準備

ブラウザ上で Python, sympy の環境を気軽に試せ，数式の見た目も MathJax で綺麗に表示される [Juypter Notebook](https://jupyter.org/try-jupyter) で Notebook を作って実験してみましょう。

新規 Notebook を作成したら，まずは sympy の初期設定をします。

```python
import sympy
sympy.init_printing()
```

`init_printing()` によって，結果を MathJax によって綺麗な数式として表示できるようになります。



次の関数も便利です。

* `display(hoge)`: `hoge` を MathJax によって綺麗に表示
* `print(sympy.latex(hoge))`: `hoge` を LaTeX ソースとして表示

# 行列Aの定義

まずは行列$A$を定義します。

### input

```python
A = sympy.Matrix([
  [10, 1**2, 0, 0,0, 0, 0, 0,0, 0, 0],
  [10**2, 28, 2**2, 0, 0,0, 0, 0, 0,0, 0],
  [0, 9**2, 42, 3**2, 0, 0,0, 0, 0, 0,0],
  [0, 0, 8**2, 52, 4**2, 0, 0,0, 0, 0, 0],
  [0, 0, 0, 7**2, 58, 5**2, 0, 0,0, 0, 0],
  [0, 0, 0, 0, 6**2, 60, 6**2, 0,0, 0, 0],
  [0, 0, 0, 0, 0, 5**2, 58, 7**2,0, 0, 0],
  [0, 0, 0, 0, 0, 0, 4**2, 52, 8**2, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 3**2, 42, 9**2, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 2**2, 28, 10**2],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 1**2, 10]
  ])
display(A)
```

### output

```math
\left[\begin{array}{ccccccccccc}10 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\100 & 28 & 4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 81 & 42 & 9 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 64 & 52 & 16 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 49 & 58 & 25 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 36 & 60 & 36 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 25 & 58 & 49 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 16 & 52 & 64 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 9 & 42 & 81 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 & 28 & 100\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 10\end{array}\right]
```

# 対角化可能性の確認

まずは行列$A$の固有値を求めてみます。

### input

```python
A.eigenvals()
```

### output

```math
\left\{ 0 : 1, \  2 : 1, \  6 : 1, \  12 : 1, \  20 : 1, \  30 : 1, \  42 : 1, \  56 : 1, \  72 : 1, \  90 : 1, \  110 : 1\right\}
```

このそれぞれは，`固有値:重複度` を表します。固有値の重複度が全て1（固有値が全て異なる）なので，この行列$A$は対角化可能であることが分かります。

# 対角化実行

対角化を実行します。$D=P^{-1}AP$ なる正則行列$P$と対角行列$D$を次のようにして見つけます。

```python
P, D = A.diagonalize()
```

それぞれの行列を成分表示してみます。

### input

```python
display(P, D)
```

### output

```math
\left[\begin{array}{ccccccccccc}1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 & 1\\-10 & 8 & -4 & -2 & 10 & -20 & 32 & -46 & 62 & -80 & 100\\45 & -27 & -3 & 33 & -45 & 15 & 87 & -297 & 657 & -1215 & 2025\\-120 & 48 & 48 & -92 & 20 & 160 & -288 & -48 & 1632 & -5760 & 14400\\210 & -42 & -126 & 98 & 140 & -280 & -168 & 1176 & -588 & -8820 & 44100\\-252 & 0 & 168 & 0 & -252 & 0 & 672 & 0 & -3528 & 0 & 63504\\210 & 42 & -126 & -98 & 140 & 280 & -168 & -1176 & -588 & 8820 & 44100\\-120 & -48 & 48 & 92 & 20 & -160 & -288 & 48 & 1632 & 5760 & 14400\\45 & 27 & -3 & -33 & -45 & -15 & 87 & 297 & 657 & 1215 & 2025\\-10 & -8 & -4 & 2 & 10 & 20 & 32 & 46 & 62 & 80 & 100\\1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right]
```

```math
\left[\begin{array}{ccccccccccc}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 12 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 20 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 30 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 42 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 56 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 72 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 90 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 110\end{array}\right]
```

念のため，本当にこれで対角化できているか確認します。

```python
P.inv()*A*P == D # => True
```

確かに対角化できているようです。

なお，$D$ の対角成分，すなわち $A$ の固有値の1つに0が現れていることから，この11次正方行列 $A$ は正則でなく，階数が10となっていることがわかります。これは，

```math
\sum_{k=0}^{10}p_{n,k}=1
```

の束縛条件があり，この11本の連立漸化式が独立でない（うち1本は他の10本から導ける）関係にあることから当然の関係と言えます。


# n乗計算

$n$を変数扱いします。

```python
sympy.var('n')
```

すると，対角行列 $D$ の $n$ 乗はこのように正しく計算されます。

### input

```python
display(D**n)
```

### output

```math
\left[\begin{array}{ccccccccccc}0^{n} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 2^{n} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 6^{n} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 12^{n} & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 20^{n} & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 30^{n} & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 42^{n} & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 56^{n} & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 72^{n} & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 90^{n} & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 110^{n}\end{array}\right]
```

ちなみに，$D^n$ の左上の成分が $0$ ではなく $0^n$ という表記になっているのは，$0^0=1$ としたいからでしょう。$D^0$ は単位行列であるべきですからね。これ以降の数式においても，$0^n$ という表記の部分は，「$n=0$ のときは1，$n\geqq1$ のときは0」という意味であると読んでください。

こうして，$A^n=PD^nP^{-1}$ が次のように計算できます。

### input

```python
display(P*(D**n)*P.inv())
```


### output

```math
\left[\begin{array}{ccccccccccc}\frac{0^{n}}{11} + \frac{110^{n}}{184756} + \frac{30 \cdot 12^{n}}{143} + \frac{5 \cdot 2^{n}}{22} + \frac{18 \cdot 20^{n}}{143} + \frac{3 \cdot 30^{n}}{52} + \frac{15 \cdot 42^{n}}{748} + \frac{25 \cdot 56^{n}}{4862} + \frac{75 \cdot 6^{n}}{286} + \frac{5 \cdot 72^{n}}{5434} + \frac{90^{n}}{9724} & - \frac{0^{n}}{110} + \frac{110^{n}}{184756} + \frac{3 \cdot 12^{n}}{715} - \frac{2^{n}}{55} + \frac{9 \cdot 20^{n}}{715} + \frac{3 \cdot 30^{n}}{260} + \frac{6 \cdot 42^{n}}{935} + \frac{23 \cdot 56^{n}}{9724} - \frac{3 \cdot 6^{n}}{286} + \frac{31 \cdot 72^{n}}{54340} + \frac{90^{n}}{12155} & \frac{0^{n}}{495} + \frac{110^{n}}{184756} - \frac{2 \cdot 12^{n}}{585} + \frac{2^{n}}{330} - \frac{2 \cdot 20^{n}}{715} - \frac{30^{n}}{2340} + \frac{29 \cdot 42^{n}}{33660} + \frac{56^{n}}{1326} - \frac{6^{n}}{2574} + \frac{73 \cdot 72^{n}}{244530} + \frac{3 \cdot 90^{n}}{48620} & - \frac{0^{n}}{1320} + \frac{110^{n}}{184756} + \frac{23 \cdot 12^{n}}{17160} - \frac{2^{n}}{1320} + \frac{20^{n}}{5720} - \frac{30^{n}}{1560} - \frac{3 \cdot 42^{n}}{7480} + \frac{56^{n}}{58344} + \frac{6^{n}}{1144} + \frac{17 \cdot 72^{n}}{163020} + \frac{90^{n}}{24310} & \frac{0^{n}}{2310} + \frac{110^{n}}{184756} - \frac{12^{n}}{2145} + \frac{2^{n}}{4620} + \frac{2 \cdot 20^{n}}{5005} + \frac{30^{n}}{2730} - \frac{42^{n}}{13090} - \frac{56^{n}}{7293} - \frac{3 \cdot 6^{n}}{4004} - \frac{72^{n}}{81510} + \frac{90^{n}}{48620} & - \frac{0^{n}}{2772} + \frac{110^{n}}{184756} - \frac{20^{n}}{2002} + \frac{5 \cdot 42^{n}}{23562} + \frac{25 \cdot 6^{n}}{36036} - \frac{5 \cdot 72^{n}}{97812} & \frac{0^{n}}{2310} + \frac{110^{n}}{184756} + \frac{12^{n}}{2145} - \frac{2^{n}}{4620} + \frac{2 \cdot 20^{n}}{5005} - \frac{30^{n}}{2730} - \frac{42^{n}}{13090} + \frac{56^{n}}{7293} - \frac{3 \cdot 6^{n}}{4004} - \frac{72^{n}}{81510} - \frac{90^{n}}{48620} & - \frac{0^{n}}{1320} + \frac{110^{n}}{184756} - \frac{23 \cdot 12^{n}}{17160} + \frac{2^{n}}{1320} + \frac{20^{n}}{5720} + \frac{30^{n}}{1560} - \frac{3 \cdot 42^{n}}{7480} - \frac{56^{n}}{58344} + \frac{6^{n}}{1144} + \frac{17 \cdot 72^{n}}{163020} - \frac{90^{n}}{24310} & \frac{0^{n}}{495} + \frac{110^{n}}{184756} + \frac{2 \cdot 12^{n}}{585} - \frac{2^{n}}{330} - \frac{2 \cdot 20^{n}}{715} + \frac{30^{n}}{2340} + \frac{29 \cdot 42^{n}}{33660} - \frac{56^{n}}{1326} - \frac{6^{n}}{2574} + \frac{73 \cdot 72^{n}}{244530} - \frac{3 \cdot 90^{n}}{48620} & - \frac{0^{n}}{110} + \frac{110^{n}}{184756} - \frac{3 \cdot 12^{n}}{715} + \frac{2^{n}}{55} + \frac{9 \cdot 20^{n}}{715} - \frac{3 \cdot 30^{n}}{260} + \frac{6 \cdot 42^{n}}{935} - \frac{23 \cdot 56^{n}}{9724} - \frac{3 \cdot 6^{n}}{286} + \frac{31 \cdot 72^{n}}{54340} - \frac{90^{n}}{12155} & \frac{0^{n}}{11} + \frac{110^{n}}{184756} - \frac{30 \cdot 12^{n}}{143} - \frac{5 \cdot 2^{n}}{22} + \frac{18 \cdot 20^{n}}{143} - \frac{3 \cdot 30^{n}}{52} + \frac{15 \cdot 42^{n}}{748} - \frac{25 \cdot 56^{n}}{4862} + \frac{75 \cdot 6^{n}}{286} + \frac{5 \cdot 72^{n}}{5434} - \frac{90^{n}}{9724}\\- \frac{10 \cdot 0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} + \frac{60 \cdot 12^{n}}{143} - \frac{20 \cdot 2^{n}}{11} + \frac{180 \cdot 20^{n}}{143} + \frac{15 \cdot 30^{n}}{13} + \frac{120 \cdot 42^{n}}{187} + \frac{575 \cdot 56^{n}}{2431} - \frac{150 \cdot 6^{n}}{143} + \frac{155 \cdot 72^{n}}{2717} + \frac{20 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} + \frac{6 \cdot 12^{n}}{715} + \frac{8 \cdot 2^{n}}{55} + \frac{18 \cdot 20^{n}}{143} + \frac{3 \cdot 30^{n}}{13} + \frac{192 \cdot 42^{n}}{935} + \frac{529 \cdot 56^{n}}{4862} + \frac{6 \cdot 6^{n}}{143} + \frac{961 \cdot 72^{n}}{27170} + \frac{16 \cdot 90^{n}}{2431} & - \frac{2 \cdot 0^{n}}{99} + \frac{25 \cdot 110^{n}}{46189} - \frac{4 \cdot 12^{n}}{585} - \frac{4 \cdot 2^{n}}{165} - \frac{4 \cdot 20^{n}}{143} - \frac{30^{n}}{117} + \frac{232 \cdot 42^{n}}{8415} + \frac{23 \cdot 56^{n}}{663} + \frac{2 \cdot 6^{n}}{1287} + \frac{2263 \cdot 72^{n}}{122265} + \frac{12 \cdot 90^{n}}{2431} & \frac{0^{n}}{132} + \frac{25 \cdot 110^{n}}{46189} + \frac{23 \cdot 12^{n}}{8580} + \frac{2^{n}}{165} + \frac{20^{n}}{572} - \frac{30^{n}}{78} - \frac{12 \cdot 42^{n}}{935} + \frac{23 \cdot 56^{n}}{29172} - \frac{6^{n}}{286} + \frac{527 \cdot 72^{n}}{81510} + \frac{8 \cdot 90^{n}}{2431} & - \frac{0^{n}}{231} + \frac{25 \cdot 110^{n}}{46189} - \frac{2 \cdot 12^{n}}{2145} - \frac{2 \cdot 2^{n}}{1155} + \frac{4 \cdot 20^{n}}{1001} + \frac{2 \cdot 30^{n}}{273} - \frac{16 \cdot 42^{n}}{6545} - \frac{46 \cdot 56^{n}}{7293} + \frac{3 \cdot 6^{n}}{1001} - \frac{31 \cdot 72^{n}}{40755} + \frac{4 \cdot 90^{n}}{2431} & \frac{5 \cdot 0^{n}}{1386} + \frac{25 \cdot 110^{n}}{46189} - \frac{5 \cdot 20^{n}}{1001} + \frac{80 \cdot 42^{n}}{11781} - \frac{25 \cdot 6^{n}}{9009} - \frac{155 \cdot 72^{n}}{48906} & - \frac{0^{n}}{231} + \frac{25 \cdot 110^{n}}{46189} + \frac{2 \cdot 12^{n}}{2145} + \frac{2 \cdot 2^{n}}{1155} + \frac{4 \cdot 20^{n}}{1001} - \frac{2 \cdot 30^{n}}{273} - \frac{16 \cdot 42^{n}}{6545} + \frac{46 \cdot 56^{n}}{7293} + \frac{3 \cdot 6^{n}}{1001} - \frac{31 \cdot 72^{n}}{40755} - \frac{4 \cdot 90^{n}}{2431} & \frac{0^{n}}{132} + \frac{25 \cdot 110^{n}}{46189} - \frac{23 \cdot 12^{n}}{8580} - \frac{2^{n}}{165} + \frac{20^{n}}{572} + \frac{30^{n}}{78} - \frac{12 \cdot 42^{n}}{935} - \frac{23 \cdot 56^{n}}{29172} - \frac{6^{n}}{286} + \frac{527 \cdot 72^{n}}{81510} - \frac{8 \cdot 90^{n}}{2431} & - \frac{2 \cdot 0^{n}}{99} + \frac{25 \cdot 110^{n}}{46189} + \frac{4 \cdot 12^{n}}{585} + \frac{4 \cdot 2^{n}}{165} - \frac{4 \cdot 20^{n}}{143} + \frac{30^{n}}{117} + \frac{232 \cdot 42^{n}}{8415} - \frac{23 \cdot 56^{n}}{663} + \frac{2 \cdot 6^{n}}{1287} + \frac{2263 \cdot 72^{n}}{122265} - \frac{12 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} - \frac{6 \cdot 12^{n}}{715} - \frac{8 \cdot 2^{n}}{55} + \frac{18 \cdot 20^{n}}{143} - \frac{3 \cdot 30^{n}}{13} + \frac{192 \cdot 42^{n}}{935} - \frac{529 \cdot 56^{n}}{4862} + \frac{6 \cdot 6^{n}}{143} + \frac{961 \cdot 72^{n}}{27170} - \frac{16 \cdot 90^{n}}{2431} & - \frac{10 \cdot 0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} - \frac{60 \cdot 12^{n}}{143} + \frac{20 \cdot 2^{n}}{11} + \frac{180 \cdot 20^{n}}{143} - \frac{15 \cdot 30^{n}}{13} + \frac{120 \cdot 42^{n}}{187} - \frac{575 \cdot 56^{n}}{2431} - \frac{150 \cdot 6^{n}}{143} + \frac{155 \cdot 72^{n}}{2717} - \frac{20 \cdot 90^{n}}{2431}\\\frac{45 \cdot 0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} - \frac{90 \cdot 12^{n}}{13} + \frac{135 \cdot 2^{n}}{22} - \frac{810 \cdot 20^{n}}{143} - \frac{45 \cdot 30^{n}}{52} + \frac{1305 \cdot 42^{n}}{748} + \frac{675 \cdot 56^{n}}{442} - \frac{225 \cdot 6^{n}}{286} + \frac{3285 \cdot 72^{n}}{5434} + \frac{1215 \cdot 90^{n}}{9724} & - \frac{9 \cdot 0^{n}}{22} + \frac{2025 \cdot 110^{n}}{184756} - \frac{9 \cdot 12^{n}}{65} - \frac{27 \cdot 2^{n}}{55} - \frac{81 \cdot 20^{n}}{143} - \frac{9 \cdot 30^{n}}{52} + \frac{522 \cdot 42^{n}}{935} + \frac{621 \cdot 56^{n}}{884} + \frac{9 \cdot 6^{n}}{286} + \frac{20367 \cdot 72^{n}}{54340} + \frac{243 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} + \frac{22 \cdot 12^{n}}{195} + \frac{9 \cdot 2^{n}}{110} + \frac{18 \cdot 20^{n}}{143} + \frac{30^{n}}{156} + \frac{841 \cdot 42^{n}}{11220} + \frac{99 \cdot 56^{n}}{442} + \frac{6^{n}}{858} + \frac{5329 \cdot 72^{n}}{27170} + \frac{729 \cdot 90^{n}}{9724} & - \frac{3 \cdot 0^{n}}{88} + \frac{2025 \cdot 110^{n}}{184756} - \frac{23 \cdot 12^{n}}{520} - \frac{9 \cdot 2^{n}}{440} - \frac{9 \cdot 20^{n}}{1144} + \frac{30^{n}}{104} - \frac{261 \cdot 42^{n}}{7480} + \frac{9 \cdot 56^{n}}{1768} - \frac{3 \cdot 6^{n}}{1144} + \frac{3723 \cdot 72^{n}}{54340} + \frac{243 \cdot 90^{n}}{4862} & \frac{3 \cdot 0^{n}}{154} + \frac{2025 \cdot 110^{n}}{184756} + \frac{12^{n}}{65} + \frac{9 \cdot 2^{n}}{1540} - \frac{18 \cdot 20^{n}}{1001} - \frac{30^{n}}{182} - \frac{87 \cdot 42^{n}}{13090} - \frac{9 \cdot 56^{n}}{221} + \frac{9 \cdot 6^{n}}{4004} - \frac{219 \cdot 72^{n}}{27170} + \frac{243 \cdot 90^{n}}{9724} & - \frac{5 \cdot 0^{n}}{308} + \frac{2025 \cdot 110^{n}}{184756} + \frac{45 \cdot 20^{n}}{2002} + \frac{145 \cdot 42^{n}}{7854} - \frac{25 \cdot 6^{n}}{12012} - \frac{365 \cdot 72^{n}}{10868} & \frac{3 \cdot 0^{n}}{154} + \frac{2025 \cdot 110^{n}}{184756} - \frac{12^{n}}{65} - \frac{9 \cdot 2^{n}}{1540} - \frac{18 \cdot 20^{n}}{1001} + \frac{30^{n}}{182} - \frac{87 \cdot 42^{n}}{13090} + \frac{9 \cdot 56^{n}}{221} + \frac{9 \cdot 6^{n}}{4004} - \frac{219 \cdot 72^{n}}{27170} - \frac{243 \cdot 90^{n}}{9724} & - \frac{3 \cdot 0^{n}}{88} + \frac{2025 \cdot 110^{n}}{184756} + \frac{23 \cdot 12^{n}}{520} + \frac{9 \cdot 2^{n}}{440} - \frac{9 \cdot 20^{n}}{1144} - \frac{30^{n}}{104} - \frac{261 \cdot 42^{n}}{7480} - \frac{9 \cdot 56^{n}}{1768} - \frac{3 \cdot 6^{n}}{1144} + \frac{3723 \cdot 72^{n}}{54340} - \frac{243 \cdot 90^{n}}{4862} & \frac{0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} - \frac{22 \cdot 12^{n}}{195} - \frac{9 \cdot 2^{n}}{110} + \frac{18 \cdot 20^{n}}{143} - \frac{30^{n}}{156} + \frac{841 \cdot 42^{n}}{11220} - \frac{99 \cdot 56^{n}}{442} + \frac{6^{n}}{858} + \frac{5329 \cdot 72^{n}}{27170} - \frac{729 \cdot 90^{n}}{9724} & - \frac{9 \cdot 0^{n}}{22} + \frac{2025 \cdot 110^{n}}{184756} + \frac{9 \cdot 12^{n}}{65} + \frac{27 \cdot 2^{n}}{55} - \frac{81 \cdot 20^{n}}{143} + \frac{9 \cdot 30^{n}}{52} + \frac{522 \cdot 42^{n}}{935} - \frac{621 \cdot 56^{n}}{884} + \frac{9 \cdot 6^{n}}{286} + \frac{20367 \cdot 72^{n}}{54340} - \frac{243 \cdot 90^{n}}{2431} & \frac{45 \cdot 0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} + \frac{90 \cdot 12^{n}}{13} - \frac{135 \cdot 2^{n}}{22} - \frac{810 \cdot 20^{n}}{143} + \frac{45 \cdot 30^{n}}{52} + \frac{1305 \cdot 42^{n}}{748} - \frac{675 \cdot 56^{n}}{442} - \frac{225 \cdot 6^{n}}{286} + \frac{3285 \cdot 72^{n}}{5434} - \frac{1215 \cdot 90^{n}}{9724}\\- \frac{120 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} + \frac{2760 \cdot 12^{n}}{143} - \frac{120 \cdot 2^{n}}{11} + \frac{360 \cdot 20^{n}}{143} - \frac{120 \cdot 30^{n}}{13} - \frac{1080 \cdot 42^{n}}{187} + \frac{600 \cdot 56^{n}}{2431} + \frac{1800 \cdot 6^{n}}{143} + \frac{4080 \cdot 72^{n}}{2717} + \frac{1440 \cdot 90^{n}}{2431} & \frac{12 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} + \frac{276 \cdot 12^{n}}{715} + \frac{48 \cdot 2^{n}}{55} + \frac{36 \cdot 20^{n}}{143} - \frac{24 \cdot 30^{n}}{13} - \frac{1728 \cdot 42^{n}}{935} + \frac{276 \cdot 56^{n}}{2431} - \frac{72 \cdot 6^{n}}{143} + \frac{12648 \cdot 72^{n}}{13585} + \frac{1152 \cdot 90^{n}}{2431} & - \frac{8 \cdot 0^{n}}{33} + \frac{3600 \cdot 110^{n}}{46189} - \frac{184 \cdot 12^{n}}{585} - \frac{8 \cdot 2^{n}}{55} - \frac{8 \cdot 20^{n}}{143} + \frac{8 \cdot 30^{n}}{117} - \frac{232 \cdot 42^{n}}{935} + \frac{8 \cdot 56^{n}}{221} - \frac{8 \cdot 6^{n}}{429} + \frac{19856 \cdot 72^{n}}{40755} + \frac{864 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} + \frac{529 \cdot 12^{n}}{4290} + \frac{2 \cdot 2^{n}}{55} + \frac{20^{n}}{286} + \frac{4 \cdot 30^{n}}{39} + \frac{108 \cdot 42^{n}}{935} + \frac{2 \cdot 56^{n}}{2431} + \frac{6 \cdot 6^{n}}{143} + \frac{2312 \cdot 72^{n}}{13585} + \frac{576 \cdot 90^{n}}{2431} & - \frac{4 \cdot 0^{n}}{77} + \frac{3600 \cdot 110^{n}}{46189} - \frac{92 \cdot 12^{n}}{2145} - \frac{4 \cdot 2^{n}}{385} + \frac{8 \cdot 20^{n}}{1001} - \frac{16 \cdot 30^{n}}{273} + \frac{144 \cdot 42^{n}}{6545} - \frac{16 \cdot 56^{n}}{2431} - \frac{36 \cdot 6^{n}}{1001} - \frac{272 \cdot 72^{n}}{13585} + \frac{288 \cdot 90^{n}}{2431} & \frac{10 \cdot 0^{n}}{231} + \frac{3600 \cdot 110^{n}}{46189} - \frac{10 \cdot 20^{n}}{1001} - \frac{80 \cdot 42^{n}}{1309} + \frac{100 \cdot 6^{n}}{3003} - \frac{680 \cdot 72^{n}}{8151} & - \frac{4 \cdot 0^{n}}{77} + \frac{3600 \cdot 110^{n}}{46189} + \frac{92 \cdot 12^{n}}{2145} + \frac{4 \cdot 2^{n}}{385} + \frac{8 \cdot 20^{n}}{1001} + \frac{16 \cdot 30^{n}}{273} + \frac{144 \cdot 42^{n}}{6545} + \frac{16 \cdot 56^{n}}{2431} - \frac{36 \cdot 6^{n}}{1001} - \frac{272 \cdot 72^{n}}{13585} - \frac{288 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} - \frac{529 \cdot 12^{n}}{4290} - \frac{2 \cdot 2^{n}}{55} + \frac{20^{n}}{286} - \frac{4 \cdot 30^{n}}{39} + \frac{108 \cdot 42^{n}}{935} - \frac{2 \cdot 56^{n}}{2431} + \frac{6 \cdot 6^{n}}{143} + \frac{2312 \cdot 72^{n}}{13585} - \frac{576 \cdot 90^{n}}{2431} & - \frac{8 \cdot 0^{n}}{33} + \frac{3600 \cdot 110^{n}}{46189} + \frac{184 \cdot 12^{n}}{585} + \frac{8 \cdot 2^{n}}{55} - \frac{8 \cdot 20^{n}}{143} - \frac{8 \cdot 30^{n}}{117} - \frac{232 \cdot 42^{n}}{935} - \frac{8 \cdot 56^{n}}{221} - \frac{8 \cdot 6^{n}}{429} + \frac{19856 \cdot 72^{n}}{40755} - \frac{864 \cdot 90^{n}}{2431} & \frac{12 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} - \frac{276 \cdot 12^{n}}{715} - \frac{48 \cdot 2^{n}}{55} + \frac{36 \cdot 20^{n}}{143} + \frac{24 \cdot 30^{n}}{13} - \frac{1728 \cdot 42^{n}}{935} - \frac{276 \cdot 56^{n}}{2431} - \frac{72 \cdot 6^{n}}{143} + \frac{12648 \cdot 72^{n}}{13585} - \frac{1152 \cdot 90^{n}}{2431} & - \frac{120 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} - \frac{2760 \cdot 12^{n}}{143} + \frac{120 \cdot 2^{n}}{11} + \frac{360 \cdot 20^{n}}{143} + \frac{120 \cdot 30^{n}}{13} - \frac{1080 \cdot 42^{n}}{187} - \frac{600 \cdot 56^{n}}{2431} + \frac{1800 \cdot 6^{n}}{143} + \frac{4080 \cdot 72^{n}}{2717} - \frac{1440 \cdot 90^{n}}{2431}\\\frac{210 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} - \frac{2940 \cdot 12^{n}}{143} + \frac{105 \cdot 2^{n}}{11} + \frac{2520 \cdot 20^{n}}{143} + \frac{210 \cdot 30^{n}}{13} - \frac{630 \cdot 42^{n}}{187} - \frac{14700 \cdot 56^{n}}{2431} - \frac{4725 \cdot 6^{n}}{143} - \frac{1470 \cdot 72^{n}}{2717} + \frac{2205 \cdot 90^{n}}{2431} & - \frac{21 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} - \frac{294 \cdot 12^{n}}{715} - \frac{42 \cdot 2^{n}}{55} + \frac{252 \cdot 20^{n}}{143} + \frac{42 \cdot 30^{n}}{13} - \frac{1008 \cdot 42^{n}}{935} - \frac{6762 \cdot 56^{n}}{2431} + \frac{189 \cdot 6^{n}}{143} - \frac{4557 \cdot 72^{n}}{13585} + \frac{1764 \cdot 90^{n}}{2431} & \frac{14 \cdot 0^{n}}{33} + \frac{11025 \cdot 110^{n}}{46189} + \frac{196 \cdot 12^{n}}{585} + \frac{7 \cdot 2^{n}}{55} - \frac{56 \cdot 20^{n}}{143} - \frac{14 \cdot 30^{n}}{117} - \frac{406 \cdot 42^{n}}{2805} - \frac{196 \cdot 56^{n}}{221} + \frac{7 \cdot 6^{n}}{143} - \frac{7154 \cdot 72^{n}}{40755} + \frac{1323 \cdot 90^{n}}{2431} & - \frac{7 \cdot 0^{n}}{44} + \frac{11025 \cdot 110^{n}}{46189} - \frac{1127 \cdot 12^{n}}{8580} - \frac{7 \cdot 2^{n}}{220} + \frac{7 \cdot 20^{n}}{286} - \frac{7 \cdot 30^{n}}{39} + \frac{63 \cdot 42^{n}}{935} - \frac{49 \cdot 56^{n}}{2431} - \frac{63 \cdot 6^{n}}{572} - \frac{833 \cdot 72^{n}}{13585} + \frac{882 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} + \frac{98 \cdot 12^{n}}{2145} + \frac{2^{n}}{110} + \frac{8 \cdot 20^{n}}{143} + \frac{4 \cdot 30^{n}}{39} + \frac{12 \cdot 42^{n}}{935} + \frac{392 \cdot 56^{n}}{2431} + \frac{27 \cdot 6^{n}}{286} + \frac{98 \cdot 72^{n}}{13585} + \frac{441 \cdot 90^{n}}{2431} & - \frac{5 \cdot 0^{n}}{66} + \frac{11025 \cdot 110^{n}}{46189} - \frac{10 \cdot 20^{n}}{143} - \frac{20 \cdot 42^{n}}{561} - \frac{25 \cdot 6^{n}}{286} + \frac{245 \cdot 72^{n}}{8151} & \frac{0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} - \frac{98 \cdot 12^{n}}{2145} - \frac{2^{n}}{110} + \frac{8 \cdot 20^{n}}{143} - \frac{4 \cdot 30^{n}}{39} + \frac{12 \cdot 42^{n}}{935} - \frac{392 \cdot 56^{n}}{2431} + \frac{27 \cdot 6^{n}}{286} + \frac{98 \cdot 72^{n}}{13585} - \frac{441 \cdot 90^{n}}{2431} & - \frac{7 \cdot 0^{n}}{44} + \frac{11025 \cdot 110^{n}}{46189} + \frac{1127 \cdot 12^{n}}{8580} + \frac{7 \cdot 2^{n}}{220} + \frac{7 \cdot 20^{n}}{286} + \frac{7 \cdot 30^{n}}{39} + \frac{63 \cdot 42^{n}}{935} + \frac{49 \cdot 56^{n}}{2431} - \frac{63 \cdot 6^{n}}{572} - \frac{833 \cdot 72^{n}}{13585} - \frac{882 \cdot 90^{n}}{2431} & \frac{14 \cdot 0^{n}}{33} + \frac{11025 \cdot 110^{n}}{46189} - \frac{196 \cdot 12^{n}}{585} - \frac{7 \cdot 2^{n}}{55} - \frac{56 \cdot 20^{n}}{143} + \frac{14 \cdot 30^{n}}{117} - \frac{406 \cdot 42^{n}}{2805} + \frac{196 \cdot 56^{n}}{221} + \frac{7 \cdot 6^{n}}{143} - \frac{7154 \cdot 72^{n}}{40755} - \frac{1323 \cdot 90^{n}}{2431} & - \frac{21 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} + \frac{294 \cdot 12^{n}}{715} + \frac{42 \cdot 2^{n}}{55} + \frac{252 \cdot 20^{n}}{143} - \frac{42 \cdot 30^{n}}{13} - \frac{1008 \cdot 42^{n}}{935} + \frac{6762 \cdot 56^{n}}{2431} + \frac{189 \cdot 6^{n}}{143} - \frac{4557 \cdot 72^{n}}{13585} - \frac{1764 \cdot 90^{n}}{2431} & \frac{210 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} + \frac{2940 \cdot 12^{n}}{143} - \frac{105 \cdot 2^{n}}{11} + \frac{2520 \cdot 20^{n}}{143} - \frac{210 \cdot 30^{n}}{13} - \frac{630 \cdot 42^{n}}{187} + \frac{14700 \cdot 56^{n}}{2431} - \frac{4725 \cdot 6^{n}}{143} - \frac{1470 \cdot 72^{n}}{2717} - \frac{2205 \cdot 90^{n}}{2431}\\- \frac{252 \cdot 0^{n}}{11} + \frac{15876 \cdot 110^{n}}{46189} - \frac{4536 \cdot 20^{n}}{143} + \frac{2520 \cdot 42^{n}}{187} + \frac{6300 \cdot 6^{n}}{143} - \frac{8820 \cdot 72^{n}}{2717} & \frac{126 \cdot 0^{n}}{55} + \frac{15876 \cdot 110^{n}}{46189} - \frac{2268 \cdot 20^{n}}{715} + \frac{4032 \cdot 42^{n}}{935} - \frac{252 \cdot 6^{n}}{143} - \frac{27342 \cdot 72^{n}}{13585} & - \frac{28 \cdot 0^{n}}{55} + \frac{15876 \cdot 110^{n}}{46189} + \frac{504 \cdot 20^{n}}{715} + \frac{1624 \cdot 42^{n}}{2805} - \frac{28 \cdot 6^{n}}{429} - \frac{14308 \cdot 72^{n}}{13585} & \frac{21 \cdot 0^{n}}{110} + \frac{15876 \cdot 110^{n}}{46189} - \frac{63 \cdot 20^{n}}{1430} - \frac{252 \cdot 42^{n}}{935} + \frac{21 \cdot 6^{n}}{143} - \frac{4998 \cdot 72^{n}}{13585} & - \frac{6 \cdot 0^{n}}{55} + \frac{15876 \cdot 110^{n}}{46189} - \frac{72 \cdot 20^{n}}{715} - \frac{48 \cdot 42^{n}}{935} - \frac{18 \cdot 6^{n}}{143} + \frac{588 \cdot 72^{n}}{13585} & \frac{0^{n}}{11} + \frac{15876 \cdot 110^{n}}{46189} + \frac{18 \cdot 20^{n}}{143} + \frac{80 \cdot 42^{n}}{561} + \frac{50 \cdot 6^{n}}{429} + \frac{490 \cdot 72^{n}}{2717} & - \frac{6 \cdot 0^{n}}{55} + \frac{15876 \cdot 110^{n}}{46189} - \frac{72 \cdot 20^{n}}{715} - \frac{48 \cdot 42^{n}}{935} - \frac{18 \cdot 6^{n}}{143} + \frac{588 \cdot 72^{n}}{13585} & \frac{21 \cdot 0^{n}}{110} + \frac{15876 \cdot 110^{n}}{46189} - \frac{63 \cdot 20^{n}}{1430} - \frac{252 \cdot 42^{n}}{935} + \frac{21 \cdot 6^{n}}{143} - \frac{4998 \cdot 72^{n}}{13585} & - \frac{28 \cdot 0^{n}}{55} + \frac{15876 \cdot 110^{n}}{46189} + \frac{504 \cdot 20^{n}}{715} + \frac{1624 \cdot 42^{n}}{2805} - \frac{28 \cdot 6^{n}}{429} - \frac{14308 \cdot 72^{n}}{13585} & \frac{126 \cdot 0^{n}}{55} + \frac{15876 \cdot 110^{n}}{46189} - \frac{2268 \cdot 20^{n}}{715} + \frac{4032 \cdot 42^{n}}{935} - \frac{252 \cdot 6^{n}}{143} - \frac{27342 \cdot 72^{n}}{13585} & - \frac{252 \cdot 0^{n}}{11} + \frac{15876 \cdot 110^{n}}{46189} - \frac{4536 \cdot 20^{n}}{143} + \frac{2520 \cdot 42^{n}}{187} + \frac{6300 \cdot 6^{n}}{143} - \frac{8820 \cdot 72^{n}}{2717}\\\frac{210 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} + \frac{2940 \cdot 12^{n}}{143} - \frac{105 \cdot 2^{n}}{11} + \frac{2520 \cdot 20^{n}}{143} - \frac{210 \cdot 30^{n}}{13} - \frac{630 \cdot 42^{n}}{187} + \frac{14700 \cdot 56^{n}}{2431} - \frac{4725 \cdot 6^{n}}{143} - \frac{1470 \cdot 72^{n}}{2717} - \frac{2205 \cdot 90^{n}}{2431} & - \frac{21 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} + \frac{294 \cdot 12^{n}}{715} + \frac{42 \cdot 2^{n}}{55} + \frac{252 \cdot 20^{n}}{143} - \frac{42 \cdot 30^{n}}{13} - \frac{1008 \cdot 42^{n}}{935} + \frac{6762 \cdot 56^{n}}{2431} + \frac{189 \cdot 6^{n}}{143} - \frac{4557 \cdot 72^{n}}{13585} - \frac{1764 \cdot 90^{n}}{2431} & \frac{14 \cdot 0^{n}}{33} + \frac{11025 \cdot 110^{n}}{46189} - \frac{196 \cdot 12^{n}}{585} - \frac{7 \cdot 2^{n}}{55} - \frac{56 \cdot 20^{n}}{143} + \frac{14 \cdot 30^{n}}{117} - \frac{406 \cdot 42^{n}}{2805} + \frac{196 \cdot 56^{n}}{221} + \frac{7 \cdot 6^{n}}{143} - \frac{7154 \cdot 72^{n}}{40755} - \frac{1323 \cdot 90^{n}}{2431} & - \frac{7 \cdot 0^{n}}{44} + \frac{11025 \cdot 110^{n}}{46189} + \frac{1127 \cdot 12^{n}}{8580} + \frac{7 \cdot 2^{n}}{220} + \frac{7 \cdot 20^{n}}{286} + \frac{7 \cdot 30^{n}}{39} + \frac{63 \cdot 42^{n}}{935} + \frac{49 \cdot 56^{n}}{2431} - \frac{63 \cdot 6^{n}}{572} - \frac{833 \cdot 72^{n}}{13585} - \frac{882 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} - \frac{98 \cdot 12^{n}}{2145} - \frac{2^{n}}{110} + \frac{8 \cdot 20^{n}}{143} - \frac{4 \cdot 30^{n}}{39} + \frac{12 \cdot 42^{n}}{935} - \frac{392 \cdot 56^{n}}{2431} + \frac{27 \cdot 6^{n}}{286} + \frac{98 \cdot 72^{n}}{13585} - \frac{441 \cdot 90^{n}}{2431} & - \frac{5 \cdot 0^{n}}{66} + \frac{11025 \cdot 110^{n}}{46189} - \frac{10 \cdot 20^{n}}{143} - \frac{20 \cdot 42^{n}}{561} - \frac{25 \cdot 6^{n}}{286} + \frac{245 \cdot 72^{n}}{8151} & \frac{0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} + \frac{98 \cdot 12^{n}}{2145} + \frac{2^{n}}{110} + \frac{8 \cdot 20^{n}}{143} + \frac{4 \cdot 30^{n}}{39} + \frac{12 \cdot 42^{n}}{935} + \frac{392 \cdot 56^{n}}{2431} + \frac{27 \cdot 6^{n}}{286} + \frac{98 \cdot 72^{n}}{13585} + \frac{441 \cdot 90^{n}}{2431} & - \frac{7 \cdot 0^{n}}{44} + \frac{11025 \cdot 110^{n}}{46189} - \frac{1127 \cdot 12^{n}}{8580} - \frac{7 \cdot 2^{n}}{220} + \frac{7 \cdot 20^{n}}{286} - \frac{7 \cdot 30^{n}}{39} + \frac{63 \cdot 42^{n}}{935} - \frac{49 \cdot 56^{n}}{2431} - \frac{63 \cdot 6^{n}}{572} - \frac{833 \cdot 72^{n}}{13585} + \frac{882 \cdot 90^{n}}{2431} & \frac{14 \cdot 0^{n}}{33} + \frac{11025 \cdot 110^{n}}{46189} + \frac{196 \cdot 12^{n}}{585} + \frac{7 \cdot 2^{n}}{55} - \frac{56 \cdot 20^{n}}{143} - \frac{14 \cdot 30^{n}}{117} - \frac{406 \cdot 42^{n}}{2805} - \frac{196 \cdot 56^{n}}{221} + \frac{7 \cdot 6^{n}}{143} - \frac{7154 \cdot 72^{n}}{40755} + \frac{1323 \cdot 90^{n}}{2431} & - \frac{21 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} - \frac{294 \cdot 12^{n}}{715} - \frac{42 \cdot 2^{n}}{55} + \frac{252 \cdot 20^{n}}{143} + \frac{42 \cdot 30^{n}}{13} - \frac{1008 \cdot 42^{n}}{935} - \frac{6762 \cdot 56^{n}}{2431} + \frac{189 \cdot 6^{n}}{143} - \frac{4557 \cdot 72^{n}}{13585} + \frac{1764 \cdot 90^{n}}{2431} & \frac{210 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} - \frac{2940 \cdot 12^{n}}{143} + \frac{105 \cdot 2^{n}}{11} + \frac{2520 \cdot 20^{n}}{143} + \frac{210 \cdot 30^{n}}{13} - \frac{630 \cdot 42^{n}}{187} - \frac{14700 \cdot 56^{n}}{2431} - \frac{4725 \cdot 6^{n}}{143} - \frac{1470 \cdot 72^{n}}{2717} + \frac{2205 \cdot 90^{n}}{2431}\\- \frac{120 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} - \frac{2760 \cdot 12^{n}}{143} + \frac{120 \cdot 2^{n}}{11} + \frac{360 \cdot 20^{n}}{143} + \frac{120 \cdot 30^{n}}{13} - \frac{1080 \cdot 42^{n}}{187} - \frac{600 \cdot 56^{n}}{2431} + \frac{1800 \cdot 6^{n}}{143} + \frac{4080 \cdot 72^{n}}{2717} - \frac{1440 \cdot 90^{n}}{2431} & \frac{12 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} - \frac{276 \cdot 12^{n}}{715} - \frac{48 \cdot 2^{n}}{55} + \frac{36 \cdot 20^{n}}{143} + \frac{24 \cdot 30^{n}}{13} - \frac{1728 \cdot 42^{n}}{935} - \frac{276 \cdot 56^{n}}{2431} - \frac{72 \cdot 6^{n}}{143} + \frac{12648 \cdot 72^{n}}{13585} - \frac{1152 \cdot 90^{n}}{2431} & - \frac{8 \cdot 0^{n}}{33} + \frac{3600 \cdot 110^{n}}{46189} + \frac{184 \cdot 12^{n}}{585} + \frac{8 \cdot 2^{n}}{55} - \frac{8 \cdot 20^{n}}{143} - \frac{8 \cdot 30^{n}}{117} - \frac{232 \cdot 42^{n}}{935} - \frac{8 \cdot 56^{n}}{221} - \frac{8 \cdot 6^{n}}{429} + \frac{19856 \cdot 72^{n}}{40755} - \frac{864 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} - \frac{529 \cdot 12^{n}}{4290} - \frac{2 \cdot 2^{n}}{55} + \frac{20^{n}}{286} - \frac{4 \cdot 30^{n}}{39} + \frac{108 \cdot 42^{n}}{935} - \frac{2 \cdot 56^{n}}{2431} + \frac{6 \cdot 6^{n}}{143} + \frac{2312 \cdot 72^{n}}{13585} - \frac{576 \cdot 90^{n}}{2431} & - \frac{4 \cdot 0^{n}}{77} + \frac{3600 \cdot 110^{n}}{46189} + \frac{92 \cdot 12^{n}}{2145} + \frac{4 \cdot 2^{n}}{385} + \frac{8 \cdot 20^{n}}{1001} + \frac{16 \cdot 30^{n}}{273} + \frac{144 \cdot 42^{n}}{6545} + \frac{16 \cdot 56^{n}}{2431} - \frac{36 \cdot 6^{n}}{1001} - \frac{272 \cdot 72^{n}}{13585} - \frac{288 \cdot 90^{n}}{2431} & \frac{10 \cdot 0^{n}}{231} + \frac{3600 \cdot 110^{n}}{46189} - \frac{10 \cdot 20^{n}}{1001} - \frac{80 \cdot 42^{n}}{1309} + \frac{100 \cdot 6^{n}}{3003} - \frac{680 \cdot 72^{n}}{8151} & - \frac{4 \cdot 0^{n}}{77} + \frac{3600 \cdot 110^{n}}{46189} - \frac{92 \cdot 12^{n}}{2145} - \frac{4 \cdot 2^{n}}{385} + \frac{8 \cdot 20^{n}}{1001} - \frac{16 \cdot 30^{n}}{273} + \frac{144 \cdot 42^{n}}{6545} - \frac{16 \cdot 56^{n}}{2431} - \frac{36 \cdot 6^{n}}{1001} - \frac{272 \cdot 72^{n}}{13585} + \frac{288 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} + \frac{529 \cdot 12^{n}}{4290} + \frac{2 \cdot 2^{n}}{55} + \frac{20^{n}}{286} + \frac{4 \cdot 30^{n}}{39} + \frac{108 \cdot 42^{n}}{935} + \frac{2 \cdot 56^{n}}{2431} + \frac{6 \cdot 6^{n}}{143} + \frac{2312 \cdot 72^{n}}{13585} + \frac{576 \cdot 90^{n}}{2431} & - \frac{8 \cdot 0^{n}}{33} + \frac{3600 \cdot 110^{n}}{46189} - \frac{184 \cdot 12^{n}}{585} - \frac{8 \cdot 2^{n}}{55} - \frac{8 \cdot 20^{n}}{143} + \frac{8 \cdot 30^{n}}{117} - \frac{232 \cdot 42^{n}}{935} + \frac{8 \cdot 56^{n}}{221} - \frac{8 \cdot 6^{n}}{429} + \frac{19856 \cdot 72^{n}}{40755} + \frac{864 \cdot 90^{n}}{2431} & \frac{12 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} + \frac{276 \cdot 12^{n}}{715} + \frac{48 \cdot 2^{n}}{55} + \frac{36 \cdot 20^{n}}{143} - \frac{24 \cdot 30^{n}}{13} - \frac{1728 \cdot 42^{n}}{935} + \frac{276 \cdot 56^{n}}{2431} - \frac{72 \cdot 6^{n}}{143} + \frac{12648 \cdot 72^{n}}{13585} + \frac{1152 \cdot 90^{n}}{2431} & - \frac{120 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} + \frac{2760 \cdot 12^{n}}{143} - \frac{120 \cdot 2^{n}}{11} + \frac{360 \cdot 20^{n}}{143} - \frac{120 \cdot 30^{n}}{13} - \frac{1080 \cdot 42^{n}}{187} + \frac{600 \cdot 56^{n}}{2431} + \frac{1800 \cdot 6^{n}}{143} + \frac{4080 \cdot 72^{n}}{2717} + \frac{1440 \cdot 90^{n}}{2431}\\\frac{45 \cdot 0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} + \frac{90 \cdot 12^{n}}{13} - \frac{135 \cdot 2^{n}}{22} - \frac{810 \cdot 20^{n}}{143} + \frac{45 \cdot 30^{n}}{52} + \frac{1305 \cdot 42^{n}}{748} - \frac{675 \cdot 56^{n}}{442} - \frac{225 \cdot 6^{n}}{286} + \frac{3285 \cdot 72^{n}}{5434} - \frac{1215 \cdot 90^{n}}{9724} & - \frac{9 \cdot 0^{n}}{22} + \frac{2025 \cdot 110^{n}}{184756} + \frac{9 \cdot 12^{n}}{65} + \frac{27 \cdot 2^{n}}{55} - \frac{81 \cdot 20^{n}}{143} + \frac{9 \cdot 30^{n}}{52} + \frac{522 \cdot 42^{n}}{935} - \frac{621 \cdot 56^{n}}{884} + \frac{9 \cdot 6^{n}}{286} + \frac{20367 \cdot 72^{n}}{54340} - \frac{243 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} - \frac{22 \cdot 12^{n}}{195} - \frac{9 \cdot 2^{n}}{110} + \frac{18 \cdot 20^{n}}{143} - \frac{30^{n}}{156} + \frac{841 \cdot 42^{n}}{11220} - \frac{99 \cdot 56^{n}}{442} + \frac{6^{n}}{858} + \frac{5329 \cdot 72^{n}}{27170} - \frac{729 \cdot 90^{n}}{9724} & - \frac{3 \cdot 0^{n}}{88} + \frac{2025 \cdot 110^{n}}{184756} + \frac{23 \cdot 12^{n}}{520} + \frac{9 \cdot 2^{n}}{440} - \frac{9 \cdot 20^{n}}{1144} - \frac{30^{n}}{104} - \frac{261 \cdot 42^{n}}{7480} - \frac{9 \cdot 56^{n}}{1768} - \frac{3 \cdot 6^{n}}{1144} + \frac{3723 \cdot 72^{n}}{54340} - \frac{243 \cdot 90^{n}}{4862} & \frac{3 \cdot 0^{n}}{154} + \frac{2025 \cdot 110^{n}}{184756} - \frac{12^{n}}{65} - \frac{9 \cdot 2^{n}}{1540} - \frac{18 \cdot 20^{n}}{1001} + \frac{30^{n}}{182} - \frac{87 \cdot 42^{n}}{13090} + \frac{9 \cdot 56^{n}}{221} + \frac{9 \cdot 6^{n}}{4004} - \frac{219 \cdot 72^{n}}{27170} - \frac{243 \cdot 90^{n}}{9724} & - \frac{5 \cdot 0^{n}}{308} + \frac{2025 \cdot 110^{n}}{184756} + \frac{45 \cdot 20^{n}}{2002} + \frac{145 \cdot 42^{n}}{7854} - \frac{25 \cdot 6^{n}}{12012} - \frac{365 \cdot 72^{n}}{10868} & \frac{3 \cdot 0^{n}}{154} + \frac{2025 \cdot 110^{n}}{184756} + \frac{12^{n}}{65} + \frac{9 \cdot 2^{n}}{1540} - \frac{18 \cdot 20^{n}}{1001} - \frac{30^{n}}{182} - \frac{87 \cdot 42^{n}}{13090} - \frac{9 \cdot 56^{n}}{221} + \frac{9 \cdot 6^{n}}{4004} - \frac{219 \cdot 72^{n}}{27170} + \frac{243 \cdot 90^{n}}{9724} & - \frac{3 \cdot 0^{n}}{88} + \frac{2025 \cdot 110^{n}}{184756} - \frac{23 \cdot 12^{n}}{520} - \frac{9 \cdot 2^{n}}{440} - \frac{9 \cdot 20^{n}}{1144} + \frac{30^{n}}{104} - \frac{261 \cdot 42^{n}}{7480} + \frac{9 \cdot 56^{n}}{1768} - \frac{3 \cdot 6^{n}}{1144} + \frac{3723 \cdot 72^{n}}{54340} + \frac{243 \cdot 90^{n}}{4862} & \frac{0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} + \frac{22 \cdot 12^{n}}{195} + \frac{9 \cdot 2^{n}}{110} + \frac{18 \cdot 20^{n}}{143} + \frac{30^{n}}{156} + \frac{841 \cdot 42^{n}}{11220} + \frac{99 \cdot 56^{n}}{442} + \frac{6^{n}}{858} + \frac{5329 \cdot 72^{n}}{27170} + \frac{729 \cdot 90^{n}}{9724} & - \frac{9 \cdot 0^{n}}{22} + \frac{2025 \cdot 110^{n}}{184756} - \frac{9 \cdot 12^{n}}{65} - \frac{27 \cdot 2^{n}}{55} - \frac{81 \cdot 20^{n}}{143} - \frac{9 \cdot 30^{n}}{52} + \frac{522 \cdot 42^{n}}{935} + \frac{621 \cdot 56^{n}}{884} + \frac{9 \cdot 6^{n}}{286} + \frac{20367 \cdot 72^{n}}{54340} + \frac{243 \cdot 90^{n}}{2431} & \frac{45 \cdot 0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} - \frac{90 \cdot 12^{n}}{13} + \frac{135 \cdot 2^{n}}{22} - \frac{810 \cdot 20^{n}}{143} - \frac{45 \cdot 30^{n}}{52} + \frac{1305 \cdot 42^{n}}{748} + \frac{675 \cdot 56^{n}}{442} - \frac{225 \cdot 6^{n}}{286} + \frac{3285 \cdot 72^{n}}{5434} + \frac{1215 \cdot 90^{n}}{9724}\\- \frac{10 \cdot 0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} - \frac{60 \cdot 12^{n}}{143} + \frac{20 \cdot 2^{n}}{11} + \frac{180 \cdot 20^{n}}{143} - \frac{15 \cdot 30^{n}}{13} + \frac{120 \cdot 42^{n}}{187} - \frac{575 \cdot 56^{n}}{2431} - \frac{150 \cdot 6^{n}}{143} + \frac{155 \cdot 72^{n}}{2717} - \frac{20 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} - \frac{6 \cdot 12^{n}}{715} - \frac{8 \cdot 2^{n}}{55} + \frac{18 \cdot 20^{n}}{143} - \frac{3 \cdot 30^{n}}{13} + \frac{192 \cdot 42^{n}}{935} - \frac{529 \cdot 56^{n}}{4862} + \frac{6 \cdot 6^{n}}{143} + \frac{961 \cdot 72^{n}}{27170} - \frac{16 \cdot 90^{n}}{2431} & - \frac{2 \cdot 0^{n}}{99} + \frac{25 \cdot 110^{n}}{46189} + \frac{4 \cdot 12^{n}}{585} + \frac{4 \cdot 2^{n}}{165} - \frac{4 \cdot 20^{n}}{143} + \frac{30^{n}}{117} + \frac{232 \cdot 42^{n}}{8415} - \frac{23 \cdot 56^{n}}{663} + \frac{2 \cdot 6^{n}}{1287} + \frac{2263 \cdot 72^{n}}{122265} - \frac{12 \cdot 90^{n}}{2431} & \frac{0^{n}}{132} + \frac{25 \cdot 110^{n}}{46189} - \frac{23 \cdot 12^{n}}{8580} - \frac{2^{n}}{165} + \frac{20^{n}}{572} + \frac{30^{n}}{78} - \frac{12 \cdot 42^{n}}{935} - \frac{23 \cdot 56^{n}}{29172} - \frac{6^{n}}{286} + \frac{527 \cdot 72^{n}}{81510} - \frac{8 \cdot 90^{n}}{2431} & - \frac{0^{n}}{231} + \frac{25 \cdot 110^{n}}{46189} + \frac{2 \cdot 12^{n}}{2145} + \frac{2 \cdot 2^{n}}{1155} + \frac{4 \cdot 20^{n}}{1001} - \frac{2 \cdot 30^{n}}{273} - \frac{16 \cdot 42^{n}}{6545} + \frac{46 \cdot 56^{n}}{7293} + \frac{3 \cdot 6^{n}}{1001} - \frac{31 \cdot 72^{n}}{40755} - \frac{4 \cdot 90^{n}}{2431} & \frac{5 \cdot 0^{n}}{1386} + \frac{25 \cdot 110^{n}}{46189} - \frac{5 \cdot 20^{n}}{1001} + \frac{80 \cdot 42^{n}}{11781} - \frac{25 \cdot 6^{n}}{9009} - \frac{155 \cdot 72^{n}}{48906} & - \frac{0^{n}}{231} + \frac{25 \cdot 110^{n}}{46189} - \frac{2 \cdot 12^{n}}{2145} - \frac{2 \cdot 2^{n}}{1155} + \frac{4 \cdot 20^{n}}{1001} + \frac{2 \cdot 30^{n}}{273} - \frac{16 \cdot 42^{n}}{6545} - \frac{46 \cdot 56^{n}}{7293} + \frac{3 \cdot 6^{n}}{1001} - \frac{31 \cdot 72^{n}}{40755} + \frac{4 \cdot 90^{n}}{2431} & \frac{0^{n}}{132} + \frac{25 \cdot 110^{n}}{46189} + \frac{23 \cdot 12^{n}}{8580} + \frac{2^{n}}{165} + \frac{20^{n}}{572} - \frac{30^{n}}{78} - \frac{12 \cdot 42^{n}}{935} + \frac{23 \cdot 56^{n}}{29172} - \frac{6^{n}}{286} + \frac{527 \cdot 72^{n}}{81510} + \frac{8 \cdot 90^{n}}{2431} & - \frac{2 \cdot 0^{n}}{99} + \frac{25 \cdot 110^{n}}{46189} - \frac{4 \cdot 12^{n}}{585} - \frac{4 \cdot 2^{n}}{165} - \frac{4 \cdot 20^{n}}{143} - \frac{30^{n}}{117} + \frac{232 \cdot 42^{n}}{8415} + \frac{23 \cdot 56^{n}}{663} + \frac{2 \cdot 6^{n}}{1287} + \frac{2263 \cdot 72^{n}}{122265} + \frac{12 \cdot 90^{n}}{2431} & \frac{0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} + \frac{6 \cdot 12^{n}}{715} + \frac{8 \cdot 2^{n}}{55} + \frac{18 \cdot 20^{n}}{143} + \frac{3 \cdot 30^{n}}{13} + \frac{192 \cdot 42^{n}}{935} + \frac{529 \cdot 56^{n}}{4862} + \frac{6 \cdot 6^{n}}{143} + \frac{961 \cdot 72^{n}}{27170} + \frac{16 \cdot 90^{n}}{2431} & - \frac{10 \cdot 0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} + \frac{60 \cdot 12^{n}}{143} - \frac{20 \cdot 2^{n}}{11} + \frac{180 \cdot 20^{n}}{143} + \frac{15 \cdot 30^{n}}{13} + \frac{120 \cdot 42^{n}}{187} + \frac{575 \cdot 56^{n}}{2431} - \frac{150 \cdot 6^{n}}{143} + \frac{155 \cdot 72^{n}}{2717} + \frac{20 \cdot 90^{n}}{2431}\\\frac{0^{n}}{11} + \frac{110^{n}}{184756} - \frac{30 \cdot 12^{n}}{143} - \frac{5 \cdot 2^{n}}{22} + \frac{18 \cdot 20^{n}}{143} - \frac{3 \cdot 30^{n}}{52} + \frac{15 \cdot 42^{n}}{748} - \frac{25 \cdot 56^{n}}{4862} + \frac{75 \cdot 6^{n}}{286} + \frac{5 \cdot 72^{n}}{5434} - \frac{90^{n}}{9724} & - \frac{0^{n}}{110} + \frac{110^{n}}{184756} - \frac{3 \cdot 12^{n}}{715} + \frac{2^{n}}{55} + \frac{9 \cdot 20^{n}}{715} - \frac{3 \cdot 30^{n}}{260} + \frac{6 \cdot 42^{n}}{935} - \frac{23 \cdot 56^{n}}{9724} - \frac{3 \cdot 6^{n}}{286} + \frac{31 \cdot 72^{n}}{54340} - \frac{90^{n}}{12155} & \frac{0^{n}}{495} + \frac{110^{n}}{184756} + \frac{2 \cdot 12^{n}}{585} - \frac{2^{n}}{330} - \frac{2 \cdot 20^{n}}{715} + \frac{30^{n}}{2340} + \frac{29 \cdot 42^{n}}{33660} - \frac{56^{n}}{1326} - \frac{6^{n}}{2574} + \frac{73 \cdot 72^{n}}{244530} - \frac{3 \cdot 90^{n}}{48620} & - \frac{0^{n}}{1320} + \frac{110^{n}}{184756} - \frac{23 \cdot 12^{n}}{17160} + \frac{2^{n}}{1320} + \frac{20^{n}}{5720} + \frac{30^{n}}{1560} - \frac{3 \cdot 42^{n}}{7480} - \frac{56^{n}}{58344} + \frac{6^{n}}{1144} + \frac{17 \cdot 72^{n}}{163020} - \frac{90^{n}}{24310} & \frac{0^{n}}{2310} + \frac{110^{n}}{184756} + \frac{12^{n}}{2145} - \frac{2^{n}}{4620} + \frac{2 \cdot 20^{n}}{5005} - \frac{30^{n}}{2730} - \frac{42^{n}}{13090} + \frac{56^{n}}{7293} - \frac{3 \cdot 6^{n}}{4004} - \frac{72^{n}}{81510} - \frac{90^{n}}{48620} & - \frac{0^{n}}{2772} + \frac{110^{n}}{184756} - \frac{20^{n}}{2002} + \frac{5 \cdot 42^{n}}{23562} + \frac{25 \cdot 6^{n}}{36036} - \frac{5 \cdot 72^{n}}{97812} & \frac{0^{n}}{2310} + \frac{110^{n}}{184756} - \frac{12^{n}}{2145} + \frac{2^{n}}{4620} + \frac{2 \cdot 20^{n}}{5005} + \frac{30^{n}}{2730} - \frac{42^{n}}{13090} - \frac{56^{n}}{7293} - \frac{3 \cdot 6^{n}}{4004} - \frac{72^{n}}{81510} + \frac{90^{n}}{48620} & - \frac{0^{n}}{1320} + \frac{110^{n}}{184756} + \frac{23 \cdot 12^{n}}{17160} - \frac{2^{n}}{1320} + \frac{20^{n}}{5720} - \frac{30^{n}}{1560} - \frac{3 \cdot 42^{n}}{7480} + \frac{56^{n}}{58344} + \frac{6^{n}}{1144} + \frac{17 \cdot 72^{n}}{163020} + \frac{90^{n}}{24310} & \frac{0^{n}}{495} + \frac{110^{n}}{184756} - \frac{2 \cdot 12^{n}}{585} + \frac{2^{n}}{330} - \frac{2 \cdot 20^{n}}{715} - \frac{30^{n}}{2340} + \frac{29 \cdot 42^{n}}{33660} + \frac{56^{n}}{1326} - \frac{6^{n}}{2574} + \frac{73 \cdot 72^{n}}{244530} + \frac{3 \cdot 90^{n}}{48620} & - \frac{0^{n}}{110} + \frac{110^{n}}{184756} + \frac{3 \cdot 12^{n}}{715} - \frac{2^{n}}{55} + \frac{9 \cdot 20^{n}}{715} + \frac{3 \cdot 30^{n}}{260} + \frac{6 \cdot 42^{n}}{935} + \frac{23 \cdot 56^{n}}{9724} - \frac{3 \cdot 6^{n}}{286} + \frac{31 \cdot 72^{n}}{54340} + \frac{90^{n}}{12155} & \frac{0^{n}}{11} + \frac{110^{n}}{184756} + \frac{30 \cdot 12^{n}}{143} + \frac{5 \cdot 2^{n}}{22} + \frac{18 \cdot 20^{n}}{143} + \frac{3 \cdot 30^{n}}{52} + \frac{15 \cdot 42^{n}}{748} + \frac{25 \cdot 56^{n}}{4862} + \frac{75 \cdot 6^{n}}{286} + \frac{5 \cdot 72^{n}}{5434} + \frac{90^{n}}{9724}\end{array}\right]
```

ものすごい行列になってしまいましたが，めでたく$n$乗計算ができました。

これにより，

```math
\boldsymbol{v}_{n} = \frac{1}{110^n} A^n \boldsymbol{v}_{0}
```

は次のように計算できます。

### input

```python
B = P*(D**n)*P.inv()/(110**n) # A^nをBとおく
v = sympy.Matrix([0,0,0,0,0,0,0,0,0,0,1]) # 初期値v_0
p = B*v # n回目の試行後の確率分布
display(p)
```

### output

```math
\left[\begin{matrix}110^{- n} \left(\frac{0^{n}}{11} + \frac{110^{n}}{184756} - \frac{30 \cdot 12^{n}}{143} - \frac{5 \cdot 2^{n}}{22} + \frac{18 \cdot 20^{n}}{143} - \frac{3 \cdot 30^{n}}{52} + \frac{15 \cdot 42^{n}}{748} - \frac{25 \cdot 56^{n}}{4862} + \frac{75 \cdot 6^{n}}{286} + \frac{5 \cdot 72^{n}}{5434} - \frac{90^{n}}{9724}\right)\\110^{- n} \left(- \frac{10 \cdot 0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} - \frac{60 \cdot 12^{n}}{143} + \frac{20 \cdot 2^{n}}{11} + \frac{180 \cdot 20^{n}}{143} - \frac{15 \cdot 30^{n}}{13} + \frac{120 \cdot 42^{n}}{187} - \frac{575 \cdot 56^{n}}{2431} - \frac{150 \cdot 6^{n}}{143} + \frac{155 \cdot 72^{n}}{2717} - \frac{20 \cdot 90^{n}}{2431}\right)\\110^{- n} \left(\frac{45 \cdot 0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} + \frac{90 \cdot 12^{n}}{13} - \frac{135 \cdot 2^{n}}{22} - \frac{810 \cdot 20^{n}}{143} + \frac{45 \cdot 30^{n}}{52} + \frac{1305 \cdot 42^{n}}{748} - \frac{675 \cdot 56^{n}}{442} - \frac{225 \cdot 6^{n}}{286} + \frac{3285 \cdot 72^{n}}{5434} - \frac{1215 \cdot 90^{n}}{9724}\right)\\110^{- n} \left(- \frac{120 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} - \frac{2760 \cdot 12^{n}}{143} + \frac{120 \cdot 2^{n}}{11} + \frac{360 \cdot 20^{n}}{143} + \frac{120 \cdot 30^{n}}{13} - \frac{1080 \cdot 42^{n}}{187} - \frac{600 \cdot 56^{n}}{2431} + \frac{1800 \cdot 6^{n}}{143} + \frac{4080 \cdot 72^{n}}{2717} - \frac{1440 \cdot 90^{n}}{2431}\right)\\110^{- n} \left(\frac{210 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} + \frac{2940 \cdot 12^{n}}{143} - \frac{105 \cdot 2^{n}}{11} + \frac{2520 \cdot 20^{n}}{143} - \frac{210 \cdot 30^{n}}{13} - \frac{630 \cdot 42^{n}}{187} + \frac{14700 \cdot 56^{n}}{2431} - \frac{4725 \cdot 6^{n}}{143} - \frac{1470 \cdot 72^{n}}{2717} - \frac{2205 \cdot 90^{n}}{2431}\right)\\110^{- n} \left(- \frac{252 \cdot 0^{n}}{11} + \frac{15876 \cdot 110^{n}}{46189} - \frac{4536 \cdot 20^{n}}{143} + \frac{2520 \cdot 42^{n}}{187} + \frac{6300 \cdot 6^{n}}{143} - \frac{8820 \cdot 72^{n}}{2717}\right)\\110^{- n} \left(\frac{210 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} - \frac{2940 \cdot 12^{n}}{143} + \frac{105 \cdot 2^{n}}{11} + \frac{2520 \cdot 20^{n}}{143} + \frac{210 \cdot 30^{n}}{13} - \frac{630 \cdot 42^{n}}{187} - \frac{14700 \cdot 56^{n}}{2431} - \frac{4725 \cdot 6^{n}}{143} - \frac{1470 \cdot 72^{n}}{2717} + \frac{2205 \cdot 90^{n}}{2431}\right)\\110^{- n} \left(- \frac{120 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} + \frac{2760 \cdot 12^{n}}{143} - \frac{120 \cdot 2^{n}}{11} + \frac{360 \cdot 20^{n}}{143} - \frac{120 \cdot 30^{n}}{13} - \frac{1080 \cdot 42^{n}}{187} + \frac{600 \cdot 56^{n}}{2431} + \frac{1800 \cdot 6^{n}}{143} + \frac{4080 \cdot 72^{n}}{2717} + \frac{1440 \cdot 90^{n}}{2431}\right)\\110^{- n} \left(\frac{45 \cdot 0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} - \frac{90 \cdot 12^{n}}{13} + \frac{135 \cdot 2^{n}}{22} - \frac{810 \cdot 20^{n}}{143} - \frac{45 \cdot 30^{n}}{52} + \frac{1305 \cdot 42^{n}}{748} + \frac{675 \cdot 56^{n}}{442} - \frac{225 \cdot 6^{n}}{286} + \frac{3285 \cdot 72^{n}}{5434} + \frac{1215 \cdot 90^{n}}{9724}\right)\\110^{- n} \left(- \frac{10 \cdot 0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} + \frac{60 \cdot 12^{n}}{143} - \frac{20 \cdot 2^{n}}{11} + \frac{180 \cdot 20^{n}}{143} + \frac{15 \cdot 30^{n}}{13} + \frac{120 \cdot 42^{n}}{187} + \frac{575 \cdot 56^{n}}{2431} - \frac{150 \cdot 6^{n}}{143} + \frac{155 \cdot 72^{n}}{2717} + \frac{20 \cdot 90^{n}}{2431}\right)\\110^{- n} \left(\frac{0^{n}}{11} + \frac{110^{n}}{184756} + \frac{30 \cdot 12^{n}}{143} + \frac{5 \cdot 2^{n}}{22} + \frac{18 \cdot 20^{n}}{143} + \frac{3 \cdot 30^{n}}{52} + \frac{15 \cdot 42^{n}}{748} + \frac{25 \cdot 56^{n}}{4862} + \frac{75 \cdot 6^{n}}{286} + \frac{5 \cdot 72^{n}}{5434} + \frac{90^{n}}{9724}\right)\end{matrix}\right]
```

# 確認：確率の和は1か？

念のため，確率の和が1になっていることを確認しておきましょう。

### input

```python
sum((p[k,0] for k in range(11)))
```

### output

```math
110^{- n} \left(- \frac{252 \cdot 0^{n}}{11} + \frac{15876 \cdot 110^{n}}{46189} - \frac{4536 \cdot 20^{n}}{143} + \frac{2520 \cdot 42^{n}}{187} + \frac{6300 \cdot 6^{n}}{143} - \frac{8820 \cdot 72^{n}}{2717}\right) + 110^{- n} \left(- \frac{120 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} - \frac{2760 \cdot 12^{n}}{143} + \frac{120 \cdot 2^{n}}{11} + \frac{360 \cdot 20^{n}}{143} + \frac{120 \cdot 30^{n}}{13} - \frac{1080 \cdot 42^{n}}{187} - \frac{600 \cdot 56^{n}}{2431} + \frac{1800 \cdot 6^{n}}{143} + \frac{4080 \cdot 72^{n}}{2717} - \frac{1440 \cdot 90^{n}}{2431}\right) + 110^{- n} \left(- \frac{120 \cdot 0^{n}}{11} + \frac{3600 \cdot 110^{n}}{46189} + \frac{2760 \cdot 12^{n}}{143} - \frac{120 \cdot 2^{n}}{11} + \frac{360 \cdot 20^{n}}{143} - \frac{120 \cdot 30^{n}}{13} - \frac{1080 \cdot 42^{n}}{187} + \frac{600 \cdot 56^{n}}{2431} + \frac{1800 \cdot 6^{n}}{143} + \frac{4080 \cdot 72^{n}}{2717} + \frac{1440 \cdot 90^{n}}{2431}\right) + 110^{- n} \left(- \frac{10 \cdot 0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} - \frac{60 \cdot 12^{n}}{143} + \frac{20 \cdot 2^{n}}{11} + \frac{180 \cdot 20^{n}}{143} - \frac{15 \cdot 30^{n}}{13} + \frac{120 \cdot 42^{n}}{187} - \frac{575 \cdot 56^{n}}{2431} - \frac{150 \cdot 6^{n}}{143} + \frac{155 \cdot 72^{n}}{2717} - \frac{20 \cdot 90^{n}}{2431}\right) + 110^{- n} \left(- \frac{10 \cdot 0^{n}}{11} + \frac{25 \cdot 110^{n}}{46189} + \frac{60 \cdot 12^{n}}{143} - \frac{20 \cdot 2^{n}}{11} + \frac{180 \cdot 20^{n}}{143} + \frac{15 \cdot 30^{n}}{13} + \frac{120 \cdot 42^{n}}{187} + \frac{575 \cdot 56^{n}}{2431} - \frac{150 \cdot 6^{n}}{143} + \frac{155 \cdot 72^{n}}{2717} + \frac{20 \cdot 90^{n}}{2431}\right) + 110^{- n} \left(\frac{0^{n}}{11} + \frac{110^{n}}{184756} - \frac{30 \cdot 12^{n}}{143} - \frac{5 \cdot 2^{n}}{22} + \frac{18 \cdot 20^{n}}{143} - \frac{3 \cdot 30^{n}}{52} + \frac{15 \cdot 42^{n}}{748} - \frac{25 \cdot 56^{n}}{4862} + \frac{75 \cdot 6^{n}}{286} + \frac{5 \cdot 72^{n}}{5434} - \frac{90^{n}}{9724}\right) + 110^{- n} \left(\frac{0^{n}}{11} + \frac{110^{n}}{184756} + \frac{30 \cdot 12^{n}}{143} + \frac{5 \cdot 2^{n}}{22} + \frac{18 \cdot 20^{n}}{143} + \frac{3 \cdot 30^{n}}{52} + \frac{15 \cdot 42^{n}}{748} + \frac{25 \cdot 56^{n}}{4862} + \frac{75 \cdot 6^{n}}{286} + \frac{5 \cdot 72^{n}}{5434} + \frac{90^{n}}{9724}\right) + 110^{- n} \left(\frac{45 \cdot 0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} - \frac{90 \cdot 12^{n}}{13} + \frac{135 \cdot 2^{n}}{22} - \frac{810 \cdot 20^{n}}{143} - \frac{45 \cdot 30^{n}}{52} + \frac{1305 \cdot 42^{n}}{748} + \frac{675 \cdot 56^{n}}{442} - \frac{225 \cdot 6^{n}}{286} + \frac{3285 \cdot 72^{n}}{5434} + \frac{1215 \cdot 90^{n}}{9724}\right) + 110^{- n} \left(\frac{45 \cdot 0^{n}}{11} + \frac{2025 \cdot 110^{n}}{184756} + \frac{90 \cdot 12^{n}}{13} - \frac{135 \cdot 2^{n}}{22} - \frac{810 \cdot 20^{n}}{143} + \frac{45 \cdot 30^{n}}{52} + \frac{1305 \cdot 42^{n}}{748} - \frac{675 \cdot 56^{n}}{442} - \frac{225 \cdot 6^{n}}{286} + \frac{3285 \cdot 72^{n}}{5434} - \frac{1215 \cdot 90^{n}}{9724}\right) + 110^{- n} \left(\frac{210 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} - \frac{2940 \cdot 12^{n}}{143} + \frac{105 \cdot 2^{n}}{11} + \frac{2520 \cdot 20^{n}}{143} + \frac{210 \cdot 30^{n}}{13} - \frac{630 \cdot 42^{n}}{187} - \frac{14700 \cdot 56^{n}}{2431} - \frac{4725 \cdot 6^{n}}{143} - \frac{1470 \cdot 72^{n}}{2717} + \frac{2205 \cdot 90^{n}}{2431}\right) + 110^{- n} \left(\frac{210 \cdot 0^{n}}{11} + \frac{11025 \cdot 110^{n}}{46189} + \frac{2940 \cdot 12^{n}}{143} - \frac{105 \cdot 2^{n}}{11} + \frac{2520 \cdot 20^{n}}{143} - \frac{210 \cdot 30^{n}}{13} - \frac{630 \cdot 42^{n}}{187} + \frac{14700 \cdot 56^{n}}{2431} - \frac{4725 \cdot 6^{n}}{143} - \frac{1470 \cdot 72^{n}}{2717} - \frac{2205 \cdot 90^{n}}{2431}\right)
```

一見，訳の分からない結果になってしまいましたが，これは数式が十分に簡約化されていないからです。`sympy.simplify()` によって簡約化しましょう。

```python
sympy.simplify(sum((p[k,0] for k in range(11)))) # => 1
```

というわけで，正しく「確率の和が1」になっていることが確認できました。


# 当初の問題

## 問題1. 十分回数操作した後の確率分布

$n\to\infty$のときの確率分布の極限を求めてみます。

### input

```python
infty = sympy.oo
q = sympy.Matrix([sympy.limit(p[k,0], n, infty) for k in range(11)]) # p[k,0] の極限を並べたベクトル q を生成
display(q)
```

### output

```math
\left[\begin{matrix}\frac{1}{184756}\\\frac{25}{46189}\\\frac{2025}{184756}\\\frac{3600}{46189}\\\frac{11025}{46189}\\\frac{15876}{46189}\\\frac{11025}{46189}\\\frac{3600}{46189}\\\frac{2025}{184756}\\\frac{25}{46189}\\\frac{1}{184756}\end{matrix}\right]
```

これも和が1になっていることを確認しておきます。

```python
sum((q[k,0] for k in range(11))) # => 1
```

確かに和が1になっています。

小数表示してみます。

### input

```python
display(sympy.Matrix([q[k,0].evalf(6) for k in range(11)]))
```

### output

```math
\left[\begin{matrix}5.41254 \cdot 10^{-6}\\0.000541254\\0.0109604\\0.0779406\\0.238693\\0.343718\\0.238693\\0.0779406\\0.0109604\\0.000541254\\5.41254 \cdot 10^{-6}\end{matrix}\right]
```

清水さんの[Juliaによる数値シミュレーション結果](https://zenn.dev/dannchu/articles/db5f441c16bfa4)とかなり近くなっていますね！


## 問題2. 十分回数操作した後に袋Aから白玉を引く確率

「$n$回の操作が完了した後に，袋Aから白玉を引く確率」は，

```math
\sum_{k=0}^{10} \frac{k}{10}p_{n,k}
```

で表されます。これを$n$の式で表すと次のようになります。

### input

```python
sympy.simplify(sum((k*p[k,0]/10 for k in range(11))))
```

### output

```math
\frac{110^{- n} \left(110^{n} + 90^{n}\right)}{2}
```

つまり，この確率は

```math
\frac{1}{2}\left(1+\left(\frac{9}{11}\right)^n\right)
```

と表されることになります。初期値が「袋Aが白玉10個全部」から始まっているので，常にこの確率は $\frac{1}{2}$ を上回りつつも，$n\to\infty$ の極限においてそれが $\frac{1}{2}$ に近づいてゆくというのは，妥当な結果ですね。


# 問題2を純理論的に解く

問題2，すなわち「$n$回の操作が完了した後に袋Aから白玉を引く確率」だけであれば，sympy による対角化を使わずに，漸化式のみで純理論的に求められます。

「$n$回の操作が完了した後に袋Aから白玉を引く確率」を $q_n$ とおくと，

```math
q_n = \sum_{k=0}^{10} \frac{k}{10}p_{n,k}
```

と表されます。$p_{n+1,k}$ の漸化式

```math
p_{n+1,k} = \frac{(11-k)^2}{110}p_{n,k-1}+\frac{k(11-k)+(10-k)(k+1)}{110}p_{n,k} + \frac{(k+1)^2}{110}p_{n,k+1}
```

を用いて，$q_n$ の漸化式を作りましょう。

```math
\begin{align*}
q_{n+1} 
&= \sum_{k=0}^{10} \frac{k}{10}p_{n+1,k} \\
&= \sum_{k=1}^{10} \frac{k}{10} \cdot \frac{(11-k)^2}{110}p_{n,k-1} \\
&  \qquad + \sum_{k=0}^{10} \frac{k}{10} \cdot \frac{k(11-k)+(10-k)(k+1)}{110}p_{n,k} \\
&  \qquad\qquad + \sum_{k=0}^9 \frac{k}{10} \cdot \frac{(k+1)^2}{110}p_{n,k+1}\\
&= \sum_{k=0}^{9} \frac{k+1}{10} \cdot \frac{(10-k)^2}{110}p_{n,k} \\
&  \qquad + \sum_{k=0}^{10} \frac{k}{10} \cdot \frac{k(11-k)+(10-k)(k+1)}{110}p_{n,k} \\
&  \qquad\qquad + \sum_{k=1}^{10} \frac{k-1}{10} \cdot \frac{k^2}{110}p_{n,k}\\
&= \sum_{k=0}^{10} \frac{k+1}{10} \cdot \frac{(10-k)^2}{110}p_{n,k} \\
&  \qquad + \sum_{k=0}^{10} \frac{k}{10} \cdot \frac{k(11-k)+(10-k)(k+1)}{110}p_{n,k} \\
&  \qquad\qquad + \sum_{k=0}^{10} \frac{k-1}{10} \cdot \frac{k^2}{110}p_{n,k}\\
&= \frac{1}{110}\sum_{k=0}^{10} (9k+10) p_{n,k} \\
&= \frac{9}{110}\sum_{k=0}^{10} k p_{n,k} + \frac{1}{11} \sum_{k=0}^n p_{n,k} \\
&= \frac{9}{11}q_n + \frac{1}{11} 
\end{align*}
```

ゆえに，この漸化式は

```math
q_{n+1} -\frac{1}{2} = \frac{9}{11}\left(q_n -\frac{1}{2}\right)
```

と変形できるので，$q_0=1$ であることから

```math
\begin{align*}
q_n 
&= \frac{1}{2} + \left(\frac{9}{11}\right)^{n}\left(q_0 -\frac{1}{2}\right)\\
&= \frac{1}{2} + \frac{1}{2}\left(\frac{9}{11}\right)^{n}
\end{align*}
```

となり，sympy を用いて求めた結果と見事に一致しました！