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

%I #57 Nov 04 2016 09:22:54

%S 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,

%T 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,

%U 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

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

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

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

%C See also table A054523 with zeros if k does not divide n, and reversed rows. [_Wolfdieter Lang_, May 29 2012]

%D 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).

%D F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1994; pp. 181 and 184.

%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 36, (2.2.10).

%H Wolfdieter Lang, <a href="/A102190/b102190.txt">Table of n, a(n) for n = 1..7069</a> (suggested by T. D. Noe, Nov 16 2015)

%H W. Lang, <a href="/A102190/a102190.txt">More terms and comments</a>

%H Carl Pomerance, Lola Thompson, Andreas Weingartner, <a href="http://arxiv.org/abs/1511.03357">On integers n for which X^n-1 has a divisor of every degree</a>, arXiv:1511.03357 [math.NT], 2015.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CycleIndex.html">Cycle Index.</a>

%F 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.

%F 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.

%e Array begins:

%e 1: [1],

%e 2: [1, 1],

%e 3: [1, 2],

%e 4: [1, 1, 2],

%e 5: [1, 4],

%e 6: [1, 1, 2, 2],

%e 7: [1, 6], ...

%e The entry for n=6 is obtained as follows:

%e Z(C_6,x)=(1*x[1]^6 + 1*x[2]^3 + 2*x[3]^2 + 2*x[6]^1)/6.

%e a(6,1)=phi(1)=1, a(6,2)=phi(2)=1, a(6,3)=phi(3)=2, a(6,4)=phi(6)=2.

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

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

%o (PARI) tabf(nn) = for (n=1, nn, print(apply(x->eulerphi(x), divisors(n)))); \\ _Michel Marcus_, Nov 13 2015

%o (PARI) tabf(nn) = for (n=1, nn, print(apply(x->poldegree(x), factor(x^n-1)[,1]))) \\ _Michel Marcus_, Nov 13 2015

%Y Cf. A054523.

%K nonn,easy,tabf

%O 1,5

%A _Wolfdieter Lang_, Feb 15 2005