No tengo acceso a el artículo anterior, pero en este momento como el
los resultados son bastante básicas, voy a tratar de incluir una prueba aquí, para el
en aras de la exhaustividad y sin ninguna pretensión de originalidad.
Vamos a utilizar el Polya Enumeración Teorema. Por definición tenemos que
$$\Big\langle {n\cima de k}\Big\rangle
= [z^n] Z(C_k)\left(\frac{z}{1-z}\right)$$
donde $Z(C_k)$ es el ciclo de índice de la cíclico grupo que actúe en $k$
ranuras.
La notación es el de la primera respuesta y no deben confundirse con los números de Euler.
Ahora tenemos
$$Z(C_k) = \frac{1}{k} \sum_{q|k} \varphi(q) a_q^{k/q}.$$
Sustituyendo $Z(C_k)$ en la anterior, obtenemos
$$\Big\langle {n\cima de k}\Big\rangle =
[z^n] \frac{1}{k}
\sum_{q|k} \varphi(q) \left(\frac{z^p}{1-z^p}\right)^{k/q}
= [z^n] \frac{1}{k}
\sum_{q|k} \varphi(q) \frac{z^k}{(1-z^q)^{k/q}}
\\ = [z^{n-k}] \frac{1}{k}
\sum_{q|k} \varphi(q) \frac{1}{(1-z^q)^{k/q}}.$$
El siguiente paso es ampliar el racional plazo en $z$ utilizando el método de Newton
binomio de tomar atención a la nota que sólo contiene los exponentes que son
múltiplos de $q$ en su poder de la serie. Este rendimientos
$$\frac{1}{k}
\sum_{q|k \wedge p|n} \varphi(q)
{\frac{n-k}{q} + \frac{k}{q} - 1 \elegir \frac{k}{q} -1}
= \frac{1}{k}
\sum_{q|k \wedge p|n} \varphi(q)
{\frac{n}{p} - 1 \elegir \frac{k}{q} -1}
\\= \frac{1}{k}
\sum_{q|k \wedge p|n} \varphi(q) \frac{k/q}{n/p}
{n/p \elegir k/q }
= \frac{1}{n}
\sum_{q|\gcd(k,n)} \varphi(q)
{n/p \elegir k/q }.$$
Esto establece la primera fórmula.
Para la suma tenemos que
$$\sum_{k=1}^n \Big\langle {n\cima de k}\Big\rangle =
\frac{1}{n}
\sum_{k=1}^n
\sum_{q|\gcd(k,n)} \varphi(q)
{n/p \elegir k/q }.$$
Re-indexación de este en $q$ y poner $k=pq$ rendimientos
$$\frac{1}{n}
\sum_{p|n} \varphi(q) \sum_{p=1}^{n/p} {n/p \elegir p}
= \frac{1}{n}
\sum_{p|n} \varphi(q) (2^{n/p} - 1)
\\ = - \frac{1}{n}
\sum_{p|n} \varphi(q)
+ \frac{1}{n}
\sum_{p|n} \varphi(q) 2^{n/p}
= - 1 +
\frac{1}{n}
\sum_{p|n} \varphi(q) 2^{n/p}.$$
Esto establece la segunda fórmula.
Hay muchos más Polya la Enumeración de los cálculos en este MSE Meta enlace.
Adenda. El recuento de piezas, al menos, igual a dos está dada por
$$[z^n] Z(C_k)\left(\frac{z^2}{1-z}\right)$$
que los rendimientos de
$$[z^{n-2k}] \frac{1}{k}
\sum_{q|k} \varphi(q) \frac{1}{(1-z^q)^{k/q}}$$
que produce
$$\frac{1}{k}
\sum_{q|k \wedge p|n} \varphi(q)
{\frac{n-2k}{q} + \frac{k}{q} - 1 \elegir \frac{k}{q} -1}
= \frac{1}{k}
\sum_{q|k \wedge p|n} \varphi(q)
{\frac{n-k}{q} - 1 \elegir \frac{k}{q} -1}
\\ = \frac{1}{k}
\sum_{q|k \wedge p|n} \varphi(q) \frac{k/q}{(n-k)/q}
{\frac{n-k}{q} \elegir \frac{k}{q}}
= \frac{1}{n-k}
\sum_{q|\gcd(k,n)} \varphi(q)
{(n-k)/p \elegir k/q}.$$
Este parece ser el recuento correcto por ejemplo, para $k=5$ $n\ge 10$
tenemos
$$1, 1, 3, 7, 14, 26, 42, 66, 99, 143, 201, 273, 364, 476,
612, 776,\ldots$$
que es OEIS A008646.
Para $k=6$ $n \ge 12$ tenemos
$$1, 1, 4, 10, 22, 42, 80, 132, 217, 335, 504, 728, 1038,
1428, 1944,\ldots$$
que es OEIS A032191.
Tenga en cuenta que por un argumento trivial estos valores para las partes, al menos, dos
también se les da por
$$\Big\langle {n-k\atop k}\Big\rangle$$
(poner en valor uno en cada ranura, a continuación, agregue un cíclicos de la composición en
$k$ partes de $n-k$, esto garantiza que todas las piezas son al menos dos, y el valor inicial no cambia la simetría.)
