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,5

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]

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.

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.

Example

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.

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 *)

Prog

(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

Crossrefs

Cf. A054523.

Sequence in context: A342416 A305531 A132066 * A138650 A266685 A272620

Adjacent sequences: A102187 A102188 A102189 * A102191 A102192 A102193

Keyword

nonn,easy,tabf

Author

Wolfdieter Lang, Feb 15 2005

Status

approved