Let p(n) denote the number of different equivalence relations on a set with n elements.

Sahil Gupta asked Nov 29, 2014

831 views

2 votes

Solve.
a) Show that $P(n) = \sum_{j=0}^{n-1}C(n-1,j)*P(n-j-1)$ satisfies the recurrence relation and the initial condition p(0) = 1.
b) Find the number of different equivalence relations on a set with n elements, where n is a positive integer not exceeding 10

Set Theory & Algebra
set-theory&algebra
relations

+ –

Sahil Gupta asked Nov 29, 2014

Sahil Gupta

831 views

See all

0 Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Voting & Accepting an answer helps improve the community

← Previous Next →

← Previous in category Next in category →

Related questions

19 votes

2 answers

shree asked Oct 24, 2014

26,376 views

On a set of n elements, how many relations are there that are both irreflexive and antisymmetric?
On a set of n elements, how many relations are there that are both irreflexive and antisymmetric? Please explain how to calculate .

On a set of n elements, how many relations are there that are both irreflexive and antisymmetric?Please explain how to calculate .

shree

26.4k views

shree asked Oct 24, 2014

Set Theory & Algebra
set-theory&algebra
relations

+ –

1 votes

1 answer

SomnathKayal asked Apr 6, 2016

3,739 views

Which of these relations on the set of all functions from Z to Z are equivalence relations?
Which of these relations on the set of all functions from Z to Z are equivalence relations? (a) $\{(f,g) \mid f(1)=g(1)\}$ ... relation. Actually I cannot able to analyze when the relations defined on set of function. If anyone describe a bit it would helpful.

Which of these relations on the set of all functions from Z to Z are equivalence relations?(a) $\{(f,g) \mid f(1)=g(1)\}$(b) $\{(f,g) \mid f(0)=g(0) \text{ or } f(1)=g(1)...

SomnathKayal

3.7k views

SomnathKayal asked Apr 6, 2016

Set Theory & Algebra
set-theory&algebra
relations
functions
equivalence-class

+ –

0 votes

2 answers

nehab.sairam asked Jul 18, 2015

3,269 views

Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s.What will be the time complexity???????

nehab.sairam

3.3k views

nehab.sairam asked Jul 18, 2015

Algorithms
algorithms
sorting
time-complexity

+ –

1 votes

0 answers

Sahil Gupta asked Nov 25, 2014

761 views

Let X be the random variable on the set of permutations of a set of n distinct integers {a 1 , a 2 , . . . , a n } with a1 < a2 < · · · < an such that X(P) equals the number of comparisons used by the bubble sort to put these integers into increasing order.

Answer the following part:a) Show that, under the assumption that the input is equally likely to be any of the n! permutations of theseintegers, the average number of com...