Counting Labeled Single Graphs

A simple directed graph on n vertices is an oriented graph with no self‐loops and no multiple edges. Two simple directed graphs \(G\) and \(H\) are said to be essentially identical if and only if for every ordered pair of vertices \((u,v)\), \(v\) is reachable from \(u\) in \(G\) if and only if \(v\) is reachable from \(u\) in \(H\) (here reachability means there exists a directed path, possibly of length \(\ge 1\), from \(u\) to \(v\)).

We call a simple directed graph \(G\) a single graph if there does not exist any other simple directed graph \(H\) (with \(H \neq G\)) that is essentially identical to \(G\). In other words, \(G\) is the unique representative in its equivalence class defined by the reachability relation.

It can be shown that \(G\) is a single graph if and only if for every two distinct vertices \(u\) and \(v\) the following holds: \[ u \leadsto v \iff (u,v) \text{ is a direct edge in } G. \] This condition forces that no directed path of length \(2\) or more exists. Equivalently, no vertex can act both as the tail of one edge and as the head of another edge. Thus, if we partition the vertex set into three parts:

• \(T\): vertices that only emit edges (and have no incoming edges),
• \(H\): vertices that only receive edges (and have no outgoing edges),
• \(I\): isolated vertices (with no incident edges),

all edges, if any, must go from a vertex in \(T\) to a vertex in \(H\). For given sizes \(|T| = a\), \(|H| = b\) and \(|I| = c\) with \(a+b+c=n\), the number of choices for the partition is \(\binom{n}{a}\binom{n-a}{b}\) and the number of ways to choose the edges is \(2^{a\cdot b}\) (each potential edge from \(T\) to \(H\) may be either present or absent). Hence, the total number of labeled single graphs on \(n\) vertices is given by

[ S(n)= \sum_{a+b+c=n} \binom{n}{a}\binom{n-a}{b} 2^{a\cdot b}. ]

Your task is to answer \(T\) independent queries. In each query you are given a positive integer \(n\) and you must output \(S(n)\), the number of labeled single graphs on \(n\) vertices.

inputFormat

The first line contains a single integer \(T\) (the number of queries). Each of the following \(T\) lines contains a single positive integer \(n\) representing the number of vertices.

For example:

2
1
2

outputFormat

For each query, output the number of labeled single graphs on \(n\) vertices on a separate line.

For the sample input above, the output should be:

3
11

sample

1
1

3