A343488 Irregular table T(n, k), n >= 0, k = 1..max(1, n), read by rows; T(n, k) is the number of permutations s of { 1..n } such that p(s) = k where p(s) is the least m > 0 such that, working in Z/nZ, s(i) + m = s(i + m) for i = 1..n.

1, 1, 2, 0, 3, 0, 3, 4, 4, 0, 16, 5, 0, 0, 0, 115, 6, 12, 42, 0, 0, 660, 7, 0, 0, 0, 0, 0, 5033, 8, 24, 0, 352, 0, 0, 0, 39936, 9, 0, 153, 0, 0, 0, 0, 0, 362718, 10, 40, 0, 0, 3830, 0, 0, 0, 0, 3624920, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 39916789, 12, 60, 372, 1872, 0, 45636, 0, 0, 0, 0, 0, 478953648

Offset: 0

Author

Rémy Sigrist, Apr 17 2021

Keywords

• nonn
• tabf

Comments

We set the row for n = 0 to [1] by convention.

The number p(s) can be interpreted as the period of the permutation s.

Examples

			Table begins:
     0:     [1]
     1:     [1]
     2:     [2, 0]
     3:     [3, 0, 3]
     4:     [4, 4, 0, 16]
     5:     [5, 0, 0, 0, 115]
     6:     [6, 12, 42, 0, 0, 660]
     7:     [7, 0, 0, 0, 0, 0, 5033]
     8:     [8, 24, 0, 352, 0, 0, 0, 39936]
     9:     [9, 0, 153, 0, 0, 0, 0, 0, 362718]
    10:     [10, 40, 0, 0, 3830, 0, 0, 0, 0, 3624920]
		

Links

• Igor Pak, Periodic permutations and the Robinson-Schensted correspondence
• Rémy Sigrist, C program for A343488
• Index entries for sequences related to permutations

Crossrefs

Cf. A000142, A324514.

Programs

C

See Links section.

Formula

T(n, 1) = max(n, 1).

T(n, n) = A324514(n).

Sum_{k = 1..max(1, n)} T(n, k) = n!.