A224814 -id:A224814 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 8, 16, 24, 36, 54, 81, 108, 144, 192, 256, 384, 576, 864, 1296, 1944, 2916, 4374, 6561, 9477, 13689, 19773, 28561, 41743, 61009, 89167, 130321, 192052, 283024, 417088, 614656, 900032, 1317904, 1929788, 2825761

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=4, r=8, I={-4,0,8}.

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, 1, -2, 2, 0, 2, -6, 6, 0, 6, 1, -1, 0, -1, 13, -13, 0, -13, 15, -15, 0, -15, -6, 6, 0, 6, 3, -3, 0, -3, -2, 2, 0, 2, 8, -8, 0, -8, 3, -3, 0, -3, -1, 1, 0, 1, -1, 1, 0, 1).

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

CoefficientList[Series[(1 - x^3 + x^4 - x^5 - x^6 - 3*x^7 + 3*x^8 - 2*x^9 - x^10 - 5*x^11 - 3*x^12 - 2*x^13 + 3*x^15 - 3*x^16 - 3*x^18 + 3*x^19 - 3*x^20 + 3*x^21 + 3*x^23 + 6*x^24 - 3*x^25 - 2*x^26 - 4*x^27 - x^29 - x^30 - 2*x^31 - x^32 + x^33 + x^35 - x^36 + x^37 + x^39)/((1 - x - x^3)*(1 + x^4 + x^6)*(1 + x^4 - x^6)*(1 - x^4 - x^12)*(1 + x^4 + 6*x^8 - 3*x^12 + 2*x^20 + x^24)), {x, 0, 50}], x] (* G. C. Greubel, Apr 28 2017 *)

a(n) = a(n-1)+a(n-3)-2*a(n-4)+2*a(n-5)+2*a(n-7)-6*a(n-8)+6*a(n-9)+6*a(n-11) +a(n-12)-a(n-13)-a(n-15)+13*a(n-16)-13*a(n-17)-13*a(n-19)+15*a(n-20)-15*a(n-21)-15*a(n-23)-6*a(n-24)+6*a(n-25)+6*a(n-27)+3*a(n-28)-3*a(n-29)-3*a(n-31)-2*a(n-32)+2*a(n-33)+2*a(n-35)+8*a(n-36)-8*a(n-37)-8*a(n-39)+3*a(n-40)-3*a(n-41)-3*a(n-43)-a(n-44)+a(n-45)+a(n-47)-a(n-48)+a(n-49)+a(n-51).
G.f.: ( 1-x^3+x^4-x^5-x^6-3*x^7+3*x^8-2*x^9-x^10-5*x^11-3*x^12-2*x^13 +3*x^15-3*x^16-3*x^18+3*x^19-3*x^20+3*x^21+3*x^23+6*x^24-3*x^25-2*x^26-4*x^27-x^29-x^30-2*x^31-x^32+x^33+x^35-x^36+x^37+x^39 ) / ((1-x-x^3)*(1+x^4+x^6)*(1+x^4-x^6)*(1-x^4-x^12)*(1+x^4+6*x^8-3*x^12+2*x^20+x^24)).
a(4*k) = (A000930(k))^4,
a(4*k+1) = (A000930(k))^3 * A000930(k+1),
a(4*k+2) = (A000930(k))^2 * (A000930(k+1))^2,
a(4*k+3) = A000930(k) * (A000930(k+1))^3.

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

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 5, 5, 6, 8, 11, 15, 25, 35, 46, 61, 85, 125, 175, 245, 341, 470, 650, 925, 1300, 1810, 2521, 3520, 4915, 6880, 9640, 13476, 18801, 26251, 36721, 51346, 71776, 100335, 140210, 195886, 273813, 382821, 535105, 747850, 1045220

Offset: 0

Michael A. Allen, Oct 03 2024

