Counting orbits under $\operatorname{Sym}(3)$

Question

I'd like a closed form expression $x(n)$ for the number of orbits of the symmetric group on $3$ points acting on the triples in $\{ (a,b,c) \mid a,b,c \in \Bbb{Z}, 1 \leq a,b,c \leq n, c = 2n−a−b \}$.

I feel like this should be a really basic problem, but my standard method of attack fails: look it up in OEIS and prove the known formula. My backup plan of "think about it" has failed: I don't know how to deal with the restriction on $c$. (Without the restriction, I happen to have learned this is the same thing as counting $1 \leq a \leq b \leq c \leq n$, and I happen to have learned this is Binomial($n+2$, $3$) because you need to place two bars between $n$ stars, but I have no general context for this.)

I suspect this is a pretty standard counting problem even with the restriction, but I never really learned how to count (fish, fish, fish, …, fish, fish, …, fish).

The counts $x(n)$ for $n=1$ to $30$ are: $0, 1, 2, 3, 4, 6, 7, 9, 11, 13, 15, 18, 20, 23, 26$, $29, 32, 36, 39, 43, 47, 51, 55, 60, 64, 69, 74, 79, 84, 90$.

I think there are $(n-1)\cdot(n+4)/2$ triples, but even that is a little fuzzy (increase increases by $1$ each time). I have no idea how many of them have $2$ equal components.

Answer 1

For each $n$ in $\mathbb{N}$, let $A_n \subset [n]^3$ be the set of triples $(a,b,c)$ such that $a+b+c=2n$. We want to count the number of orbits of $S_3$ acting on the triples of $A_n$. This is given by Burnside's lemma as $$ |A_n/S_3| = \frac{1}{6}\sum_{g \in S_3}|A_n^{g}|, $$ where for each $g \in S_3$, $A_n^g$ is the set of triples fixed by $g$. So we need to count the elements of $A_n$ (since these are preserved by the identity operation), the elements of $A_n$ that are of the form $(a,a,c)$ (since these are preserved under a two-component swap), and the elements of $A_n$ that are of the form $(a,a,a)$ (since these are preserved under the two rotations). Calling these three counts $a_n$, $b_n$, and $c_n$ respectively, the result will be $$ |A_n/S_3| = \frac{1}{6}\left(a_n + 3b_n + 2c_n\right). $$ The number of triples of the form $(a,a,a)\in A_n$ is $c_n=1$ if $n$ is a multiple of $3$, and $0$ otherwise. The number of triples of the form $(a,a,c)\in A_n$ is $b_n = \lfloor{n/2}\rfloor$, since the doubled element can take any value from $\lceil{n/2}\rceil$ to $n-1$, inclusive. Finally, we must compute the total number of triples $(a,b,c)\in A_n$. If $(a,b,c)$ were chosen from all of $\mathbb{N}^3$, the count would be $(n-1)(2n-1)$, since this is the number of ways to break a line of $2n$ elements in two distinct places. Here we must remove the cases where one of the components is greater than $n$. The number to be removed is $$ \begin{eqnarray} 3 \sum_{i=n+1}^{2n-2} (2n-i-1) &=& 3\sum_{i=1}^{n-2} (i) \\ &=& \frac{3}{2}(n-1)(n-2), \end{eqnarray} $$ giving us $$ a_n = (n-1)(2n-1) - \frac{3}{2}(n-1)(n-2) = \frac{1}{2}(n-1)(n+4). $$

So the final result is $$ \begin{eqnarray} |A_n/S_3| &=& \frac{1}{6}\left(\frac{1}{2}(n-1)(n+4) + 3\left\lfloor{\frac{1}{2}n}\right\rfloor + 2c_n\right) \\ &=& \frac{1}{12}\left(n^2 + 6n - 4\right) + \epsilon_n, \end{eqnarray} $$ where $|\epsilon_n| < 1/2$; i.e., the number of orbits is the closest integer to $(n^2+6n-4)/12$.

Answer 2

It is $x(n)=\lfloor \frac{n^2+4n+1}{12} \rfloor + \lfloor \frac {n+3}{6} \rfloor$

No proof, just used your data, took two differences, and played.