YouKn0wWho's blog

Combinatorics on a Linear Graph
By YouKn0wWho, 4 years ago, In English

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$$$

  • Vote: I like it
  • +22
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

$$$\binom{n-k}{k}$$$

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain a bit, please?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      nvm. I have just found it here. I am so dumb!

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you elaborate it??

    → Reply