login
Number of pairs of length n permutations achievable by double-ended priority queue.
1

%I #16 Jun 19 2024 18:58:47

%S 1,4,32,392,6488,135360,3408120,100520432,3398723928,129588803696,

%T 5500585388616,257232445666832

%N Number of pairs of length n permutations achievable by double-ended priority queue.

%H Sean A. Irvine, <a href="/A007763/a007763.pdf">Notes on A007763</a>

%H M. D. Atkinson and R. Beals, <a href="https://www.cs.otago.ac.nz/staffpriv/mike/Papers/PriorityQueues/PQs-Beals.pdf">Priority queues and permutations</a>, SIAM J. Comput. 23 (1994), 1225-1230.

%e From _Bert Dobbelaere_, Jun 18 2024: (Start)

%e The input {2,1,4,3} can be reordered to {4,1,3,2} via the DEPQ using the following sequence of operations:

%e insert(2)

%e insert(1)

%e insert(4)

%e readMax() => 4

%e readMin() => 1

%e insert(3)

%e readMax() => 3

%e readMin() => 2

%e Of the (4!)^2 possible (input,output) pairs, only 392 can be achieved with a valid operation sequence, hence a(4) = 392. (End)

%Y Cf. A000272 (single-ended priority queue).

%K nonn,more

%O 1,2

%A mda(AT)cs.st-andrews.ac.uk (Michael Atkinson)

%E Title improved and a(7)-a(9) from _Sean A. Irvine_, Jan 23 2018

%E a(10)-a(12) from _Bert Dobbelaere_, Jun 18 2024