A007763 - OEIS

A007763

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

1, 4, 32, 392, 6488, 135360, 3408120, 100520432, 3398723928, 129588803696, 5500585388616, 257232445666832

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

M. D. Atkinson and R. Beals, Priority queues and permutations, SIAM J. Comput. 23 (1994), 1225-1230.

EXAMPLE

From Bert Dobbelaere, Jun 18 2024: (Start)

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

insert(2)

insert(1)

insert(4)

readMax() => 4

readMin() => 1

insert(3)

readMax() => 3

readMin() => 2

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

CROSSREFS

Cf. A000272 (single-ended priority queue).

KEYWORD

nonn,more

AUTHOR

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

EXTENSIONS

Title improved and a(7)-a(9) from Sean A. Irvine, Jan 23 2018

a(10)-a(12) from Bert Dobbelaere, Jun 18 2024

STATUS

approved