ryamadaのコンピュータ・数学メモ

Primitive

数学

こちらでBDDのことをやっていて、Primitiveな配列というものが出てきた
ある長さLの配列がn個(複数)あって、それらをタンデムにつないで、長さが２倍の配列(長さ2L)を作るときのこと
連結するにあたって、同じものを組み合わせないで作る配列が「長さ2LのPrimitiveな列」というのだそうだ
- n個のものをタンデムにつなぐ場合の数は $n\times n$
- ただし、同じものをタンデムにつないではいけないので、 $n \times n - n = n(n-1)$
- $n=2^{2^{k-1}}$ のときは $2^{2^{k-1}}(2^{2^{k-1}}-1)=2^{2*2^{k-1}}-2^{2^{k-1}}=2^{2^k}-2^{2^{k-1}}$
ここで言う"Primitive"というのは、「より小さいものを使って構成することができない」という意味だろう
そんな意味で"Primitive sequence"というものもあるそうだ(こちら)
- $\{1,2,...,n\}$ のべき集合の要素のうち、相互に「よりちいさいものの組み合わせでは表せないような要素のセット」のことだという
"Prime numbers"は素数だが、これも、積について、「よりちいさいものの組合せでは表せないような要素」という意味