44109 「遞降階乘多項式」除以 $x^2-x-1$ 的餘式與OEIS A265165
「遞降階乘多項式」除以 $x^2-x-1$ 的餘式與OEIS A265165

一、序言

首先, 定義 $x^{(n)}=x(x-1)\cdots (x-n+1)$, 稱為「$x$ 的 $n$ 次遞降階乘多項式」, 此種多項式, 與第二類 Stirling 數, 有密切的關聯 (參考資料 )。

筆者在探索費氏數列與第二類 Stirling 數的過程中, 遇到了一個問題 : 「$x(x-1)\cdots(x-n+1)$ 除以 $x^2-x-1$ 的餘式為何?」注意到其中的 $x^2-x-1$, 正是費氏數列的特徵多項式。

具體而言, 設 $x(x-1)\cdots(x-n+1)$ 除以 $x^2-x-1$ 的餘式為 $A_nx+B_n$, 商式為 $Q(x)$, 亦即 $x(x-1)\cdots(x-n+1)=(x^2-x-1)\cdot Q(x)+A_nx+B_n$, 則 $A_n$ 與 $B_n$ 的表達式為何, 又有什麼樣的規律呢?

回溯既往, 自多項式除法出現以來, 人們做過無數次的多項式除法, 早已發展出一般性的結論, 即所謂的「餘式定理」, 出現在每一位高中學生的數學課本上。 但是相對地, 作為一個特殊情形, 拿 $x(x-1)\cdots(x-n+1)$ 除以 $x^2-x-1$, 在筆者有限的見聞之中, 並沒有看過針對此特例量身打造的現成結論, 故藉此契機, 探索此一問題的答案。

另一方面, 拜科技進步之賜, 網路上有所謂的 OEIS, 即 On-line Encyclopedia of Integer Sequences (線上整數數列百科) , 在研究數列時, 只要輸入數列的前幾項, 就能查詢是否為已知的數列, 若為已知的數列, 還可查到其來源的論文或期刊所在, 是一個相當有用的工具。

在試算了數列 $A_n$ 與 $B_n$ 的前幾項之後, 出人意料之外的是, 數列 $B_n$ 與編號為「OEIS A265165」的數列, 「幾乎」一模一樣 : 將正負交替出現的 $B_n$ 取絕對值之後, 即可得 OEIS A265165。但是查詢OEIS A265165的來龍去脈, 查到的卻是 , 看起來和筆者的問題, 可說是風馬牛不相及。 這其中的奧妙, 引起了筆者的高度興趣。 在考察兩數列的遞迴關係之後, 證明了一個結論 : 設 OEIS A265165 為數列 $\langle b_n\rangle$, 則有 $B_n=(-1)^n\cdot b_n$。

二、探索過程

(一)多項式除法求餘式 :

先試算 $B_n$ 的前幾項, 透過多項式除法, 可得 : \begin{eqnarray*} x^{(1)}&=&x=(x^2-x-1)\cdot 0+(x+0)\Rightarrow A_1=1,\ B_1=0,\\ x^{(2)}&=&x^2-x=(x^2-x-1)\cdot 1+(0x+1)\Rightarrow A_2=0,\ B_2=1,\\ x^{(3)}&=&x^3-3x^2+2x=(x^2-x-1)\cdot (x-2)+(x-2)\Rightarrow A_3=1,\ B_3=-2,\\ x^{(4)}&=&x^4-6x^3+11x^2-6x\\ &=&(x^2-x-1)\cdot (x^2-5x+7)+(-4x+7)\Rightarrow A_4=-4,\ B_4=7,\\ x^{(5)}&=&x^5-10x^4+35x^3-50x^2+24x\\ &=&(x^2-x-1)\cdot (x^3-9x^2+27x-32)+(19x-32)\Rightarrow A_5=19,\ B_5=-32,\\ x^{(6)}&=&x^6-15x^5+85x^4-225x^3+274x^2-120x\\ &=&(x^2-x-1)\cdot (x^4-14x^3+72x^2-167x+179)+(-108x+179)\\ &&\Rightarrow A_6=-108,\ B_6=179. \end{eqnarray*} 至此, 可得 $B_n$ 的前幾項為 :

$B_1=0,\ B_2=1,\ B_3=-2,\ B_4=7,\ B_5=-32,\ B_6=179.$

(二)OEIS A265165 :

透過 OEIS, 獲知參考資料 , 查閱之後, 在該文的第 13 頁, 有數列 $\langle b_n\rangle$, 其中有一段說明 : 「The first values of $b_n$ (the number of basis permutations of length $n$) are 1, 2, 7, 32, 179, 1182, 8993, 77440 for $2\le n\le 9$. We added this sequence to the On-line Encyclopedia of Integer Sequences (hereafter abbreviated OEIS),see Sloane and collaborators(2016)... 」

