A001883 -id:A001883 - cp's OEIS frontend

A001891 Hit polynomials; convolution of natural numbers with Fibonacci numbers F(2), F(3), F(4), ....

0, 1, 4, 10, 21, 40, 72, 125, 212, 354, 585, 960, 1568, 2553, 4148, 6730, 10909, 17672, 28616, 46325, 74980, 121346, 196369, 317760, 514176, 831985, 1346212, 2178250, 3524517, 5702824, 9227400, 14930285, 24157748, 39088098, 63245913, 102334080, 165580064

Offset: 0

N. J. A. Sloane, Simon Plouffe

a(n) is the sum of the n-th row of the triangle in A119457 for n > 0. - Reinhard Zumkeller, May 20 2006
Convolution of odds (A005408) with Fibonacci numbers (A000045). - Graeme McRae, Jun 06 2006
Equals row sums of triangle A152203. - Gary W. Adamson, Nov 29 2008
Define a triangle by T(n,0) = n*(n+1)+1, T(n,n) = 1, and T(r,c) = T(r-1,c) + T(r-2,c-1). This triangle starts: 1; 3,1; 7,2,1; 13,5,2,1; 21,12,4,2,1; the sum of terms in row n is a(n+1). - J. M. Bergot, Apr 23 2013
a(n) = number of k-tuples (u(1), u(2), ..., u(k)) with 1 <= u(1) < u(2) < ... < u(k) <= n such that u(i) - u(i-1) <= 2 for i = 2,...,k. Changing the bound from 2 to 3, then 4, then 5, yields A356619, A356620, A356621. The patterns suggest that the limiting sequence as the bound increases is A000295. - Clark Kimberling, Aug 24 2022

J. Riordan, The enumeration of permutations with three-ply staircase restrictions, unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963. (See A001883)
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
N. J. A. Sloane, Annotated copy of Riordan's Three-Ply Staircase paper (unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963)
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Partial sums of A001911.
A diagonal of triangle in A080061.
Right-hand column 5 of triangle A011794.
Cf. A001883-A001890. A152203.
Cf. A000295, A356619, A356620, A356621.

List([0..40], n-> Fibonacci(n+5) -2*n-5); # G. C. Greubel, Jul 06 2019

[Fibonacci(n+5)-(5+2*n): n in [0..40]]; // Vincenzo Librandi, Jun 07 2013

