Totally Greedy Sequences Defined by Second-Order Linear Recurrences With Constant Coefficients
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908446220091392 |
|---|---|
| author | Pérez-Rosés, Hebert |
| author_facet | Pérez-Rosés, Hebert |
| contents | The change-making problem consists of representing a certain amount of money with the least possible number of coins, from a given, pre-established set of denominations. The greedy algorithm works by choosing the coins of largest possible denomination first. This greedy strategy does not always produce the least number of coins, except when the set of denominations obeys certain properties. We call a set of denominations with these properties a greedy set. If the set of denominations is an infinite sequence, we call it totally greedy if every prefix subset is greedy. In this paper we investigate some totally greedy sequences arising from second-order linear recurrences with constant coefficients, as well as their subsequences, and we prove sufficient conditions under which these sequences are totally greedy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16609 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Totally Greedy Sequences Defined by Second-Order Linear Recurrences With Constant Coefficients Pérez-Rosés, Hebert Combinatorics 11B37, 11B39, 11Y55, 68R05 F.2.2; G.2.1 The change-making problem consists of representing a certain amount of money with the least possible number of coins, from a given, pre-established set of denominations. The greedy algorithm works by choosing the coins of largest possible denomination first. This greedy strategy does not always produce the least number of coins, except when the set of denominations obeys certain properties. We call a set of denominations with these properties a greedy set. If the set of denominations is an infinite sequence, we call it totally greedy if every prefix subset is greedy. In this paper we investigate some totally greedy sequences arising from second-order linear recurrences with constant coefficients, as well as their subsequences, and we prove sufficient conditions under which these sequences are totally greedy. |
| title | Totally Greedy Sequences Defined by Second-Order Linear Recurrences With Constant Coefficients |
| topic | Combinatorics 11B37, 11B39, 11Y55, 68R05 F.2.2; G.2.1 |
| url | https://arxiv.org/abs/2405.16609 |