A259776 -id:A259776 - cp's OEIS frontend

A259784 Number T(n,k) of permutations p of [n] with no fixed points where the maximal displacement of an element equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 1, 3, 5, 0, 0, 0, 6, 18, 20, 0, 0, 1, 12, 44, 111, 97, 0, 0, 0, 24, 116, 396, 744, 574, 0, 0, 1, 44, 331, 1285, 3628, 5571, 3973, 0, 0, 0, 84, 932, 4312, 15038, 34948, 46662, 31520, 0, 0, 1, 159, 2532, 15437, 59963, 181193, 359724, 434127, 281825, 0

Offset: 0

Alois P. Heinz, Jul 05 2015

			Triangle T(n,k) begins:
  1;
  0, 0;
  0, 1,  0;
  0, 0,  2,   0;
  0, 1,  3,   5,    0;
  0, 0,  6,  18,   20,    0;
  0, 1, 12,  44,  111,   97,    0;
  0, 0, 24, 116,  396,  744,  574,    0;
  0, 1, 44, 331, 1285, 3628, 5571, 3973, 0;

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

Rows sums give A000166.
Column k=0 and main diagonal give A000007.
Columns k=1-10 give: A059841 (for n>0), A321048, A321049, A321050, A321051, A321052, A321053, A321054, A321055, A321056.
First lower diagonal gives A259834.
T(2n,n) gives A259785.
Cf. A259776.

b:= proc(n, s, k) option remember; `if`(n=0, 1, `if`(n+k in s,
      b(n-1, (s minus {n+k}) union `if`(n-k>1, {n-k-1}, {}), k),
      add(`if`(j=n, 0, b(n-1, (s minus {j}) union
      `if`(n-k>1, {n-k-1}, {}), k)), j=s)))
    end:
A:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), b(n, {$max(1, n-k)..n}, k)):
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..12);

b[n_, s_, k_] := b[n, s, k] = If[n==0, 1, If[MemberQ[s, n+k], b[n-1, (s ~Complement~ {n+k}) ~Union~ If[n-k>1, {n-k-1}, {}], k], Sum[If[j==n, 0, b[n-1, (s ~Complement~ {j}) ~Union~ If[n-k>1, {n-k-1}, {}], k]], {j, s}]] ];
A[n_, k_] := If[k == 0, If[n == 0, 1, 0], b[n, Range[Max[1, n-k], n], k]];
T[n_, k_] :=  A[n, k] - If[k == 0, 0, A[n, k-1]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 05 2019, after Alois P. Heinz *)

T(n,k) = A259776(n,k) - A259776(n,k-1) for k>0, T(n,0) = A000007(n).

A033305 Number of permutations (p1,...,pn) such that 1 <= |pk - k| <= 2 for all k.

Original entry on oeis.org

1, 0, 1, 2, 4, 6, 13, 24, 45, 84, 160, 300, 565, 1064, 2005, 3774, 7108, 13386, 25209, 47472, 89401, 168360, 317056, 597080, 1124425, 2117520, 3987721, 7509690, 14142276, 26632782, 50154949, 94451976, 177872293

Offset: 0

N. J. A. Sloane

Lehmer, D. H.; Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755-770. North-Holland, Amsterdam, 1970.
R. P. Stanley, Enumerative Combinatorics I, p. 252, Example 4.7.16.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Vladimir Kruchinin and D. V. Kruchinin, Composita and their properties, arXiv:1103.2582 [math.CO], 2011-2013.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,-1).

Column k=2 of A259776.

Cf. A112575, A183324, A260074.

I:=[1,0,1,2,4]; [n le 5 select I[n] else Self(n-1) +Self(n-2) +Self(n-3) +Self(n-4) -Self(n-5): n in [1..41]]; // G. C. Greubel, Jan 14 2022

LinearRecurrence[{1,1,1,1,-1},{1,0,1,2,4},40] (* Harvey P. Dale, Aug 28 2012 *)

