I have a random walk on $\mathbb{Z}$ with starting point $0$ and with length $n$ and possible steps to right, left or stay where you are, all with the same probabilities. I am interested in exact probability that the walk will visit $k$ distinct values.


I think this should be known but I cannot find such result.



Range of random walk
Just an addition to Pablo Lessa's comment. If probability to stay at a point is zero, then you have a simple random walk and the Reflection Principle is valid. So, your question will follow if you find the joint distribution of the maximum and minimum, as the simple random walk visits all points between them. The exact formula for the joint distribution of the maximum and minimum can be found in e.g. book of Billingsley, Convergence of probability measures, Chapter 2.11. The question can also be reformulated as the distribution of the first exit time from an interval [-a,b]. Then, another reference (for the zero-mean random walk) is this paper <http://dx.doi.org/10.1214/aoms/1177706262> of Kemperman, Asymptotic expansions for the Smirnov test for the range of cumulative sums. Ann. Math. Statist. 30 1959 448–462. The more general case (when probability to stay at 0 is greater than 0) can be treated similarly to the above references. 


