A376743 -id:A376743 - cp's OEIS frontend

A079999 Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-2,-1,3} for all i=1,...,n.

1, 0, 0, 0, 1, 1, 1, 1, 1, 4, 4, 5, 7, 10, 16, 22, 29, 40, 60, 84, 118, 165, 230, 330, 466, 653, 919, 1297, 1831, 2585, 3640, 5124, 7233, 10201, 14380, 20272, 28572, 40289, 56816, 80096, 112912, 159196, 224449, 316456, 446164, 629004, 886821, 1250329, 1762801

Offset: 0

Vladimir Baltic, Feb 10 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.

Michael A. Allen and Kenneth Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, Linear and Multilinear Algebra, 72:13 (2024), 2091-2103.
Michael A. Allen and Kenneth Edwards, Identities relating permanents of some classes of (0,1) Toeplitz matrices to generalized Fibonacci numbers, Fibonacci Quarterly, 63:2 (2025), 163-177.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics, 4:1 (2010), 119-135.
Kenneth Edwards and Michael A. Allen, Strongly restricted permutations and tiling with fences, Discrete Applied Mathematics, 187 (2015), 82-90.
Index entries for linear recurrences with constant coefficients, signature (0,0,1,1,2,1,0,-1,0,-1).

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

LinearRecurrence[{0,0,1,1,2,1,0,-1,0,-1},{1,0,0,0,1,1,1,1,1,4},50] (* Harvey P. Dale, Dec 12 2024 *)

Recurrence: a(n) = a(n-3) + a(n-4) + 2*a(n-5) + a(n-6) - a(n-8) - a(n-10) for n>=10.

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

A375981 Number of subsets of {1,2,...,n} such that no two elements differ by 1, 4, or 5.

Original entry on oeis.org

1, 2, 3, 5, 8, 11, 14, 19, 25, 34, 49, 70, 99, 141, 196, 270, 375, 520, 723, 1014, 1420, 1985, 2777, 3874, 5396, 7526, 10496, 14642, 20449, 28555, 39860, 55647, 77660, 108356, 151214, 211028, 294507, 411071, 573763, 800796, 1117679, 1559895, 2177002

Offset: 0

Michael A. Allen, Sep 04 2024

a(n) is the number of compositions of n+5 into parts 1, 6, 8, 9, 12, 15, 18, 21, ...

			For n = 6, the 14 subsets are {}, {1}, {2}, {3}, {1,3}, {4}, {1,4}, {2,4}, {5}, {2,5}, {3,5}, {6}, {3,6}, {4,6}.
The a(4) = 8 compositions of 9 into parts 1, 6, 8, 9, ... are 1+1+1+1+1+1+1+1+1, 1+1+1+6, 1+1+6+1, 1+6+1+1, 6+1+1+1, 1+8, 8+1, 9.

Michael A. Allen, Combinations without specified separations, Communications in Combinatorics and Optimization (in press).
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1,0,1,0,1,0,0,-1).
Index entries for subsets of {1,..,n} with disallowed differences

See comments for other sequences related to restricted combinations.

Cf. A376743.

CoefficientList[Series[(1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 - x^8 - x^9 - x^10)/(1 - x - x^3 + x^4 - x^6 - x^8 + x^11),{x,0,42}],x]
LinearRecurrence[{1, 0, 1, -1, 0, 1, 0, 1, 0, 0, -1}, {1, 2, 3, 5, 8, 11, 14, 19, 25, 34, 49}, 42]

a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-6) + a(n-8) - a(n-11) for n >= 11.

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

A377715 Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-2,3,4} for all i=1,...,n.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 3, 1, 0, 0, 1, 6, 6, 1, 1, 1, 10, 20, 10, 5, 6, 15, 50, 50, 25, 30, 36, 105, 175, 125, 115, 141, 231, 490, 525, 435, 541, 673, 1246, 1820, 1695, 1901, 2361, 3361, 5501, 6301, 6601, 8295, 10440, 15820, 21410, 23286

