# [seqfan] Re: Permutations avoiding a pair sum

rhhardin at att.net rhhardin at att.net
Thu Feb 25 21:50:31 CET 2010

Thanks Max, William, I'll add all that.  The following checking bc(1) reproduces all my values

define factorial(i) {
auto prod,j;
prod=1;
for(j=2; j<=i; j++)prod*=j;
return prod;
}
define binomial(n,k) {
return factorial(n)/(factorial(n-k)*factorial(k));
}
define a(n,k) {
auto m,sv,j,sum;
sv=scale;
scale=0;
m=(n-k+1)/2;
scale=sv;
if(k>n+1)return factorial(n);
sum=0;
for(j=0; j<=m; j++) {
sum+=(-2)^j*binomial(m,j)*factorial(n-j);
}
return sum;
}

The remaining formal detail is what's the official syntax
for returning n! if k>n+1 in those two formulas?

(PARI et al interfere with the old version of Cygwin that I have installed
and so I haven't used them)

--
rhhardin at mindspring.com
rhhardin at att.net (either)

-------------- Original message ----------------------
From: Max Alekseyev <maxale at gmail.com>
>
> I forgot to mention that m stands for the total number of pairs that
> sum up to n+k.
>
> Also, the formula can be given in slightly more compact way:
>
> a(n,k) = \sum_{j=0}^m (-2)^j \binom{m}{j} (n-j)!
>
> { a(n,k) = local(m); m=floor( (n-k+1)/2 ); sum(j=0,m, (-2)^j *
> binomial(m,j) * (n-j)!) }
>
> Max
>
> On Thu, Feb 25, 2010 at 2:24 PM, Max Alekseyev <maxale at gmail.com> wrote:
> > There is a general formula for all these sequences.
> >
> > a(n,k) = \sum_{j=0}^m (-1)^j \binom{m}{j} 2^j (n-j)!
> >
> > where m = floor( (n-k+1)/2 ).
> >
> > The same formula in PARI/GP:
> >
> > { a(n,k) = local(m); m=floor( (n-k+1)/2 ); sum(j=0,m, (-1)^j *
> > binomial(m,j) * 2^j * (n-j)!) }
> >
> > This formula immediately proves the empirical evidence:
> > when n+k is even, we have m(n,k)=m(n,k+1) and a(n,k)=a(n,k+1).
> >
> > Regards,
> > Max
> >
> > On Thu, Feb 25, 2010 at 9:06 AM,  <rhhardin at att.net> wrote:
> >> Is there an obvious proof that the (Empirical) below can be omitted?
> >> I don't see a mapping that would prove it.
> >>
> >> I'll submit these after seeing if more terms can be computed.
> >>
> >> (The even terms of the first are A007060, which has a formula.
> >> Maybe somebody can intuit a generalization.)
> >>
> >> %I A000001
> >> %S A000001
> 0,2,8,48,240,1968,13824,140160,1263360,15298560,168422400,2373073920,
> >> %T A000001
> 30865121280,496199854080,7445355724800,134510244986880,2287168006717440
> >> %N A000001 Number of permutations of 1..n with no adjacent pair summing to
> n+1
> >> %C A000001 (Empirical) If a(n,k) is the number of permutations of 1..n with
> >>         summing to n+k, then a(n,k)=a(n,k+1) for n+k even.
> >> %K A000001 nonn
> >> %O A000001 2,2
> >>
> >> %I A000002
> >> %S A000002
> 2,2,12,48,336,1968,17760,140160,1543680,15298560,199019520,2373073920,
> >> %T A000002
> 35611269120,496199854080,8437755432960,134510244986880,2556188496691200
> >> %N A000002 Number of permutations of 1..n with no adjacent pair summing to
> n+2
> >> %C A000002 (Empirical) If a(n,k) is the number of permutations of 1..n with
> >>         summing to n+k, then a(n,k)=a(n,k+1) for n+k even.
> >> %K A000002 nonn
> >> %O A000002 2,1
> >>
> >> %I A000003
> >> %S A000003
> 2,6,12,72,336,2640,17760,175680,1543680,18385920,199019520,2771112960,
> >> %T A000003
> 35611269120,567422392320,8437755432960,151385755852800,2556188496691200
> >> %N A000003 Number of permutations of 1..n with no adjacent pair summing to
> n+3
> >> %C A000003 (Empirical) If a(n,k) is the number of permutations of 1..n with
> >>         summing to n+k, then a(n,k)=a(n,k+1) for n+k even.
> >> %K A000003 nonn
> >> %O A000003 2,1
> >>
> >> %I A000004
> >> %S A000004
> 2,6,24,72,480,2640,23040,175680,1895040,18385920,235791360,2771112960,
> >> %T A000004
> 41153495040,567422392320,9572600217600,151385755852800,2858960008396800
> >> %N A000004 Number of permutations of 1..n with no adjacent pair summing to
> n+4
> >> %C A000004 (Empirical) If a(n,k) is the number of permutations of 1..n with
> >>         summing to n+k, then a(n,k)=a(n,k+1) for n+k even.
> >> %K A000004 nonn
> >> %O A000004 2,1
> >>
> >> %I A000005
> >> %S A000005
> 2,6,24,120,480,3600,23040,221760,1895040,22176000,235791360,3242695680,
> >> %T A000005
> 41153495040,649729382400,9572600217600,170530956288000,2858960008396800
> >> %N A000005 Number of permutations of 1..n with no adjacent pair summing to
> n+5
> >> %C A000005 (Empirical) If a(n,k) is the number of permutations of 1..n with
> >>         summing to n+k, then a(n,k)=a(n,k+1) for n+k even.
> >> %K A000005 nonn
> >> %O A000005 2,1
> >>
> >> %I A000006
> >> %S A000006
> 2,6,24,120,720,3600,30240,221760,2338560,22176000,280143360,3242695680,
> >> %T A000006 47638886400,649729382400,10872058982400,170530956288000,
> >> %U A000006 3200021920972800,56707673547571200
> >> %N A000006 Number of permutations of 1..n with no adjacent pair summing to
> n+6
> >> %C A000006 (Empirical) If a(n,k) is the number of permutations of 1..n with
> >>         summing to n+k, then a(n,k)=a(n,k+1) for n+k even.
> >> %K A000006 nonn
> >> %O A000006 2,1
> >>
> >> %I A000007
> >> %S A000007
> 2,6,24,120,720,5040,30240,282240,2338560,26853120,280143360,3802982400,
> >> %T A000007 47638886400,745007155200,10872058982400,192275074252800,
> >> %U A000007 3200021920972800
> >> %N A000007 Number of permutations of 1..n with no adjacent pair summing to
> n+7
> >> %C A000007 (Empirical) If a(n,k) is the number of permutations of 1..n with
> >>         summing to n+k, then a(n,k)=a(n,k+1) for n+k even.
> >> %K A000007 nonn
> >> %O A000007 2,1
> >>
> >> %I A000008
> >> %S A000008
> 2,6,24,120,720,5040,40320,282240,2903040,26853120,333849600,3802982400,
> >> %T A000008 55244851200,745007155200,12362073292800,192275074252800,
> >> %U A000008 3584572069478400
> >> %N A000008 Number of permutations of 1..n with no adjacent pair summing to
> n+8
> >> %C A000008 (Empirical) If a(n,k) is the number of permutations of 1..n with
> >>         summing to n+k, then a(n,k)=a(n,k+1) for n+k even.
> >> %K A000008 nonn
> >> %O A000008 2,1
> >>
> >> %I A000009
> >> %S A000009
> 2,6,24,120,720,5040,40320,362880,2903040,32659200,333849600,4470681600,
> >> %T A000009 55244851200,855496857600,12362073292800,216999220838400,
> >> %U A000009 3584572069478400
> >> %N A000009 Number of permutations of 1..n with no adjacent pair summing to
> n+9
> >> %C A000009 (Empirical) If a(n,k) is the number of permutations of 1..n with
> >>         summing to n+k, then a(n,k)=a(n,k+1) for n+k even.
> >> %K A000009 nonn
> >> %O A000009 2,1
> >>
> >> %I A000010
> >> %S A000010
> 2,6,24,120,720,5040,40320,362880,3628800,32659200,399168000,4470681600,
> >> %T A000010 64186214400,855496857600,14073067008000,216999220838400,
> >> %U A000010 4018570511155200
> >> %N A000010 Number of permutations of 1..n with no adjacent pair summing to
> n+10
> >> %C A000010 (Empirical) If a(n,k) is the number of permutations of 1..n with
> >>         summing to n+k, then a(n,k)=a(n,k+1) for n+k even.
> >> %K A000010 nonn
> >> %O A000010 2,1
> >>
> >>
> >> --
> >> rhhardin at mindspring.com
> >> rhhardin at att.net (either)
> >>
> >>
> >>
> >> _______________________________________________
> >>
> >> Seqfan Mailing list - http://list.seqfan.eu/
> >>
> >
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/