Expected Number of Connected Components

You are given n points (numbered from 0 to n-1). Between any two distinct points i and j, an undirected edge exists independently with probability \(p_{i,j}\) (with \(p_{i,j} = p_{j,i}\) and \(p_{i,i} = 0\)).

Compute the expected number of connected components in the random graph.

Explanation

A set \(S\) of vertices forms a connected component if:

• The subgraph induced by \(S\) is connected. In other words, there exists a spanning tree in \(S\); mathematically, the probability that \(S\) is connected is \(\Pr(\text{$S$ is connected})\).
• There are no edges connecting any vertex in \(S\) with any vertex outside \(S\). That is, for every \(i \in S\) and \(j \notin S\), an edge between \(i\) and \(j\) appears with probability \(p_{i,j}\), so the probability of no edge is \(1-p_{i,j}\). Hence, the isolation probability of \(S\) is \(\prod_{i\in S,\, j\notin S} (1-p_{i,j})\).

By the linearity of expectation, the expected number of connected components is the sum over all nonempty subsets \(S\) of the probability that \(S\) forms a connected component, i.e.,

[ E = \sum_{\emptyset \neq S \subseteq {0,1,\ldots,n-1}} \Big( \Pr(\text{$S$ is connected}) \times \prod_{i\in S,, j \notin S} (1-p_{i,j}) \Big). ]

</p>

Note: You may assume that \(n\) is small (e.g. \(n \le 15\)) so that an exponential algorithm is acceptable.

inputFormat

The first line contains an integer \(n\) representing the number of nodes.

Then follows \(n\) lines, each containing \(n\) real numbers. The \(j\)-th number in the \(i\)-th line is \(p_{i,j}\) (a real number between 0 and 1) representing the probability that an edge exists between node \(i\) and node \(j\). It is guaranteed that \(p_{i,i} = 0\) for all \(i\) and \(p_{i,j} = p_{j,i}\) for all \(i, j\).

outputFormat

Output a single real number which is the expected number of connected components. Answers within an absolute or relative error of \(10^{-6}\) will be accepted.

sample

1
0.0

1.000000

</p>