[seqfan] Permutations: sum of max of each adjacent pair

Ron Hardin rhhardin at att.net
Thu Aug 12 01:47:44 CEST 2010


Take the sum of the maximum of every adjacent pair in a permutation of 0..(n-1).
a(n)= number of permutations with sum X.

Apparently the minimum possible sum is X=n*(n-1)/2, which gives A000079
(all offsets n=2)

2,4,8,16,32,64,128,256,512,1024
Number of permutations of 0..(n-1) with the sum of the maximum of each adjacent 
pair = n*(n-1)/2

Apparently the maximum possible sum is X=n*(n-1)/2+floor((n-1)^2/4), which gives 
A092186

2,2,8,12,72,144,1152,2880,28800,86400,1036800,3628800,50803200,
203212800,3251404800
Number of permutations of 0..(n-1) with the sum of the maximum of each adjacent 
pair = n*(n-1)/2 + floor((n-1)^2/4)

Taking an X in the middle, a new series

2,4,8,36,160,848,5792,41712,338688,2902464,30968064,346316544,
4034119680,48892557312,707976364032
Number of permutations of 0..(n-1) with the sum of the maximum of each adjacent 
pair = n*(n-1)/2 + floor((n-1)^2/8)


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






More information about the SeqFan mailing list