A135401, A000898

[Max Alekseyev]

On Jan 20, 2008 6:12 AM, Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:

> Does A135401(n) = A000898(floor(n/2)), for n =
> all positive integers?

That's correct!

Let p=(p(1),...,p(n)) be a permutation such that p(k) = n+1-p(n+1-k)
for all 1<=k<=n.
Then every pair elements of {k,n+1-k} (i.e., where the sum of elements
is n+1) is mapped by p into {p(k),p(n+1-k)} with the same property
p(k) + p(n+1-k) = n+1. Therefore, every such permutation induces a
permutation q on the 2-sets {k,n+1-k} and for odd n has a fixed point
p((n+1)/2) = (n+1)/2.
Furthermore, it is easy to see that if p is self-inverse then so is q.

For every permutation q on the sets {k,n+1-k}, 1<=k<=[n/2], let's
count how many p induce it.
It is clear that if q has exactly m fixed points (so that the other
[n/2]-m 2-sets form pairs of inverse under q elements) then there
exist 2^m to define p on the elements of fixed points of q and
2^(([n/2]-m)/2) for the remaining elements.
Hence, the total number of permutations corresponding q is 2^m *
2^(([n/2]-m)/2) = 2^(([n/2]+m)/2).

The number of permutations q on s=[n/2] elements with exactly m fixed
points is non-zero only if m and s are of the same oddness, and in
this case it is
binomial(s,m) * (s-m)! / 2^((s-m)/2) / ((s-m)/2)!
= binomial(s,m) * (s-m-1)!!
= s! / m! / 2^((s-m)/2) / ((s-m)/2)!

Hence, A135401(n) = SUM s! * 2^m / m! / ((s-m)/2)!, where sum is taken
over m, 0 <= m <= s=[n/2], of the same oddness as s. Let s-m=2t so
that m=s-2t and
A135401(n) = SUM[ t=0..[s/2] ] s! * 2^(s-2t) / ( (s-2t)! * t! ) = s!
[x^s] e^(2x) * e^(x^2)
= s! [x^s] e^(x^2+2x) = A000898(s), according to its e.g.f.

Regards,
Max




Dear Seqfans:

There was a bug in the email server "sequences at research.att.com"
which I have just fixed.

That program has probably been broken for several weeks.

Thanks to Neven Juric for telling me about the problem.

The bug did not affect "superseeker at research.att.com"


By the way, in the next week or two, both of these
email servers will be moved to our new machine.
There may be further problems at that point - please
tell me if you see anything wrong.

[Incidentally there is a DIFFERENT bug in Superseeker
which I have not yet fixed.  But it is only minor.]