Awesome q2a theme
0 votes
Let $n$, $m$ and $k$ be three positive integers such that $n \geq m \geq k$. Let $S$ be a subset of $\{1, 2, …, n\}$ of size $k$. Consider sampling a function uniformly at random from the set of all functions mapping $\{1, …, n\}$ to $\{1, …, m\}$. What is the probability that $f$ is not injective on the set S, i.e., there exists $i, j \in S$ such that $f(i) = f(j)$?

In the following, the binomial coefficient $n\choose k$ counts the number of $k$-element subsets of an n-element set.

(A) $1 – \frac{k!}{k^k}$

(B) $1 – \frac{m!}{m^k}$

(C) $1 – \frac{k!{m\choose k}}{m^k}$

(D) $1 – \frac{k!{n\choose k}}{n^k}$

(E) $1 – \frac{k!{n\choose k}}{m^k}$
in Combinatory by (3.6k points) | 4 views

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
9,200 questions
3,182 answers
96,168 users