login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A180187 Number of successions in all the permutations p of [n] such that p(1)=1 and having no 3-sequences. A succession of a permutation p is a position i such that p(i +1) - p(i) = 1. 3

%I

%S 0,1,0,3,14,72,468,3453,28782,267831,2752828,30984336,379125192,

%T 5011756625,71190365580,1081514329155,17499480412746,300473929597320,

%U 5457031426340748,104520033700333069,2105651342251571562

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

%C From _Emeric Deutsch_, Sep 07 2010: (Start)

%C a(n) is also the number of fixed points in all those permutations of [n-1] 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.

%C 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.

%C (End)

%D 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

%F a(n) = Sum_{k>=0} k*A180186(n,k).

%F a(n) = Sum_{k=0..floor(n/2)} k*binomial(n-k,k)*d(n-1-k), where d(j)=A000166(j) are the derangement numbers.

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

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

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

%t a[n_] := Sum[k Binomial[n - k, k] Subfactorial[n - k - 1], {k, 0, n/2}];

%t a /@ Range[1, 21] (* _Jean-Fran├žois Alcover_, Oct 29 2019 *)

%Y Cf. A000166, A180186.

%Y A column of A216718. - _N. J. A. Sloane_, Sep 15 2012

%K nonn

%O 1,4

%A _Emeric Deutsch_, Sep 06 2010

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 6 18:59 EDT 2020. Contains 334832 sequences. (Running on oeis4.)