倍數無關集

一個 集合 的 正整數 是倍數無關的，如果對於任何整數 , 該集合 (或者等價地， 意味著 )。 例如，在 的子集中，集合 , , , , , 和 是倍數無關的，而 和 不是。

集合 的倍數無關子集數量 可以使用 和以下 遞推關係 計算

(1)

其中 是 斐波那契數, 1, 1, 2, 3, 5, 8, ... (OEIS A000045), 並且 是 二進位制進位序列，表示 的 二進位制 表示中末尾 0 的數量。 對於 , 2, ..., 由 0, 1, 0, 2, 0, 1, 3, 0, 1, ... (OEIS A007814) 給出，而相應的 是 2, 3, 6, 10, 20, 30, 60, 96, 192, ... (OEIS A050291)。

定義

(2)

其中 是 的 基數 (成員數量)。 那麼對於 , 2, ..., 由 1, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9, 10, ... (OEIS A050292) 給出。 的顯式公式由下式給出

(3)

其中

(4)

如果 的 特徵函式 (如上定義)，並且 的前幾個值是 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, ... (OEIS A035263)。 的一個簡單 遞推關係 由下式給出

(5)

其中 (Wang 1989)，其中 是 向下取整函式， 是 向上取整函式。 的一個漸近公式由下式給出

(6)

(Wang 1989)。