2020年3月16日月曜日

200316

Crystal


A332954(3)

https://math.stackexchange.com/questions/3572301/why-are-the-numbers-of-two-different-permutations-the-same
上記の回答にあるように、a からb への全単射が存在する。
このことを確認してみた。

def a(k, m, n)
  a = (m..m + n - 1).map{|i| [i]}
  len = 1
  while len < n
    b = Array(Array(Int32)).new
    a.each{|c|
      (m..m + n - 1).each{|num|
        if !c.includes?(num)
          i = c.clone + [num]
          if (i[-2] * (len + k + 1)) > (i[-1] * (len + k))
            b << i
          end
        end
      }
    }
    a = b
    len += 1
  end
  a
end

def b(k, m, n)
  a = (m..m + n - 1).map{|i| [i]}
  len = 1
  while len < n
    b = Array(Array(Int32)).new
    a.each{|c|
      (m..m + n - 1).each{|num|
        if !c.includes?(num)
          i = c.clone + [num]
          if (i[-2] * (len + k + 1)) >= (i[-1] * (len + k))
            b << i
          end
        end
      }
    }
    a = b
    len += 1
  end
  # bijection
  a.map{|c| c.map{|i| i + 1} + [m]}
end

# 具体例も出力
(0..5).each{|i|
  (0..i + 1).each{|j|
    p a = (2..5).map{|k| a(i, j, k)}
    p b = (1..4).map{|k| b(i, j, k)}
    p [i, j, a == b]
  }
}

(0..13).each{|i|
  (0..i + 1).each{|j|
    a = (2..16).map{|k| a(i, j, k)}
    b = (1..15).map{|k| b(i, j, k)}
    p [i, j, a == b]
  }
}

