A072850 Number of permutations p of [n] satisfying i-2 <= p(i) <= i+4 for all i in [n].

1, 1, 2, 6, 18, 54, 146, 391, 1081, 3004, 8320, 22984, 63424, 175176, 484113, 1337721, 3695886, 10210702, 28209954, 77940078, 215337554, 594943087, 1643728129, 4541349672, 12547013504, 34665373744, 95774808224, 264610227072, 731075061761, 2019841706529, 5580494794730

Offset

0,3

Links

Paolo Xausa, Table of n, a(n) for n = 0..1000 (terms 1..400 from R. H. Hardin).

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,2,4,6,10,12,-4,-6,-6,0,-2,-2,0,1,1).

Formula

Recurrence: a(n) = a(n-1) + 2*a(n-2) + 4*a(n-3) + 6*a(n-4) + 10*a(n-5) + 12*a(n-6) - 4*a(n-7) - 6*a(n-8) - 6*a(n-9) - 2*a(n-11) - 2*a(n-12) + a(n-14) + a(n-15).

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

Mathematica

LinearRecurrence[{1, 2, 4, 6, 10, 12, -4, -6, -6, 0, -2, -2, 0, 1, 1}, {1, 1, 2, 6, 18, 54, 146, 391, 1081, 3004, 8320, 22984, 63424, 175176, 484113}, 30] (* Paolo Xausa, Jan 23 2026 *)

Crossrefs

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

Sequence in context: A358417 A372899 A214799 * A254941 A182899 A160175

Adjacent sequences: A072847 A072848 A072849 * A072851 A072852 A072853

Keyword

nonn,easy

Author

Vladimir Baltic, Jul 25 2002

Extensions

a(0)=1 prepended by Alois P. Heinz, Jan 23 2026

Status

approved