A072856 -id:A072856 - cp's OEIS frontend

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

1, 0, 0, 1, 1, 0, 2, 2, 1, 3, 5, 3, 6, 10, 9, 12, 21, 22, 27, 43, 52, 61, 91, 117, 140, 195, 260, 318, 426, 572, 718, 939, 1258, 1608, 2083, 2769, 3584, 4630, 6110, 7961, 10297, 13509, 17655, 22888, 29916, 39125, 50840, 66313, 86696, 112853, 147069, 192134

Offset: 0

Vladimir Baltic, Feb 19 2003

Number of compositions (ordered partitions) of n into elements of the set {3,4,6}.

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.

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 (0,0,1,1,0,1).

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.

LinearRecurrence[{0,0,1,1,0,1},{1,0,0,1,1,0},60] (* Harvey P. Dale, Oct 05 2016 *)

a(n) = a(n-3)+a(n-4)+a(n-6).

G.f.: -1/(x^6+x^4+x^3-1).

A079976 Expansion of g.f. 1/(1-x-x^2-x^4-x^5).

Original entry on oeis.org

1, 1, 2, 3, 6, 11, 20, 36, 65, 118, 214, 388, 703, 1274, 2309, 4185, 7585, 13747, 24915, 45156, 81841, 148329, 268832, 487232, 883061, 1600463, 2900685, 5257212, 9528190, 17268926, 31298264, 56725087, 102808753, 186330956, 337706899

Offset: 0

Vladimir Baltic, Feb 17 2003

nonn

Number of compositions of n into elements of the set {1,2,4,5}.

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

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.

Kassie Archer and Aaron Geary, Powers of permutations that avoid chains of patterns, arXiv:2312.14351 [math.CO], 2023. See p. 15.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics 4 (2010), 119-135
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3
Index entries for linear recurrences with constant coefficients, signature (1,1,0,1,1)

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.

CoefficientList[Series[1/(1-x-x^2-x^4-x^5),{x,0,40}],x] (* or *) LinearRecurrence[ {1,1,0,1,1},{1,1,2,3,6},40] (* Harvey P. Dale, Mar 16 2023 *)

a(n) = a(n-1)+a(n-2)+a(n-4)+a(n-5).

Since this sequence arises in several different contexts, I made the definition as simple as possible. - N. J. A. Sloane, Apr 17 2011

A079981 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={-2,0,1,2}.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 2, 0, 3, 0, 8, 0, 12, 0, 27, 0, 52, 0, 95, 0, 196, 0, 369, 0, 720, 0, 1408, 0, 2709, 0, 5292, 0, 10249, 0, 19894, 0, 38675, 0, 74992, 0, 145692, 0, 282823, 0, 549000, 0, 1066095, 0, 2069496, 0, 4018065, 0, 7801024, 0, 15144960, 0, 29404281, 0

Offset: 0

Vladimir Baltic, Feb 17 2003

Also, 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={-2,-1,0,2}. a(n)=A079980(k) if n=2k, a(n)=0 otherwise.

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.

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 (0,0,0,1,0,4,0,2,0,2,0,-2,0,1,0,0,0,1).

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.

Bisection gives A079980 (even part).

LinearRecurrence[{0,0,0,1,0,4,0,2,0,2,0,-2,0,1,0,0,0,1},{1,0,0,0,1,0,2,0,3,0,8,0,12,0,27,0,52,0},80] (* Harvey P. Dale, Aug 18 2012 *)

Recurrence: a(n) = a(n-4)+4*a(n-6)+2*a(n-8)+2*a(n-10)-2*a(n-12)+a(n-14)+a(n-18).

G.f.: -(x^12-2*x^6+1)/(x^18+x^14-2*x^12+2*x^10+2*x^8+4*x^6+x^4-1).

A079989 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={1,2}.

Original entry on oeis.org

1, 1, 1, 1, 5, 13, 27, 51, 103, 221, 498, 1064, 2240, 4728, 10076, 21559, 46075, 98085, 208759, 444727, 948151, 2021335, 4307861, 9179111, 19560273, 41686260, 88842852, 189337896, 403497908, 859893060, 1832537757, 3905386173, 8322891733, 17737112293, 37799944529

Offset: 0

Vladimir Baltic, Feb 17 2003

Also, 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={-2,-1}.

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.

Stefano Spezia, Table of n, a(n) for n = 0..3000
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,1,2,1,3,4,-7,-7,-6,6,-2,-1,1,4,1,-3,0,1,-1,-1).

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.

a(n) = a(n-1) +a(n-2) +2*a(n-3) +a(n-4) +3*a(n-5) +4*a(n-6) -7*a(n-7) -7*a(n-8) -6*a(n-9) +6*a(n-10) -2*a(n-11) -a(n-12) +a(n-13) +4*a(n-14) +a(n-15) -3*a(n-16) +a(n-18) -a(n-19) -a(n-20).

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

