A228094 Triangle starting at row 3 read by rows of the number of permutations in the n-th Dihedral group which are the product of k disjoint cycles, d(n,k), n >= 3, 1 <= k <= n.

2, 3, 1, 2, 3, 2, 1, 4, 0, 5, 0, 1, 2, 2, 4, 3, 0, 1, 6, 0, 0, 7, 0, 0, 1, 4, 2, 0, 5, 4, 0, 0, 1, 6, 0, 2, 0, 9, 0, 0, 0, 1, 4, 4, 0, 0, 6, 5, 0, 0, 0, 1, 10, 0, 0, 0, 0, 11, 0, 0, 0, 0, 1, 4, 2, 2, 2, 0, 7, 6, 0, 0, 0, 0, 1, 12, 0, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, 1

Offset: 3

Author

Robert A. Beeler, Aug 09 2013

Keywords

• nonn
• tabf

Comments

The multivariable row polynomials give n times the cycle index for the Dihedral group D_n, called Z(D_n) (see the MathWorld link with the Harary reference). For example, 12*Z(D_6) = 2*(y_6)^1 + 2*(y_3)^2 + 4*(y_2)^3+3*(y_1)^2*(y_2)^2 + 1*(y_1)^6.

Examples

			Triangle begins
   2, 3, 1;
   2, 3, 2, 1;
   4, 0, 5, 0, 1;
   2, 2, 4, 3, 0,  1;
   6, 0, 0, 7, 0,  0, 1;
   4, 2, 0, 5, 4,  0, 0, 1;
   6, 0, 2, 0, 9,  0, 0, 0, 1;
   4, 4, 0, 0, 6,  5, 0, 0, 0, 1;
  10, 0, 0, 0, 0, 11, 0, 0, 0, 0, 1;
   4, 2, 2, 2, 0,  7, 6, 0, 0, 0, 0, 1;
   ...
		

References

• Robert A. Beeler, How to Count: An Introduction to Combinatorics and Its Applications, Springer International Publishing, 2015. See Theorem 8.4.12 at pp. 246-247.
• Frank Harary and Edgar M. Palmer, Graphical Enumeration, Academic Press, 1973, p. 37.

Links

• Stefano Spezia, First 150 rows of the triangle, flattened
• Eric Weisstein's World of Mathematics, Cycle Index.

Crossrefs

Cf. A000010, A054523, A130534.

Programs

Mathematica

d[n_,k_]:=If[Divisible[n,k],EulerPhi[n/k],0]+If[OddQ[n]&&k==(n+1)/2,n,If[EvenQ[n]&&(k==n/2||k==(n+2)/2),n/2,0]]; Table[d[n,k],{n,3,12},{k,n}]//Flatten (* Stefano Spezia, Jun 26 2023 *)

Formula

d(n,k) = A054523(n,k) + d'(n,k), where: If n is odd, then d'(n,k)= n when k=(n+1)/2 and d'(n,k)=0 otherwise. If n is even, then d'(n,k)=n/2 when k=n/2, (n+2)/2 and d'(n,k)=0 otherwise.

Extensions

Terms corrected by Stefano Spezia, Jun 30 2023