Skip to main content
LibreTexts - Ukrayinska

1: Підрахунок

Одне з перших речей, які ви вивчаєте в математиці, - це те, як рахувати. Тепер ми хочемо порахувати великі колекції речей швидко і точно. Наприклад:

  • У групі з 10 чоловік, якщо всі тиснуть руку всім іншим рівно один раз, скільки рукостискань відбулося?
  • Скільки способів ви можете розповсюдити печиво 1010 дівчат-скаутів 77 бойскаутам?
  • Скільки існує анаграм «анаграми»?

Перш ніж вирішувати подібні питання, давайте розглянемо основи підрахунку.

  • 1.1: Адитивні та мультиплікативні принципи
    Розглянемо цю досить просту проблему підрахунку: у Red Dogs і Donuts існує 14 різновидів пончиків, і 16 видів хот-догів. Якщо ви хочете або пончик, або собаку, скільки варіантів у вас є? Це не дуже важко, просто додайте 14 і 16. Це завжди буде працювати? Що тут важливо?
  • 1.2: Біноміальні коефіцієнти
    Ось деякі очевидно різні дискретні об'єкти, які ми можемо порахувати: підмножини, бітові рядки, шляхи решітки та біноміальні коефіцієнти. Ми наведемо приклад кожного типу проблеми підрахунку (і скажемо, що ці речі навіть є). Як ми побачимо, ці проблеми підрахунку напрочуд схожі.
  • 1.3: Комбінації та перестановки
    Перестановка - це (можлива) перестановка об'єктів.
  • 1.4: Комбінаторні докази
    Щоб дати комбінаторний доказ для біноміальної ідентичності, скажімо, A = B ви робите наступне: (1) Знайдіть проблему підрахунку, на яку ви зможете відповісти двома способами. (2) Поясніть, чому одна відповідь на проблему підрахунку A. (3) Поясніть, чому інша відповідь на проблему підрахунку B. Оскільки і A, і B є відповіді на одне і те ж питання, ми повинні мати A = B. Складна річ придумує питання.
  • 1.5: Зірки та бари
    Багато проблем підрахунку в цьому розділі можуть спочатку здаватися прикладами функцій підрахунку. Зрештою, коли ми намагаємося підрахувати кількість способів розповсюдження файлів cookie дітям, ми призначаємо кожен файл cookie малюкові так само, як ви призначаєте елементи домену функції елементам в кодомені.
  • 1.6: Розширений підрахунок за допомогою PIE
    Принцип включення/виключення (PIE) дає метод знаходження кардинальності об'єднання необов'язково нероз'єднаних множин. Якщо між множинами є будь-яке перекриття, ці елементи підраховуються кілька разів. Таким чином, ми віднімаємо речі в кожному перетині пари множин. Але це видаляє елементи, які є у всіх трьох наборах один раз занадто часто, так що ми повинні додати його назад в.
  • 1.E: Підрахунок (вправи)
  • 1.S: Підрахунок (резюме)
    Хоча ми розглянули багато методів підрахунку, ми насправді лише подряпали поверхню великого предмета перерахувальної комбінаторики. Є математики, які роблять оригінальні дослідження в цій галузі, навіть коли ви читаєте це. Підрахунок може бути дуже важким.