A180190 -id:A180190 - 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.

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

Offset: 1

Emeric Deutsch, Sep 07 2010

nonn

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 kFor 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

			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

Alois P. Heinz, Table of n, a(n) for n = 1..200
Uriel Feige, Tighter bounds for online bipartite matching, 2018.

Cf. A000142, A000166, A000255, A002467, A028417, A180190.
Cf. A116853, A276975.
Column k=1 of A306234, A306461, and of A324362(n-1).

a180191 n = if n == 1 then 0 else sum $ a116853_row (n - 1)
-- Reinhard Zumkeller, Aug 31 2014

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

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

{a(n) = if( n<2, 0, n--; subst( polinterpolate( vector( n, k, k!)), x, n+1))} /* Michael Somos, Jan 05 2012 */

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

A018927 For each permutation p of {1,2,...,n} define maxjump(p) = max(p(i) - i); a(n) is sum of maxjumps of all p.

Original entry on oeis.org

0, 1, 7, 45, 313, 2421, 20833, 198309, 2073793, 23664021, 292834513, 3907994949, 55967406433, 856355084661, 13944569166193, 240803714700069, 4395998055854593, 84596337986326101, 1711691067680320273, 36329581765125539589, 807099012174816776353

Offset: 1

Emeric Deutsch

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..448
Aubrey Blecher, Charlotte Brennan, Arnold Knopfmacher, Toufik Mansour, and Mark Shattuck, Pushes in permutations, J. Comb. Math. Comb. Comp. (2020) Vol. 115, 77-95.

Cf. A056151, A127452, A130153, A180190.

Table[Sum[k*k!*((k+1)^(n-k)-k^(n-k)),{k,0,n-1}],{n,1,20}] (* Vaclav Kotesovec, Mar 17 2014 *)

a(n) = Sum_{k=0..n-1} k*k!*((k+1)^(n-k)-k^(n-k)).
a(n) = Sum_{k=0..n*(n-1)/2} k*A127452(n-1,k). - Paul D. Hanna, Jan 15 2007
a(n) = Sum_{k=0..n-1} k * A180190(n,k). - Alois P. Heinz, Feb 21 2019

Showing 1-2 of 2 results.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula