I started by considering the graph of $y=_nC_x$ - illustrated above.
I then looked at the natural logarithm - after all, Stirling's formula gives factorials as powers.
This curve looks like a quadratic, so I tried to fit a quadratic of the form $y=x(n-x)$.
You can see that this is not quite right. I therefore tried variations of the form $y=\left(x(n-x)\right)^p$ until I found a good fit with $p={3 \over 4}$
I don't know why this works, but it seems to. I'll now work on creating an inverse function, which should be quite easy.
We have the relationship $\ln(_nC_k) \approx ak^{3 \over 4}(n-k)^{3 \over 4}$
where $a=\frac{\ln\left(_nC_{n \over 2}\right)}{\left({n \over 2}\right)^{3 \over 4}\left({n \over 2}\right)^{3 \over 4}}$
$k^{3 \over 4}(n-k)^{3 \over 4}=\frac{\ln\left(_nC_k\right)}a $
$k(n-k)=\left(\frac{\ln\left(_nC_k\right)}a\right)^{4 \over 3} $
Let's call this $k(n-k)=b$, where $b=\left(\frac{\ln\left(_nC_k\right)}a\right)^{4 \over 3} $
Then $kn-k^2=b$ can be rewritten $k^2-kn+b=0$
$k_1=\frac{n-\sqrt{n^2-4b}}{2}$
$k_2=\frac{n+\sqrt{n^2-4b}}{2}$
I've tested this and the values it gives for $k$ are pretty close - probably only need to test integers one or two above and below the value of $k_1$.
I would really appreciate an explanation of why this works!
An explanation, why this works by Alex Ravsky.
By Stirling’s formula, for each natural $m$ there exists a number $0<\theta<1$ such that $$m!=\sqrt{2\pi m}\left(\frac me\right)^m e^{\frac \theta{12m}}.$$ Thus
$$\ln(m!)=\tfrac12(\ln 2+\ln\pi+\ln m)+m(\ln m - 1)+O\left(\frac {1}{m}\right).$$
Let $k=\lambda n$ for $0<\lambda<1$. Then
$$\ln {n \choose k}=\ln \frac{n!}{k!(n-k)!}=$$
$$n(\ln n-1)- k(\ln k-1)-(n-k)(\ln (n-k)-1)+\frac 12(\ln n-\ln k-\ln (n-k))+O(1)=$$
$$n\ln n- k\ln k-(n-k)\ln (n-k)+\frac 12(\ln n-\ln k-\ln (n-k))+O(1)=$$
$$n\ln n- \lambda n (\ln\lambda+\ln n) -(1-\lambda)n(\ln(1-\lambda)+\ln n)+
\frac 12(\ln n-\ln\lambda-\ln n-\ln (1-\lambda)-\ln n)+O(1)=$$
$$ - \lambda n \ln\lambda -(1-\lambda)n\ln(1-\lambda)-\frac 12(\ln n+\ln\lambda+\ln (1-\lambda))+O(1)=$$
$$\left(n-\frac 12\right)f(\lambda)-\frac 12\ln n+O(1),$$
where $f(\lambda)=- \lambda \ln\lambda -(1-\lambda) \ln(1-\lambda) $.
The graphs below suggest that a function $g(\lambda)=2\sqrt{2}\ln (2)(\lambda(1-\lambda))^{3/4}$ is an extremely good approximation of $f(\lambda)$.
PS. Maybe we also can similarly obtain approximations of $\ln CR(n,k)$ and $\ln P(n,k)$ using some functions depending on $\lambda=k/n$. Remark that for $CR(n,k)$ case we allow $\lambda>1$.
Note that
\begin{align}
(1+x+\ldots+x^{2n})^2 &= \sum_{i=0}^{n}x^{2i}+2\sum_{i=1}^{2n}x^i+2x\sum_{i=2}^{2n}x^i+\ldots2x^{2n-1}x^{2n}\\
&=\sum_{i=0}^{n}x^{2i}+2\sum_{j=0}^{2n-1}\left(x^j\sum_{i=j+1}^{2n}x^i\right).
\end{align}
So, we have
\begin{multline}
(1+x+\ldots+x^{2n})^2 (x+x^3+\ldots) \\=\left[ \sum_{i=0}^{n}x^{2i} \right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]+2\sum_{j=0}^{2n-1}\left[\sum_{i=j+1}^{2n}x^{i+j}\right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]
\end{multline}
We find the coefficient of $x^{3n}$ in the above expression for two separate cases:
Case 1: $n$ is odd
$x^{3n}$ in $\left[ \sum_{i=0}^{n}x^{2i} \right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$ is due to the terms corresponding to
\begin{equation}
(2i,2k-1)=(0,3n), (2,3n-2), \ldots, (3n-1,1).
\end{equation}
Thus, the coefficient of $x^{3n}$ = $\frac{3n+1}{2}$.
For $j$ odd, $x^{3n}$ in $2\left[\sum_{i=j+1}^{2n}x^{i+j}\right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$ is due to the terms corresponding to
\begin{equation}
(i+j,2k-1)=(2j+2,3n-2j-2), (2j+4,3n-2j-4), \ldots, (2n+j-1,n-j+1),
\end{equation}
for $i+j\leq 3n-1$ and $j\leq\frac{3n-1}{2}-1$. Thus, the coefficient of $x^{3n}$ is given by
\begin{equation}
\min\{3n-2j-1,2n-j-1\} = \begin{cases}
2n-j-1&\text{ for } 1\leq j\leq n\\
3n-2j-1&\text{ for } n< j\leq \frac{3n-1}{2}-1
\end{cases}
\end{equation}
For $j$ even, $x^{3n}$ in $2\left[\sum_{i=j+1}^{2n}x^{i+j}\right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$ is due to the terms corresponding to
\begin{equation}
(i+j,2k-1)=(2j+2,3n-2j-2), (2j+4,3n-2j-4), \ldots, (2n+j,n-j),
\end{equation}
for $i+j\leq 3n-1$ and $j\leq\frac{3n-1}{2}-1$. Thus, the coefficient of $x^{3n}$ is given by
\begin{equation}
\min\{3n-2j-1,2n-j\} = \begin{cases}
2n-j&\text{ for } 1\leq j\leq n-1\\
3n-2j-1&\text{ for } n-1< j\leq \frac{3n-1}{2}-1
\end{cases}
\end{equation}
Thus, the required coefficient is given by
\begin{equation}
\frac{3n+1}{2}+\sum_{j=0}^{\frac{3n-1}{2}-1}(2n-j)+\sum_{j=n}^{\frac{3n-1}{2}-1}(n-j-1) - \frac{n-1}{2} = \frac{7n^2+6n+3}{4}.
\end{equation}
Case 2: $n$ is even
$x^{3n}$ does not appear in $\left[ \sum_{i=0}^{n}x^{2i} \right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$. Thus, the coefficient of $x^{3n}=0$.
For $j$ odd, $x^{3n}$ in $2\left[\sum_{i=j+1}^{2n}x^{i+j}\right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$ is due to the terms corresponding to
\begin{equation}
(i+j,2k-1)=(2j+1,3n-2j-1), (2j+3,3n-2j-3), \ldots, (2n+j,n-j),
\end{equation}
for $j+i\leq 3n-1$ and $j\leq \frac{3n}{2}-1$. Thus, the coefficient of $x^{3n}$ is given by
\begin{equation}
\min\{3n-2j,2n-j+1\} = \begin{cases}
2n-j+1&\text{ for } 1\leq j\leq n-1\\
3n-2j&\text{ for } n-1<j\leq \frac{3n}{2}-1
\end{cases}
\end{equation}
For $j$ even, $x^{3n}$ in $2\left[\sum_{i=j+1}^{2n}x^{i+j}\right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$ is due to the terms corresponding to
\begin{equation}
(i+j,2k-1)=(2j+1,3n-2j-1), (2j+3,3n-2j-3), \ldots, (2n+j-1,n-j+1),
\end{equation}
for $j+i\leq 3n-1$ and $j\leq \frac{3n}{2}-1$. Thus, the coefficient of $x^{3n}$ is given by
\begin{equation}
\min\{3n-2j,2n-j\} = \begin{cases}
2n-j&\text{ for } 1\leq j\leq n\\
3n-2j&\text{ for } n<j\leq \frac{3n}{2}-1
\end{cases}
\end{equation}
Thus, the required coefficient is given by
\begin{equation}
\sum_{j=0}^{\frac{3n}{2}-1}(2n-j)+\sum_{j=n+1}^{\frac{3n}{2}-1}(n-j) + n/2 = \frac{7n^2+6n}{4}.
\end{equation}
Overall, the number of possibilities is $\frac{7n^2+6 n+3\alpha}{4}$, where
\begin{equation}
\alpha = \begin{cases}
1, & \text{if } n \text{ is odd}\\
0, & \text{if } n \text{ is even}
\end{cases}
\end{equation}
P.S.: Thanks for introducing the technique of solving using enumerators to me.
Best Answer
Seems like I've managed to find an interpretation.
I initially though that permutation defines a strict ordering of $K$ numbers, but that leads into nowhere.
Let's denote $\{a_i\}$ as the sequence of chosen $K$ elements. Then the sequence corresponds to a permutation $p$ if $a_{p_i} \lt a_{p_j}$, for $i \lt j$, i.e. the position of $k$-th smallest element is $p_k$. It's easy to see that the $LIS$ is preserved: $$i \lt j, p_i \lt p_j \implies a_{p_i} \lt a_{p_j}$$. If we didn't allow repetition, then $\binom{N}{K}$ would count the number of ways to choose a sequence that corresponds to a given permutation as we already know the order of chosen numbers — assign smallest of them to $a_{p_1}$, second smallest to $a_{p_2}$, etc.
Now, if we have a descent, that is $p_i \gt p_{i + 1}$, we can ease the requirement of $a_{p_i} \lt a_{p_{i + 1}}$ to that of $a_{p_i} \le a_{p_{i + 1}}$ because the two elements will never belong to some increasing subsequence in both cases, and, on the other hand, $a_{p_{i + 1}}$ can still be in all increasing subsequences it used to be as it can only become equal to — and never less than, due to construction — the previous element in the subsequence only if we have a descending run, but any two elements in a descending run can never be in some increasing subsequence.
Now, suppose that we have only one descent $p_i \gt p_{i + 1}$. Then there are $$\binom{N}{K}+\binom{N}{K-1} = \binom{N+1}{K}$$ ways to choose a sequence — first summand corresponds to the case where all numbers distinct, and the second one corresponds to the case where $a_{p_i} = a_{p_{i + 1}}$.
If we had two descents, there would be $$\binom{N}{K}+2\binom{N}{K-1} + \binom{N}{K-2} = \binom{N+2}{K}$$ ways. Since there are two ways to choose either descent we count the second summand twice.
In general, for a permutation with $d$ descents the sum is $$\sum_{i=0}^{d}\binom{d}{i}\binom{N}{K-i}=\binom{N+d}{K}$$
The equality is precisely the Vandermonde's identity, thanks to @Phicar for pointing it out.
Since every possible subset of descent indices is contained in at least one permutation (not sure about it; it's a claim by intuition), we can indeed map a permutation to some subset of weak orderings of $K$ elements — a permutation with $d$ descents maps to some subset of cardinality $2^{d}$.
I've also checked programmatically that $$\sum_p 2^{d} = \text{Fubini number}$$. So it seems that a bijection I looked for is indeed established, that is, a bijection between the set of permutations of $K$ numbers and a partition of a set of weak ordering of $K$ elements that preserves $LIS$.
It's a pity that many claims in this post seem to rely on intuition and checking small cases with a computer program, for I lack knowledge and skills to make a rigorous explanation.
To sum up. I think the matter is closed only after there is a rigorous proof of the last two summation identities.