• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Discrete Mathematics

Let A be a set of n(n > 0) elements. Let N_B be the number of binary relations on A and let N_F be the number of functions from A to A. a. Give the expression for N_B in terms of n. b. Give the expression for N_F in terms of n. c. Which is larger for all possible n, N_B or N_F?

GATE 2002 · Discrete Mathematics · Relations · medium

Answer: N_B = 2^(n^2); N_F = n^n; N_B >= N_F for all n >= 1, with strict inequality for n >= 2.

  1. Count binary relations N_B: |A x A| = n * n = n^2. A binary relation is any subset of A x A. By the subset-count formula, N_B = 2^(n^2).
  2. Count functions N_F: Functions from A (m = n elements) to A (n elements): N_F = n^n.
  3. Compare N_B and N_F: Compare 2^(n^2) vs n^n. Take logarithm: n^2 * ln(2) vs n * ln(n), i.e. n * ln(2) vs ln(n). For n=1: 1*0.693 vs 0 — N_B=2 >= N_F=1. For n=2: 2*0.693=1.386 vs 0.693 — N_B=16 > N_F=4. For n >= 2, n * ln(2) > ln(n) since ln(2) > 0 and n grows faster than ln(n). Therefore N_B >= N_F for all n >= 1.