Sample uniformly from sorted monotonic integer sequences Consider all ${x+x-1 \choose x}$ different integer valued sequences $S$ of length $x$ whose elements are from $\{1,\dots,x\}$ and where $S_i \leq S_{i+1}$.     
How can I sample uniformly from this set of sequences?
The simplest possible strategy is to sample each number uniformly and independently from $\{1,\dots,x\}$ and then sort the resulting sequence. However I don't think this gives a uniform sample.
 A: First of all, you're right to presume that your select-and-sort approach can't give a uniform sample: that approach samples from a space of size $n^n$, and since $2n-1\choose n$ doesn't divide $n^n$ for any $n$, it can't be mapped uniformly down to the space you're after.
Fortunately, there is a relatively straightforward way of getting a uniform sample.  Since there's an easy stars-and-bars bijection between the values you're after and size-$n$ subsets of $\{1\ldots 2n-1\}$, I'll speak in terms of the latter problem, but I'll note the mapping back to your set as appropriate.  More generally, we can talk about sampling uniformly from the $n\choose m$ subsets of $\{1\ldots n\}$ of size $m$.  Consider the first element 1; then exactly $\dfrac{n-1\choose m-1}{n\choose m}=\frac mn$ths of the combinations contain this element. What's more, of the combinations that do, the rest of the elements form the ${m-1\choose n-1}$ possible combinations of $m-1$ things from $\{2\ldots n\}$, and the combinations that don't are the ${m\choose n-1}$ possible combinations of $m$ things from $\{2\ldots n\}$.  This means that if we put 1 in our set with probability $\frac mn$ and then update our requirements appropriately, the rest just falls into line.  That gives the following generation algorithm:
n=2x-1; m=x
num_chosen = 0
for (i=1..2x-1)
  if Rand() < m/n
    // i goes in our set - For this problem, we actually add (i-num_chosen) to S
    S[num_chosen]=i-num_chosen
    n = n-1
    m = m-1
    num_chosen = num_chosen+1
  else
    n = n-1

This approach requires $2x-1$ random deviates, but aside from that all of the logic is straightforward. And needing $O(x)$ random numbers shouldn't be a surprise; since ${2x-1\choose x}\approx 4^x$ up to some sub-exponential factors, we should expect to need at least $\lg(4^x)=\Theta(x)$ bits of entropy to generate a uniform random sample.
A: Stepwise Sampling Method
A uniform random selection from the set of such sequences can be constructed stepwise, sampling each element in turn, using an appropriate (often non-uniform) distribution in each step.
Letting $N(m,x)$ denote the number of nondecreasing length-$m$ sequences with elements in $[1..x]$, it follows that  $$N(m,x)=\binom{m+x-1}{m}.$$ 
Thus there are $N(x,x)=\binom{2x-1}{x}$ nondecreasing length-$x$ sequences with elements in $[1..x]$.
The following algorithm (implemented in Sagemath) uses the function $N(m,x)$ to produce the necessary stepwise sampling distributions that generate a uniformly distributed outcome sequence:
def N(m,x): return binomial(m+x-1,m)

def rnd_seq(x):
    seq = []
    a = 1                            # an element will be drawn from [a..x]  
    e = 0                            # e is the index of the selected node
    numer = [N(x,x)]                 # initial list of numerators
    for i in [1..x]:
        denom = numer[e]             # numerator of previously selected node
        numer = [N(x-i, x-a+1-j+1) for j in [1..x-a+1]]
        P = [num/denom for num in numer]   # prob's assigned to resp. elements in [0..x-a]
        G = GeneralDiscreteDistribution(P) 
        e = G.get_random_element()   # random e is uniform on [0..x-a]
        y = e + a                    # shift to make y in [a..x]
        a = y                        # save the current random y
        seq += [y]                   # append y to the sequence
    return seq

This corresponds to a rooted tree with $N(x,x)$ terminal nodes, every node being weighted by the number of terminal nodes for which it is an ancestor. Here's a picture for the case $x=3$:

On my machine the above program requires less than $1$ second per sequence when $x=100$, even though the number of terminal nodes is then $N(100,100)=\binom{199}{100}\approx 10^{58.7}$. 

Rejection Sampling Method (inefficient) 
Without the monotonicity constraint, we can regard each sequence to be the unique bijective base-$x$ notation for an integer between $min=(111...1)_{\text{bijective base-}x}=\frac{x^x-1}{x-1}$ and $max=(xxx...x)_{\text{bijective base-}x}=x\cdot\frac{x^x-1}{x-1}$. To draw a uniform sample from your monotonic subset, we can just repeatedly sample this whole range of integers uniformly until a value, say $v$, in the subset is obtained (discarding any whose bijective base-$x$ notation is not monotonic), then output the bijective base-$x$ notation for $v$. 
