A339333 Triangle read by rows, 1 <= k <= n: T(n,k) is the sum of the minimal number of coins needed for amounts 1..n with an optimal k-coin system of denominations.

1, 3, 2, 6, 4, 3, 10, 6, 5, 4, 15, 9, 7, 6, 5, 21, 11, 9, 8, 7, 6, 28, 14, 11, 10, 9, 8, 7, 36, 18, 13, 12, 11, 10, 9, 8, 45, 21, 16, 14, 13, 12, 11, 10, 9, 55, 25, 19, 16, 15, 14, 13, 12, 11, 10, 66, 30, 22, 18, 17, 16, 15, 14, 13, 12, 11

Offset: 1

Author

Pontus von Brömssen, Nov 30 2020

Keywords

• nonn
• tabl

Comments

T(n,k) <= A339334(n,k).

T(n,k) >= 2n - k, with equality if and only if n <= A001212(k).

Examples

			Triangle begins:
  n\k|  1  2  3  4  5  6  7  8  9 10 11 12
  ---|-------------------------------------
   1 |  1
   2 |  3  2
   3 |  6  4  3
   4 | 10  6  5  4
   5 | 15  9  7  6  5
   6 | 21 11  9  8  7  6
   7 | 28 14 11 10  9  8  7
   8 | 36 18 13 12 11 10  9  8
   9 | 45 21 16 14 13 12 11 10  9
  10 | 55 25 19 16 15 14 13 12 11 10
  11 | 66 30 22 18 17 16 15 14 13 12 11
  12 | 78 33 24 20 19 18 17 16 15 14 13 12
For n = 8, there is a unique optimal 3-coin system (1,3,4), with the representations
  1 = 1
  2 = 1 + 1
  3 = 3
  4 = 4
  5 = 4 + 1
  6 = 3 + 3
  7 = 4 + 3
  8 = 4 + 4
with a total of 13 = T(8,3) terms.
Shallit (2003) shows that T(99,k) is 4950, 900, 515, 389, 329, 292, 265 for k = 1..7.
		

Links

• Pontus von Brömssen, Rows n = 1..40, flattened
• Jeffrey Shallit, What this country needs is an 18¢ piece, The Mathematical Intelligencer 25 (2003), issue 2, 20-23.
• Jeffrey Shallit, What this country needs is an 18¢ piece.
• Wikipedia, Change-making problem

Crossrefs

Cf. A000217, A001212, A322832, A339334.

Formula

T(n,1) = A000217(n).

It appears that T(n,2) - T(n-1,2) = A322832(n).

T(n,k) = A339334(n,k) for all k when 1 <= n <= 7 or n = 10.

T(n,k) = A339334(n,k) for all n when k = 1 or k = 2.