# Fundamental Counting Principle Proof (NOT via induction)

• Chicago_Boy1
In summary, the conversation discusses the Fundamental Counting Principle and how to prove it without induction. The principle states that if set A has m elements and set B has n elements, then the Cartesian product of A and B has mn elements. The speaker is unsure how to prove this and is seeking guidance. The idea of "drawing little trees" is mentioned as a possible method, but the speaker is still confused. They also mention their understanding of "A has m elements" and how it can be rephrased to help with the proof.
Chicago_Boy1
Hello all,

I am going through some sample problems exercises in Paul Sally's Tools of the Trade, and am being asked to prove the Fundamental Counting Principle. That is, If A has m elements and B has n elements, then A X B has mn elements.

Sally goes on to write that "this is simple to prove by drawing little trees or using some other artifice."

Basically, I am not really sure what he means by "drawing little trees." Can someone guide me through how I can actually prove this WITHOUT induction?

P.S. I know that I am supposed to show that I've attempted to solve the problem, but honestly I have no idea where to even start.

What is your definition of "$$A$$ has $$m$$ elements" for a set $$A$$? It's probably something like "$$A$$ is in bijective correspondence with the set $$[m] = \{0, 1, \dots, m - 1\}$$" (although knowing Sally, he probably starts counting with 1 instead). So you can rephrase the problem as: If $$f: A \to [m]$$ is a bijection and $$g: B \to [n]$$ is a bijection, find a bijection $$h: A \times B \to [mn]$$. Does that help?

## 1. How does the Fundamental Counting Principle work?

The Fundamental Counting Principle states that if there are n ways to do one task and m ways to do another task, then there are n x m ways to do both tasks. This can be used to find the total number of outcomes in a multi-step process by multiplying the number of choices at each step.

## 2. What is the formula for the Fundamental Counting Principle?

The formula for the Fundamental Counting Principle is n x m, where n represents the number of choices for the first task and m represents the number of choices for the second task.

## 3. Can the Fundamental Counting Principle be used for more than two tasks?

Yes, the Fundamental Counting Principle can be extended to more than two tasks. For example, if there are three tasks with n, m, and p choices respectively, the total number of outcomes would be n x m x p.

## 4. How can the Fundamental Counting Principle be applied in real life?

The Fundamental Counting Principle can be applied in various situations, such as calculating the number of possible outcomes in a game or the number of different meal combinations at a restaurant. It can also be used in probability to determine the likelihood of a certain outcome.

## 5. Is the Fundamental Counting Principle always accurate?

Yes, the Fundamental Counting Principle is always accurate as it is a fundamental mathematical principle. However, it assumes that all choices are equally likely and does not take into account any restrictions or limitations. Therefore, it may not be applicable in certain situations.

• Calculus and Beyond Homework Help
Replies
6
Views
1K
• Calculus and Beyond Homework Help
Replies
4
Views
3K
• Electrical Engineering
Replies
4
Views
1K
• Mechanics
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
5K
• Math Proof Training and Practice
Replies
5
Views
1K
• Calculus and Beyond Homework Help
Replies
7
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
869
• Calculus and Beyond Homework Help
Replies
3
Views
2K