Let A be the set of all arrays of length n in non-decreasing order with entries from the set {1,..,n}.
Let B be the set of all arrays of length n in increasing order with entries from the set {1,...,2n-1}.
Let f be a function such that f : A->B and f(x)=y, where y [ i ] = x [ i ] + i, for all i in {0, ..., n-1}.
First let us show that y=f(x) is in B. y is of length n and minimum of y[i](i in {0,...,n-1}) is minimum of x[0] which is 1
and maximum of y[i](i in {0,...,n-1}) is x[n-1]+n-1 which is n+n-1=2n-1. So y is in B.
Let us show that f is bijective.
First let us show that f is injective.
Let x1, x2 be in A and x1!=x2. x1!=x2 implies that there is an i in {0, .., n-1} such that x1[i]!=x2[i] or equivalently
x1[i]+i!=x2[i]+i or f(x1)!=f(x2). So f is injective.
Now let us show f is surjective.
Given y in B and we take x such that x [ i ] = y [ i ] - i, for all i in {0,...,n-1}
we can notice that x is in A(x is of length n and x[i] is in {1,...,n} for al i in {0,...,n-1} because minimum of x[i] is 1 and maximum is n ( don't forget that y is increasing )).
So f is surjective.
Thus f is bijective.
A and B are finite so they have the same number of elements.
We need to find the number of elements in A because the answer we are looking for is the cardinal of the set of arrays A union with the set of all arrays in A in reverse order(let's denote it by R).
Notice that |A|=|R| and that |A union R| = |A|+|R|-|A intersection R|. A intersection R is the set of constant arrays and |A intersection R| is n.
So the answer is 2*|A|-n.
But |A| = |B| and B is the set of all increasing arrays of length n with entries from{1,..,2n-1}.
So the answer is the binomial number. So |A|=|B|=((2n-1)!)/((n!)*((n-1)!)).
Thus the final number is 2*(((2n-1)!)/((n!)*((n-1)!)))-n. Notice that you need modular arithmetic inverse to compute the binomial number.
The computation of the modular inverse can be done in O(log n) by using Fermat theorem or gcd properties.

I read once the part with the bijective function in combinatorics book written by Ioan Tomescu and it stuck to my mind. You are welcomed!