Notes on Tree

Some of the notes while I read about trees from chapter 9 - Trees in the book "Discrete Mathematics and Its applications" by Rosen ....




\

Discrete Maths, ProblemSet#7

These are my solutions to 7th problem set of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

Here are my solutions....

Graph Theory Notes

Some of the notes while I read about graphs from chapter 8 - Graphs in the book "Discrete Mathematics and Its applications" by Rosen ....

Discrete Maths, Lecture-20 : Cryptography

These are my notes from 20th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

This lecture covers the basic number theory background needed to understand RSA algorithm and shows analysis of how and why RSA encryption/decryption works.

Here are my notes...

Discrete Maths, Lecture-18 : Euclid's Algorithm

These are my notes from 18th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

Here are my notes...

Discrete Maths, ProblemSet#6

These are my solutions to 6th problem set of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

Discrete Maths, Lecture-16 : Generating Functions - II

These are my notes from 16th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

Here are my notes...

Discrete Maths, Lecture-15 : Generating Functions

These are my notes from 15th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

This lecture covers Generating Functions(a way to represent sequences), their usage in solving some counting problems and recurrance equations.

Here are my notes...

Discrete Maths, Lecture-14 - Discrete Probability

These are my notes from 14th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

This lecture introduces basic discrete probability, mainly the two things..

1. P(A) = #of favorable cases where A happen / total # of cases

2. Probability of A, given B has happened

P(A|B) = P(A /\ B) / P(B)

Here are my notes...

Discrete Maths, ProblemSet#5

These are my solutions to 5th problem set of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

Doing this problem set makes me realize that One needs to continually practice solving counting problems to learn permutation-combination properly by heart, it really becomes confusing pretty quickly for not-so-trivial cases.

Anyway, Here are my solutions...

Discrete Maths, Lecture-13 : Counting-III

These are my notes from 13th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

This lecture covers following topics..
1. Inclusion-Exclusion principle (a generalization of sum rule using same theorem from set theory)
2. Pigeonhole Principle
3. Derrangement Problem

Here are my notes...

Discrete Maths, Lecture-12 : Counting-II

These are my notes from 12th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

This lecture covers generalized permutation and combinations (that basically means repetition is allowed). Though there are "formulae" presented for each case but more emphasis is(and should be) given to how we can think and solve the problems of generalized permutation and combinations using the already covered 5 principles and simple permutation/combination. The intention of this lecture is not to give you the formula but to teach you how you reach to them.

Here are my notes...

combination formula and recursion

Today, while solving some problems in counting I tried to relate the combination formula and recursion.
The idea is, can we derive combination formula using recursion?

Let us start with a particular case.

How many ways can we make groups of 2 out of n people?

Let T(n) be the answer for n people.
Let us think wishfully and see if we can get to solution for n when solution for n-1 is known.

[n]	[# of pairs]	[pairs]
2 - A,B	1	(A,B)
3 - A,B,C	3	(A,B);(B,C);(C,A)
4 - A,B,C,D	6	(A,B);(B,C);(C,D);(D,A);(A,C);(B,D)

From above table, it is easy to observe that
T(n) = T(n-1) + (n-1)
We can solve this recurrence using substitution and see that
T(n) = n(n-1)/2
which is indeed (n combination 2).

How many ways can we make group of k ppl out of n ppl?

Let it be denoted by T(n,k).
Clearly, T(k,k) = 1
We can apply the process as in above case by solving for T(n,3), T(n,4) etc and easily see that
T(n,k) = T(n-1, k) + T(n-1, k-1)

Discrete Maths, Lecture-11 : Counting-I

These are my notes from 11th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

In Summary, this lecture covers following things...

• 5 important principles of counting(2 official and 3 unofficial ones) namely Multiplication principle, Addition principle, Counting the Opposite, Counting double and Just another principle.
• Permutation and Combination(and its relation to Binomial coefficients)
• Interesting observations of Pascal's triangle
• Ways to prove theorems using counting arguments.

A general thing that always helped is that when you're solving some general case n, observe the behaviour for small values of n such as 1,2,3 etc .. this gives good insight/understanding into the problem.

Here are my notes....
Note: Unless specified otherwise, in these notes n objects implicitly mean n distinct objects.