A180191 - OEIS

%I #59 Jul 04 2021 20:48:56

%S 0,1,3,13,67,411,2921,23633,214551,2160343,23897269,288102189,

%T 3760013027,52816397219,794536751217,12744659120521,217140271564591,

%U 3916221952414383,74539067188152941,1493136645424092773,31400620285465593339,691708660911435955579

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

%C a(n) = A180190(n,1).

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

%C From _Jon Perry_, Jan 04 2013: (Start)

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

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

%C (End)

%C For n > 0: row sums of triangle A116853. - _Reinhard Zumkeller_, Aug 31 2014

%H Alois P. Heinz, <a href="/A180191/b180191.txt">Table of n, a(n) for n = 1..200</a>

%H Uriel Feige, <a href="http://www.wisdom.weizmann.ac.il/~feige/mypapers/OnlineMatchingFeige2018.pdf">Tighter bounds for online bipartite matching</a>, 2018.

%F a(n) = n! - d(n) - d(n-1), where d(j) = A000166(j) are the derangement numbers.

%F a(n) = n! - A000255(n-1) = A002467(n) - A000166(n-1). - _Jon Perry_, Jan 05 2013

%F a(n) = (n-1)! [x^(n-1)] (1-exp(-x))/(1-x)^2. - _Alois P. Heinz_, Feb 23 2019

%e x^2 + 3*x^3 + 13*x^4 + 67*x^5 + 411*x^6 + 2921*x^7 + 23633*x^8 + ...

%e a(3) = 3 because we have 123, 312, and 231; the permutations 132, 213, and 321 have no successions.

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

%p 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);

%t f[n_] := Sum[ -(-1)^k (n - k)! Binomial[n - 1, k], {k, 1, n}]; Array[f, 20] (* _Robert G. Wilson v_, Oct 16 2010 *)

%o (PARI) {a(n) = if( n<2, 0, n--; subst( polinterpolate( vector( n, k, k!)), x, n+1))} /* _Michael Somos_, Jan 05 2012 */

%o (Haskell)

%o a180191 n = if n == 1 then 0 else sum $ a116853_row (n - 1)

%o -- _Reinhard Zumkeller_, Aug 31 2014

%Y Cf. A000142, A000166, A000255, A002467, A028417, A180190.

%Y Cf. A116853, A276975.

%Y Column k=1 of A306234, A306461, and of A324362(n-1).

%K nonn

%O 1,3

%A _Emeric Deutsch_, Sep 07 2010