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