h(n) := sum(sum(binomial(k,r) *sum(binomial(r,m) *sum(binomial(m,j) *binomial(j,n-m-k-j-r) *(-1)^(n-m-k-j-r), j,0,m), m,0,r), r,0,k), k,1,n); a(n):=h(n)-h(n-1); /* Vladimir Kruchinin, Sep 10 2010 */

[( (1-x)/((1+x)*(1-2*x+x^2-2*x^3+x^4)) ).series(x,n+1).list()[n] for n in (0..40)] # G. C. Greubel, Jan 14 2022

G.f.: (1-x)/((1+x)*(1 - 2*x + x^2 - 2*x^3 + x^4)).
a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) - a(n-5).
a(n) = h(n) - h(n-1), n>0, h(n) = Sum_{k=1..n} (Sum_{r=0..k} (C(k,r)*Sum_{m=0..r}(C(r,m)*Sum_{j=0..m} C(m,j)*C(j,n-m-k-j-r)*(-1)^(n-m-k-j-r) ))). - Vladimir Kruchinin, Sep 10 2010
Limit_{n -> oo} a(n)/a(n-1) = (1 + sqrt(2) + sqrt(2*sqrt(2)-1)) /2 = 1.88320350591... for n>2. Limit_{n -> oo} a(n-1)/a(n) = (1 + sqrt(2) - sqrt(2*sqrt(2)-1)) /2 = 0.53101005645... for n>0. - Tim Monahan, Aug 09 2011
7*a(n) = 2*(-1)^n - 8*A112575(n) - 2*A112575(n-2) + 6*A112575(n-1) + 5*A112575(n+1). - R. J. Mathar, Sep 27 2013
Empirical: a(n) + a(n+1) = A183324(n). - R. J. Mathar, Sep 27 2013

New description from Max Alekseyev, Jul 09 2006

A079997 Number of permutations satisfying -k<=p(i)-i<=r and p(i)-i not in I, i=1..n, with k=3, r=3, I={0}.

Original entry on oeis.org

1, 0, 1, 2, 9, 24, 57, 140, 376, 1016, 2692, 7020, 18369, 48344, 127465, 335510, 882081, 2319136, 6100393, 16049440, 42220168, 111053856, 292109320, 768373144, 2021186393, 5316647448, 13985104873, 36786882378, 96765680857, 254536684328

Offset: 0

Vladimir Baltic, Feb 17 2003

D. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755-770. North-Holland, Amsterdam, 1970.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135
Index entries for linear recurrences with constant coefficients, signature (1, 3, 0, 6, 10, 0, -12, -10, -2, 0, 0, -1, 1, 1).

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.
Column k=3 of A259776.
Cf. A260081.

LinearRecurrence[{1,3,0,6,10,0,-12,-10,-2,0,0,-1,1,1},{1,0,1,2,9,24,57,140,376,1016,2692,7020,18369,48344},40] (* Harvey P. Dale, Nov 27 2013 *)

a(n) = a(n-1)+3*a(n-2)+6*a(n-4)+10*a(n-5)-12*a(n-7)-10*a(n-8)-2*a(n-9)-a(n-12)+a(n-13)+a(n-14)

G.f.: -(x^8+x^7-x^5-2*x^4+x^3-2*x^2-x+1)/(x^14 +x^13 -x^12 -2*x^9 -10*x^8 -12*x^7 +10*x^5 +6*x^4 +3*x^2 +x-1).

A259777 Number of permutations p of [n] with no fixed points and displacement of elements restricted by four: 1 <= |p(i)-i| <= 4.

Original entry on oeis.org

1, 0, 1, 2, 9, 44, 168, 536, 1661, 5328, 18129, 62592, 214657, 726614, 2438656, 8192120, 27614544, 93315688, 315490856, 1065719578, 3597204049, 12138879608, 40968868129, 138302514360, 466929286109, 1576394674460, 5321736915096, 17964911573280, 60645076322201