A224812 Number of subsets of {1,2,...,n-10} without differences equal to 2, 4, 6, 8 or 10.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 63, 81, 108, 144, 192, 256, 336, 441, 567, 729, 918, 1156, 1462, 1849, 2365, 3025, 3905, 5041, 6532, 8464, 10948, 14161, 18207, 23409, 29988, 38416, 49196, 63001, 80822, 103684, 133308, 171396, 220662, 284089, 365638, 470596, 605052, 777924, 999306, 1283689, 1648515

Offset: 0

Vladimir Baltic, May 18 2013

a(n) is the number of permutations (p(1), p(2), ..., p(n)) satisfying -k <= p(i)-i <= r and p(i)-i in the set I, i=1..n, with k=2, r=10, I={-2,0,10}.

G. C. Greubel, 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 (April, 2010), 119-13
Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 0, 0, 1, -1, 1, -1, 1, 3, -2, 2, -1, 1, 0, 0, -2, 1, -2, 0, 0, -3, 1, -2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1).

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014, A217694, A224808-A224815.

CoefficientList[Series[-(x + 1)*(x^23 - x^22 + x^21 - x^20 + x^19 - x^13 + x^12 - 3*x^11 + 3*x^10 - 3*x^9 + 2*x^8 - 2*x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1)/((x^6 + x - 1)*(x^30 + x^24 - 2*x^20 - 2*x^18 - x^14 - 2*x^12 + x^10 + x^8 + x^6 + 1)), {x, 0, 50}], x] (* G. C. Greubel, Oct 28 2017 *)

x='x+O('x^50); Vec(-(x + 1)*(x^23 - x^22 + x^21 - x^20 + x^19 - x^13 + x^12 - 3*x^11 + 3*x^10 - 3*x^9 + 2*x^8 - 2*x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1)/((x^6 + x - 1)*(x^30 + x^24 - 2*x^20 - 2*x^18 - x^14 - 2*x^12 + x^10 + x^8 + x^6 + 1))) \\ G. C. Greubel, Oct 28 2017

a(n) = a(n-1) +a(n-7) -a(n-8) +a(n-9) -a(n-10) +a(n-11) +3*a(n-12) -2*a(n-13) +2*a(n-14) -a(n-15) +a(n-16) -2*a(n-19) +a(n-20) -2*a(n-21) -3*a(n-24) +a(n-25) -2*a(n-26) +a(n-31) +a(n-36).
G.f.: -(x+1) *(x^23 -x^22 +x^21 -x^20 +x^19 -x^13 +x^12 -3*x^11 +3*x^10 -3*x^9 +2*x^8 -2*x^7 +x^6 -x^5 +x^4 -x^3 +x^2 -x +1)/ ((x^6 +x -1) *(x^30 +x^24 -2*x^20 -2*x^18 -x^14 -2*x^12 +x^10 +x^8 +x^6+1) ).
a(2*k) = (A005708(k))^2, a(2*k+1) = A005708(k) * A005708(k+1).

A224813 Number of subsets of {1,2,...,n-12} without differences equal to 2, 4, 6, 8, 10 or 12.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 80, 100, 130, 169, 221, 289, 374, 484, 616, 784, 980, 1225, 1505, 1849, 2279, 2809, 3498, 4356, 5478, 6889, 8715, 11025, 13965, 17689, 22344, 28224, 35448, 44521, 55704, 69696, 87120, 108900, 136290, 170569, 213934, 268324, 337218, 423801, 533169, 670761, 843570

Offset: 0

Vladimir Baltic, May 18 2013

a(n) is the number of permutations (p(1), p(2), ..., p(n)) satisfying -k <= p(i)-i <= r and p(i)-i in the set I, i=1..n, with k=2, r=12, I={-2,0,12}.

G. C. Greubel, 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 (April, 2010), 119-13
Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 0, 0, 1, -1, 1, -1, 1, -1, 1, 3, -2, 2, -1, 1, 0, 0, -3, 2, -4, 2, -3, 0, 0, -3, 1, -2, 0, 0, 0, 0, 3, -1, 3, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1).

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014, A217694, A224808-A224815.

CoefficientList[Series[-(-1 + x^7 + x^9 + x^11 + 2*x^14 + x^16 - 2*x^21 - 2*x^23 - x^28 + x^35)/((x^7 + x - 1)*(x^42 - x^36 - 2*x^30 - 3*x^28 + 2*x^24 + 2*x^22 + x^18 + 2*x^16 + 3*x^14 - x^12 - x^10 - x^8 - 1)), {x, 0, 1000}], x] (* G. C. Greubel, Oct 28 2017 *)

x='x+O('x^50); Vec(-(-1 + x^7 + x^9 + x^11 + 2*x^14 + x^16 - 2*x^21 - 2*x^23 - x^28 + x^35)/((x^7 + x - 1)*(x^42 - x^36 - 2*x^30 - 3*x^28 + 2*x^24 + 2*x^22 + x^18 + 2*x^16 + 3*x^14 - x^12 - x^10 - x^8 - 1))) \\ G. C. Greubel, Oct 28 2017

