login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A055790 a(n) = n*a(n-1) + (n-2)*a(n-2), a(0) = 0, a(1) = 2. 21
0, 2, 4, 14, 64, 362, 2428, 18806, 165016, 1616786, 17487988, 206918942, 2657907184, 36828901754, 547499510764, 8691268384262, 146725287298888, 2624698909845026, 49592184973992676, 986871395973226286, 20630087248996393888, 451982388752415571082 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=1 and n-1 zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al. Extremes of permanents of (0,1)-matrices, p. 201-202. - Jaap Spies, Dec 12 2003

With a(0) = 1, number of degree-(n+1) permutations p such that p(i) != i+2 for each i=1,2,...,n+1. - Vladeta Jovovic, Jan 03 2003

Equivalently number of degree-(n+1) permutations p such that p(i) != i-2 for each i=1,2,...,n+1.

With a(0) = 1, number of degree-(n+1) permutations without fixed points between 2 and n. - Olivier Gérard, Jul 29 2016

Also column 3 of Euler's difference table (third diagonal in example of A068106). - Enrique Navarrete, Oct 31 2016

For n>=2, the number of circular permutations (in cycle notation) on [n+2] that avoid substrings (j,j+3), 1<=j<=n-1.  For example, for n=2, the 4 circular permutations in S4 that avoid the substring {14} are (1234),(1243),(1324),(1342). Note that each of these circular permutations represent 4 permutations in one-line notation (see link 2017). - Enrique Navarrete, Feb 15 2017

REFERENCES

Brualdi, Richard A. and Ryser, Herbert J., Combinatorial Matrix Theory, Cambridge NY (1991), Chapter 7.

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..250

T. Mansour and M. Shattuck, Counting permutations by the number of successors within cycles, Discr. Math., 339 (2016), 1368-1376.

Enrique Navarrete, Generalized K-Shift Forbidden Substrings in Permutations, arXiv:1610.06217 [math.CO], 2016.

Enrique Navarrete, Forbidden Substrings in Circular K-Successions, arXiv:1702.02637 [math.CO], 2017.

Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002). Linear Algebra Appl. 373 (2003), pp. 197-210.

FORMULA

For n > 0, a(n) = round[(n+3+1/n)*n!/e] = 2*A000153(n) = A000255(n-1)+A000255(n) = A000166(n-1)+2*A000166(n)+A000166(n+1).

G.f.: Q(0)*(1+x)/x - 1/x - 2, where Q(k)= 1 + (2*k + 1)*x/( (1+x) - 2*x*(1+x)*(k+1)/(2*x*(k+1) + (1+x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 08 2013

G.f.: (1+x)^2/x/Q(0) - 1/x - 2, where Q(k)= 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 08 2013

G.f.: 2*(1+x)/G(0) - 1-x, where G(k)= 1 + 1/(1 - x*(2*k+2)/(x*(2*k+1) - 1 + x*(2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 31 2013

G.f.: W(0) -1, where W(k) = 1 - x*(k+2)/( x*(k+1) - 1/(1 - x*(k+1)/( x*(k+1) - 1/W(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 26 2013

a(n) ~ sqrt(Pi/2)*n^n*sqrt(n)*(12*n + 37)/(6*exp(n+1)). - Ilya Gutkovskiy, Jul 29 2016

0 = a(n)*(+a(n+1) + 3*a(n+2) - a(n+3)) + a(n+1)*(-a(n+1) + 2*a(n+2) - a(n+3)) + a(n+2)*(+a(n+2)) for n>=0. - Michael Somos, Nov 01 2016

EXAMPLE

G.f. = 2*x + 4*x^2 + 14*x^3 + 64*x^4 + 362*x^5 + 2428*x^6 + ...

a(3) = 3*a(2)+(3-2)*a(1) = 12+2 = 14.

for n=1, the 2 permutations of [2] matches:

12, 21

for n=2, the 4 permutations of [3] without 2 as a fixed point are

132, 213, 231, 312.

for n=3, the 14 permutations of [4] without fixed point at 2 or 3 are

1324 1342 1423    2143 2314 2341 2413

3124 3142 3412 3421    4123 4312 4321

MAPLE

f := proc(n) option remember; if n <= 1 then 2*n else n*f(n-1)+(n-2)*f(n-2); fi; end;

MATHEMATICA

a[0] = 0; a[1] = 2; a[n_] := a[n] = a[n] = n*a[n - 1] + (n - 2)*a[n - 2];

Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Nov 14 2017 *)

RecurrenceTable[{a[0]==0, a[1]==2, a[n]==n*a[n-1]+(n-2)a[n-2]}, a, {n, 30}] (* Harvey P. Dale, May 07 2018 *)

PROG

(Haskell)

a055790 n = a055790_list !! n

a055790_list = 0 : 2 : zipWith (+)

   (zipWith (*) [0..] a055790_list) (zipWith (*) [2..] $ tail a055790_list)

-- Reinhard Zumkeller, Mar 05 2012

(PARI) a(n) = if(n==0, 0, round((n+3+1/n)*n!/exp(1))) \\ Felix Fröhlich, Jul 29 2016

CROSSREFS

Cf. A000166 (Derangements, permutations without fixed points ).

Cf. A000255 (permutations with p(i)!=i+1, same type of recurrence).

Cf. A000153, A000261, A001909, A001910, A090010, A090012-A090016.

Apart from first term, appears in triangles A047920 or A068106 of differences of factorials, i.e. as third term of A000142, A001563, A001564, A001565 etc.

Sequence in context: A089127 A132852 A132079 * A322623 A245139 A020131

Adjacent sequences:  A055787 A055788 A055789 * A055791 A055792 A055793

KEYWORD

nonn

AUTHOR

Henry Bottomley, Jul 13 2000

EXTENSIONS

Comments corrected, new interpretation and examples by Olivier Gérard, Jul 29 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 8 01:46 EST 2019. Contains 329850 sequences. (Running on oeis4.)