Offset: 0

Michael A. Allen, Nov 04 2024

			a(5) = 1: 45123.
a(6) = 1: 561234.

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

Michael A. Allen and Kenneth Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, Lin. Multilin. Alg. 72:13 (2024) 2091-2103.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics, 4(1) (2010), 119-135.
Kenneth Edwards and Michael A. Allen, Strongly restricted permutations and tiling with fences, Discrete Applied Mathematics, 187 (2015), 82-90.
Index entries for linear recurrences with constant coefficients, signature (0,0,1,0,2,2,0,-1,-2,-1,-1,-1,0,0,1).

See A376743 for other sequences related to strongly restricted permutations.

CoefficientList[Series[(1 - x^3 - x^5 - x^6 + x^9)/(1 - x^3 - 2*x^5 - 2*x^6 + x^8 + 2*x^9 + x^10 + x^11 + x^12 - x^15),{x,0,56}],x]
LinearRecurrence[{0, 0, 1, 0, 2, 2, 0, -1, -2, -1, -1, -1, 0, 0, 1}, {1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 3, 1, 0, 0}, 57]

a(n) = a(n-3) + 2*a(n-5) + 2*a(n-6) - a(n-8) - 2*a(n-9) - a(n-10) - a(n-11) - a(n-12) + a(n-15) for n >= 15.

G.f.: (1 - x^3 - x^5 - x^6 + x^9)/(1 - x^3 - 2*x^5 - 2*x^6 + x^8 + 2*x^9 + x^10 + x^11 + x^12 - x^15).

A378005 Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-2,4,5} for all i=1,...,n.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 3, 1, 0, 0, 0, 1, 6, 6, 1, 0, 0, 1, 10, 20, 10, 1, 1, 1, 15, 50, 50, 15, 6, 7, 21, 105, 175, 105, 36, 42, 49, 196, 490, 490, 231, 183, 217, 392, 1176, 1764, 1246, 785, 946, 1141, 2646, 5292, 5418, 3613, 3664, 4390, 6601, 14112, 19614

Offset: 0

Michael A. Allen, Nov 13 2024

			a(6) = 1: 561234.
a(7) = 1: 6712345.

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

Michael A. Allen and Kenneth Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, Lin. Multilin. Alg. 72:13 (2024) 2091-2103.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics, 4(1) (2010), 119-135.
Kenneth Edwards and Michael A. Allen, Strongly restricted permutations and tiling with fences, Discrete Applied Mathematics, 187 (2015), 82-90.
Index entries for linear recurrences with constant coefficients, signature (0,0,1,0,0,2,3,0,-2,-2,0,-1,-2,-3,1,1,1,0,0,0,1).

See A376743 for other sequences related to strongly restricted permutations.

Cf. A377715, A001263.

CoefficientList[Series[1/((1-x^7-x^6-x^13/(1-x^7-x^6/(1-x^7/(1-x^3))))), {x, 0, 65}],x]

a(n) = a(n-3) + 2*a(n-6) + 3*a(n-7) - 2*a(n-9) - 2*a(n-10) - a(n-12) - 2a(n-13) - 3*a(n-14) + a(n-15) + a(n-16) + a(n-17) + a(n-21) for n >= 21.

G.f.: (1 - x)*(1 + x + x^2 - x^6 - 3*x^7 - 3*x^8 - 2*x^9 - x^10 - x^11 - x^12 - x^13)/(1 - x^3 - 2*x^6 - 3*x^7 + 2*x^9 + 2*x^10 + x^12 + 2*x^13 + 3*x^14 - x^15 - x^16 - x^17 - x^21).

cp's OEIS Frontend

A079999 Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-2,-1,3} for all i=1,...,n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A375981 Number of subsets of {1,2,...,n} such that no two elements differ by 1, 4, or 5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A377715 Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-2,3,4} for all i=1,...,n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A378005 Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-2,4,5} for all i=1,...,n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula