My very own Project Euler problem was published a couple months ago! Another wording of the problem goes as follows. Suppose we have a graph where each vertex represents a distinct nonempty subset of $\{1,2,...,n\}$. We then draw an edge between two vertices $iff$ their intersection is nonempty. For example, for $n=10$, one possible graph is the following.
We notice that there are 2 connected components. Let $G(n,c)$ be the number of such graphs (given n) with exactly c connected components. Find $G(10^4,10) \mod 1,000,000,007$.
You can check your answer on the PE website
problem 553.
No comments:
Post a Comment