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

1, 1, 1, 1, 1, 1, 1, 2, 4, 6, 9, 12, 16, 20, 25, 35, 49, 70, 100, 140, 196, 266, 361, 494, 676, 936, 1296, 1800, 2500, 3450, 4761, 6555, 9025, 12445, 17161, 23711, 32761, 45250, 62500, 86250, 119025, 164220, 226576, 312732, 431649, 595899, 822649, 1135564, 1567504, 2163456, 2985984

Offset: 0

Author

Vladimir Baltic, Apr 18 2013

Keywords

• nonn
• easy

Comments

a(n) is the number of subsets of {1,2,...,n-6} without differences equal to 2, 4 or 6.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
• Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135
• Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,-1,1,2,-1,1,0,0,-1,0,0, 1).

Crossrefs

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

Programs

Mathematica

CoefficientList[Series[(1 - x^5 - x^8)/(1 - x - x^5 + x^6 - x^7 - 2*x^8 + x^9 - x^10 + x^13 + x^16), {x, 0, 50}], x] (* G. C. Greubel, Oct 28 2017 *)
LinearRecurrence[{1,0,0,0,1,-1,1,2,-1,1,0,0,-1,0,0,-1},{1,1,1,1,1,1,1,2,4,6,9,12,16,20,25,35},60] (* Harvey P. Dale, Dec 02 2024 *)

PARI

x='x+O('x^66); Vec((1-x^5-x^8)/(1-x-x^5+x^6-x^7-2*x^8+x^9-x^10+x^13+x^16) ) \\ Joerg Arndt, Apr 19 2013

Formula

a(n) = a(n-1) + a(n-5) - a(n-6) + a(n-7) + 2*a(n-8) - a(n-9) + a(n-10) - a(n-13) + a(n-16).

G.f.: (1-x^5-x^8)/(1-x-x^5+x^6-x^7-2*x^8+x^9-x^10+x^13+x^16).

a(2*k-2) = (A003269(k))^2,

a(2*k-1) = A003269(k) * A003269(k+1)