Categories

See More
Popular Forum

MBA (4887) B.Tech (1769) Engineering (1486) Class 12 (1030) Study Abroad (1004) Computer Science and Engineering (988) Business Management Studies (865) BBA (846) Diploma (746) CAT (651) B.Com (648) B.Sc (643) JEE Mains (618) Mechanical Engineering (574) Exam (525) India (462) Career (452) All Time Q&A (439) Mass Communication (427) BCA (417) Science (384) Computers & IT (Non-Engg) (383) Medicine & Health Sciences (381) Hotel Management (373) Civil Engineering (353) MCA (349) Tuteehub Top Questions (348) Distance (340) Colleges in India (334)
See More

How to visualise and understand the sum and product rules of counting?

Course Queries Syllabus Queries

Max. 2000 characters
Replies

usr_profile.png

User

( 4 months ago )

I'm a sixth form student from an A-level background studying the national curriculum in Bangladesh. One of the topics covered in the syllabus are the aforementioned rules of counting. There are mostly theorems and definitions and proofs in the books. The examples that are there build up on these theorems but I don't understand all of the theorems to begin with.

I found a tree diagram in a Cambridge A level S1 book that explained the permutations of three letters ABC.
Now, from the tree diagram, I understand that for the first position we can have three letters and for the second position we are left with two letters and so on - meaning each of the three main branches have two sub-branches and each of the two sub-branches each have one branch. This shows that there are 3*2*1 arrangements. Extending this concept, they showed that for n unique objects there are n*(n-1)*(n-2)*...*3*2*1 permutations which is denoted by n!.

tl;dr

Can you explain the product rule in layman's terms? I don't understand the part about independence and dependence of events on which the rule being used depends. Please include examples which illustrate the concept. :(

usr_profile.png

User

( 4 months ago )

A product in ordinary arithmetic is just a repeated sum: 3×5=3+3+3+3+33×5=3+3+3+3+3. The same goes for the product rule in combinatorics: it is just a repeated application of the sum rule.

I'm going to assume you're happy with the sum rule: this is the idea that if we're counting things (arrangements, outcomes, whatever) that fall under several non-overlapping cases, we count each case separately, then add them up.

The product rule happens when there are many non-overlapping cases that are counted in the exact same way. In that case, you're going to add them all up, and if there are nn cases and kk outcomes in each case, you're going to get k+k++kn=nkk+k+⋯+k⏟n=nk.

For example, suppose we want to count the number of permutations of the letters A,B,C,D. We split these up into 44 cases: the case where A is first, the case where B is first, the case where C is first, and the case where D is first. Then we notice that each of these cases is identical: in each of them, we have three letters left over, and three slots to place them in. This is a problem you've already solved: there are 321=63⋅2⋅1=6 permutations of A,B,C, so there are 66 permutations of any three letters. If we have 44cases and 66 permutations in each case, then there are 464⋅6 permutations in total.


A large part of the product rule is just becoming familiar enough with this idea that you do it on autopilot. If you want to know the number of 44-letter sequences from the English alphabet, the argument above suggests that you

  1. Split them up into 2626 cases based on the first letter.
  2. Realize that each case is identical: counting the number of 33-letter sequences.
  3. Split up each case into 

what's your interest


forum_ban8_5d8c5fd7cf6f7.gif