A364317 Irregular triangle T read by rows: T(n, k) gives the number of permutations of [n] = {1, 2, ..., n} with a cycle of length m = floor(n/2) + k = A138099(n, k), for 1 <= k <= n - floor(n/2) = ceiling(n/2).

1, 1, 3, 2, 8, 6, 40, 30, 24, 180, 144, 120, 1260, 1008, 840, 720, 8064, 6720, 5760, 5040, 72576, 60480, 51840, 45360, 40320, 604800, 518400, 453600, 403200, 362880, 6652800, 5702400, 4989600, 4435200, 3991680, 3628800

Offset: 1

Author

Wolfdieter Lang, Aug 12 2023

Keywords

• nonn
• tabf
• easy

Comments

The length of row n is ceiling(n/2) = A008619(n-1).

The numbers for these cycles of permutations of [n], appear in the solution of the Locker Problem. See the link, p. 25.

For the probability of failures with the strategy used in the locker problem with n lockers and opening of up to floor(n/2) lockers see A058313(n)/A058312(n), for n > = 1. For n = 1 the one team member is not allowed to open the one locker (with the member's wallet) because (n/2) = 0; so certainly a failure.

For the probability of success in this locker problem for n lockers see A119248(n)/A058312(n), for n >= 1.

Examples

			The irregular triangle begins:
n\k       1       2       3       4       5       6 ...
-------------------------------------------------------
1:        1
2:        1
3:        3       2
4:        8       6
5:       40      30      24
6:      180     144     120
7:     1260    1008     840     720
8:     8064    6720    5760    5040
9:    72576   60480   51840   45360   40320
10:  604800  518400  453600  403200  362880
11: 6652800 5702400 4989600 4435200 3991680 3628800
...
T(5, 1) = 40 because m(5, 1) = 2 + 1 = 3, and for each of the binomial(5, 3) = 10 possibilities for choosing three numbers from [5] there are (3 - 1)! = 2 3-cycles if each starts with the smallest number, e.g., for {2, 3, 5} the cycles are (2, 3, 5) and (2, 5, 3). For the remaining 5-3 = 2 numbers there are 2! possible permutations; in the example permutations of {1, 4}, namely (1)(4) and (1,4). Thus T(5, 3) = binomial(5, 3)*2!*2! = 10*2*2 = 40 = 5!/3.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..1024 (rows 1..63 of the triangle, flattened)
• Eugene Curtis and Max Warshauer, The Locker Puzzle, The Mathematical Intelligencer 28 (2006), pp. 28-31.
• Christoph Pöppe, Freiheit für die Kombinatoriker, Spektrum, Highlights 1.21, pp. 16-18 (in German).
• Wikipedia, 100 prisoners problem.
• Wikipedia (in German), Problem der 100 Gefangenen.

Crossrefs

Cf. A008619, A058313/A058312, A119248/A058312, A126074, A138099.

Programs

Mathematica

A364317row[n_]:=n!/(Floor[n/2]+Range[Ceiling[n/2]]);Array[A364317row,10] (* Paolo Xausa, Sep 25 2023 *)

Formula

T(n, k) = binomial(n, m(n, k))*(m(n, k) - 1)!*(n - m(n, k))! = n!/m(n, k), with m(n, k) = floor(n/2) + k = A138099(n, k), for n >= 1 and k = 1, 2, ..., ceiling(n/2).