✨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 $a\_n$, $b\_n$ và $c\_n$, 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 $F$ thường được ký hiệu là _$F$n.

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.right|thumb|Dãy vô hạn của [[các số thực (trong màu xanh). Dãy này không tăng hay giảm, không hội tụ và cũng không có tính Cauchy. Tuy nhiên nó có bị chặn (đường đỏ nét đứt)]]

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 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ụ

thumb|[[lát gạch|Lát với các ô vuông có độ dài của cạnh là số Fibonacci liên tiếp]]

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á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 $(2n)${n\in\mathbb N}. Dãy các số chính phương có thể viết là $(n^2)${n\in\mathbb N}. 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ư $(a$n){n\in\mathbb N}, biểu thức này ký hiệu dãy trong đó phần tử thứ n lấy từ biến $a\_n$. Ví dụ: :n){n\in\mathbb N} \ a_2 &= \text{phần tử thứ }2 \ a3 &= \text{phần tử thứ }3 \ &\;\;\vdots \ a{n-1} &= \text{phần tử thứ }n-1 \ an &= \text{phần tử thứ }n \ a{n+1} &= \text{phần tử thứ }n+1\ &\;\; \vdots \end{align} 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 $(b$n){n\in\mathbb N} có thể là dãy khác với $(a$n){n\in\mathbb N}. Ta cũng có thể xét dãy của các dãy: $((a${m, n}){n\in\mathbb N})_{m\in\mathbb N} ký hiệu dãy trong đó phần tử thứ m là dãy $(a${m, n}){n\in\mathbb N}.

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 $(k^2)\_\{k\; =\; 1\}^\{10\}$ chỉ dãy 10 số chính phương $(1,\; 4,\; 9,\; \backslash ldots,\; 100)$. Các giới hạn $\backslash infty$ và $-\backslash infty$ đề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 $(a$n){n = 1}^\infty giống với dãy $(a$n){n\in\mathbb N}, và không chứa phần tử nào "tại vô hạn". Dãy $(a$n){n = -\infty}^\infty là dãy vô hạn hai bên, và được ký hiệu theo liệt kê là $(\backslash ldots,\; a\_\{-1\},\; a\_0,\; a\_1,\; a\_2,\; \backslash ldots)$.

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 $(a\_k)$ 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à :$(a$k){k=0}^\infty = ( a_0, a_1, a_2, \ldots ). 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.

• $(1,\; 9,\; 25,\; \backslash ldots)$
• $(a\_1,\; a\_3,\; a\_5,\; \backslash ldots),\; \backslash qquad\; a\_k\; =\; k^2$
• $(a\_\{2k-1\})\_\{k=1\}^\backslash infty,\; \backslash qquad\; a\_k\; =\; k^2$
• $(a\_\{k\})\_\{k=1\}^\backslash infty,\; \backslash qquad\; a\_k\; =\; (2k-1)^2$
• $\backslash left((2k-1)^2\backslash right)\_\{k=1\}^\backslash infty$

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 $(a${k}){k=1}^\infty, 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 :$a$n = a{n-1} + a_{n-2}, với hai phần tử ban đầu $a\_0\; =\; 0$ và $a\_1\; =\; 1$. 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: :$\backslash begin\{cases\}a$n = a{n-1} - n,\quad \text{nếu kết quả dương và hiện chưa có trong dãy}\an = a{n-1} + n, \quad\text{ngược lại}, \end{cases} với phần tử khởi tạo $a\_0\; =\; 0.$

Hệ thức truy hồi tuyến tính có hệ số hằng là công thức có dạng :$a\_n=c\_0\; +c$1a{n-1}+\dots+ck a{n-k}, trong đó $c\_0,\backslash dots,\; c\_k$ là các hằng số. Có công thức tổng quát để biểu diễn các phần tử $a\_n$ 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ó $c\_0=0,\; c\_1=c\_2=1,$ 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 :$a\_n=c$1a{n-1}+\dots+ck a{n-k}, trong đó $c\_1,\backslash dots,\; c\_k$ 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 $a\_n$ 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 $\backslash to$ 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 a_n. ::a_n=a(n) Nếu X là hữu hạn ta có dãy hữu hạn: :: a_n1,...,a_n. Ngược lại nó được xem là vô hạn. :: a₁,a₂,...,a_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ử $a\_\{n\_0\}$ dãy thường được ký hiệu: :$(x$n){n \ge n_0 } với x_n là phần tử thứ n.

Người ta thường xét hơn các dãy bắt đầu từ phần tử $a\_1$. :$(x$n){n \ge 1 } với x_n là phần tử thứ n

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.

• Bài toán đếm: đếm số các dãy (hữu han) của một tập hợp thoả mãn một hoặc một số tính chất nào đó.
• Bài toán liệt kê:liệt kê toàn bộ các dãy (hữu hạn) của một tập hợp thoả mãn một hoặc một số tính chất nào đó.
• Bài toán tòn tại: xét xem các dãy (hữu hạn) của một tập hợp thoả mãn một hoặc một số tính chất nào đó có tốn tại không?

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.