[seqfan] Re: Permutations avoiding a pair sum

[Max Alekseyev]

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 no adjacent pair
>         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 no adjacent pair
>         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 no adjacent pair
>         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 no adjacent pair
>         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 no adjacent pair
>         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 no adjacent pair
>         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 no adjacent pair
>         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 no adjacent pair
>         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 no adjacent pair
>         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 no adjacent pair
>         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/
>