LinearRecurrence[{3,-2,-1,1}, {0,1,4,10}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 16 2012 *)
Table[Fibonacci[n+5] -(2*n+5), {n,0,40}] (* G. C. Greubel, Jul 06 2019 *)
maxDiff = 2;
Map[Length[Select[Map[{#, Max[Differences[#]]} &,
  Drop[Subsets[Range[#]], # + 1]], #[[2]] <= maxDiff &]] &,
  Range[16]] (* Peter J. C. Moses, Aug 14 2022 *)

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,-1,-2,3]^n*[0;1;4;10])[1,1] \\ Charles R Greathouse IV, Apr 08 2016

[fibonacci(n+5) -2*n-5 for n in (0..40)] # G. C. Greubel, Jul 06 2019

G.f.: x*(1+x)/((1-x-x^2)*(1-x)^2). - Simon Plouffe in his 1992 dissertation
a(n) = Fibonacci(n+5) - (5+2*n). - Wolfdieter Lang
a(n) = a(n-1) + a(n-2) + (2n+1); a(-x)=0. - Barry E. Williams, Mar 27 2000
a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4). - Sam Lachterman (slachterman(AT)fuse.net), Sep 22 2003
a(n) - a(n-1) = A101220(2,1,n). - Ross La Haye, May 31 2006
a(n) = (-3 + (2^(-1-n)*((1-sqrt(5))^n*(-11+5*sqrt(5)) + (1+sqrt(5))^n*(11+5*sqrt(5)))) / sqrt(5) - 2*(1+n)). - Colin Barker, Mar 11 2017

A000211 a(n) = a(n-1) + a(n-2) - 2, a(0) = 4, a(1) = 3.

Original entry on oeis.org

4, 3, 5, 6, 9, 13, 20, 31, 49, 78, 125, 201, 324, 523, 845, 1366, 2209, 3573, 5780, 9351, 15129, 24478, 39605, 64081, 103684, 167763, 271445, 439206, 710649, 1149853, 1860500, 3010351, 4870849, 7881198

Offset: 0

N. J. A. Sloane

Let I=I_n be the n X n identity matrix and P=P_n be the incidence matrix of the cycle (1,2,3,...,n). Then, for n>=3, a(n) is the number of (0,1) n X n matrices A<=P^(-1)+I+P with exactly two 1's in every row and column. - Vladimir Shevelev, Apr 11 2010

J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 233.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics I, Example 4.7.15, p. 252.

T. D. Noe, Table of n, a(n) for n = 0..500
N. Metropolis, M. L. Stein, and P. R. Stein, Permanents of cyclic (0,1) matrices, J. Combin. Theory, 7 (1969), 291-321.
H. Minc, Permanents of (0,1)-circulants, Canad. Math. Bull., 7 (1964), 253-263.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy]
N. J. A. Sloane, Annotated copy of Riordan's Three-Ply Staircase paper (unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963).
K. Yamamoto, Structure polynomial of Latin rectangles and its application to a combinatorial problem, Memoirs of the Faculty of Science, Kyusyu University, Series A, 10 (1956), 1-13.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Cf. A000204.

a000211 n = a000211_list !! n
a000211_list = 4 : 3 : map (subtract 2)
   (zipWith (+) a000211_list (tail a000211_list))
-- Reinhard Zumkeller, Feb 29 2012

A000211:=-(1+z)*(4*z-3)/(z-1)/(z**2+z-1); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence except for the leading 4
with(combinat): seq(fibonacci(n-1)+fibonacci(n+1)+2, n=0..32); # Zerinvary Lajos, Feb 01 2008
a:= n-> (Matrix([[4,1,5]]). Matrix(3, (i,j)-> if (i=j-1) then 1 elif j=1 then [2, 0, -1][i] else 0 fi)^n)[1,1]: seq(a(n), n=0..33); # Alois P. Heinz, Aug 01 2008

Transpose[NestList[{Last[#],First[#]+Last[#]-2}&,{4,3},40]] [[1]]  (* Harvey P. Dale, Mar 22 2011 *)
Table[LucasL[n] + 2, {n, 0, 40}] (* Jean-François Alcover, Jul 30 2015 *)
LinearRecurrence[{2, 0, -1}, {4, 3, 5}, 40] (* Jean-François Alcover, Mar 15 2020 *)

a(n)=([0,1,0; 0,0,1; -1,0,2]^n*[4;3;5])[1,1] \\ Charles R Greathouse IV, Jan 05 2016

G.f.: 2/(1-x)+(2-x)/(1-x-x^2) = (4-5*x-x^2) / ((x-1)*(x^2+x-1)).
a(n) = Lucas number A000032(n) + 2.
Binomial transform of [4, -1, 3, -4, 7, -11, 18, ...], i.e., the series continues as a signed version of the Lucas series, A000204. - Gary W. Adamson, Nov 08 2007
a(n) = F(n-1) + F(n+1) + 2, where F(n) is the n-th Fibonacci number. - Zerinvary Lajos, Feb 01 2008; corrected by Michel Marcus, Jan 05 2021
a(n) = per(I+P+P^2) = per(P^(-1)+I+P). - Vladimir Shevelev, Apr 11 2010
E.g.f.: 2*exp(x/2)*(exp(x/2) + cosh(sqrt(5)*x/2)). - Ilya Gutkovskiy, Feb 01 2017

A000271 Sums of ménage numbers.

Original entry on oeis.org

1, 0, 0, 1, 3, 16, 96, 675, 5413, 48800, 488592, 5379333, 64595975, 840192288, 11767626752, 176574062535, 2825965531593, 48052401132800, 865108807357216, 16439727718351881, 328839946389605643, 6906458590966507696

Offset: 0

N. J. A. Sloane

Permanent of the (0,1)-matrix having (i,j)-th entry equal to 0 iff this is on the diagonal or the first upper-diagonal. - Simone Severini, Oct 14 2004
Equivalently, number of permutations p of {1,2,...,n} such that p(i)-i not in {0,1}. - Andrew Howroyd, Sep 19 2017
From Vladimir Shevelev, Jun 21 2015: (Start)
Let 2*n!*V(n)=A137886(n) be the number of ways of seating n married couples at 2*n chairs arranged side-by-side in a straight line, men and women in alternate positions, so that no husband is next to his wife.
It is known [Riordan, Ch. 8, Th. 1, t=0] that, if 2*n!*U(n) is a solution of an analogous problem at a circular table, then U(n) = V(n) - V(n-1), n>=3, where U(n) = A000179(n). Thus V(n) = Sum_{i=3,...,n} A000179(i), n>=1, and comparing the initial conditions, we conclude that a(n) = V(n), n>=1. This gives a combinatorial interpretation for 2*n!*a(n).
(End)

			G.f. = 1 + x^3 + 3*x^4 + 16*x^5 + 96*x^6 + 675*x^7 + 5413*x^8 + ...

W. Ahrens, Mathematische Unterhaltungen und Spiele. Teubner, Leipzig, Vol. 1, 3rd ed., 1921; Vol. 2, 2nd ed., 1918. See Vol. 2, p. 79.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 198.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff.

Seiichi Manyama, Table of n, a(n) for n = 0..450 (terms 0..100 from T. D. Noe)
W. Ahrens, Mathematische Unterhaltungen und Spiele, Leipzig: B. G. Teubner, 1901.
J. D. H. Dickson, Discussion of two double series arising from the number of terms in determinants of certain forms, Proc. London Math. Soc., 10 (1879), 120-122.
J. D. H. Dickson, Discussion of two double series arising from the number of terms in determinants of certain forms, Proc. London Math. Soc., 10 (1879), 120-122. [Annotated scanned copy]
Dmitry Efimov, Determinants of generalized binary band matrices, arXiv:1702.05655 [math.RA], 2017.
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 222.
Y. Li, Ménage Numbers and Ménage Permutations, J. Int. Seq. 18 (2015) 15.6.8
H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy]
M. Wyman and L. Moser, On the problème des ménages, Canad. J. Math., 10 (1958), 468-480.

Cf. A000179, A000904, A001883, A137886, A292574. A diagonal of A058057.

[ &+[(-1)^(n-k)*Binomial(n+k, 2*k)*Factorial(k): k in [0..n]]: n in [0..21]]; // Bruno Berselli, Apr 11 2011

V := proc(n) local k; add( binomial(2*n-k,k)*(n-k)!*(x-1)^k, k=0..n); end; W := proc(r,s) coeff( V(r),x,s ); end; A000271 := n->W(n-2,0);

Table[Sum[(-1)^(n - k) k! Binomial[n + k, 2 k], {k, 0, n}], {n, 0, 22}] (* Jean-François Alcover, Apr 11 2011, after Paul Barry *)
RecurrenceTable[{a[0] == 1, a[1] == a[2] == 0, a[n] == (n - 1) a[n - 2] + (n - 1) a[n - 1] +  a[n - 3]}, a, {n, 30}] (* Harvey P. Dale, Jun 01 2012 *)
Table[(-1)^n HypergeometricPFQ[{1, -n, n + 1}, {1/2}, 1/4], {n, 20}] (* Michael Somos, May 28 2014 *)

a(n) = if(n, round( 2*exp(-2)*(besselk(n+1,2) + besselk(n,2)) ), 1) \\ Charles R Greathouse IV, May 11 2016

a(n) = (n - 1) a(n - 2) + (n - 1) a(n - 1) + a(n - 3).
From Paul Barry, Feb 08 2009: (Start)
G.f.: 1/(1+x-x/(1+x-x/(1+x-2x/(1+x-2x/(1+x-3x/(1+x-3x/(1+x-4x/(1+... (continued fraction);
a(n) = Sum_{k=0..n} binomial(2n-k,k)*(n-k)!*(-1)^k. (End)
a(n) = (-1)^n*hypergeom([1, -n, n+1],[1/2],1/4). - Mark van Hoeij, Nov 12 2009
a(n) = round( 2*exp(-2)*(BesselK(1+n,2) + BesselK(n,2)) ) for n>0. - Mark van Hoeij, Nov 12 2009
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n+k,2*k)*k!. - Paul Barry, Jun 23 2010
G.f.: Sum_{n>=0} n!*x^n/(1+x)^(2*n+1). - Ira M. Gessel, Jan 15 2013
a(n) ~ exp(-2)*n!. - Vaclav Kotesovec, Mar 10 2014
a(-1 - n) = -a(n) for all n in Z. - Michael Somos, May 28 2014
a(n) = Sum_{i=3..n} A000179(i), n>=1. - Vladimir Shevelev, Jun 21 2015
0 = a(n)*(-a(n+2) - a(n+3)) + a(n+1)*(+a(n+1) + 2*a(n+2) + a(n+3) - a(n+4)) + a(n+2)*(+a(n+2) + 2*a(n+3) - a(n+4)) + a(n+3)*(+a(n+3)) for all n in Z. - Michael Somos, Oct 16 2016

More terms from James Sellers, Aug 21 2000

More terms from Simone Severini, Oct 14 2004

A075851 Number of permutations s of {1,2,...,n} such that |s(i)-i|>2 for each i=1,2,...,n.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 8, 112, 1168, 13365, 159414, 2036488, 27780408, 404351752, 6263006598, 102946702825, 1790795492176, 32880327473840, 635630231970048, 12907624693811937, 274744151265431700, 6117666413618771968, 142238172767973342656

Offset: 0

Reiner Martin, Oct 15 2002

nonn

a(n) equals the permanent of the n X n matrix with 0's along the main diagonal, the superdiagonal, the subdiagonal, the sub-subdiagonal, the super-superdiagonal, and 1's everywhere else. - John M. Campbell, Jul 09 2011

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A001883, A075852.

b:= proc(s) option remember; (n-> `if`(n=0, 1, add(
      `if`(abs(n-i)>2, b(s minus {i}), 0), i=s)))(nops(s))
    end:
a:= n-> b({$1..n}):
seq(a(n), n=0..15);  # Alois P. Heinz, Jan 25 2019

a[0] = 1; a[n_] := a[n] = If[n<6, 0, SparseArray[{Band[{1, 1}] -> 0, Band[{2, 1}] -> 0, Band[{3, 1}] -> 0, Band[{1, 2}] -> 0, Band[{1, 3}] -> 0}, {n, n}, 1] // Permanent];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 23}] (* Jean-François Alcover, Apr 30 2019 *)

More terms from Vladimir Baltic, Vladeta Jovovic, Jan 04 2003
a(21) from Alois P. Heinz, Jul 04 2015
a(22)-a(23) from Alois P. Heinz, Jan 22 2019
a(0)=1 prepended by Alois P. Heinz, Jan 25 2019

A075852 Number of permutations s of {1,2,...,n} such that |s(i)-i|>3 for each i=1,2,...,n.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 1, 16, 436, 6984, 114124, 1799688, 29125117, 486980182, 8490078104, 154750897552, 2951968964768, 58917663227568, 1229367602071416, 26787823838035750, 608794318333169289, 14411810690642972432

Offset: 0

Reiner Martin, Oct 15 2002

nonn

a(n) equals the permanent of the n X n matrix with 0's along the main diagonal, the subdiagonal, the superdiagonal, the sub-subdiagonal, the super-superdiagonal, the sub-sub-subdiagonal, the super-super-superdiagonal, and 1's everywhere else. - John M. Campbell, Jul 09 2011

Alois P. Heinz, Table of n, a(n) for n = 0..450
George Spahn and Doron Zeilberger, Automatic Counting of Generalized Latin Rectangles and Trapezoids, arXiv:2108.11285 [math.CO], 2021.

Cf. A001883, A075851.

b:= proc(s) option remember; (n-> `if`(n=0, 1, add(
      `if`(abs(n-i)>3, b(s minus {i}), 0), i=s)))(nops(s))
    end:
a:= n-> b({$1..n}):
seq(a(n), n=0..15);  # Alois P. Heinz, Jan 25 2019

a[0] = 1; a[n_] := a[n] = If[n < 8, 0, SparseArray[{Band[{1, 1}] -> 0, Band[{2, 1}] -> 0, Band[{3, 1}] -> 0, Band[{4, 1}] -> 0, Band[{1, 2}] -> 0, Band[{1, 3}] -> 0, Band[{1, 4}] -> 0}, {n, n}, 1] // Permanent];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 23}] (* Jean-François Alcover, May 01 2019 *)

More terms from Vladimir Baltic, Vladeta Jovovic, Jan 04 2003
a(21) from Alois P. Heinz, Jul 04 2015
a(22)-a(23) from Alois P. Heinz, Jan 22 2019
a(0)=1 prepended by Alois P. Heinz, Jan 25 2019

A183244 T(n,k) = Number of permutations of 1..n+2*k-1 with each element displaced by at least k.

Original entry on oeis.org

1, 1, 2, 1, 4, 9, 1, 8, 29, 44, 1, 16, 112, 206, 265, 1, 32, 436, 1168, 1708, 1854, 1, 64, 1708, 6984, 13365, 15702, 14833, 1, 128, 6724, 41808, 114124, 159414, 159737, 133496, 1, 256, 26572, 250464, 998112, 1799688, 2036488, 1780696, 1334961, 1, 512

Offset: 1

R. H. Hardin, Jan 03 2011

Table starts
........1.........1..........1............1.............1...............1
........2.........4..........8...........16............32..............64
........9........29........112..........436..........1708............6724
.......44.......206.......1168.........6984.........41808..........250464
......265......1708......13365.......114124........998112.........8751552
.....1854.....15702.....159414......1799688......21201024.......252813312
....14833....159737....2036488.....29125117.....441629332......6860776320
...133496...1780696...27780408....486980182....9154333160....178195229760
..1334961..21599745..404351752...8490078104..192565379941...4564491262444
.14684570.283294740.6263006598.154750897552.4146526612518.116967725946488

			All permutations of 1-5 with minimum displacement 2:
(3,4,5,1,2) (3,4,5,2,1) (4,5,1,2,3) (5,4,1,2,3).

R. H. Hardin, Table of n, a(n) for n = 1..201

Column 1 is A000166(n+1).
Column 2 is A001883(n+3).
Column 3 is A075851(n+5).
Column 4 is A075852(n+7).

T[n_, k_] := Permanent[nrows = n+2k-1; Table[If[Abs[i-j] <= k-1, 0, 1], {i, 1, nrows}, {j, 1, nrows}]]; Table[t = T[n-k+1, k]; Print[ "T(", n-k+1, ",", k, ") = ", t]; t, {n, 1, 9}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jan 07 2016, adapted from Sage *)

def A183244_T(n,k):
    return Matrix(lambda i,j: 0 if abs(i-j) <= (k-1) else 1, nrows=n+2*k-1).permanent() # D. S. McNeil, Jan 04 2011

A080018 Triangle of coefficients of polynomials P(n; x) = Permanent(M), where M=[m(i,j)] is n X n matrix defined by m(i,j)=x if -1<=i-j<=1 else m(i,j)=1.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 1, 2, 3, 1, 2, 10, 6, 5, 4, 20, 28, 44, 16, 8, 29, 104, 207, 180, 151, 36, 13, 206, 775, 1288, 1407, 830, 437, 76, 21, 1708, 6140, 10366, 10384, 7298, 3100, 1138, 152, 34, 15702, 55427, 91296, 92896, 63140, 31278, 10048, 2744, 294, 55

Offset: 0

Vladeta Jovovic, Vladimir Baltic, Jan 20 2003

			1;
0,  1;
0,  0,  2;
0,  1,  2,  3;
1,  2, 10,  6,  5;
4, 20, 28, 44, 16, 8;
...
P(4; x) = Permanent(MATRIX([[x, x, 1, 1], [x, x, x, 1], [1, x, x, x], [1, 1, x, x]])) = 1+2*x+10*x^2+6*x^3+5*x^4.

J. Riordan, The enumeration of permutations with three-ply staircase restrictions, unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963. See Table 1. - N. J. A. Sloane, Aug 27 2013

Alois P. Heinz, Rows n = 0..20, flattened

Row sums = A000142, first column = A001883, second column = A001884, third column = A001885, fourth column = A001886.

Main diagonal and lower diagonal give: A000045(n+1), A178523. - Alois P. Heinz, Jul 03 2013

with(LinearAlgebra):
T:= proc(n) option remember; local p;
      if n=0 then 1 else
        p:= Permanent(Matrix(n, (i,j)-> `if`(abs(i-j)<2, x, 1)));
        seq(coeff(p, x, i), i=0..n)
      fi
    end:
seq(T(n), n=0..10);  # Alois P. Heinz, Jul 03 2013

t[0] = {1}; t[n_] := CoefficientList[Permanent[Array[If[Abs[#1 - #2] < 2, x, 1]&, {n, n}]], x]; Table[t[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 24 2014, after Alois P. Heinz *)

A080061 Triangle of coefficients of polynomials P(n; x) = Permanent(M), where M=[m(i,j)] is n X n matrix defined by m(i,j)=x if 0<=i-j<=2 else m(i,j)=1.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 4, 1, 1, 4, 8, 10, 1, 5, 21, 38, 34, 21, 1, 33, 122, 209, 206, 109, 40, 1, 236, 849, 1400, 1351, 836, 295, 72, 1, 1918, 6719, 10849, 10543, 6629, 2821, 715, 125, 1, 17440, 59873, 95516, 92708, 60284, 26870, 8372, 1604, 212, 1, 175649, 593686

Offset: 0

Vladeta Jovovic, Vladimir Baltic, Jan 23 2003

			1;
0,1;
0,1,1;
0,1,4,1;
1,4,8,10,1;
5,21,38,34,21,1;
... P(5; x) = Permanent(Matrix(5, 5, [[x,1,1,1,1],[x,x,1,1,1],[x,x,x,1,1],[1,x,x,x,1],[1,1,x,x,x]]))= 5+21*x+38*x^2+34*x^3+21*x^4+x^5.

J. Riordan, The enumeration of permutations with three-ply staircase restrictions, unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963. See Table 1. - N. J. A. Sloane, Aug 27 2013 (See A001883)

R. J. Mathar, Table of n, a(n) for n = 0..209

Row sums = A000142, first column = A001887, second column = A001888, third column = A001889, fourth column = A001890, A080018.

Cf. A001883.

A080061_line := proc(n)
    local M,r,c,p,pord ;
    if n = 0 then
        return [1] ;
    else
        M := Matrix(n,n) ;
        for r to n do
        for c to n do
            if r-c >=0 and r-c <=2 then
                M[r,c] := x ;
            else
                M[r,c] := 1 ;
            end if;
        end do:
        end do:
        p := LinearAlgebra[Permanent](M) ;
        pord := degree(p) ;
        [seq( coeff(p,x,r),r=0..pord)] ;
    end if;
end proc:
for n from 0 to 10 do
    print(A080061_line(n)) ;
end do: # R. J. Mathar, Sep 18 2013

M[n_] := Table[If[0 <= i-j <= 2, x, 1], {i, 1, n}, {j, 1, n}]; M[0]={{1}}; Table[CoefficientList[Permanent[M[n]], x], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 06 2016 *)

A299789 Number T(n,k) of permutations p of [n] such that min_{j=1..n} |p(j)-j| = k; triangle T(n,k), n >= 0, 0 <= k <= floor(n/2), read by rows.

Original entry on oeis.org

0, 1, 1, 1, 4, 2, 15, 8, 1, 76, 40, 4, 455, 236, 28, 1, 3186, 1648, 198, 8, 25487, 13125, 1596, 111, 1, 229384, 117794, 14534, 1152, 16, 2293839, 1175224, 146372, 12929, 435, 1, 25232230, 12903874, 1621282, 152430, 6952, 32, 302786759, 154615096, 19563257, 1922364, 112416, 1707, 1

Offset: 0

Alois P. Heinz, Jan 21 2019

			T(4,0) = 15: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2314, 2431, 3124, 3214, 3241, 4132, 4213, 4231.
T(4,1) = 8: 2143, 2341, 2413, 3142, 3421, 4123, 4312, 4321.
T(4,2) = 1: 3412.
T(5,2) = 4: 34512, 34521, 45123, 54123.
T(6,3) = 1: 456123.
T(7,3) = 8: 4567123, 4567132, 4567213, 4567231, 5671234, 5761234, 6571234, 7561234.
T(8,4) = 1: 56781234.
T(9,4) = 16: 567891234, 567891243, 567891324, 567891342, 567892134, 567892143, 567892314, 567892341, 678912345, 679812345, 687912345, 697812345, 768912345, 769812345, 867912345, 967812345.
Triangle T(n,k) begins:
          0;
          1;
          1,         1;
          4,         2;
         15,         8,        1;
         76,        40,        4;
        455,       236,       28,       1;
       3186,      1648,      198,       8;
      25487,     13125,     1596,     111,      1;
     229384,    117794,    14534,    1152,     16;
    2293839,   1175224,   146372,   12929,    435,    1;
   25232230,  12903874,  1621282,  152430,   6952,   32;
  302786759, 154615096, 19563257, 1922364, 112416, 1707, 1;
  ...

Alois P. Heinz, Rows n = 0..21, flattened

Columns k=0-1 give: A002467, A296050.
Row sums give A000142 (for n>0).
T(2n,n) gives A057427.
T(2n+1,n) gives A000079.
T(2n+2,n) gives A306545.
Cf. A000166, A001883, A075851, A075852, A129118, A130152, A306543.

b:= proc(s) option remember; (n-> `if`(n=1, x^(s[1]-1),
      add((p-> add(coeff(p, x, i)*x^min(i, abs(n-j)),
      i=0..degree(p)))(b(s minus {j})), j=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..max(0, degree(p))))(b({$1..n})):
seq(T(n), n=0..14);
# second Maple program:
A:= proc(n, k) option remember; `if`(n=0, 0, LinearAlgebra[
      Permanent](Matrix(n, (i, j)-> `if`(abs(i-j)>=k, 1, 0))))
    end:
T:= (n, k)-> A(n, k)-A(n, k+1):
seq(seq(T(n, k), k=0..n/2), n=0..14);

A[n_, k_] := A[n, k] = If[n==0, 0, Permanent[Table[If[Abs[i-j] >= k, 1, 0], {i, 1, n}, {j, 1, n}]]];
T[n_, k_] := A[n, k] - A[n, k+1];
Table[T[n, k], {n, 0, 14}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, May 01 2019, from 2nd Maple program *)

T(n,k) = A306543(n,k) - A306543(n,k+1) for n > 0.
Sum_{k=1..floor(n/2)} k * T(n,k) = A129118(n).
Sum_{k=1..floor(n/2)} T(n,k) = A000166(n).
Sum_{k=2..floor(n/2)} T(n,k) = A001883(n).
Sum_{k=3..floor(n/2)} T(n,k) = A075851(n).
Sum_{k=4..floor(n/2)} T(n,k) = A075852(n).

A323671 Number T(n,k) of permutations p of [n] with no fixed points such that |{ j : |p(j)-j| = 1 }| = k; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 0, 2, 0, 1, 2, 3, 2, 1, 4, 12, 14, 8, 6, 0, 29, 68, 82, 54, 25, 6, 1, 206, 496, 546, 376, 170, 48, 12, 0, 1708, 3960, 4349, 2922, 1353, 430, 98, 12, 1, 15702, 35816, 38632, 26048, 12084, 4052, 982, 160, 20, 0, 159737, 358786, 383523, 257552, 120919, 41508, 10647, 1998, 270, 20, 1

Offset: 0

Alois P. Heinz, Jan 23 2019

			T(4,0) = 1: 3412.
T(4,1) = 2: 3421, 4312.
T(4,2) = 3: 2413, 3142, 4321.
T(4,3) = 2: 2341, 4123.
T(4,4) = 1: 2143.
Triangle T(n,k) begins:
      1;
      0,     0;
      0,     0,     1;
      0,     0,     2,     0;
      1,     2,     3,     2,     1;
      4,    12,    14,     8,     6,    0;
     29,    68,    82,    54,    25,    6,   1;
    206,   496,   546,   376,   170,   48,  12,   0;
   1708,  3960,  4349,  2922,  1353,  430,  98,  12,  1;
  15702, 35816, 38632, 26048, 12084, 4052, 982, 160, 20, 0;
  ...

Alois P. Heinz, Rows n = 0..23, flattened

Column k=0 gives A001883.
Row sums give A000166.
Main diagonal and lower diagonal give A059841, A110660.
Cf. A296050, A320582.

b:= proc(s) option remember; expand((n-> `if`(n=0, 1, add(
      (t-> `if`(t=0, 0, `if`(t=1, x, 1)*b(s minus {j}))
       )(abs(n-j)), j=s)))(nops(s)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b({$1..n})):
seq(T(n), n=0..12);

b[s_] := b[s] = Expand[Function[n, If[n==0, 1, Sum[Function[t, If[t==0, 0, If[t==1, x, 1]*b[s~Complement~{j}]]][Abs[n-j]], {j, s}]]][Length[s]]];
T[n_] := PadRight[CoefficientList[b[Range[n]], x], n+1];
T /@ Range[0, 12] // Flatten (* Jean-François Alcover, Feb 09 2021, after Alois P. Heinz *)

Sum_{k=1..n} T(n,k) = A296050(n).

cp's OEIS Frontend

A001891 Hit polynomials; convolution of natural numbers with Fibonacci numbers F(2), F(3), F(4), ....

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A000211 a(n) = a(n-1) + a(n-2) - 2, a(0) = 4, a(1) = 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A000271 Sums of ménage numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A075851 Number of permutations s of {1,2,...,n} such that |s(i)-i|>2 for each i=1,2,...,n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A075852 Number of permutations s of {1,2,...,n} such that |s(i)-i|>3 for each i=1,2,...,n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A183244 T(n,k) = Number of permutations of 1..n+2*k-1 with each element displaced by at least k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

A080018 Triangle of coefficients of polynomials P(n; x) = Permanent(M), where M=[m(i,j)] is n X n matrix defined by m(i,j)=x if -1<=i-j<=1 else m(i,j)=1.