Thế nào là hoán vị của một dãy số?

#1

Anh chị trong nhóm chỉ giúp em hiểu thế nào là hoán vị của một dãy số được không ạ :((
Lấy ví dụ như dãy “1 2 3” đi ạ
< Help me >

#2

Xét tập {1, 2, 3}
Nếu tạo 1 dãy từ tập này sẽ có nhiều cách tạo khác nhau.
VD: [1, 2, 3], [3, 1, 2]… Người ta gọi mỗi thứ tự đó là 1 hoán vị.

2 Likes
#3

Có cái này à?
Mình nhớ dãy số có thứ tự rồi mà, hoán vị gì nữa.

3 Likes
#4

có cách nào để xác định được một hoán vị tiếp theo đó ạ ??
e đọc trên google mà ko hiểu được :((

#5

chỉ cho 1 hoán vị thì không có cơ sở nào để xác định hoán vị nào là “tiếp theo”
Bạn cần định nghĩa mối tương quan giữa các hoán vị, mới biết “tiếp theo” là kiểu gì.
Ví dụ như định nghĩa thứ tự lớn nhỏ: [1, 2, 3] < [1, 3, 2] < [2, 1, 3]

p/s: mình không biết bạn đọc ở bài viết nào, nhưng bài toán nên là xét một tập S thay vì xét 1 hoán vị thì mới “make sense”

2 Likes
#6

Xét dãy (4, 2, 5, 3, 1):

  • Nhận thấy (5, 3, 1) là dãy con giảm dần cuối cùng
    • Số liền trước của (5, 3, 1) là 2
  • Tìm các số lớn hơn 2 trong (5, 3, 1) được { 3; 5 }
  • Chọn số nhỏ nhất trong tập là 3.
  • Đổi vị trí 2 và 3, được dãy (4, 3, 5, 2, 1)
  • Đảo ngược (5, 2, 1), được (4, 3, 1, 2, 5)

Tương tự:

  • (4, 3, 1, 2, 5) -> (4, 3, 1, 5, 2)
  • (4, 3, 1, 5, 2) -> (4, 3, 2, 5, 1) -> (4, 3, 2, 1, 5) // đổi 1 và 2
  • (4, 3, 2, 1, 5) -> (4, 3, 2, 5, 1)
  • (4, 3, 2, 5, 1) -> (4, 3, 5, 2, 1) -> (4, 3, 5, 1, 2) // đổi 2 và 5
  • (4, 3, 5, 1, 2) -> (4, 3, 5, 2, 1)
  • (4, 3, 5, 2, 1) -> (4, 5, 3, 2, 1) -> (4, 5, 1, 2, 3) // đổi 3 và 5
  • …
3 Likes
#7

Hoán vị của một tập n phần tử là chỉnh hợp không lặp chập k của n khi k=n.

1 Like
#8

Tóm tắt: Không có khái niệm hoán vị của một dãy số, chỉ có khái niệm hoán vị của một tập hợp.

Dãy số: (sequence)
Cho tập S, dãy số là 1 hàm từ tập số tự nhiên N vào tập S, hàm có tính chất song ánh (bijection)
Ví dụ:
Cho tập S = { 1, 3, 4, 5 } và hàm f: N -> S sao cho: f(1) = 5, f(2) = 1, f(3) = 4, f(4) = 3.
Khi đó hàm f là 1 dãy từ S, được viết dưới dạng (5, 1, 4, 3)

Hàm số khác g: N -> S sao cho: g(1) = 4, g(2) = 3, g(3) = 1, g(4) = 5.
Hàm g cũng là 1 dãy của S, được viết (4, 3, 1, 5)

Hoán vị: (permutation)
Cho tập S, hoán vị là 1 hàm từ tập S vào tập S, hàm có tính chất song ánh.
Ví dụ:
Cho tập S = { a, b, c, d } và hàm f: S -> S sao cho f(a) = b, f(b) = a, f( c ) = d, f(d) = c
Khi đó hàm f là 1 hoán vị của S.

Hàm số khác g: S -> S sao cho: g(a) = d, g(b) = b, g( c ) = a, g(d) = c
Hàm g cũng là 1 hoán vị của S.

Hoán vị: (cách thông thường)
Cho tập S và 1 toán tử “<” quy định thứ tự (order) các phần tử trong S.
Ta chọn 1 dãy số f, f: N -> S, sao cho x1 < x2 thì f(x1) < f(x2), với x1,x2 thuộc N.
Gọi y = g(x), g: S ->S, là một hoán vị của S.
Hàm hợp h: N -> S, h(x) = (g . f)(x) = g(f(x)) là 1 dãy số và cũng là hoán vị theo cách thông thường.

Ví dụ:
Tập S = { a, b, c, d }
Toán tử < trên S định nghĩa thứ tự như sau: a < b, a < c, a < d, b < c, b < d, c < d.
Khi đó ta chọn được dãy f: N -> S sao cho: f(1) = a, f(2) = b, f(3) = c, f(4) = d, f được biểu diễn (a, b, c, d).

Xét 2 hoán vị sau:
Hoán vị g: S -> S, g(a) = b, g(b) = a, g( c ) = d, g(d) = c.
=> Hàm hợp gf = g . f: N -> S:

  • gf(1) = g(f(1)) = g(a) = b
  • gf(2) = g(f(2)) = g(b) = a
  • gf(3) = g(f(3)) = g( c ) = d
  • gf(4) = g(f(4)) = g(d) = c

=> gf được biểu diễn (b, a, d, c)

Hoán vị h: S -> S, h(a) = d, h(b) = b, h( c ) = a, h(d) = c
=> Hàm hợp hf = h . f: N -> S:

  • hf(1) = h(f(1)) = h(a) = d
  • hf(2) = h(f(2)) = h(b) = b
  • hf(3) = h(f(3)) = h( c ) = a
  • hf(4) = h(f(4)) = h(d) = c

=> hf được biểu diễn (d, b, a, c)

(mục đích: ôn lại toán rời rạc)

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?