login
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.
22
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
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
Column k=1 of A306234, A306461, and of A324362(n-1).
Sequence in context: A350855 A295226 A028418 * A080832 A194019 A020017
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Sep 07 2010
STATUS
approved