Probability of getting all elements of S in x y-long subsets of samples drawn from permutations of S? Full disclosure: I am a computer science student, so I am not exactly a math academic, but I started to think about this question yesterday and since I am stuck I can't think of a better place to go for help to. 
The problem is as follows:
We start with some set $A$ which has $n$-elements. Then we consider a set $B$ - of all $n$-length permutations of $A$. Then we draw $x$ samples from the set $A$ (with replacement!). Then we consider only first $y$-elements of every sample we have drawn. What is the probability that in the sum of all our $y$-length samples there are all elements of the initial set $A$?
Example:
$A = \{a,b,c\}, x = 3, y = 2, B = \{abc,acb,bca,bac,cab,cba\}$. Now we draw $3$ times from $B$. Let's say I got $abc, bca, acb$. I look at first two elements $(ab,bc,ac)$ and this time I got every element of $A$. But of course, I easily could not.
What would be the general formula $f(n,x,y)$ for calculating this probability? 
I can't wrap my head around counting all satisfying combinations within $n^x$ space...
I sincerely hope this will not be considered as spam ;)
 A: I'd consider this an inclusion/exclusion question- we want to find the probability that our set of first $y$ elements is missing some element, then the chance that it is missing two elements and so on. Say, for example, that our set of first $2$ elements is missing $a$. Each of the permutations we pick then must start with either $bc$ or $cb$. There is one permutation starting with $bc$ (namely $bca$) and one starting with $cb$ (namely $cba$). So everytime we pick something from $B$, it must be one of those $2$. $|B|=6$ ($B$ has $6$ elements, if you're not familiar with the notation), so there is a $1/3$ chance we pick one of those permutations. Since $x=3$, we must do this $3$ times, so there is a $1/27$ chance that our set of first $2$ elements does not contain $a$. This same process holds for $b$ and $c$, so for each element, there is a $1/27$ chance of not getting it.
Now, in most cases of inclusion exclusion, we would need to subtract the probability of missing elements $a$ and $b$, since the two could overlap, and the same for every other two element combination, then add back the probability of missing all $3$. However, it is impossible in this case to miss more than one element, since the first two elements of a permutation are always different. So $3/27=1/9$ is the probability of not getting every element in this case, so you have an $8/9$ chance to get every element.
In general, let $f(n,x,y)$ denote the number of ways to not have every element with $n,x,y$ as before. If we're missing $i$ different elements, then the number of permutations we can choose from is ${n-i\choose y}y!(n-y)!$. This is because there are $n-i$ elements we can use for the first $y$ elements, $y!$ ways to organize them (note that we can simplify this to the number of permutations of $y$ elements chosen from $n-i$ elements, or $(n-i)_{y}$, called $n-i$ falling factorial $y$. We then must organize the remaining $n-y$ elements, which can be done $(n-y)!$ ways. Then, we must pick one of these ${n-i\choose y}y!(n-y)!$ permutations $x$ times, so the number of ways of doing that is found by its $x$-th power.
Then $f(n,x,y)=\sum_{i=1}^{n} (-1)^{i-1}{n\choose i}({n-i \choose y}y!(n-y)!)^x$. The part about summation and $(-1)^{i-1}$ are just parts of inclusion-exclusion, but the idea is that we could be missing any single element. The number of ways we miss $a$ also includes the number of ways we miss $a$ and $b$. The number of ways we miss $b$ also includes the number of ways we miss $a$ and $b$, so we double count, and we have to subtract it out. However, this leads to more double counting- again, you really need inclusion exclusion to get this. $i$ refers to how many elements we miss, and $n\choose i$ counts how many ways to miss $i$ elements. We can miss any from $1$ to $n$ elements (though the case where $i=n$ can only make sense if $y=0$. When it doesn't "make sense", we'll get $y>n-i$ and ${n\choose n-i}=0$ by the convention that when $k>n$, ${n\choose k}=0$).
To find the probability, we can then just divide this by the total number of ways to pick permutations from $B$, which is $|B|^x$. But $|B|=n!$ so this is $(n!)^x$.
EDIT: You can also say that $f(n,x,y)$ finds the probability by changing the equation to $f(n,x,y)=\sum_{i=1}^{n} (-1)^{i-1}{n\choose i}(\frac{{n-i \choose y}y!(n-y)!}{(n!)})^x$. This is obviously the same as just dividing the whole sum by $(n!)^x$, but you can interpret $(\frac{{n-i \choose y}y!(n-y)!}{n!})^x$ as the probability of picking a word missing $i$ elements.
