A102190 Irregular triangle read by rows: coefficients of cycle index polynomial for the cyclic group C_n, Z(C_n,x), multiplied by n.

1, 1, 1, 1, 2, 1, 1, 2, 1, 4, 1, 1, 2, 2, 1, 6, 1, 1, 2, 4, 1, 2, 6, 1, 1, 4, 4, 1, 10, 1, 1, 2, 2, 2, 4, 1, 12, 1, 1, 6, 6, 1, 2, 4, 8, 1, 1, 2, 4, 8, 1, 16, 1, 1, 2, 2, 6, 6, 1, 18, 1, 1, 2, 4, 4, 8, 1, 2, 6, 12, 1, 1, 10, 10, 1, 22, 1, 1, 2, 2, 2, 4, 4, 8, 1, 4, 20, 1, 1, 12, 12, 1, 2, 6, 18, 1, 1, 2, 6, 6

Offset: 1

Author

Wolfdieter Lang, Feb 15 2005

Keywords

• nonn
• easy
• tabf

Comments

Row n gives the coefficients of x[k]^{n/k} with increasing divisors k of n.

The length of row n is tau(n) = A000005(n) (number of divisors of n, including 1 and n).

See also table A054523 with zeros if k does not divide n, and reversed rows. [Wolfdieter Lang, May 29 2012]

Examples

			Array begins:
1: [1],
2: [1, 1],
3: [1, 2],
4: [1, 1, 2],
5: [1, 4],
6: [1, 1, 2, 2],
7: [1, 6], ...
The entry for n=6 is obtained as follows:
Z(C_6,x)=(1*x[1]^6 + 1*x[2]^3 + 2*x[3]^2 + 2*x[6]^1)/6.
a(6,1)=phi(1)=1, a(6,2)=phi(2)=1, a(6,3)=phi(3)=2, a(6,4)=phi(6)=2.
		

References

• N. G. De Bruijn, Polya's theory of counting, in E. F. Beckenbach, ed., Applied Combinatorial Mathematics, Wiley, 1964, pp. 144-184 (see Example 5.7).
• F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1994; pp. 181 and 184.
• F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 36, (2.2.10).

Links

• Wolfdieter Lang, Table of n, a(n) for n = 1..7069 (suggested by T. D. Noe, Nov 16 2015)
• W. Lang, More terms and comments
• Carl Pomerance, Lola Thompson, Andreas Weingartner, On integers n for which X^n-1 has a divisor of every degree, arXiv:1511.03357 [math.NT], 2015.
• Eric Weisstein's World of Mathematics, Cycle Index.

Crossrefs

Cf. A054523.

Programs

Mathematica

k[n_, m_] := Divisors[n][[m]]; a[n_, m_] := EulerPhi[k[n, m]]; Flatten[Table[a[n, m], {n, 1, 28}, {m, 1, DivisorSigma[0, n]}]] (* Jean-François Alcover, Jul 25 2011, after given formula *)
row[n_] := If[n == 1, {1}, n List @@ CycleIndexPolynomial[CyclicGroup[n], Array[x, n]] /. x[] -> 1]; Array[row, 30] // Flatten (* _Jean-François Alcover, Nov 04 2016 *)

PARI

tabf(nn) = for (n=1, nn, print(apply(x->eulerphi(x), divisors(n)))); \\ Michel Marcus, Nov 13 2015

PARI

tabf(nn) = for (n=1, nn, print(apply(x->poldegree(x), factor(x^n-1)[,1]))) \\ Michel Marcus, Nov 13 2015

Formula

a(n, m) = phi(k(m)), m=1..tau(n), n>=1, with k(m) the m-th divisor of n, written in increasing order.

Z(C_n, x):=sum(sum(phi(k)*x[k]^{n/k}, k|n))/n, where phi(n)= A000010(n) (Euler's totient function) and k|n means 'k divides n'. Cf. Harary-Palmer reference and MathWorld link.