login
A224814
Number of subsets of {1,2,...,n-9} without differences equal to 3, 6 or 9.
4
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 8, 12, 18, 27, 36, 48, 64, 80, 100, 125, 175, 245, 343, 490, 700, 1000, 1400, 1960, 2744, 3724, 5054, 6859, 9386, 12844, 17576, 24336, 33696, 46656, 64800, 90000, 125000, 172500, 238050, 328509, 452295, 622725, 857375, 1182275, 1630295, 2248091, 3106141, 4291691, 5929741, 8190250, 11312500, 15625000, 21562500
OFFSET
0,11
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=3, r=9, I={-3,0,9}.
LINKS
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, 1, 0, -1, 1, 0, -3, 4, 0, 5, -2, 0, 3, -8, 0, 1, -4, 0, 3, -4, 0, -3, 0, 0, -5, 8, 0, 7, -2, 0, -9, 2, 0, 5, 4, 0, 1, -6, 0, -3, 2, 0, 2, 1, 0, -1, -1, 0, 0, 1).
FORMULA
a(n) = a(n-1) +a(n-4) -a(n-6) +a(n-7) -3*a(n-9) +4*a(n-10) +5*a(n-12) -2*a(n-13) +3*a(n-15) -8*a(n-16) +a(n-18) -4*a(n-19) +3*a(n-21) -4*a(n-22) -3*a(n-24) -5*a(n-27) +8*a(n-28) +7*a(n-30) -2*a(n-31) -9*a(n-33) +2*a(n-34) +5*a(n-36) +4*a(n-37) +a(n-39) -6*a(n-40) -3*a(n-42) +2*a(n-43) +2*a(n-45) +a(n-46) -a(n-48) -a(n-49) +a(n-52).
G.f.: (1 -x^4 -x^5 -x^7 -x^8 +2*x^9 -x^10 -3*x^12 -x^13 -2*x^15 +3*x^16 +3*x^17 +2*x^18 -x^20 -4*x^21 +x^23 +3*x^24 +3*x^25 +x^27 -4*x^28 -x^29 -2*x^30 +x^31 +2*x^33 +x^34 -x^36 -x^37 +x^40 )/((1-x-x^4)*(1-x^9-x^12)*(1 +x^6 +4*x^9 -4*x^12 -2*x^15 +4*x^18 -3*x^21 -3*x^24 +7*x^27 -6*x^30 +3*x^33 -x^36)).
a(3*k) = (A003269(k))^3,
a(3*k+1) = (A003269(k))^2 * A003269(k+1),
a(3*k+2) = A003269(k) * (A003269(k+1))^2.
MATHEMATICA
CoefficientList[Series[(1 - x^4 - x^5 - x^7 - x^8 + 2*x^9 - x^10 - 3*x^12 - x^13 - 2*x^15 + 3*x^16 + 3*x^17 + 2*x^18 - x^20 - 4*x^21 + x^23 + 3*x^24 + 3*x^25 + x^27 - 4*x^28 - x^29 - 2*x^30 + x^31 + 2*x^33 +x^34 - x^36 - x^37 + x^40)/((1 - x - x^4)*(1 - x^9 - x^12)*(1 + x^6 + 4*x^9 - 4*x^12 - 2*x^15 + 4*x^18 - 3*x^21 - 3*x^24 + 7*x^27 - 6*x^30 + 3*x^33 - x^36)), {x, 0, 50}], x] (* G. C. Greubel, Oct 28 2017 *)
PROG
(PARI) x='x+O('x^50); Vec((1 -x^4 -x^5 -x^7 -x^8 +2*x^9 -x^10 -3*x^12 -x^13 -2*x^15 +3*x^16 +3*x^17 +2*x^18 -x^20 -4*x^21 +x^23 +3*x^24 +3*x^25 +x^27 -4*x^28 -x^29 -2*x^30 +x^31 +2*x^33 +x^34 -x^36 -x^37 +x^40 )/((1-x-x^4)*(1-x^9-x^12)*(1 +x^6 +4*x^9 -4*x^12 -2*x^15 +4*x^18 -3*x^21 -3*x^24 +7*x^27 -6*x^30 +3*x^33 -x^36))) \\ G. C. Greubel, Oct 28 2017
KEYWORD
nonn,easy
AUTHOR
Vladimir Baltic, May 18 2013
STATUS
approved