IT1160 Discrete Mathematics: Lab Sheet 05 - Permutations & Combinations Study Notes

Overview of Permutations and Combinations

Permutations and combinations are fundamental concepts in mathematics used to determine the total number of ways to arrange or select elements from a specific set. These principles are essential for solving counting problems and are widely used in computing and probability.

Definitions and Key Differences

  • Permutation: This refers to the total number of ways to arrange elements from a set. In a permutation, the order matters. For instance, the sequence (A, B) is considered a different permutation than (B, A).

  • Combination: This refers to the total number of ways to select elements from a set. In a combination, the order does not matter. For instance, (A, B) and (B, A) are considered the same combination.

Mathematical Formulas

In these formulas, nn represents the total number of items in the set, and rr represents the number of items being chosen or arranged.

  • Permutation Formula:     nPr=n!(n−r)!nP_r = \frac{n!}{(n - r)!}

  • Combination Formula:     nCr=n!r!(n−r)!nC_r = \frac{n!}{r!(n - r)!}

Python Itertools Package for Counting

Python provides a built-in library called itertools to handle various counting and arrangement tasks efficiently. Below is a summary of the available functions based on the type of operation needed:

Type

Itertools Function

Permutations without repetition

itertools.permutations(iterable, r)

Permutations with repetition

itertools.product(iterable, repeat=r)

Permutations with indistinguishable objects

No direct itertools function available

Combinations without repetition

itertools.combinations(iterable, r)

Combinations with repetition

itertools.combinations_with_replacement(iterable, r)

Laboratory Exercises: Part 01

1. Theater Scheduling (Permutations)

A theater company schedules performances using a specific set of actors where each performance requires a unique order.

  • Scenario: 3 actors identified as "A", "B", and "C".

  • Task A: Generate all possible schedules (arrangements).

  • Task B: Identify the specific 5th schedule within the generated list of possibilities.

2. Password Design (Multi-Step Counting)

A computer science student is designing passwords with specific character constraints.

  • Constraints:

    • 2 lowercase letters chosen from the set ["a", "b", "c", "d"].

    • 3 digits chosen from 5 possible digits: 0,1,2,3,40, 1, 2, 3, 4.

  • Task: Write a Python program to generate every unique password and calculate the total count.

3. Robot Navigation (Grid Paths)

A robot navigates a Cartesian (XY) plane starting at the origin (0,0)(0,0) and moving toward the top-right corner (3,3)(3,3).

  • Movement Rules: The robot can only move Right (R) or Up (U).

  • Task A: Create a program to calculate the total number of unique paths.

  • Task B: Display one example of a valid path sequence.

4. Committee Formation (Combinations)

A team leader forms committees from a group of employees. Since a committee is a group where individual position does not matter, this is a combination problem.

  • Scenario: Employees ["A", "B", "C", "D"].

  • Constraint: Each committee must consist of exactly 2 members.

  • Task A: List all possible unique committees.

  • Task B: Identify the 3rd committee in the generated list.

5. Bouquet Design (Combinations with Repetition)

A florist creates bouquets using 3 specific types of flowers: ["Rose", "Lily", "Tulip"].

  • Constraints: Each bouquet must contain 3 flowers; repetition of types is permitted.

  • Task A: List all possible bouquets.

  • Task B: Identify and display only the bouquets where all three flowers are different types.

Laboratory Exercises: Part 02

1. Permutations of Colored Books

This problem involves permutations with indistinguishable objects (identical items).

  • Inventory: 7 books total.

    • 3 red books.

    • 2 green books.

    • 1 blue book.

    • 1 orange book.

  • Task A: Calculate the total number of unique permutations possible.

  • Task B: Calculate the number of permutations if all red books must remain adjacent (together) and all green books must remain adjacent.

2. Three-Digit Number Formation

Using digits 1,2,3,4,51, 2, 3, 4, 5 to create three-digit numbers.

  • Constraint: Repetition of digits is not allowed.

  • Task A: Determine how many unique three-digit numbers can be created.

  • Task B: Calculate how many of these three-digit numbers are greater than 500500.

3. Grid Navigation with Obstacles

A 3×33 \times 3 grid is traversed from (0,0)(0,0) to (3,3)(3,3), but a specific coordinate is blocked.

  • Obstacle Location: (2,2)(2,2).

  • Task A: Determine how many total paths would normally go through the point (2,2)(2,2).

  • Task B: Determine the total number of valid paths that avoid the obstacle at (2,2)(2,2).

4. Distributed Computing System Selection

A system administrator must activate 11 servers from a pool of 15 distinct servers categorized as follows:

  • Categories:

    • 8 compute servers (for processing).

    • 5 storage servers (for data storage).

    • 2 backup servers (for fault tolerance).

  • Task A: Calculate the number of different sets of 11 servers if there are no restrictions on type.

  • Task B: Calculate the selections possible if the policy dictates exactly 6 compute servers, 4 storage servers, and 1 backup server.

5. Virtual Machine (VM) Allocation

A cloud provider offers 4 types of VMs: Compute-optimized, Memory-optimized, Storage-optimized, and GPU-based.

  • Requirement: Allocate 10 VMs to a project.

  • Rules:

    • Multiple VMs of the same type are allowed.

    • Only the count of each type matters (indistinguishable within types).

    • The order of allocation is irrelevant.

  • Task: Write a Python program to determine the number of distinct VM allocation combinations possible based on these criteria.