|
| |
|
|
A055790
|
|
a(n) = n*a(n-1) + (n-2)*a(n-2), a(0) = 0, a(1) = 2.
|
|
27
|
|
|
|
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
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
|
|
|
|
FORMULA
|
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];
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)
(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).
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Comments corrected, new interpretation and examples by Olivier Gérard, Jul 29 2016
|
|
|
STATUS
|
approved
|
| |
|
|
