A189600 Number of permutations of 1..n with displacements restricted to {-7,-6,-5,-4,-3,-2,0,1}.

1, 1, 2, 4, 7, 12, 21, 37, 64, 111, 194, 339, 591, 1030, 1796, 3132, 5461, 9522, 16604, 28953, 50485, 88030, 153498, 267655, 466710, 813802, 1419027, 2474358, 4314538, 7523260, 13118310, 22874400, 39886095, 69549390, 121273283, 211464244

Offset

1,3

Comments

a(n+1) is the number of multus bitstrings of length n with no runs of 8 ones. - Steven Finch, Mar 25 2020

Links

R. H. Hardin, Table of n, a(n) for n = 1..200

Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.

Robert Israel, Proof of empirical recurrence

Formula

Empirical: a(n) = a(n-1) + a(n-3) + a(n-4) + a(n-5) + a(n-6) + a(n-7) + a(n-8).

Empirical g.f.: -x*(1 + x^2 + x^3 + x^4 + x^5 + x^6 + x^7) / ( (x^2 + 1)*(x^6 + x^5 + x^2 + x - 1) ). - R. J. Mathar, Jul 25 2012

Empirical recurrence verified (see link). - Robert Israel, Jan 27 2019

Example

Some solutions for n=13:
   1  1  1  4  1  5  1  6  1  1  1  5  3  3  5  1
   8  2  2  1  2  1  2  1  2  2  4  1  1  1  1  4
   2  3  3  2  3  2  3  2 10  3  2  2  2  2  2  2
   3  4  4  3  7  3  4  3  3  4  3  3  4  8  3  3
   4  5  7  9  4  4  7  4  4 12  5  4  5  4  4  5
   5  8  5  5  5  6  5  5  5  5  6  6 11  5  9 10
   6  6  6  6  6  9  6  7  6  6  7 12  6  6  6  6
   7  7 12  7  8  7  8  8  7  7  8  7  7  7  7  7
  13 13  8  8  9  8 13  9  8  8  9  8  8 13  8  8
   9  9  9 10 12 10  9 10  9  9 10  9  9  9 10  9
  10 10 10 11 10 13 10 11 11 10 13 10 10 10 13 11
  11 11 11 12 11 11 11 12 12 11 11 11 12 11 11 12
  12 12 13 13 13 12 12 13 13 13 12 13 13 12 12 13

Maple

f:= proc(n) option remember; local k;
  if n < 0 then return 0 fi;
  f(n-1) + add(f(n-k), k=3..8)
end proc:
f(0):= 1:
map(f, [$1..60]); # Robert Israel, Jan 27 2019

Crossrefs

Sequence in context: A245531 A189593 A100671 * A005251 A014167 A103197

Adjacent sequences: A189597 A189598 A189599 * A189601 A189602 A189603

Keyword

nonn

Author

R. H. Hardin, Apr 24 2011

Status

approved