1
$\begingroup$

You have been given a set of characters of size $k$ and you have to make strings of length $n$. How many strings are possible. A constraint is that every character must be used at least once in each such strings. For $n = k$ the answer is $k!$ I wanted it to generalize it for $k\leq n$, but i havent come up with any solution to it yet.

$\endgroup$
  • $\begingroup$ Use Inclusion/Exclusion. For more details, please see Stirling numbers of the second kind, and the Twelvefold Way (onto functions from an $n$-element set to a $k$-element set). $\endgroup$ – André Nicolas Dec 26 '14 at 21:05
1
$\begingroup$


Hi, you can treat a word $x=x_1x_2\ldots x_n$ as a function $f:[n]\longrightarrow [k]$ where $x_i=f(i)$. So if you want that at least $1$ character, say $x_j$, to be equal to a symbol $a\in [k]$ for every symbol $a$, then you are looking for surjective functions. As a hint try to calculate all functions between $[n]=\{1,2,\ldots ,n\}$ and $[k]=\{1,2,\ldots ,k\}$and take out the ones that are not surjective (i.e. there exists $a\in [k]$ such that there is no $i\in [n]$ with $f(i)=a$).
Hope it helps.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ ah how poor math class we had. what are surjective functions $\endgroup$ – Faiz Halde Dec 26 '14 at 21:09
  • $\begingroup$ Hi, those are functions $f:X\longrightarrow Y$ such that for every single $y\in Y$ there is an $x\in X$ such that $f(x)=y$. In other words, the function $f$ goes to every possible element of $Y$. $\endgroup$ – Phicar Dec 26 '14 at 21:11
  • 1
    $\begingroup$ (Surjective functions are also known as onto functions.) $\endgroup$ – apnorton Dec 26 '14 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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