[an error occurred while processing the directive]

<p class="header">Занятие 17. Комбинаторика - 3. Генерация объекта по номеру и номера по объекту.</p>

<p>Комбинаторика изучает множества однотипных объектов. Объекты в таком множестве
можно упорядочить по некоторому признаку и затем занумеровать. Возникает
задача определения объекта по его номеру и номера по объекту. Рассмотрим способ 
решения этой задачи на примере перестановок фиксированной длины N.</p>

<p>В качестве способа упорядочивания возьмем лексикографический (пример 
лексикографического порядка перестановок длины 3: (1,2,3), (1,3,2), (2,1,3),
(2,3,1), (3,1,2), (3,2,1)). Сначала научимся определять перестановку по номеру. 
Для этого научимся отвечать на вопрос: &quot;Сколько существует объектов
с заданным началом?&quot; Для перестановок ответ прост: (N-k)!, где k - длина 
префикса. Будем перебирать все префиксы длины 1 в лексикографическом порядке.
Как только сумма количества перестановок с такими префиксами станет не меньше номера,
начинаем перебирать все префиксы длины два, полученные продолжением последнего
префикса длины один, и так далее. Обратная задача решается аналогично:
перебираем все префиксы длины один, меньшие соответствующего префикса нашей перестановки,
затем длины два, полученные продолжением префикса длины один нашей перестановки и т.д.
Сумма по всем перебранным префиксам будет на 1 меньше номера перестановки.</p>

<p>Прочие задачи генерации номера по объекту и объекта по номеру решаются аналогично:
мы последовательно строим объект, перебирая все возможные начала. Самой сложной частью,
как правило, являлется определение количества объектов с заданным префиксом. Если явной 
формулы не существует, приходится прибегать к динамическому программированию.</p>

<table align=center valign=top border=0 cellspacing=0 width=95%>
<tbody>
  <tr><td>
    Задача 17-1. По номеру!
    <ul>
      <li><a href="description1.shtml">Условие</a></li>
      <li><a href="handout1.shtml">Разбор</a></li>
      <li><a href="task1.rar">Тесты</a></li>
  </ul>
  </td></tr>
  <tr><td>
    Задача 17-2. По размещению!
    <ul>
      <li><a href="description2.shtml">Условие</a></li>
      <li><a href="handout2.shtml">Разбор</a></li>
      <li><a href="task2.rar">Тесты</a></li>
  </ul>
  </td></tr> 
  <tr><td>
    Задача 17-3. Гладкие числа.
    <ul>
      <li><a href="description3.shtml">Условие</a></li>
      <li><a href="handout3.shtml">Разбор</a></li>
      <li><a href="task3.rar">Тесты</a></li>
  </ul>
  </td></tr>
  <tr><td>
    Задача 17-4. Следующая...
    <ul>
      <li><a href="description4.shtml">Условие</a></li>
      <li><a href="handout4.shtml">Разбор</a></li>
      <li><a href="task4.rar">Тесты</a></li>
  </ul>
  </td></tr>
</tbody>
</table>

[an error occurred while processing the directive]