出力結果
[[[1, 0]], [[2, 1, 0]], [[2, 3, 1, 0], [3, 2, 1, 0]], [[2, 3, 4, 1, 0], [3, 4, 2, 1, 0], [4, 3, 2, 1, 0]]]
[[[1, 0]], [[2, 1, 0]], [[2, 3, 1, 0], [3, 2, 1, 0]], [[2, 3, 4, 1, 0], [3, 4, 2, 1, 0], [4, 3, 2, 1, 0]]]
[0, 0, true]
[[[2, 1]], [[2, 3, 1], [3, 2, 1]], [[2, 3, 4, 1], [3, 4, 2, 1], [4, 3, 2, 1]], [[2, 3, 4, 5, 1], [3, 4, 5, 2, 1], [3, 5, 4, 2, 1], [4, 5, 3, 2, 1], [5, 3, 4, 2, 1], [5, 4, 3, 2, 1]]]
[[[2, 1]], [[2, 3, 1], [3, 2, 1]], [[2, 3, 4, 1], [3, 4, 2, 1], [4, 3, 2, 1]], [[2, 3, 4, 5, 1], [3, 4, 5, 2, 1], [3, 5, 4, 2, 1], [4, 5, 3, 2, 1], [5, 3, 4, 2, 1], [5, 4, 3, 2, 1]]]
[0, 1, true]
[[[1, 0]], [[2, 1, 0]], [[3, 2, 1, 0]], [[3, 4, 2, 1, 0], [4, 3, 2, 1, 0]]]
[[[1, 0]], [[2, 1, 0]], [[3, 2, 1, 0]], [[3, 4, 2, 1, 0], [4, 3, 2, 1, 0]]]
[1, 0, true]
[[[2, 1]], [[3, 2, 1]], [[3, 4, 2, 1], [4, 3, 2, 1]], [[3, 4, 5, 2, 1], [4, 5, 3, 2, 1], [5, 4, 3, 2, 1]]]
[[[2, 1]], [[3, 2, 1]], [[3, 4, 2, 1], [4, 3, 2, 1]], [[3, 4, 5, 2, 1], [4, 5, 3, 2, 1], [5, 4, 3, 2, 1]]]
[1, 1, true]
[[[3, 2]], [[3, 4, 2], [4, 3, 2]], [[3, 4, 5, 2], [4, 5, 3, 2], [5, 4, 3, 2]], [[3, 4, 5, 6, 2], [4, 5, 6, 3, 2], [5, 6, 4, 3, 2], [6, 4, 5, 3, 2], [6, 5, 4, 3, 2]]]
[[[3, 2]], [[3, 4, 2], [4, 3, 2]], [[3, 4, 5, 2], [4, 5, 3, 2], [5, 4, 3, 2]], [[3, 4, 5, 6, 2], [4, 5, 6, 3, 2], [5, 6, 4, 3, 2], [6, 4, 5, 3, 2], [6, 5, 4, 3, 2]]]
[1, 2, true]
[[[1, 0]], [[2, 1, 0]], [[3, 2, 1, 0]], [[4, 3, 2, 1, 0]]]
[[[1, 0]], [[2, 1, 0]], [[3, 2, 1, 0]], [[4, 3, 2, 1, 0]]]
[2, 0, true]
[[[2, 1]], [[3, 2, 1]], [[4, 3, 2, 1]], [[4, 5, 3, 2, 1], [5, 4, 3, 2, 1]]]
[[[2, 1]], [[3, 2, 1]], [[4, 3, 2, 1]], [[4, 5, 3, 2, 1], [5, 4, 3, 2, 1]]]
[2, 1, true]
[[[3, 2]], [[4, 3, 2]], [[4, 5, 3, 2], [5, 4, 3, 2]], [[4, 5, 6, 3, 2], [5, 6, 4, 3, 2], [6, 5, 4, 3, 2]]]
[[[3, 2]], [[4, 3, 2]], [[4, 5, 3, 2], [5, 4, 3, 2]], [[4, 5, 6, 3, 2], [5, 6, 4, 3, 2], [6, 5, 4, 3, 2]]]
[2, 2, true]
[[[4, 3]], [[4, 5, 3], [5, 4, 3]], [[4, 5, 6, 3], [5, 6, 4, 3], [6, 5, 4, 3]], [[4, 5, 6, 7, 3], [5, 6, 7, 4, 3], [6, 7, 5, 4, 3], [7, 5, 6, 4, 3], [7, 6, 5, 4, 3]]]
[[[4, 3]], [[4, 5, 3], [5, 4, 3]], [[4, 5, 6, 3], [5, 6, 4, 3], [6, 5, 4, 3]], [[4, 5, 6, 7, 3], [5, 6, 7, 4, 3], [6, 7, 5, 4, 3], [7, 5, 6, 4, 3], [7, 6, 5, 4, 3]]]
[2, 3, true]
[[[1, 0]], [[2, 1, 0]], [[3, 2, 1, 0]], [[4, 3, 2, 1, 0]]]
[[[1, 0]], [[2, 1, 0]], [[3, 2, 1, 0]], [[4, 3, 2, 1, 0]]]
[3, 0, true]
[[[2, 1]], [[3, 2, 1]], [[4, 3, 2, 1]], [[5, 4, 3, 2, 1]]]
[[[2, 1]], [[3, 2, 1]], [[4, 3, 2, 1]], [[5, 4, 3, 2, 1]]]
[3, 1, true]
[[[3, 2]], [[4, 3, 2]], [[5, 4, 3, 2]], [[5, 6, 4, 3, 2], [6, 5, 4, 3, 2]]]
[[[3, 2]], [[4, 3, 2]], [[5, 4, 3, 2]], [[5, 6, 4, 3, 2], [6, 5, 4, 3, 2]]]
[3, 2, true]
[[[4, 3]], [[5, 4, 3]], [[5, 6, 4, 3], [6, 5, 4, 3]], [[5, 6, 7, 4, 3], [6, 7, 5, 4, 3], [7, 6, 5, 4, 3]]]
[[[4, 3]], [[5, 4, 3]], [[5, 6, 4, 3], [6, 5, 4, 3]], [[5, 6, 7, 4, 3], [6, 7, 5, 4, 3], [7, 6, 5, 4, 3]]]
[3, 3, true]
[[[5, 4]], [[5, 6, 4], [6, 5, 4]], [[5, 6, 7, 4], [6, 7, 5, 4], [7, 6, 5, 4]], [[5, 6, 7, 8, 4], [6, 7, 8, 5, 4], [7, 8, 6, 5, 4], [8, 6, 7, 5, 4], [8, 7, 6, 5, 4]]]
[[[5, 4]], [[5, 6, 4], [6, 5, 4]], [[5, 6, 7, 4], [6, 7, 5, 4], [7, 6, 5, 4]], [[5, 6, 7, 8, 4], [6, 7, 8, 5, 4], [7, 8, 6, 5, 4], [8, 6, 7, 5, 4], [8, 7, 6, 5, 4]]]
[3, 4, true]
[[[1, 0]], [[2, 1, 0]], [[3, 2, 1, 0]], [[4, 3, 2, 1, 0]]]
[[[1, 0]], [[2, 1, 0]], [[3, 2, 1, 0]], [[4, 3, 2, 1, 0]]]
[4, 0, true]
[[[2, 1]], [[3, 2, 1]], [[4, 3, 2, 1]], [[5, 4, 3, 2, 1]]]
[[[2, 1]], [[3, 2, 1]], [[4, 3, 2, 1]], [[5, 4, 3, 2, 1]]]
[4, 1, true]
[[[3, 2]], [[4, 3, 2]], [[5, 4, 3, 2]], [[6, 5, 4, 3, 2]]]
[[[3, 2]], [[4, 3, 2]], [[5, 4, 3, 2]], [[6, 5, 4, 3, 2]]]
[4, 2, true]
[[[4, 3]], [[5, 4, 3]], [[6, 5, 4, 3]], [[6, 7, 5, 4, 3], [7, 6, 5, 4, 3]]]
[[[4, 3]], [[5, 4, 3]], [[6, 5, 4, 3]], [[6, 7, 5, 4, 3], [7, 6, 5, 4, 3]]]
[4, 3, true]
[[[5, 4]], [[6, 5, 4]], [[6, 7, 5, 4], [7, 6, 5, 4]], [[6, 7, 8, 5, 4], [7, 8, 6, 5, 4], [8, 7, 6, 5, 4]]]
[[[5, 4]], [[6, 5, 4]], [[6, 7, 5, 4], [7, 6, 5, 4]], [[6, 7, 8, 5, 4], [7, 8, 6, 5, 4], [8, 7, 6, 5, 4]]]
[4, 4, true]
[[[6, 5]], [[6, 7, 5], [7, 6, 5]], [[6, 7, 8, 5], [7, 8, 6, 5], [8, 7, 6, 5]], [[6, 7, 8, 9, 5], [7, 8, 9, 6, 5], [8, 9, 7, 6, 5], [9, 7, 8, 6, 5], [9, 8, 7, 6, 5]]]
[[[6, 5]], [[6, 7, 5], [7, 6, 5]], [[6, 7, 8, 5], [7, 8, 6, 5], [8, 7, 6, 5]], [[6, 7, 8, 9, 5], [7, 8, 9, 6, 5], [8, 9, 7, 6, 5], [9, 7, 8, 6, 5], [9, 8, 7, 6, 5]]]
[4, 5, true]
[[[1, 0]], [[2, 1, 0]], [[3, 2, 1, 0]], [[4, 3, 2, 1, 0]]]
[[[1, 0]], [[2, 1, 0]], [[3, 2, 1, 0]], [[4, 3, 2, 1, 0]]]
[5, 0, true]
[[[2, 1]], [[3, 2, 1]], [[4, 3, 2, 1]], [[5, 4, 3, 2, 1]]]
[[[2, 1]], [[3, 2, 1]], [[4, 3, 2, 1]], [[5, 4, 3, 2, 1]]]
[5, 1, true]
[[[3, 2]], [[4, 3, 2]], [[5, 4, 3, 2]], [[6, 5, 4, 3, 2]]]
[[[3, 2]], [[4, 3, 2]], [[5, 4, 3, 2]], [[6, 5, 4, 3, 2]]]
[5, 2, true]
[[[4, 3]], [[5, 4, 3]], [[6, 5, 4, 3]], [[7, 6, 5, 4, 3]]]
[[[4, 3]], [[5, 4, 3]], [[6, 5, 4, 3]], [[7, 6, 5, 4, 3]]]
[5, 3, true]
[[[5, 4]], [[6, 5, 4]], [[7, 6, 5, 4]], [[7, 8, 6, 5, 4], [8, 7, 6, 5, 4]]]
[[[5, 4]], [[6, 5, 4]], [[7, 6, 5, 4]], [[7, 8, 6, 5, 4], [8, 7, 6, 5, 4]]]
[5, 4, true]
[[[6, 5]], [[7, 6, 5]], [[7, 8, 6, 5], [8, 7, 6, 5]], [[7, 8, 9, 6, 5], [8, 9, 7, 6, 5], [9, 8, 7, 6, 5]]]
[[[6, 5]], [[7, 6, 5]], [[7, 8, 6, 5], [8, 7, 6, 5]], [[7, 8, 9, 6, 5], [8, 9, 7, 6, 5], [9, 8, 7, 6, 5]]]
[5, 5, true]
[[[7, 6]], [[7, 8, 6], [8, 7, 6]], [[7, 8, 9, 6], [8, 9, 7, 6], [9, 8, 7, 6]], [[7, 8, 9, 10, 6], [8, 9, 10, 7, 6], [9, 10, 8, 7, 6], [10, 8, 9, 7, 6], [10, 9, 8, 7, 6]]]
[[[7, 6]], [[7, 8, 6], [8, 7, 6]], [[7, 8, 9, 6], [8, 9, 7, 6], [9, 8, 7, 6]], [[7, 8, 9, 10, 6], [8, 9, 10, 7, 6], [9, 10, 8, 7, 6], [10, 8, 9, 7, 6], [10, 9, 8, 7, 6]]]
[5, 6, true]
[0, 0, true]
[0, 1, true]
[1, 0, true]
[1, 1, true]
[1, 2, true]
[2, 0, true]
[2, 1, true]
[2, 2, true]
[2, 3, true]
[3, 0, true]
[3, 1, true]
[3, 2, true]
[3, 3, true]
[3, 4, true]
[4, 0, true]
[4, 1, true]
[4, 2, true]
[4, 3, true]
[4, 4, true]
[4, 5, true]
[5, 0, true]
[5, 1, true]
[5, 2, true]
[5, 3, true]
[5, 4, true]
[5, 5, true]
[5, 6, true]
[6, 0, true]
[6, 1, true]
[6, 2, true]
[6, 3, true]
[6, 4, true]
[6, 5, true]
[6, 6, true]
[6, 7, true]
[7, 0, true]
[7, 1, true]
[7, 2, true]
[7, 3, true]
[7, 4, true]
[7, 5, true]
[7, 6, true]
[7, 7, true]
[7, 8, true]
[8, 0, true]
[8, 1, true]
[8, 2, true]
[8, 3, true]
[8, 4, true]
[8, 5, true]
[8, 6, true]
[8, 7, true]
[8, 8, true]
[8, 9, true]
[9, 0, true]
[9, 1, true]
[9, 2, true]
[9, 3, true]
[9, 4, true]
[9, 5, true]
[9, 6, true]
[9, 7, true]
[9, 8, true]
[9, 9, true]
[9, 10, true]
[10, 0, true]
[10, 1, true]
[10, 2, true]
[10, 3, true]
[10, 4, true]
[10, 5, true]
[10, 6, true]
[10, 7, true]
[10, 8, true]
[10, 9, true]
[10, 10, true]
[10, 11, true]
[11, 0, true]
[11, 1, true]
[11, 2, true]
[11, 3, true]
[11, 4, true]
[11, 5, true]
[11, 6, true]
[11, 7, true]
[11, 8, true]
[11, 9, true]
[11, 10, true]
[11, 11, true]
[11, 12, true]
[12, 0, true]
[12, 1, true]
[12, 2, true]
[12, 3, true]
[12, 4, true]
[12, 5, true]
[12, 6, true]
[12, 7, true]
[12, 8, true]
[12, 9, true]
[12, 10, true]
[12, 11, true]
[12, 12, true]
[12, 13, true]
[13, 0, true]
[13, 1, true]
[13, 2, true]
[13, 3, true]
[13, 4, true]
[13, 5, true]
[13, 6, true]
[13, 7, true]
[13, 8, true]
[13, 9, true]
[13, 10, true]
[13, 11, true]
[13, 12, true]
[13, 13, true]
[13, 14, true]
投稿者 時刻:
ラベル:

0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。

登録: コメントの投稿 (Atom)