• Source: 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 2 = 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


    =

    ∑

    m
    =
    0


    n



    a

    m




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

    .
    Dengan syarat-syarat





    a

    0


    =
    1



    {\displaystyle a_{0}=1\,}





    2

    a

    k


    ≥

    a

    k
    +
    1



    for all

    k
    ≥
    0


    {\displaystyle 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



    {\displaystyle a_{0}=1\,}






    s

    k
    −
    1


    ≥

    a

    k


    −
    1

    for all

    k
    ≥
    1


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


    cukup agar an 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 (F6 + F5 + F3 + F2 + F1 = 8 + 5 + 2 + 1 + 1 = 17, bentuk maksimal)
     111001 (F6 + F5 + F4 + F1 = 8 + 5 + 3 + 1 = 17)
     111010 (F6 + F5 + F4 + F2 = 8 + 5 + 3 + 1 = 17)
    1000111 (F7 + F3 + F2 + F1 = 13 + 2 + 1 + 1 = 17)
    1001001 (F7 + F4 + F1 = 13 + 3 + 1 = 17)
    1001010 (F7 + F4 + F2 = 13 + 3 + 1 = 17, bentuk minimal, yang digunakan pada kode Fibonacci)
    Bentuk maksimal di atas akan selalu menggunakan F1 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 F1 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


    Referensi




    Tautan eksternal


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

Kata Kunci Pencarian: