@PerAlexandersson So I was right - I was missing something terribly obvious - a typo :)

@PerAlexandersson I was just reviewing the original remarks concerning 123-avoiding parity-alternating permutations and isn't there a bijection in the odd case as well (just reverse the sequence of values?) I'm probably missing something incredibly obvious.

@PeterTaylor Nice!

@PerAlexandersson Here are the values through n=29 (more or less the limit of my patience at this point) using a simple DFS (there are ways to refine it which would dig out more terms but I'm not sure it's worth it). Incidentally, it appears the exponential growth rate is about 2 which would make sense from the heuristic that each element has a 1/2 chance of being the right parity, so we expect about 4^n/2^n. 1, 1, 1, 1, 2, 3, 6, 11, 22, 44, 89, 185, 382, 808, 1702, 3635, 7779, 16736, 36229, 78466, 171238, 373203, 819186, 1795611, 3958662, 8721086, 19294525, 42691298, 94733886, 210379132

@bof A permutation is 321-avoiding if, when you read its sequence of values you never encounter a subsequence (not necessarily consecutive) of three in decreasing order. Another characterisation (not immediately obvious!) is that its sequence of values can be partitioned into two increasing sequences. See wikipedia on permutation patterns for more.

@PerAlexandersson OK, fewer bugs than anticipated. Still not fully optimised code (doing a breadth-first rather than depth-first search) but a longer list of values is: 1, 1, 1, 1, 2, 3, 6, 11, 22, 44, 89, 185, 382, 808, 1702, 3635, 7779, 16736, 36229, 78466, 171238, 373203, 819186, 1795611, 3958662

@PerAlexandersson I'm just fiddling with a bit of Java code for doing this (it's a type of problem with which I have some familiarity!) I may have some more numbers in a few hours (indeed one will not store permutations, just a depth-first search effectively).

I think it should be possible to use a search-based approach to generate terms more efficiently (but still effectively by generating the permutations themselves). For instance, if p is a permutation of [n] of this type then either p(1) = 1 (and then we 'know' how many of that sort there are since the remainder is effectively a shifted version of a previous case), or p(1) is an odd number greater than 1. Then, p(2) must be an even number greater than p(1) (since the value 1 must occur before any other value less than p(1)). Perhaps though your filtering already takes this into account.

The approach used in PermLab and in all the other bits of software that I'm aware of focus on generating all the permutations of a given length avoiding a pattern. The problem of course is that this can only work so long as that number is reasonably small. The main question is whether you store all the permutations of length $k$ to generate those of $k+1$ (much quicker in time, but memory-expensive) which is Kuszmaul's approach or use a tree (which with depth-first traversal requires very little memory).

Not that it isn't obvious, but in the definition of $\delta(S)$ a parameter other than $n$ in the second half might be convenient (since it's bound in the first half). Slightly more seriously should we interpret $n+1$ to equal 1? That is, is $\delta(\{1,n\})$ equal to 1 or to 2?

No worries and thanks.

My feeling is that when one writes "We define an explicit bijection ..." one means a bijection whose computation depends only on the description of an individual object in the domain -- in particular the main dichotomy for me is between explicit and recursively defined bijections. Having said all that I'll also say that I'd be happier if "explicit bijection" were left as an informal notion! Especially since I suspect that I've been entirely inconsistent in its use.

I know nothing about the topic but on the basis of the numbers and conjectures alone it would seem that one might be looking for a correspondence with compositions of n-1 (of which there are 2^{n-2}) with the various restrictions corresponding to restricting the size of the largest part (Fibonacci = largest part of size at most 2 etc.) The data seem to support the first interpretation with the Dyck paths of period (n+1) apparently being exactly those that are simply the concatenation of a series of peaks i.e., concatenations of parts 1^k 0^k for some k > 0.