Thursday, June 23, 2016

(B4) - Project Euler

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