無巧不成書 : 將 $x(x-1)\cdots(x-n+1)$ 除以 $x^2-x-1$ 得餘式 $A_nx+B_n$, 將 $B_n$ 的前幾項取絕對值之後, 所得數列正是 OEIS A265165 的前幾項, 這是怎麼一回事呢?

(三)連結 :

的第 11 頁, 有 $\langle b_n\rangle$ 的遞迴關係式 : 「$\cdots$ Equivalently, its coefficients $b_n$ satisfy the recurrence $b_{n+2}=2nb_{n+1}+(1+n-n^2)b_n$, $b_0=b_1=0$, $b_2=1$」 於是, 試著考察 $B_n$ 的遞迴關係 :

設 $x(x-1)\cdots(x-n+1)$ 除以 $x^2-x-1$ 的餘式為 $A_nx+B_n$, 商式為 $Q(x)$, 則有 \begin{eqnarray*} &&x(x-1)\cdots(x-n+1)=(x^2-x-1)\cdot Q(x)+A_nx+B_n\\ &\Rightarrow&x(x\!-\!1)\!\cdots\!(x\!-\!n\!+\!1)(x\!-\!n)\!=\!(x^2\!-\!x\!-\!1)\!\cdot\! Q(x)\!\cdot\! (x\!-\!n)\!+\!(A_nx\!+\!B_n)(x\!-\!n). \end{eqnarray*} 注意到 \begin{eqnarray*} (A_nx+B_n)(x-n)&=&A_nx^2+(B_n-nA_n)x-nB_n\\ &=&A_n(x^2-x-1)+[B_n+(1-n)A_n]x+(A_n-nB_n), \end{eqnarray*} 於是可得 \begin{eqnarray*} x^{(n+1)}&=&x(x-1)\cdots(x-n+1)(x-n)\\ &=&(x^2-x-1)\cdot Q(x)\cdot (x-n)+A_n(x^2-x-1)+[B_n+(1-n)A_n]x\\ &&+(A_n-nB_n)\\ &=&(x^2-x-1)\cdot [Q(x)\cdot (x-n)+A_n]+[(1-n)A_n+B_n]x+(A_n-nB_n), \end{eqnarray*} 由此可得 \begin{eqnarray} A_{n+1}&=&(1-n)A_n+B_n,\label{1}\\ {\hbox{與}} B_{n+1}&=&A_n-nB_n,\label{2} \end{eqnarray} 由 \eqref{2} 得 $$A_n=B_{n+1}+nB_n\ \Rightarrow\ A_{n+1}=B_{n+2}+(n+1)B_{n+1}.$$ 於是式 \eqref{1} 成為 : \begin{eqnarray*} &&B_{n+2}+(n+1)B_{n+1}=(1-n)(B_{n+1}+nB_n)+B_n\\ &\Rightarrow&B_{n+2}+2nB_{n+1}+(n^2-n-1)B_n=0. \end{eqnarray*} 令 $B_n=(-1)^n\cdot c_n$, 得 \begin{eqnarray*} &&(-1)^{n+2}c_{n+2}+2n(-1)^{n+1}c_{n+1}+(n^2-n-1)(-1)^nc_n=0\\ &\Rightarrow&c_{n+2}-2nc_{n+1}+(n^2-n-1)c_n=0, \end{eqnarray*} 此式與數列 OEIS A265165 (即 $b_n$) 所滿足的二階遞迴式完全相同, 再注意到 $c_1=-B_1=0=b_1$ 與 $c_2=B_2=1=b_2$, 即可得數列 $c_n$ 與數列 $b_n$ 完全相同, 於是有 $c_n=b_n$, 所以可得 $B_n=(-1)^n\cdot c_n=(-1)^n\cdot b_n$, 至此, 證明了 $B_n=(-1)^n\cdot b_n$, 這說明了 $B_n$ 與 $b_n$ 兩數列的關聯性。

三、結語

本文對 $B_n$ 與 $b_n$ 兩數列的關聯性, 有了一點初步的認識, 但是關於此兩數列的對應以及背景, 仍有「見樹不見林」之感。 此外, 數列 $A_n$ 的規律, 也有待探索。特由此文拋磚引玉, 就教於各位賢明的讀者。

參考資料

陳建燁。 第二類 Stirling 數的完全齊次對稱多項式表示法(一) : 使用比較係數法。 高中數學學科中心電子報第 131 期, 2018 年 2 月, 1-4。 https://oeis.org (The On-line Encyclopedia of Integer Sequences, founded in 1964 by N.J.A. Sloane). Cyril Banderier, Jean-Luc Baril, Celine Moreira Dos Santos, Right-jumps & pattern avoiding permutations, Discrete Mathematics and Theoretical Computer Science, vol.18 : 2, 2017, 11-13.

---本文作者任教台北市立第一女子高級中學---