[seqfan] Re: Permutations avoiding a pair sum

[Max Alekseyev]

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 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/
>>
>