login
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.
1
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,1
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.
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
Eric Weisstein's World of Mathematics, Cycle Index.
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.
EXAMPLE
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;
...
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 *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Robert A. Beeler, Aug 09 2013
EXTENSIONS
Terms corrected by Stefano Spezia, Jun 30 2023
STATUS
approved