a(n) = a(n-1) +a(n-7) -a(n-8) +a(n-9) -a(n-10) +a(n-11) -a(n-12) +a(n-13) +3*a(n-14) -2*a(n-15) +2*a(n-16) -a(n-17) +a(n-18) -3*a(n-21) +2*a(n-22) -4*a(n-23) +2*a(n-24) -3*a(n-25) -3*a(n-28) +a(n-29) -2*a(n-30) +3*a(n-35) -a(n-36) +3*a(n-37) +a(n-42) -a(n-49).
G.f.: -(-1 +x^7 +x^9 +x^11 +2*x^14 +x^16 -2*x^21 -2*x^23 -x^28 +x^35)/( (x^7+x-1) *(x^42 -x^36 -2*x^30 -3*x^28 +2*x^24 +2*x^22 +x^18 +2*x^16 +3*x^14 -x^12 -x^10 -x^8 -1) ).
a(2*k) = (A005709(k))^2, a(2*k+1) = A005709(k) * A005709(k+1).

A323800 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 4.

Original entry on oeis.org

0, 42, 274, 1227, 4833, 18827, 75693, 304900, 1212960, 4753020, 18410363, 70943107, 272701262, 1046410914, 4007815161, 15319362279, 58456445860, 222775782355, 848216866767, 3227396592600, 12273205919568, 46650941505906, 177252609519698, 673266690295879

Offset: 4

Alois P. Heinz, Jan 28 2019

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

Column k=4 of A130152.

Cf. A002526, A072856.

a(n) = A072856(n) - A002526(n).

A323801 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 5.

Original entry on oeis.org

0, 216, 1818, 10402, 50879, 234061, 1076807, 5090497, 24239396, 114890044, 539033760, 2502282836, 11522663348, 52848995167, 241925339959, 1106164932006, 5052307570906, 23047344846397, 104994467312301, 477733956914534, 2171607914492408, 9864023776496558

Offset: 5

Alois P. Heinz, Jan 28 2019

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

Column k=5 of A130152.

Cf. A072856, A154654.

a(n) = A154654(n) - A072856(n).

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

Original entry on oeis.org

1, 1, 2, 4, 7, 14, 27, 51, 98, 187, 357, 683, 1305, 2494, 4767, 9110, 17411, 33276, 63596, 121544, 232293, 443954, 848478, 1621597, 3099169, 5923081, 11320094, 21634776, 41348026, 79023662, 151028714, 288643577, 551650823, 1054305916

Offset: 0

Vladimir Baltic, Feb 19 2003

Number of compositions (ordered partitions) of n into elements of the set {1,2,3,5,6}.

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.

D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
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,1,1,0,1,1).

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.

LinearRecurrence[{1,1,1,0,1,1},{1,1,2,4,7,14},40] (* Harvey P. Dale, Jun 05 2013 *)

a(n) = a(n-1)+a(n-2)+a(n-3)+a(n-5)+a(n-6).

G.f.: -1/(x^6+x^5+x^3+x^2+x-1).

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

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 3, 2, 5, 5, 9, 10, 16, 20, 30, 39, 56, 75, 106, 144, 201, 275, 382, 525, 727, 1001, 1384, 1908, 2636, 3636, 5021, 6928, 9565, 13200, 18222, 25149, 34715, 47914, 66137, 91285, 126001, 173914, 240052, 331336, 457338, 631251, 871304, 1202639

Offset: 0

Vladimir Baltic, Feb 17 2003

Number of compositions (ordered partitions) of n into elements of the set {2,4,5}.

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.

Harvey P. Dale, 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 (0,1,0,1,1).

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.

a=b=c=d=0;Table[e=a-d+1;a=b;b=c;c=d;d=e,{n,25}] (* Vladimir Joseph Stephan Orlovsky, Feb 26 2011*)
LinearRecurrence[{0,1,0,1,1},{1,0,1,0,2},50] (* Harvey P. Dale, Apr 12 2014 *)

Recurrence: a(n) = a(n-2)+a(n-4)+a(n-5).

G.f.: -1/(x^5+x^4+x^2-1)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A079976 Expansion of g.f. 1/(1-x-x^2-x^4-x^5).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A079981 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={-2,0,1,2}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A079989 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={1,2}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A224812 Number of subsets of {1,2,...,n-10} without differences equal to 2, 4, 6, 8 or 10.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A224813 Number of subsets of {1,2,...,n-12} without differences equal to 2, 4, 6, 8, 10 or 12.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A323800 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 4.

Views

Author

Keywords

Links

Crossrefs

Formula

A323801 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 5.

Views

Author

Keywords

Links

Crossrefs

Formula