Offset: 0

Alois P. Heinz, Jul 05 2015

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

Column k=4 of A259776.

Cf. A260092.

b[n_, s_, k_] := b[n, s, k] = If[n == 0, 1, If[MemberQ[s, n + k], b[n - 1, Join[s ~Complement~ {n + k}] ~Union~ If[n - k > 1, {n - k - 1}, {}], k], Sum[If[j == n, 0, b[n - 1, Join[s ~Complement~ {j}] ~Union~ If[n - k > 1, {n - k - 1}, {}], k]], {j, s}]]];
A[n_, k_] := If[k == 0, If[n == 0, 1, 0], b[n, Range[Max[1, n-k], n], k]];
Table[A[n, 4], {n, 0, 30}] (* Jean-François Alcover, Oct 18 2021, after Alois P. Heinz in A259776 *)

G.f.: (-x^35 +4*x^33 +2*x^32 -3*x^31 -3*x^30 +9*x^29 -10*x^28 +8*x^27 -9*x^26 -61*x^25 -39*x^24 +62*x^23 -12*x^22 -176*x^21 +95*x^20 +36*x^19 -10*x^18 +58*x^17 +132*x^16 -81*x^15 +38*x^14 +166*x^13 -104*x^12 +35*x^11 -51*x^10 -135*x^9 +36*x^8 -10*x^7 +3*x^6 +27*x^5 -x^4 +2*x^2 +2*x -1) / (x^43 -5*x^41 -x^39 +x^38 +13*x^37 -5*x^36 +x^35 +15*x^34 +93*x^33 +15*x^32 +7*x^31 -11*x^30 +7*x^29 -7*x^28 -97*x^27 -215*x^26 -731*x^25 -437*x^24 +339*x^23 -323*x^22 -941*x^21 +85*x^20 +605*x^19 -61*x^18 +715*x^17 +1045*x^16 -317*x^15 +213*x^14 +535*x^13 -255*x^12 -151*x^11 -273*x^10 -323*x^9 -37*x^8 +9*x^7 +55*x^6 +47*x^5 +x^4 +3*x^2 +2*x -1).

A259778 Number of permutations p of [n] with no fixed points and displacement of elements restricted by five: 1 <= |p(i)-i| <= 5.

Original entry on oeis.org

1, 0, 1, 2, 9, 44, 265, 1280, 5289, 20366, 78092, 307978, 1268773, 5312280, 22254973, 92569648, 381758301, 1565720382, 6420604761, 26380036552, 108607137785, 447677119208, 1845681472072, 7605764624216, 31326172589888, 128986886647264, 531083492316608

Offset: 0

Alois P. Heinz, Jul 05 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Vaclav Kotesovec, Recurrence (of order 142) and g.f.

Column k=5 of A259776.

Cf. A260094.

A259779 Number of permutations p of [n] with no fixed points and displacement of elements restricted by six: 1 <= |p(i)-i| <= 6.

Original entry on oeis.org

1, 0, 1, 2, 9, 44, 265, 1854, 10860, 55314, 259285, 1178912, 5382017, 25157980, 121727936, 598440744, 2954197380, 14540741660, 71135825805, 345881286126, 1675123912129, 8108391695252, 39291412775944, 190687692089500, 926601640342609, 4505656310652572

Offset: 0

Alois P. Heinz, Jul 05 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Vaclav Kotesovec, Recurrence (of order 494) and g.f.

Column k=6 of A259776.

Cf. A260111.

A259780 Number of permutations p of [n] with no fixed points and displacement of elements restricted by seven: 1 <= |p(i)-i| <= 7.

Original entry on oeis.org

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 101976, 619009, 3449752, 18376224, 96559908, 511111965, 2761247612, 15348014345, 86603917480, 491567055577, 2789697424330, 15773859067112, 88743605142976, 496953313619236, 2774429422110882, 15478834487896593

