Barisan lengkap

Dalam matematika, barisan suatu bilangan asli disebut barisan lengkap, jika setiap bilangan bulat positif dapat dinyatakan sebagai jumlah dari nilai-nilai dalam barisan tersebut, dengan setiap nilai digunakan paling banyak satu kali.

Sebagai contoh, barisan pangkat dua (1, 2, 4, 8, ...), yang merupakan basis sistem bilangan biner, adalalah barisan lengkap; Jika diberikan bilangan asli apa pun, kita dapat memilih nilai yang sesuai dengan 1 bit dalam representasi binernya dan menjumlahkannya untuk mendapatkan bilangan tersebut (misalnya 37 = 100101 ₂ = 1 + 4 + 32). Barisan ini minimal, karena tidak ada nilai yang bisa dihapus dari urutan ini tanpa membuat beberapa bilangan alami menjadi tidak dapat direpresentasikan. Contoh sederhana barisan yang tidak lengkap adalah bilangan genap, karena penjumlahan bilangan genap hanya menghasilkan bilangan genap—tidak ada bilangan ganjil yang dapat dibentuk.

Syarat kelengkapan

Tanpa mengurangi keumuman, diasumsikan barisan a _n berada dalam urutan tak menurun, dan didefinisikan jumlah parsial dari a _n sebagai:

$s_{n}=\sum _{m=0}^{n}a_{m}$ .

Dengan syarat-syarat

$a_{0}=1\,$

$2a_{k}\geq a_{k+1}{\text{ for all }}k\geq 0$

adalah keduanya merupakan syarat yang diperlukan dan cukup untuk n menjadi barisan lengkap

Yang mengakibatkan

$a_{0}=1\,$

$s_{k-1}\geq a_{k}-1{\text{ for all }}k\geq 1$

cukup agar a_n menjadi barisan yang lengkap.

Namun, ada barisan lengkap yang tidak memenuhi akibat ini, misalnya (barisan A203074 pada OEIS) , yang terdiri dari bilangan 1 dan bilangan prima pertama setelah masing-masing pangkat 2.

Barisan lengkap lainnya

Barisan lengkap meliputi:

• Barisan bilangan 1 diikuti bilangan prima (diteliti oleh SS Pillai dan lain-lain); ini mengikuti postulat Bertrand .
• Barisan bilangan praktis yang memiliki 1 sebagai suku pertama dan memuat semua pangkat 2 lainnya sebagai himpunan bagian. (barisan A005153 pada OEIS)
• Angka Fibonacci, serta angka Fibonacci dengan salah satu angkanya dihilangkan. Berdasarkan identitas bahwa jumlah n bilangan Fibonacci pertama adalah bilangan Fibonacci ke-(n + 2) dikurangi 1.

Aplikasi

Sama seperti pangkat dua yang membentuk barisan lengkap karena sistem bilangan biner. Sebenarnya barisan lengkap apa pun dapat digunakan untuk menyandikan bilangan bulat sebagai string bit. Posisi bit paling kanan ditetapkan ke anggota barisan pertama dan terkecil; paling kanan berikutnya ke anggota berikutnya; dan seterusnya. Bit yang disetel ke 1 disertakan dalam penjumlahan. Representasi ini mungkin tidak unik.

Pengkodean Fibonacci

Misalnya, dalam sistem aritmatika Fibonacci, berdasarkan deret Fibonacci, angka 17 dapat dikodekan dalam enam cara berbeda:

 110111 (F₆ + F₅ + F₃ + F₂ + F₁ = 8 + 5 + 2 + 1 + 1 = 17, bentuk maksimal)

 111001 (F₆ + F₅ + F₄ + F₁ = 8 + 5 + 3 + 1 = 17)

 111010 (F₆ + F₅ + F₄ + F₂ = 8 + 5 + 3 + 1 = 17)

1000111 (F₇ + F₃ + F₂ + F₁ = 13 + 2 + 1 + 1 = 17)

1001001 (F₇ + F₄ + F₁ = 13 + 3 + 1 = 17)

1001010 (F₇ + F₄ + F₂ = 13 + 3 + 1 = 17, bentuk minimal, yang digunakan pada kode Fibonacci)

Bentuk maksimal di atas akan selalu menggunakan F₁ dan selalu memiliki angka satu di akhir. Pengkodean lengkap tanpa angka 1 di akhir dapat ditemukan di (barisan A104326 pada OEIS). Dengan menghilangkan angka satu di akhir, pengkodean untuk 17 di atas muncul sebagai suku ke-16 dari A104326. Bentuk minimalnya tidak akan pernah menggunakan F₁ dan akan selalu memiliki angka nol di belakangnya. Pengkodean lengkap tanpa akhiran nol dapat ditemukan di ((barisan A014417 pada OEIS). Pengkodean ini dikenal sebagai representasi Zeckendorf.

Dalam sistem bilangan ini, setiap substring "100" dapat diganti dengan "011" dan sebaliknya karena definisi bilangan Fibonacci. Penerapan aturan-aturan ini secara terus-menerus akan mengubah dari yang maksimal menjadi minimal, dan sebaliknya. Fakta bahwa bilangan apa pun (lebih besar dari 1) dapat direpresentasikan dengan angka terminal 0 berarti bahwa selalu mungkin untuk menambahkan 1, dan mengingat bahwa 1 dan 2 dapat direpresentasikan dalam pengkodean Fibonacci, kelengkapannya diikuti dengan induksi.

Lihat juga

• Penomoran Ostrowski

Tautan eksternal

• Weisstein, Eric W. "Complete Sequence". MathWorld.