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,5

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).

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

Example

a(3) = 1: 231.
a(4) = 6: 2143, 2341, 2413, 3142, 3412, 3421.

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 *)

Prog

(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)
(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.

Crossrefs

Cf. A000166, A001045, A216963.

Column k=1 of A303564.

Sequence in context: A255613 A022730 A266944 * A290921 A240880 A099432

Adjacent sequences: A301269 A301270 A301271 * A301273 A301274 A301275

Keyword

nonn,easy

Author

Isabella Huang, Mar 17 2018

Extensions

a(10)-a(20) from Alois P. Heinz, Apr 25 2018

a(21)-a(27) from Alois P. Heinz, Apr 29 2018

Status

approved