The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A180191 Number of permutations of [n] having at least one succession. A succession of a permutation p is a position i such that p(i+1)-p(i) = 1. 21
 0, 1, 3, 13, 67, 411, 2921, 23633, 214551, 2160343, 23897269, 288102189, 3760013027, 52816397219, 794536751217, 12744659120521, 217140271564591, 3916221952414383, 74539067188152941, 1493136645424092773, 31400620285465593339, 691708660911435955579 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS a(n) = A180190(n,1). a(n+2) = p(n+2) where p(x) is the unique degree-n polynomial such that p(k) = k! for k = 1, ..., n+1. - Michael Somos, Jan 05 2012 From Jon Perry, Jan 04 2013: (Start) Number of permutations of {1,...,n-1,n+1} with at least one indexed point p(k)=k with 1<=k<=n. Note that this means p(k)=n+1 is never an indexed point as k1, a(n) is the number of permutations of [n+1] that have a fixed point and contain 12; for example the a(3)=3 such permutations of {1,2,3,4} are 1234, 1243, and 3124. (End) For n > 0: row sums of triangle A116853. - Reinhard Zumkeller, Aug 31 2014 LINKS Alois P. Heinz, Table of n, a(n) for n = 1..200 Uriel Feige, Tighter bounds for online bipartite matching, 2018. FORMULA a(n) = n! - d(n) - d(n-1), where d(j) = A000166(j) are the derangement numbers. a(n) = n! - A000255(n-1) = A002467(n) - A000166(n-1). - Jon Perry, Jan 05 2013 a(n) = (n-1)! [x^(n-1)] (1-exp(-x))/(1-x)^2. - Alois P. Heinz, Feb 23 2019 EXAMPLE x^2 + 3*x^3 + 13*x^4 + 67*x^5 + 411*x^6 + 2921*x^7 + 23633*x^8 + ... a(3) = 3 because we have 123, 312, and 231; the permutations 132, 213, and 321 have no successions. a(4) = 13 since p(x) = (3*x^2 - 7*x + 6) / 2 interpolates p(1) = 1, p(2) = 2, p(3) = 6, and p(4) = 13. - Michael Somos, Jan 05 2012 MAPLE d := 1: for n to 50 do d[n] := n*d[n-1]+(-1)^n end do: seq(factorial(n)-d[n]-d[n-1], n = 1 .. 22); MATHEMATICA f[n_] := Sum[ -(-1)^k (n - k)! Binomial[n - 1, k], {k, 1, n}]; Array[f, 20] (* Robert G. Wilson v, Oct 16 2010 *) PROG (PARI) {a(n) = if( n<2, 0, n--; subst( polinterpolate( vector( n, k, k!)), x, n+1))} /* Michael Somos, Jan 05 2012 */ (Haskell) a180191 n = if n == 1 then 0 else sum \$ a116853_row (n - 1) -- Reinhard Zumkeller, Aug 31 2014 CROSSREFS Cf. A000142, A000166, A000255, A002467, A028417, A180190. Cf. A116853, A276975. Column k=1 of A306234, A306461, and of A324362(n-1). Sequence in context: A350855 A295226 A028418 * A080832 A194019 A020017 Adjacent sequences: A180188 A180189 A180190 * A180192 A180193 A180194 KEYWORD nonn AUTHOR Emeric Deutsch, Sep 07 2010 STATUS approved

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

Last modified September 22 17:59 EDT 2023. Contains 365531 sequences. (Running on oeis4.)