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

Stefano Spezia, First 150 rows of the triangle, flattened

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

Cf. A000010, A054523, A130534.

Sequence in context: A054073 A194871 A194899 * A059832 A105316 A105933

Adjacent sequences: A228091 A228092 A228093 * A228095 A228096 A228097

Keyword

nonn,tabf

Author

Robert A. Beeler, Aug 09 2013

Extensions

Terms corrected by Stefano Spezia, Jun 30 2023

Status

approved