Other sequences related to strongly restricted permutations pi(i) of i in {1,..,n} along with the sets of allowed p(i)-i (containing at least 3 elements): A000045 {-1,0,1}, A189593 {-1,0,2,3,4,5,6}, A189600 {-1,0,2,3,4,5,6,7}, A006498 {-2,0,2}, A080013 {-2,1,2}, A080014 {-2,0,1,2}, A033305 {-2,-1,1,2}, A002524 {-2,-1,0,1,2}, A080000 {-2,0,3}, A080001 {-2,1,3}, A080004 {-2,0,1,3}, A080002 {-2,2,3}, A080005 {-2,0,2,3}, A080008 {-2,1,2,3}, A080011 {-2,0,1,2,3}, A079999 {-2,-1,3}, A080003 {-2,-1,0,3}, A080006 {-2,-1,1,3}, A080009 {-2,-1,0,1,3}, A080007 {-2,-1,2,3}, A080010 {-2,-1,0,2,3}, A080012 {-2,-1,1,2,3}, A072827 {-2,-1,0,1,2,3}, A224809 {-2,0,4}, A189585 {-2,0,1,3,4}, A189581 {-2,-1,0,3,4}, A072850 {-2,-1,0,1,2,3,4}, A189587 {-2,0,1,3,4,5}, A189588 {-2,-1,0,3,4,5}, A189594 {-2,0,1,3,4,5,6}, A189595 {-2,-1,0,3,4,5,6}, A189601 {-2,0,1,3,4,5,6,7}, A189602 {-2,-1,0,3,4,5,6,7}, A224811 {-2,0,8}, A224812 {-2,0,10}, A224813 {-2,0,12}, A006500 {-3,0,3}, A079981 {-3,1,3}, A079983 {-3,0,1,3}, A079982 {-3,2,3}, A079984 {-3,0,2,3}, A079988 {-3,1,2,3}, A079989 {-3,0,1,2,3}, A079986 {-3,-1,1,3}, A079992 {-3,-1,0,1,3}, A079987 {-3,-1,2,3}, A079990 {-3,-1,0,2,3}, A079993 {-3,-1,1,2,3}, A079985 {-3,-2,2,3}, A079991 {-3,-2,0,2,3}, A079996 {-3,-2,0,1,2,3}, A079994 {-3,-2,1,2,3}, A079997 {-3,-2, -1,1,2,3}, A002526 {-3,-2,-1,0,1,2,3}, A189586 {-3,0,1,2,4}, A189583 {-3,-1,0,2,4}, A189582 {-3,-2,0,1,4}, A189584 {-3,-2,-1,0,4}, A189589 {-3,0,1,2,4,5}, A189590 {-3,-1,0,2,4,5}, A189591 {-3,-2,1,4,5}, A189592 {-3,-2,-1,0,4,5}, A224810 {-3,0,6}, A189596 {-3,0,1,2,4,5,6}, A189597 {-3,-1,0,2,4,5,6}, A189598 {-3,-2,0,1,4,5,6}, A189599 {-3,-2,-1,0,4,5,6}, A224814 {-3,0,9}, A031923 {-4,0,4}, A072856 {-4,-3, -2,-1,0,1,2,3,4}, A224815 {-4,0,8}, A154654 {-5,-4,-3,-2,-1,0,1,2,3,4,5}, A154655 {-6,-5,-4,-3, -2,-1,0,1,2,3,4,5,6}.

[Keyword "less", because this comment should be moved to the Index to the OEIS, it is not appropriate here. - N. J. A. Sloane, Oct 25 2024]

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

See comments for other sequences related to strongly restricted permutations.

CoefficientList[Series[(1 - x^3 - x^4 - x^6 + x^9)/(1 - x^3 - x^4 - x^5 - 2*x^6 - x^7 + 2*x^9 + 2*x^10 + x^12 - x^15),{x,0,49}],x]
LinearRecurrence[{0, 0, 1, 1, 1, 2, 1, 0, -2, -2, 0, -1, 0, 0, 1}, {1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 5, 5, 6, 8}, 50]

a(n) = a(n-3) + a(n-4) + a(n-5) + 2*a(n-6) + a(n-7) - 2*a(n-9) - 2*a(n-10) - a(n-12) + a(n-15).

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula