A301272 Number of derangements of S_n with exactly one peak.
0, 0, 0, 1, 6, 33, 152, 663, 2778, 11413, 46332, 186867, 750878, 3011025, 12060480, 48277423, 193186146, 772908429, 3091983236, 12368675691, 49476275622, 197908422985, 791640682440, 3166577409831, 12666340397546, 50665425902853, 202661837829132, 810647630936803
Offset: 0
Examples
a(3) = 1: 231. a(4) = 6: 2143, 2341, 2413, 3142, 3412, 3421.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1663
- R. J. Cano, Sequencer program in PARI.
- Index entries for linear recurrences with constant coefficients, signature (6,-5,-16,12,16).
Programs
-
Maple
a:= n-> floor((<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>, <0|0|0|0|1>, <16|12|-16|-5|6>>^n. <<1/8, 0, 0, 1, 6>>)[1, 1]): seq(a(n), n=0..30); # Alois P. Heinz, Apr 29 2018 -
Mathematica
Join[{0}, LinearRecurrence[{6, -5, -16, 12, 16}, {0, 0, 1, 6, 33}, 30]] (* Jean-François Alcover, May 31 2019 *) CoefficientList[Series[x^3(2x^2+1)/((1-4x)(x+1)^2(2x-1)^2),{x,0,40}],x] (* Harvey P. Dale, Sep 01 2021 *) -
PARI
A301272(n)={my(c=0,v,t,ok);for(k=0,n!-1,v=numtoperm(n,k);ok=1;for(i=1,n,if((v[i]==i),ok=0;break));if(ok,t=0;for(i=2,n-1,if((v[i]>v[i-1])&&(v[i]>v[i+1]),t++;if(t>1,break)));if(t==1,c++)));c} \\ R. J. Cano, Apr 25 2018
-
PARI
\\ See Cano link.
-
Python
def count_peaks(pi): count = 0 for i in range(i,len(pi)-1): if pi[i] > pi[i+1] and pi[i] > pi[i-1]: count += 1 return count def main(args): n = int(args[0]) set = {1,2,...,n} drmts = [] for pi in itertools.permutations(set): drmts.append(pi) for i in range(n): if pi[i] == i+1: drmts.remove(pi) break num = 0 for pi in drmts: if count_peaks(pi) == 1: num += 1 print('number of 1 peak derangements: ', num)
Formula
G.f.: x^3*(2*x^2+1)/((1-4*x)*(x+1)^2*(2*x-1)^2). - Alois P. Heinz, Apr 29 2018
Extensions
a(10)-a(20) from Alois P. Heinz, Apr 25 2018
a(21)-a(27) from Alois P. Heinz, Apr 29 2018