login
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).
3

%I #21 Sep 25 2023 18:22:37

%S 1,1,3,2,8,6,40,30,24,180,144,120,1260,1008,840,720,8064,6720,5760,

%T 5040,72576,60480,51840,45360,40320,604800,518400,453600,403200,

%U 362880,6652800,5702400,4989600,4435200,3991680,3628800

%N 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).

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

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

%C 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.

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

%H Paolo Xausa, <a href="/A364317/b364317.txt">Table of n, a(n) for n = 1..1024</a> (rows 1..63 of the triangle, flattened)

%H Eugene Curtis and Max Warshauer, <a href="http://gato-docs.its.txstate.edu/jcr:dabe5ae5-c4b8-4009-a00f-5215bf010aeb/Locker_Puzzle.pdf">The Locker Puzzle</a>, The Mathematical Intelligencer 28 (2006), pp. 28-31.

%H Christoph Pöppe, <a href="https://www.spektrum.de/magazin/freiheit-fuer-die-kombinatoriker/848868">Freiheit für die Kombinatoriker</a>, Spektrum, Highlights 1.21, pp. 16-18 (in German).

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/100_prisoners_problem">100 prisoners problem</a>.

%H Wikipedia (in German), <a href="https://de.wikipedia.org/wiki/Problem_der_100_Gefangenen">Problem der 100 Gefangenen</a>.

%F 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).

%e The irregular triangle begins:

%e n\k 1 2 3 4 5 6 ...

%e -------------------------------------------------------

%e 1: 1

%e 2: 1

%e 3: 3 2

%e 4: 8 6

%e 5: 40 30 24

%e 6: 180 144 120

%e 7: 1260 1008 840 720

%e 8: 8064 6720 5760 5040

%e 9: 72576 60480 51840 45360 40320

%e 10: 604800 518400 453600 403200 362880

%e 11: 6652800 5702400 4989600 4435200 3991680 3628800

%e ...

%e 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.

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

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

%K nonn,tabf,easy

%O 1,3

%A _Wolfdieter Lang_, Aug 12 2023