cp's OEIS Frontend

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.

%I A180191 #59 Jul 04 2021 20:48:56
%S A180191 0,1,3,13,67,411,2921,23633,214551,2160343,23897269,288102189,
%T A180191 3760013027,52816397219,794536751217,12744659120521,217140271564591,
%U A180191 3916221952414383,74539067188152941,1493136645424092773,31400620285465593339,691708660911435955579
%N 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.
%C A180191 a(n) = A180190(n,1).
%C A180191 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 A180191 From _Jon Perry_, Jan 04 2013: (Start)
%C A180191 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 A180191 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 A180191 (End)
%C A180191 For n > 0: row sums of triangle A116853. - _Reinhard Zumkeller_, Aug 31 2014
%H A180191 Alois P. Heinz, <a href="/A180191/b180191.txt">Table of n, a(n) for n = 1..200</a>
%H A180191 Uriel Feige, <a href="http://www.wisdom.weizmann.ac.il/~feige/mypapers/OnlineMatchingFeige2018.pdf">Tighter bounds for online bipartite matching</a>, 2018.
%F A180191 a(n) = n! - d(n) - d(n-1), where d(j) = A000166(j) are the derangement numbers.
%F A180191 a(n) = n! - A000255(n-1) = A002467(n) - A000166(n-1). - _Jon Perry_, Jan 05 2013
%F A180191 a(n) = (n-1)! [x^(n-1)] (1-exp(-x))/(1-x)^2. - _Alois P. Heinz_, Feb 23 2019
%e A180191 x^2 + 3*x^3 + 13*x^4 + 67*x^5 + 411*x^6 + 2921*x^7 + 23633*x^8 + ...
%e A180191 a(3) = 3 because we have 123, 312, and 231; the permutations 132, 213, and 321 have no successions.
%e A180191 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 A180191 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 A180191 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 A180191 (PARI) {a(n) = if( n<2, 0, n--; subst( polinterpolate( vector( n, k, k!)), x, n+1))} /* _Michael Somos_, Jan 05 2012 */
%o A180191 (Haskell)
%o A180191 a180191 n = if n == 1 then 0 else sum $ a116853_row (n - 1)
%o A180191 -- _Reinhard Zumkeller_, Aug 31 2014
%Y A180191 Cf. A000142, A000166, A000255, A002467, A028417, A180190.
%Y A180191 Cf. A116853, A276975.
%Y A180191 Column k=1 of A306234, A306461, and of A324362(n-1).
%K A180191 nonn
%O A180191 1,3
%A A180191 _Emeric Deutsch_, Sep 07 2010