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,10

Comments

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}.

Links

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

Formula

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.

Mathematica

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 *)

Crossrefs

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

Sequence in context: A005943 A330131 A008233 * A031923 A304076 A225549

Adjacent sequences: A224812 A224813 A224814 * A224816 A224817 A224818

Keyword

nonn,easy

Author

Vladimir Baltic, May 18 2013

Status

approved