A135401, A000898

[Maximilian Hasler]

I will copy 100 times "I won't post prematurely to the seqfan list",
and as additional punishment I elaborated the following formula:

{A135401(n)=sum(cc=0,n\4,binomial(n\2,2*cc)*binomial(2*cc,cc)*cc!/2^cc
*sum(m=0,(n\2-2*cc)\2,binomial(n\2-2*cc,2*m)*binomial(2*m,m)*m!*2^(n\2-2*cc-3*m)))}

vector(20,n,A135401(n))
= [1, 2, 2, 6, 6, 20, 20, 76, 76, 312, 312, 1384, 1384, 6512, 6512,
32400, 32400, 168992, 168992, 921184]

and explanation:
If n is odd, we must have p((n+1)/2)=(n+1)/2 and the set P(n) of
"valid" permutations is in bijection with P(n-1), by discarding the
middle index and decreasing all indices/values >n/2 by 1, i.e.
a(n)=a(n-1) and we can restrict us to even n.
Clearly, any p in P(n) is determined by its values for k=1...n/2.
Let c=0..[n/4] be the number of couples (k,p(k)), k<p(k)<=n/2, and
m=0..[(n/2-2c)/2] be the number of couples (k,p(k)), k<=n/2<p(k)<n+1-k,
then there remain 2^(n/2-2c-2m) possibilities to separate the
remaining points into fixed points and k such that p(k)=n+1-k.
The number of choosing c couples among n/2 numbers is calculated as follows:
We have binomial(n/2,2)=(n/2)(n/2-1)/2 ways to choose the first
couple, then binomial(n/2-2,2)=(n/2-2)(n/2-3)/2 ways to choose the
second couple, etc up to binomial(n/2-2c+2,2)=(n/2-2c+2)(n/2-2c+1)/2;
but since the order of these choices does not matter,we must divide
the product of these numbers (equal to (n/2)!/(n/2-2c)!/2^c) by c!.

Sorry again for previously sent trash....
Maximilian

On Jan 20, 2008 11:55 AM, Maximilian Hasler <maximilian.hasler at gmail.com> wrote:
> I confirm my first hypothesis (that of being too tired)...
> the sequence I give is the number of permutations satisfying the given
> formula, but not necessarily self-inverse(?). Thus it should be an
> upper bound, so I still don't understand why I get 70 where OEIS gives
> 76...
> (but maybe I'll understand it in some hours or days...)
> sorry for flooding your mailboxes....
> M.H.
>
>
> On Jan 20, 2008 11:44 AM, Maximilian Hasler <maximilian.hasler at gmail.com> wrote:
> > I'm maybe a bit tired and miss something obvious, but the definition of
> > http://www.research.att.com/~njas/sequences/A135401
> > seems to indicate that one can simply choose any list of [n/2] numbers among
> > {1...n} \ {(n+1)/2} for p(1)...p([n/2]) and the remaining values of p
> > are given by
> > the formula p(k) = n+1-p(n+1-k),
> > This would mean
> > A135401(n)=binomial(n\2*2,n\2)
> > vector(20,n,A135401(n)) = [1, 2, 2, 6, 6, 20, 20, 70, 70, 252, 252,
> > 924, 924, 3432, 3432, 12870, 12870, 48620, 48620, 184756]
> >
> > but instead of 70 there is 76 given in the current version.
> >
> > Maximilian
> >
> >
> > On Jan 20, 2008 10:12 AM, Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:
> > > Does A135401(n) = A000898(floor(n/2)), for n =
> > > all positive integers?
> > >
> > > The rook problem on an n-by-n chessboard, as I
> > > understand it, is directly connected to
> > > permutations of (1,2,3,...n).
> > > So maybe the connection between these two
> > > sequences is obvious.
> > >
> > >
> > > Thanks,
> > > Leroy Quet
> > >
> > >
> > >
> > >
> > >
> > > \/\/\/\///////\\\\\\\/\/\/\/
> > > /\/\/\///////**\\\\\\\/\/\/\
> > > \/\/\///////*/\*\\\\\\\/\/\/
> > > /\/\/\\\\\\\*\/*///////\/\/\
> > > \/\/\/\\\\\\\**///////\/\/\/
> > > /\/\/\/\\\\\\\///////\/\/\/\
> > >
> > >
> > >       ____________________________________________________________________________________
> > > Be a better friend, newshound, and
> > > know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ
> > >
> > >
> > >
> >
> >
> >
> > --
> > Maximilian F. Hasler (Maximilian.Hasler(AT)gmail.com)
> >
>
>
>
> --
> Maximilian F. Hasler (Maximilian.Hasler(AT)gmail.com)
>



-- 
Maximilian F. Hasler (Maximilian.Hasler(AT)gmail.com)