Dãy (toán học)

Trong toán học, dãy là một họ có thứ tự các đối tượng toán học và cho phép lặp lại các phần tử trong đó. Giống như tập hợp, nó chứa các phần tử (hay còn gọi là "số hạng"). Số các phần tử (có thể vô hạn) được gọi là độ dài của dãy số. Trái với tập hợp, một phần tử có thể xuất hiện nhiều lần trong dãy và cũng trái với tập hợp, thứ tự trong dãy cũng quan trọng. Trong định nghĩa chính thức, dãy được định nghĩa là hàm số từ tập các số tự nhiên (số vị trí các phần tử trong dãy) sang các phần tử tại vị trí đó. Thuật ngữ dãy được tổng quát hoá thành họ sắp chỉ số (họ sắp chỉ số được định nghĩa là hàm số từ một tập chỉ số "tuỳ ý").
Thứ tự của phần tử trong dãy rất quan trọng. Trong dãy, có thể có một hoặc không phần tử đứng trước (hoặc sau) các phần tử còn lại, trong khi đó các phần tử còn lại sẽ luôn có ít nhất một phần tử đứng trước và ít nhất một phần tử đứng sau. Lấy ví dụ, (M, A, R, Y) là dãy các chữ cái với chữ 'M' đứng trước và chữ 'Y' đứng cuối, do đó chữ 'M' có ba phần tử đứng sau nhưng không có phần tử đứng trước. Dãy này khác với (A, R, M, Y). 
Dãy (1, 1, 2, 3, 5, 8), mặc dù chứa số 1 ở hai vị trí khác nhau, vẫn được coi là một dãy hợp lệ. Một dãy có thể "hữu hạn", như những ví dụ trên, hoặc "vô hạn", như dãy các số nguyên dương chẵn (2, 4, 6, ...).
Vị trí của một phần tử trong dãy được gọi là "số vị trí", "hạng" hay "chỉ số". Phần tử đầu tiên có chỉ số 0 hoặc 1, dựa trên nội dung đang thảo luận. Trong giải tích,dãy số thường được đánh ký hiệu bằng các chữ cái viết thường dưới dạng formula_1, formula_2 và formula_3, trong đó chữ "n" viết dưới chỉ phần tử thứ "n" trong dãy; ví dụ chẳng hạn, phần tử thứ "n" trong dãy Fibonacci "formula_4" thường được ký hiệu là "formula_5".
Trong điện toán và khoa học máy tính, dãy hữu hạn đôi khi được gọi là xâu, từ hay danh sách, các tên khác biệt với nhau thường là vì chúng tương ứng với các cách khác nhau trong biểu diễn dãy hữu hạn trong bộ nhớ máy tính; dãy vô hạn thì hay được gọi là dòng hay "stream".Dãy rỗng ( ) được bao gồm trong hầu như mọi khái niệm của dãy, song có thể bỏ dựa theo bối cảnh.
Ví dụ và ký hiệu.
Dãy có thể được coi là danh sách các phần tử dưới một thứ tự cụ thể nào đó. Dãy rất hữu dụng trong một lượng lớn môn học nghiên cứu các hàm số, không gian, và các cấu trúc toán học khác có sử dụng tính hội tụ của dãy. Cụ thể, dãy là cơ sở để học và nghiên cứu chuỗi, và cả hai đều là thành phần quan trọng trong các phương trình vi phân và trong giải tích. Dãy nói riêng cũng là chủ đề thú vị của riêng chúng, một số được nghiên cứu riêng và một số được dùng để làm câu đố, ví dụ như nghiên cứu dãy các số nguyên tố.
Có nhiều cách để ký hiệu dãy, nhưng có một số trong đó chỉ có ích cho một số dãy đặc biệt. Một trong những những cách đơn giản nhất để biểu diễn dãy là liệt kê các phần tử trong dãy ra. Ví dụ chẳng hạn, dãy bốn số tự nhiên lẻ đầu tiên có thể viết là (1, 3, 5, 7). Ký hiệu này cũng có thể dùng cho dãy vô hạn. Ví dụ chẳng hạn, dãy vô hạn của các số nguyên dương lẻ được viết là (1, 3, 5, 7, ...). Song vì dấu ba chấm có thể mơ hồ, nên ký hiệu liệt kê hữu dụng nhất với các dãy mà có thể nhận dạng chúng qua các phần tử đầu tiên trong dãy, các cách ký hiệu khác sẽ được thảo luận sau các ví dụ.
Các ví dụ.
Các số nguyên tố là các số tự nhiên lớn hơn 1 và không có ước nào ngoại trừ 1 và chính nó. Xét chúng trong thứ tự tự nhiên, ta được dãy (2, 3, 5, 7, 11, 13, 17, ...). Các số nguyên tố được nghiên cứu rộng rãi trong toán học, chủ yếu nằm trong lý thuyết số với nhiều kết quả quan trọng gắn với nó. 
Các số Fibonacci tạo thành một dãy trong đó ngoại trừ phần từ đầu tiên và phần tử thứ hai trong dãy, mỗi phần tử còn lại đều là tổng của hai phần tử đứng ngay trước nó. Hai phần tử đầu tiên có thể la 0 và 1 hoặc 1 và 1. Dãy các số Fibonacci được gọi là dãy Fibonacci và thường được viết như sau (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...).
Các ví dụ khác bao gồm các dãy chứa các số hữu tỉ, số thực và số phức. Dãy (.9, .99, .999, .9999, ...), chẳng hạn, chạm dần đến số 1. Thậm chí, mọi số thực có thể viết thành giới hạn của dãy các số hữu tỉ (qua biển diễn thập phân của nó chẳng hạn. Lấy ví dụ, là giới hạn của dãy tăng dần (3, 3.1, 3.14, 3.141, 3.1415, ...). Một dãy khác có liên quan là dãy các chữ số thập phân của , tức dãy (3, 1, 4, 1, 5, 9, ...). Không giống như dãy trước, dãy này không có mẫu nhận dạng dễ nhìn.
Một ví dụ không bao gồm số của dãy là dãy các hàm số, trong đó mỗi phần tử của dãy là hàm số có hình dạng được xác định bởi chỉ số của hàm số đó trong dãy.
Bảng tra cứu dãy số nguyên trực tuyến bao gồm một lượng lớn dãy các số nguyên.
Cách viết chỉ số.
Các cách ký hiệu khác có ích đối với các dãy có mẫu nhận dạng không dễ đoán hoặc không có ngay từ đầu như dãy các chữ số của . Một trong những cách ký hiệu là viết một công thức tổng quát để tính phần tử thứ "n" trong dãy là hàm số của "n", đóng nó trong dấu ngoặc rồi bao gồm thêm một đoạn chữ nhỏ viết dưới chỉ ra các tập các giá trị mà "n" có thể nhận. Lấy ví dụ, trong ký hiệu này, dãy các số tự nhiên chẵn có thể ký hiệu thành formula_6. Dãy các số chính phương có thể viết là formula_7. Biến "n" được gọi là chỉ số, và tập các giá trị nó có thể nhận được được gọi là tập chỉ số.
Bằng việt kết hợp cách ký hiệu này với kỹ thuật coi các phần tử trong dãy là các biến độc lập. Ta có thể viết các biểu thức như formula_8, biểu thức này ký hiệu dãy trong đó phần tử thứ "n" lấy từ biến formula_1. Ví dụ:
Bên cạnh đó, ta còn có thể xét nhiều dãy khác nhau trong cùng một lúc bằng cách sử dụng tên biến khác; chẳng hạn formula_11 có thể là dãy khác với formula_8. Ta cũng có thể xét dãy của các dãy: formula_13 ký hiệu dãy trong đó phần tử thứ "m" là dãy formula_14.
Một cách khác để viết miền trong đoạn viết dưới của dãy là viết khoảng giá trị mà nó có thể nhận bằng cách chỉ ra giá trị nhỏ nhất và lớn nhất nó có thển hận. Ví dụ chẳng hạn, ký hiệu formula_15 chỉ dãy 10 số chính phương formula_16. Các giới hạn formula_17 và formula_18 đều được cho phép, nhưnng nó không biểu diễn giá trị hợp lệ cho chỉ số, mà chỉ là cận trên đúng hay cận dưới đúng của các giá trị đó, tương ứng. Ví dụ chẳng hạn, dãy formula_19 giống với dãy formula_8, và không chứa phần tử nào "tại vô hạn". Dãy formula_21 là dãy vô hạn hai bên, và được ký hiệu theo liệt kê là formula_22.
Trong trường hợp tập các chỉ số đã được ngầm hiểu trước, thì có thể bỏ cả đoạn chỉ số trên và dưới. Khi đó, ta thường hiểu formula_23 ký hiệu cho một dãy tuỳ ý. Thường thì chỉ số "k" được ngầm định chạy từ 1 đến ∞. Tuy nhiên, các dãy thường có chỉ số bắt đầu từ 0, tức là
Trong một số trường hợp khi các phần tử trong dãy có quan hệ gần gũi với các số tự nhiên và có mẫu nhận dạng dễ nhìn, thì tập chỉ số có thể suy ra được bằng cách liệt kê vài phần tử đầu tiên. Lấy ví dụ, tập các bình phương của các số lẻ có thể ký hiệu theo một trong năm cách sau.
Hơn nữa, đoạn chỉ số dưới và trên có thể bỏ đi trong cách thứ ba, thứ tư và thứ năm, nếu tập chỉ số đã được hiểu là tập các số tự nhiên. Trong cách thứ hai và thứ ba, có dãy đã được định nghĩa formula_30, nhưng nó không giống với dãy ký hiệu theo biểu thức.
Định nghĩa dãy bằng đệ quy.
Dãy mà phần tử có quan hệ với phần tử đứng trước nó thường được định nghĩa bằng đệ quy. Cách định nghĩa này khác với định nghĩa dãy có các phần tử là giá trị của hàm số của vị trí của chúng.
Để có thể định nghĩa bằng đệ quy, ta cần một luật, hay quy tắc, được gọi là "quan hệ lặp lại" để xây dựng mỗi phần tử trong dãy dựa trên các phần tử đứng trước đó. Bên cạnh đó yêu cầu cần phải định nghĩa hay xác định trước phần tử đứng đầu (hay còn gọi là phần tử khởi tạo) để các phần tử đứng sau có thể được tính bằng quan hệ. Công thức suy ra được từ quan hệ đó được gọi là công thức truy hồi hoặc hệ thức truy hồi.
Dãy Fibonacci là một ví dụ hay thường gặp, và được định nghĩa theo công thức truy hồi sau
với hai phần tử ban đầu formula_32 và formula_33. Qua vài bước tính toán, 10 phần tử đầu tiên của dãy này sẽ là 0, 1, 1, 2, 3, 5, 8, 13, 21, và 34.
Một ví dụ phức tạp về dãy được định nghĩa theo quan hệ đệ quy là dãy Recamán, dãy này được định nghĩa như sau:
với phần tử khởi tạo formula_35
"Hệ thức truy hồi tuyến tính có hệ số hằng" là công thức có dạng
trong đó formula_37 là các hằng số. Có công thức tổng quát để biểu diễn các phần tử formula_1 thành hàm số của ; xem truy hồi tuyến tính. Trong trường hợp của dãy Fibonacci, ta có formula_39 và hàm của lấy từ công thức Binet.
Dãy holonom là dãy được định nghĩa bằng công thức hồi quy dưới dạng
trong đó formula_41 là các đa thức biến . Hầu như đối với mọi dãy holonom không có công thức cụ thể nào để biểu diễn formula_1 bằng hàm số của . Mặc dù vậy, các dãy holonom vẫn đóng vai trò quan trọng trong nhiều nhánh của toán học. Ví dụ chẳng hạn, nhiều hàm đặc biệt có chuỗi Taylor với các hệ số là phần tử của dãy holonom. Sử dụng đệ quy cho phép tính nhanh chóng giá trị của các hàm đặc biệt đó.
Không phải mọi dãy đều có thể định nghĩa bằng đệ quy. Một ví dụ là dãy các số nguyên tố theo thứ tự tự nhiên (2, 3, 5, 7, 11, 13, 17, ...).
Định nghĩa.
Theo quan điểm của lý thuyết tập hợp, dãy là một ánh xạ "a": "X" formula_43 "Y", trong đó X là tập hợp số tự nhiên, hoặc tập con của tập số tự nhiên nhỏ hơn / lớn hơn một số tự nhiên "m" nào đó.
Khi đó thay cho "a"(n) ta dùng ký hiệu an.
Nếu X là hữu hạn ta có dãy hữu hạn:
Ngược lại nó được xem là vô hạn.
Đôi khi, dãy hữu hạn cũng có thể được xem là vô hạn với các phần tử thừ thứ "m" trở đi là bằng nhau.
Nếu Y là tập hợp số, dãy "a" được gọi là dãy số.
Nếu Y là tập các số thực (hoặc phức) ta có dãy số thực (hoặc phức) 
Nếu Y là tập hợp các hàm số ta có dãy hàm.
Nếy Y là tập hợp số tự nhiên ta có dãy số tự nhiên (ít dùng) 
Khi bắt đầu từ phần tử formula_44 dãy thường được ký hiệu:
Người ta thường xét hơn các dãy bắt đầu từ phần tử formula_46.
Dãy hữu hạn.
Khi các phần tử của dãy nhận giá trị trong một tập hữu hạn n phần tử, các bài toán về dãy hữu hạn được xem xét trong toán học tổ hợp (với các khái niệm chỉnh hợp, hoán vị, dãy có lặp...) gồm bài toán đếm, bài toán liệt kê và bài toán tồn tại.
Dãy vô hạn.
Khi các phần tử của một dãy vô hạn thuộc một không gian metric (trong không gian có khái niệm khoảng cách giữa hai phần tử) chẳng hạn các dãy số thực,dãy hàm hoặc không gian tôpô (trong đó có khái niệm lân cận) các bài toán về dãy liên quan tới khái niệm giới hạn, tính hội tụ, phân kỳ.
Dãy trong khoa học học máy tính.
Trong khoa học máy tính, khái niệm dãy (hữu hạn) thể hiện cụ thể thành các danh sách (tuyến tính), mảng, ngăn xếp, hàng đợi... là những cấu trúc dữ liệu quan trọng.
Các khái niệm về giải thuật, máy Turing cũng đều liên quan đến các dãy.