# [seqfan] Re: A combinatorial problem

Alexander P-sky apovolot at gmail.com
Wed Jan 19 16:06:48 CET 2011

```Below is what WolframAlpha's gives:

sum((-1)^k*C(2*n-k-4, k)*(n-k-2)!*(n-k-2), k=0...n-3) =
sum_(k=0)^(-3+n)(-1)^k (2 n-k-4k) (n-k-2)! (n-k-2) =
n (n-2)! _1F_1(5/2-n;4-2 n;-4)-2 (n-2)! _1F_1(5/2-n;4-2 n;-4)+2 n
(n-3)! _1F_1(7/2-n;5-2 n;-4)-5 (n-3)! _1F_1(7/2-n;5-2 n;-4)+(-1)^n
(n-2) _2F_2(1/2, 1;2-n, n-2;-4)-(-1)^n (n-2) _2F_2(1/2, 1;2-n, n-1;-4)

http://www.wolframalpha.com/input/?i=sum%28%28-1%29^k*C%282*n-k-4%2c+k%29*%28n-k-2%29!*%28n-k-2%29%2c+k%3d0...n-3%29&s=27&incTime=true

ARP
======================================================
On 1/17/11, Vladimir Shevelev <shevelev at bgu.ac.il> wrote:
> Dear SeqFans,
>
> I found a simple necessary condition for a suitable n. It is
> Sum{k=0,...,n-3}(-1)^k*C(2n-k-4, k)*(n-k-2)!*(n-k-2)=A000179/(n-2)
>
> I ask anyone to verify this much more simple condition for n>6. It seems
> that, possibly, no other solutions except of n=3,4,6.
>
> Regards,
>
> ----- Original Message -----
> From: Vladimir Shevelev <shevelev at bgu.ac.il>
> Date: Saturday, January 15, 2011 22:19
> Subject: [seqfan] Re: A combinatorial problem
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
>
>> I would like to add to a solution of the problem the following:
>> if to take into account all trivial restrictions on binomial
>> coefficients, then  we have:
>> max(r+k-n-1, 2r+k-2n-2, 0)<=i<=r-2. ( It seems that I
>> wrote r=1,...,n, but it should be r=3,...,n).
>>
>> With these restrictions one can calculate n-2 sums for
>> r=3,4,...,n. Moreover,  using a symmetry, one can calculate
>> floor((n+3) / 2) sums for r=1,...,floor((n+3)/2) only. Every
>> (full) sum should be equal to  A000179(n) / (n-2).
>>
>> Regards,
>>
>>
>> ----- Original Message -----
>> From: Vladimir Shevelev <shevelev at bgu.ac.il>
>> Date: Friday, January 14, 2011 18:00
>> Subject: [seqfan] Re: A combinatorial problem
>> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
>>
>> > Correction. I wrote that "the interior sums B does not depend
>> on
>> > r."  I ask to ignore this phraze: of course, instead of
>> B,
>> > I ment the full sum: Sum{k=0,...,n-1}(...) does not depend on
>> r,
>> > since equals to
>> > A000179(n)/(n-2).
>> >
>> > Regards,
>> >
>> >
>> >
>> > ----- Original Message -----
>> > From: Vladimir Shevelev <shevelev at bgu.ac.il>
>> > Date: Friday, January 14, 2011 14:19
>> > Subject: [seqfan] A combinatorial problem
>> > To: seqfan at list.seqfan.eu
>> >
>> > > Dear SeqFans,
>> > >
>> > > I ask anyone to extend a sequence which is connected with
>> the
>> > > following modification of the menage problem. A well known
>> > > mathematician N found himself with his wife among the
>> guests,
>> > > which were
>> > > n(>=3) married couples. After seating the ladies on every
>> > other
>> > > chair at a circular table, N was the first offered to choose
>> > an
>> > > arbitrary chair but not side by side with his wife. For
>> which
>> > > values of n the number of ways of seating of other men (
>> under
>> > > the condition that no husband is beside his wife) does not
>> > > depend on how far N takes his seat from his wife?
>> > >
>> > > The first terms of this sequence are 3,4,6.  I proved
>> > that
>> > > the problem reduces to description the values of n>=3 for
>> > which,
>> > > for every r=1,...,n, we have
>> > > Sum{k=0,...,n-1}((-1)^k)*(n-k-1)!*B=A000179(n)/(n-2),
>> > > where B=Sum{i=0,...,k}C(2r-i-4, i)*C(2n-2r-k+i+2, k-i),
>> i.e.,
>> > > for such an n, B does not depend on r  (here C-binomial
>> > > coefficients).In addition, I proved that A000179(n)/(n-2) is
>> > > integer, if n has the form 2^t+2 ( and I conjecture that
>> here
>> > > one can write "iff").
>> > >
>> > > E.g., if n=3, then, for every r,  if k=0, then B=1; if
>> > k=1,
>> > > then B=2; if k=2, then B=1. Thus
>> > > 1*2!-2*1!+1*0!=A000179(3)/1=1.
>> > >
>> > > Regards,
>> > >
>> > >
>> > > _______________________________________________
>> > >
>> > > Seqfan Mailing list - http://list.seqfan.eu/
>> > >
>> >
>> >
>> > _______________________________________________
>> >
>> > Seqfan Mailing list - http://list.seqfan.eu/
>> >
>>
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>