Offset: 0

Alois P. Heinz, Jul 05 2015

nonn

Conjectured recurrence order is 1780. - Vaclav Kotesovec, Jul 07 2015

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

Column k=7 of A259776.

Cf. A260091.

A259781 Number of permutations p of [n] with no fixed points and displacement of elements restricted by eight: 1 <= |p(i)-i| <= 8.

Original entry on oeis.org

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1053136, 7429428, 48212485, 296810944, 1780911209, 10628061638, 63975026748, 392088233154, 2461796588937, 15675639817952, 100493852548697, 645295580260184, 4136342103328781, 26418529357842470, 168032289856555025

Offset: 0

Alois P. Heinz, Jul 05 2015

nonn

Conjectured recurrence order is 6563. - Vaclav Kotesovec, Jul 07 2015

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

Column k=8 of A259776.

Cf. A260115.

A259782 Number of permutations p of [n] with no fixed points and displacement of elements restricted by nine: 1 <= |p(i)-i| <= 9.

Original entry on oeis.org

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 11881152, 95568369, 709693034, 4983272692, 33840285766, 226398597533, 1513188564484, 10205785143785, 69950515246416, 489604464034696, 3472020025514928, 24798829697691764, 177618356951602784

Offset: 0

Alois P. Heinz, Jul 05 2015

nonn

Conjectured recurrence order is 24566. - Vaclav Kotesovec, Jul 07 2015

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

Column k=9 of A259776.

Cf. A257953.

A259783 Number of permutations p of [n] with no fixed points and displacement of elements restricted by ten: 1 <= |p(i)-i| <= 10.

Original entry on oeis.org

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 145510740, 1314803006, 11013531389, 87155940048, 663875231097, 4947896842392, 36563337902968, 270617834212996, 2021217246729905, 15317729587621252, 118254506519672137, 924131987256868248

Offset: 0

Alois P. Heinz, Jul 05 2015

nonn

Conjecture: Column k > 0 of A259776 has a linear recurrence (with constant coefficients) of order = A005317(k) = (2^k + C(2*k,k))/2. For k=10 is conjectured recurrence order 92890. - Vaclav Kotesovec, Jul 07 2015

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

Column k=10 of A259776.

Cf. A260216.

cp's OEIS Frontend

A259784 Number T(n,k) of permutations p of [n] with no fixed points where the maximal displacement of an element equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A033305 Number of permutations (p1,...,pn) such that 1 <= |pk - k| <= 2 for all k.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

SageMath

Formula

Extensions

A079997 Number of permutations satisfying -k<=p(i)-i<=r and p(i)-i not in I, i=1..n, with k=3, r=3, I={0}.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A259777 Number of permutations p of [n] with no fixed points and displacement of elements restricted by four: 1 <= |p(i)-i| <= 4.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A259778 Number of permutations p of [n] with no fixed points and displacement of elements restricted by five: 1 <= |p(i)-i| <= 5.

Views

Author

Keywords

Links

Crossrefs

A259779 Number of permutations p of [n] with no fixed points and displacement of elements restricted by six: 1 <= |p(i)-i| <= 6.

Views

Author

Keywords

Links

Crossrefs

A259780 Number of permutations p of [n] with no fixed points and displacement of elements restricted by seven: 1 <= |p(i)-i| <= 7.

Views

Author

Keywords

Comments

Links

Crossrefs

A259781 Number of permutations p of [n] with no fixed points and displacement of elements restricted by eight: 1 <= |p(i)-i| <= 8.

Views

Author

Keywords

Comments

Links

Crossrefs

A259782 Number of permutations p of [n] with no fixed points and displacement of elements restricted by nine: 1 <= |p(i)-i| <= 9.

Views

Author

Keywords

Comments

Links

Crossrefs

A259783 Number of permutations p of [n] with no fixed points and displacement of elements restricted by ten: 1 <= |p(i)-i| <= 10.

Views