主題
Search

組合鎖


考慮一個組合鎖,它由 n 個按鈕組成,這些按鈕可以以任意組合方式按下(包括一次按下多個按鈕),但方式要使得每個數字恰好被按下一次。那麼,具有 n 個按鈕的可能的組合鎖的數量 a_n列表(即,有序集合)的數量給出,這些列表由 不相交非空 子集 組成,這些子集來自 集合 {1,2,...,n},並且每個數字恰好包含一次。例如,有兩個按鈕的組合鎖有三種可能的組合:{{1,2}}{{1},{2}}{{2},{1}}。類似地,有 13 種可能的三按鈕組合鎖:{{1,2,3}}{{1},{2,3}}{{2},{1,3}}{{3},{1,2}}{{1,2},{3}}{{1,3},{2}}{{2,3},{1}}{{1},{2},{3}}{{1},{3},{2}}{{2},{1},{3}}{{2},{3},{1}}{{3},{1},{2}}{{3},{2},{1}}

a_n 滿足 線性遞推方程

 a_n=sum_(i=0)^(n-1)(n; n-i)a_i,
(1)

其中 a_0=1。這也可以寫成

a_n=(d^n)/(dx^n)(1/(2-e^x))|_(x=0)
(2)
=1/2sum_(k=0)^(infty)(k^n)/(2^k),
(3)

其中使用了定義 0^0=1。此外,

a_n=sum_(k=1)^(n)<n; k-1>2^(n-k)
(4)
=sum_(k=1)^(n)<n; k-1>2^(k-1),
(5)

其中 <n; k>尤拉數。根據 第二類斯特林數 S(n,k)

 a_n=sum_(k=1)^nk!S(n,k).
(6)

a_n 也可以用閉合形式給出:

 a_n=1/2Li_(-n)(1/2),
(7)

其中 Li_n(z)多重對數函式a_n 的前幾個值,對於 n=1, 2, ... 是 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ... (OEIS A000670)。

數量

 b_n=(a_n)/(n!)
(8)

滿足不等式

 1/(2(ln2)^n)<=b_n<=1/((ln2)^n).
(9)

使用 探索

參考文獻

Sloane, N. J. A. 序列 A000670/M2952,出自“整數序列線上百科全書”。Velleman, D. J. 和 Call, G. S. “排列與組合鎖”。Math. Mag. 68, 243-253, 1995.

在 中被引用

組合鎖

請引用為

Weisstein, Eric W. “組合鎖”。來自 Web 資源。 https://mathworld.tw/CombinationLock.html

主題分類