MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 deleted 12 characters in body

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication. They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$. An elegant technique in this area is the so-called colour-coding method.

Edit 1. A partial answer to unknown's question is that, $k \in T_n$ for all $k \leq n^{3/2}$ ($n$ large). To see this choose $j$ maximal such that $\binom{j}{3} \leq k$. By making a clique on $j$ vertices, and then taking a disjoint union of triangles on the remaining vertices, we can make a graph with exactly $k$ triangles provided $k-\binom{j}{3} \leq \frac{n-j}{3}$. After some number crunching, this is possible provided $k \leq n^{3/2}$.

Edit 2. Here is a some information for $k$ which are not in $T_n$. As Gerhard mentionsnotes, removing an edge from $K_n$ destroys exactly $n-2$ triangles. Thus, $\binom{n}{3} - t \notin T_n$ for all $t=1, \dots, n-3$. The next triangle-densest graph is obtained by removing two incident edges, which destroys $2n-5$ triangles. Thus, $\binom{n}{3} - t \notin T_n$, for $t=n-1, n, \dots, 2n-6$. The next two densest triangle-densest graph graphs are obtained by removing a matching of size 2, which destroys $2n-4$ triangles, or the edges of a triangle, which destroys $3n-8$ triangles. Thus, $\binom{n}{3}-t \notin T_n$ for $t=2n-3, 2n-2, \dots, 3n-9$.

3 added 661 characters in body

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication. They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$. An elegant technique in this area is the so-called colour-coding method.

Edit 1. A partial answer to unknown's question is that, $k \in T_n$ for all $k \leq n^{3/2}$ ($n$ large). To see this choose $j$ maximal such that $\binom{j}{3} \leq k$. By making a clique on $j$ vertices, and then taking a disjoint union of triangles on the remaining vertices, we can make a graph with exactly $k$ triangles provided $k-\binom{j}{3} \leq \frac{n-j}{3}$. After some number crunching, this is possible provided $k \leq n^{3/2}$.

Edit 2. Here is a some information for $k$ which are not in $T_n$. As Gerhard mentions, removing an edge from $K_n$ destroys exactly $n-2$ triangles. Thus, $\binom{n}{3} - t \notin T_n$ for all $t=1, \dots, n-3$. The next triangle-densest graph is obtained by removing two incident edges, which destroys $2n-5$ triangles. Thus, $\binom{n}{3} - t \notin T_n$, for $t=n-1, n, \dots, 2n-6$. The next two densest triangle-densest graph are obtained by removing a matching of size 2, which destroys $2n-4$ triangles, or the edges of a triangle, which destroys $3n-8$ triangles. Thus, $\binom{n}{3}-t \notin T_n$ for $t=2n-3, 2n-2, \dots, 3n-9$.

2 added 468 characters in body; deleted 15 characters in body

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication. They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$. An elegant technique in this area is the so-called colour-coding method.

Edit. A partial answer to unknown's question is that, $k \in T_n$ for all $k \leq n^{3/2}$ ($n$ large). To see this choose $j$ maximal such that $\binom{j}{3} \leq k$. By making a clique on $j$ vertices, and then taking a disjoint union of triangles on the remaining vertices, we can make a graph with exactly $k$ triangles provided $k-\binom{j}{3} \leq \frac{n-j}{3}$. After some number crunching, this is possible provided $k \leq n^{3/2}$.

1