El recuento de las órbitas en $\operatorname{Sym}(3)$

Question

Me gustaría una forma cerrada de la expresión de $x(n)$ para el número de órbitas de el grupo simétrico de a $3$ puntos de actuar en los triples en $\{ (a,b,c) \mid a,b,c \in \Bbb{Z}, 1 \leq a,b,c \leq n, c = 2n−a−b \}$.

Me siento como este debe ser realmente un problema básico, pero mi método estándar de ataque falla: buscar en OEIS y probar la conocida fórmula. Mi plan de copia de seguridad de "pensar en ello" ha fallado: no sé cómo lidiar con la restricción en $c$. (Sin la restricción, resulta que he aprendido de esto es la misma cosa, ya que el recuento $1 \leq a \leq b \leq c \leq n$, y resulta que he aprendido este es Binomial($n+2$, $3$) debido a que usted necesita para colocar dos barras de entre $n$ estrellas, pero yo no tengo ningún contexto general).

Sospecho que esto es bastante estándar contando problema, incluso con la restricción, pero nunca he aprendido a contar (pescado, pescado, pescado, ..., pescado, pescados, ..., pescado).

Los condes $x(n)$ $n=1$ $30$: $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$.

Creo que hay un $(n-1)\cdot(n+4)/2$ triples, pero incluso eso es un poco difusa (aumento de los aumentos de las $1$ cada vez). No tengo idea de cómo muchos de ellos han $2$ igualdad de los componentes.

Answer 1

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

Ninguna prueba, sólo utiliza sus datos, se tomó dos diferencias, y jugado.

Answer 2

Para cada una de las $n$$\mathbb{N}$, vamos a $A_n \subset [n]^3$ el conjunto de tripletas $(a,b,c)$ tal que $a+b+c=2n$. Queremos contar el número de órbitas de $S_3$ que actúa sobre los triples de $A_n$. Esto se da por Burnside del lexemacomo $$ |A_n/S_3| = \frac{1}{6}\sum_{g \en S_3}|A_n^{g}|, $$ donde para cada $g \in S_3$, $A_n^g$ es el conjunto de triples fijos por $g$. Así que tenemos que contar los elementos de $A_n$ (ya que estos son conservados por la identidad de la operación), los elementos de $A_n$ que son de la forma $(a,a,c)$ (ya que estos se conservan bajo una de dos componentes de intercambio), y los elementos de $A_n$ que son de la forma $(a,a,a)$ (ya que estos se conservan bajo las dos rotaciones). Llamar a estos tres cargos $a_n$, $b_n$, y $c_n$ respectivamente, el resultado será $$ |A_n/S_3| = \frac{1}{6}\left(a_n + 3b_n + 2c_n\right). $$ El número de tripletas de la forma $(a,a,a)\in A_n$ $c_n=1$ si $n$ es un múltiplo de a $3$, e $0$ lo contrario. El número de tripletas de la forma$(a,a,c)\in A_n$$b_n = \lfloor{n/2}\rfloor$, desde el duplicado elemento puede tomar cualquier valor de$\lceil{n/2}\rceil$$n-1$, inclusive. Por último, debemos calcular el número total de triples $(a,b,c)\in A_n$. Si $(a,b,c)$ fueron elegidos de todas las de $\mathbb{N}^3$, el recuento ser $(n-1)(2n-1)$, ya que este es el número de maneras de romper una línea de $2n$ elementos en dos distintos lugares. Aquí debemos eliminar los casos donde uno de los componentes es mayor que $n$. El número que hay que sacar es $$ \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} $$ nos da $$ a_n = (n-1)(2n-1) - \frac{3}{2}(n-1)(n-2) = \frac{1}{2}(n-1)(n+4). $$

Así que el resultado final es $$ \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} $$ donde $|\epsilon_n| < 1/2$; es decir, el número de órbitas es el entero más cercano a $(n^2+6n-4)/12$.

Answer 3

Esto también se puede hacer usando el Polya Enumeración Teorema. Recordar el ciclo de índice del grupo simétrico de tres elementos que pueden ser calculadas usando lápiz y papel por factorización de los seis constituyente permutaciones y tiene el valor $$Z(S_3) = \frac{1}{6}\left(a_1^3 + 3 a_1 a_2 + 2 a_3 \right).$$ Entonces, el valor está dado por $$[z^{2n}] Z(S_3)(z+z^2+\cdots+z^n).$$ Haciendo la sustitución obtenemos $$[z^{2n}]\frac{1}{6}(z+z^2+\cdots+z^n)^3 \\+ [z^{2n}]\frac{1}{2} (z+z^2+\cdots+z^n) (z^2+z^4+\cdots+z^{2n}) \\+ [z^{2n}]\frac{1}{3} (z^3+z^6+\cdots+z^{3n}).$$ Ahora, la aportación que el primer término es $$[z^{2n}]\frac{z^3}{6}(1+z+\cdots+z^{n-1})^3 = [z^{2n-3}]\frac{1}{6} \frac{(1-z^n)^3}{(1-z)^3}.$$ Este es, de hecho, (utilizar el binomio de Newton) $$[z^{2n-3}]\frac{1}{6} \frac{1-3z^n}{(1-z)^3} =\frac{1}{6}{2n-3+2\elegir 2} -\frac{1}{2}{n-3+2\elegir 2} \\= \frac{1}{6}{2n-1\elegir 2} -\frac{1}{2}{n-1\elegir 2} \\ = \frac{1}{12} n^2 +\frac{1}{4} n - \frac{1}{3}.$$ Para el segundo término vemos por la inspección, que para los términos de $z+z^2+\cdots+z^n$ que son incluso existe una correspondencia término de $z^2+z^4+\cdots+z^{2n}$ que da un exponente la suma de $2n$ hacer una contribución de $$\frac{1}{2}\bigg\lfloor\frac{n}{2}\bigg\rfloor = \frac{1}{4} n - \frac{1}{4} (n\bmod 2).$$ Por último, el tercer término es el que aporta el valor de $1/3$ si $n$ es divisible por tres. Esto da el resultado final $$\frac{1}{12} n^2 +\frac{1}{2} n + \begin{cases} 0 & \quad\text{if}\quad n \bmod 6 = 0,\\ -\frac{7}{12} & \quad\text{if}\quad n \bmod 6 = 1,5 \\ -\frac{1}{3} & \quad\text{if}\quad n \bmod 6 = 2,4 \\ -\frac{1}{4} & \quad\text{if}\quad n \bmod 6 = 3. \end{casos}.$$

La computación en este MSE enlace es algo similar, como es el que en este MSE vínculo II , que también utiliza el binomio de Newton.