Размен монет

[DiscipleOfTheWatch]

Я видел другие темы про размен монет, там приводятся формулы из комбинаторики, но меня интересует другое.
В книге Structure and Interpretation of Computer Programs я натолкнулся на такое рассуждение.

Цитата:

Способы размена могут быть поделены на две группы: те, которые не используют первый тип монеты, и те, которые его используют. Следовательно, общее число способов размена какой-либо суммы равно числу способов разменять эту сумму без привлечения монет первого типа плюс число способов размена в предположении, что мы этот тип используем. Но последнее число равно числу способов размена для суммы, которая остается после того, как мы один раз употребили первый тип монеты.

Я совершенно не понимаю этого рассуждения. Я не понимаю даже, как к нему можно было придти. Вот допустим у нас есть монеты с достоинством 1, 5 и 10 центов и нам надо найти количество способов размена 11 центов. Таких способов четыре:
1) 1 1 1 1 1 1 1 1 1 1 1
2) 5 1 1 1 1 1 1
3) 5 5 1
4) 10 1

У меня никак не получается применить рассуждение из SICP к этому примеру.

[Otta]

Ну и какой тип монет Вы предпочитаете взять за "первый"?

[DiscipleOfTheWatch]

Otta в сообщении #745115 писал(а):

Ну и какой тип монет Вы предпочитаете взять за "первый"?

Ну пускай 1й - 1 цент, 2й - 5 центов, 3й - 10 центов

[Otta]

Оставьте в стороне второй и третий.
Ок, первый - один цент.
И что Вам непонятно?

Цитата:

общее число способов размена какой-либо суммы равно числу способов разменять эту сумму без привлечения монет первого типа плюс число способов размена в предположении, что мы этот тип используем.

число способов разменять монету с использованием первого типа = ? (смотрите, Вы их выписали явно)
без первого типа = ?

На самом деле, рассуждение такое тривиальное, что даже и объяснять его неловко.

[DiscipleOfTheWatch]

Otta в сообщении #745122 писал(а):

На самом деле, рассуждение такое тривиальное, что даже и объяснять его неловко.

Да, действительно, разобрался после того, как расписал всё на бумаге

[Otta]

)) Что ж там было расписывать. Либо тип входит в набор, либо не входит - других вариантов нет.
Но хорошо, что разобрались.

[DiscipleOfTheWatch]

Otta в сообщении #745126 писал(а):

)) Что ж там было расписывать. Либо тип входит в набор, либо не входит - других вариантов нет.
Но хорошо, что разобрались.

Позвольте ещё два вопроса
1) Почему "число способов размена в предположении, что мы этот тип используем" равно "числу способов размена для суммы, которая остается после того, как мы один раз употребили первый тип монеты"?
2) Почему мы считаем, что если сумма денег равна нулю, то у нас один способ размена? Вроде бы логичнее, что если у нас ноль денег, то ноль способов размена.

[provincialka]

Просто это удобно. Чтобы формулы оказались верными и для $n=0$.
Кроме того, это логично. Нет никакого противоречия: ничего не делать можно только одним способом, независимо от типа "недействия"

[DiscipleOfTheWatch]

provincialka в сообщении #745168 писал(а):

Просто это удобно. Чтобы формулы оказались верными и для $n=0$.
Кроме того, это логично. Нет никакого противоречия: ничего не делать можно только одним способом, независимо от типа "недействия"

Но если у меня есть одно-, пяти- и десятицентовые монеты, и меня попросят положить на стол ими сумму в ноль центов, то я не отдам ни одной монеты, это по идее и значит, что способов размена - ноль.

[provincialka]

Это все условность. Это просто удобно. Так же в пустом множестве есть одно подмножество (само пустое множество).

[DiscipleOfTheWatch]

DiscipleOfTheWatch в сообщении #745155 писал(а):

1) Почему "число способов размена в предположении, что мы этот тип используем" равно "числу способов размена для суммы, которая остается после того, как мы один раз употребили первый тип монеты"?

[Someone]

Ну так мы же один раз употребили монету первого типа. Значит, как бы мы ни разменяли оставшуюся сумму, монета первого типа уже есть.

DiscipleOfTheWatch в сообщении #745155 писал(а):

2) Почему мы считаем, что если сумма денег равна нулю, то у нас один способ размена? Вроде бы логичнее, что если у нас ноль денег, то ноль способов размена.

Именно один: не давать никаких монет.

Подумайте, почему пустых множеств именно одна штука, а не ноль штук. И почему в каждом множестве есть именно одно пустое подмножество, а не ноль штук.

[arseniiv]

DiscipleOfTheWatch в сообщении #745745 писал(а):

1) Почему "число способов размена в предположении, что мы этот тип используем" равно "числу способов размена для суммы, которая остается после того, как мы один раз употребили первый тип монеты"?

А вы разменяйте монетами в 1, 5 и 10 центов 10 центов, 6 центов и 1 цент. А потом сравните с

DiscipleOfTheWatch в сообщении #745113 писал(а):

<…> количество способов размена 11 центов. Таких способов четыре:
1) 1 1 1 1 1 1 1 1 1 1 1
2) 5 1 1 1 1 1 1
3) 5 5 1
4) 10 1

для каждого типа монет, от которых и оставалось от 11 центов соответственно 10, 6 и 1.

[DiscipleOfTheWatch]

Всем спасибо за указания