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.

0, 1, 3, 13, 67, 411, 2921, 23633, 214551, 2160343, 23897269, 288102189, 3760013027, 52816397219, 794536751217, 12744659120521, 217140271564591, 3916221952414383, 74539067188152941, 1493136645424092773, 31400620285465593339, 691708660911435955579

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 k<n+1. Permutations of {1,2,4} with an indexed point p(k)=k are 124, 142 and 421, so a(3)=3.

For n>1, 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[0] := 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