Find the number of ways to select $$$k$$$ non-intersecting edges from a linear graph with $$$n$$$ nodes. In a linear graph every $$$i$$$ and $$$(i - 1)$$$ is connected by an undirected edge for each $$$i$$$ from $$$2$$$ to $$$n$$$.
Two edges intersect if they share some node. Two ways are different if there is some edge which is selected in one way but in the other.
Constraints: $$$1 \leq k < n \leq 10^5$$$
$$$\binom{n-k}{k}$$$
Can you explain a bit, please?
nvm. I have just found it here. I am so dumb!
After selection you can contract the $$$k$$$ edges. Then there are $$$n-k$$$ vertices left, and we just have a size-$$$k$$$ subset of these $$$n-k$$$ vertices.
can you elaborate it??