

A180187


Number of successions in all the permutations p of [n] such that p(1)=1 and having no 3sequences. A succession of a permutation p is a position i such that p(i +1)  p(i) = 1.


3



0, 1, 0, 3, 14, 72, 468, 3453, 28782, 267831, 2752828, 30984336, 379125192, 5011756625, 71190365580, 1081514329155, 17499480412746, 300473929597320, 5457031426340748, 104520033700333069, 2105651342251571562
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

From Emeric Deutsch, Sep 07 2010: (Start)
a(n) is also the number of fixed points in all those permutations of [n1] that have no adjacent fixed points. Example: a(4)=3 because in 132, 213, 231, 312, 321 we have 1+1+0+0+1 fixed points.
a(n) is also the number of permutations of [n] having exactly 1 pair of adjacent fixed points. Example: a(4)=3 because we have 1243, 4231, and 2134.
(End)


REFERENCES

Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012.  From N. J. A. Sloane, Sep 15 2012


LINKS

Table of n, a(n) for n=1..21.


FORMULA

a(n) = Sum_{k>=0} k*A180186(n,k).
a(n) = Sum_{k=0..floor(n/2)} k*binomial(nk,k)*d(n1k), where d(j)=A000166(j) are the derangement numbers.


EXAMPLE

a(4)=3 because in 1*243, 1324, 13*42, 142*3, 1432 we have 3 successions (marked *).


MAPLE

d[0] := 1: for n to 51 do d[n] := n*d[n1]+(1)^n end do: seq(sum(k*binomial(nk, k)*d[n1k], k = 0 .. floor((1/2)*n)), n = 1 .. 22);


MATHEMATICA

a[0] = 1; a[n_] := a[n] = n*a[n  1] + (1)^n; f[n_] := Sum[k*Binomial[n  k, k]*a[n  k  1], {k, 0, n/2}]; Array[f, 21] (* Robert G. Wilson v, Apr 01 2011 *)
a[n_] := Sum[k Binomial[n  k, k] Subfactorial[n  k  1], {k, 0, n/2}];
a /@ Range[1, 21] (* JeanFrançois Alcover, Oct 29 2019 *)


CROSSREFS

Cf. A000166, A180186.
A column of A216718.  N. J. A. Sloane, Sep 15 2012
Sequence in context: A098648 A026295 A118650 * A295104 A080238 A307443
Adjacent sequences: A180184 A180185 A180186 * A180188 A180189 A180190


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Sep 06 2010


STATUS

approved



