Question

In: Computer Science

Why the recursion in Pascal's Triangle is also the recursion for counting sub-sets.

Why the recursion in Pascal's Triangle is also the recursion for counting sub-sets.

Solutions

Expert Solution

If we closely look at the numbers of any row of Pascal's Triangle

For example row 6:

The fisrt value, second value........  till sixth value of row 6 are

In case of counting subsets

Number of subsets of size 1 in a set of 5 values:

Number of subsets of size 2 in a set of 5 values:

Number of subsets of size 3 in a set of 5 values:

Number of subsets of size 4 in a set of 5 values:

Number of subsets of size 5 in a set of 5 values:

Hence we can see that both the recursive program calculates nCr values. Therefore the recursive program in both the cases is same.

venereology answered 2 days ago
Next > < Previous

Related Solutions

Rewrite your program for finding Pascal's Triangle to use iteration (loops) instead of recursion. Include in...
Rewrite your program for finding Pascal's Triangle to use iteration (loops) instead of recursion. Include in both algorithms code to keep track of the total time used to run the algorithms in milliseconds. Run these algorithms for n = 10, n = 20, and n = 30. Print out both the original output and the time to run for both algorithms. Please make sure you comment your code thoroughly. The code should be nicely formatted and should use proper variables.
(x+5y)^21 expand using Pascal's triangle
(x+5y)^21 expand using Pascal's triangle
Answer the following using Binomial theorem and Pascal's Triangle: a. Find the middle term in the...
Answer the following using Binomial theorem and Pascal's Triangle: a. Find the middle term in the expansion of (4x – x3)14 b. Use Pascal’s triangle to expand (3x + 2y)6.
For each of the following sets, prove that thay are convex sets or not. Also graph...
For each of the following sets, prove that thay are convex sets or not. Also graph the sets. a) ? 1= {(?1 , ?2 ): ?1 ^2 + ?2^2 ≥ 1} b)?2 = {(?1 ,?2 ): ?1 ^2 + ?2^ 2 = 1} c)?3 = {(?1 , ?2 ): ?1 ^2 + ?2 ^2 ≥ 1}
Write a three.js/HTML programming to generate a Sierpenski Triangle using recursion (generate until 10 depth of...
Write a three.js/HTML programming to generate a Sierpenski Triangle using recursion (generate until 10 depth of recursion) Need the index code with it too so I am able to run it Example of triangle below:
Write a three.js/HTML programming to generate a Sierpenski Triangle using recursion (generate until 10 depth of...
Write a three.js/HTML programming to generate a Sierpenski Triangle using recursion (generate until 10 depth of recursion) Need the index code with it too so I am able to run it
java create a class for triangle and also driver(area and perimeter) also write its getters and...
java create a class for triangle and also driver(area and perimeter) also write its getters and setters for the right triangle
Recursion Discussions Question: Why would you want to use recursion? Concerning programming, when would you want...
Recursion Discussions Question: Why would you want to use recursion? Concerning programming, when would you want to use iterative vs. recursive programming? Where does coding fit in concerning the software process (i.e. its use in design, in coding, etc.)? Describe recursion problems, and why does it seem to fit with recursion? (e.g. nature, math, music, sports game, etc.)  
Identify the 3 elements of the fraud triangle and explain how they work. Also, using the...
Identify the 3 elements of the fraud triangle and explain how they work. Also, using the internet provide an example of fraud discovered by external auditors and try to identify the red flags related to the fraud.
let A= {1,2} and C={8,9}. for each i=1,2, construct sets B sub i as well as...
let A= {1,2} and C={8,9}. for each i=1,2, construct sets B sub i as well as functions f sub i: A to B sub I, 1<=i<=4, with the following properties: 1) g sub 1 ° f sub 1 is onto C but f sub 1 is not onto B sub I. 2) g sub 2° f sub 2 is one-to-one but g sub 2 is not one-to-one.
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT