Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

Choose $t$ numbers from $n$ $(n>t)$ distinct numbers with replacement and the order of the $t$ numbers matters.

$P(X=1) = \dfrac{{numbers\ of\ unique\ t-set \ which\ has\ 1\ distinct\ number}}{n^t}$ (i.e. $n/n^t$),

$P(X=2)= \dfrac{{numbers\ of\ unique\ t-set \ which\ has\ 2\ distinct\ numbers}}{n^t}$,


$P(X=t) = \dfrac{{numbers\ of\ unique\ t-set \ which\ has\ t\ distinct\ numbers}}{n^t}$,

$P(X>t) = 0$.

For example, $n = 5$ and $t = 3$,
$P(X=1) = \dfrac{5}{125}$,

$P(X=2) = \dfrac{5 \times 4 \times 3}{125}= \dfrac{60}{125}$,

$P(X=3) = \dfrac{5 \times 4 \times 3}{125}= \dfrac{60}{125}$.

It seems to be very complicated for large $t$, is there a formula or even distribution function for that?

Unique means different taking orders into consideration. e.g. (1,1,3) = (1,1,3) but not equal to (1,3,1)

share|cite|improve this question

marked as duplicate by joriki, Jim, Asaf Karagila, Calvin Lin, Erick Wong Mar 16 '13 at 8:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

What do you mean with "unique"? –  Matemáticos Chibchas Mar 15 '13 at 18:41
@MatemáticosChibchas see update –  colinfang Mar 15 '13 at 19:04
I strongly suggest you to change "unique" by "tuple", which is a standard term. –  Matemáticos Chibchas Mar 15 '13 at 20:26
See also –  joriki Mar 15 '13 at 22:50

1 Answer 1

up vote 2 down vote accepted

Let $k$ be such that $1\leq k\leq t$. You want to count the number of $t$-tuples $a=(a_1,\dots,a_t)$, with, say, each $a_i\in\{1,2,\dots,n\}$, such that the unordered set $\{a_1,\dots,a_t\}$ has exactly $k$ elements. But your tuple $a$ can be thought as a function $a:\{1,\dots,t\}\to\{1,2,\dots,n\}$ (which sends each number $i$ to the number $a_i$), so what you want to count is the number of functions $f:\{1,\dots,t\}\to\{1,\dots,n\}$ such that the image of $f$ has exactly $k$ elements.

How to count these functions? first, choose the "target" $k$-subset of $\{1,\dots,n\}$, say $A$. This can be made in $\binom nk$ ways. Now for this set $A$ you want to count all the surjective functions from $\{1,\dots,t\}$ onto $A$, which in turn can be made in $k!\,\begin{Bmatrix} t\\ k \end{Bmatrix}\,$ ways, where $\begin{Bmatrix} \vphantom{} \\ \vphantom{} \end{Bmatrix}$ denotes the Stirling numbers of the second kind; see here for an explanation. Therefore the total number of desired functions is

$$k!\,\binom nk\begin{Bmatrix} t\\ k \end{Bmatrix}\,.$$

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.