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

%I #27 Mar 25 2020 10:54:26

%S 1,1,2,4,7,12,21,37,64,111,194,339,591,1030,1796,3132,5461,9522,16604,

%T 28953,50485,88030,153498,267655,466710,813802,1419027,2474358,

%U 4314538,7523260,13118310,22874400,39886095,69549390,121273283,211464244

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

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

%H R. H. Hardin, <a href="/A189600/b189600.txt">Table of n, a(n) for n = 1..200</a>

%H Steven Finch, <a href="https://arxiv.org/abs/2003.09458">Cantor-solus and Cantor-multus distributions</a>, arXiv:2003.09458 [math.CO], 2020.

%H Robert Israel, <a href="/A189600/a189600_1.pdf">Proof of empirical recurrence</a>

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

%F 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

%F Empirical recurrence verified (see link). - _Robert Israel_, Jan 27 2019

%e Some solutions for n=13:

%e 1 1 1 4 1 5 1 6 1 1 1 5 3 3 5 1

%e 8 2 2 1 2 1 2 1 2 2 4 1 1 1 1 4

%e 2 3 3 2 3 2 3 2 10 3 2 2 2 2 2 2

%e 3 4 4 3 7 3 4 3 3 4 3 3 4 8 3 3

%e 4 5 7 9 4 4 7 4 4 12 5 4 5 4 4 5

%e 5 8 5 5 5 6 5 5 5 5 6 6 11 5 9 10

%e 6 6 6 6 6 9 6 7 6 6 7 12 6 6 6 6

%e 7 7 12 7 8 7 8 8 7 7 8 7 7 7 7 7

%e 13 13 8 8 9 8 13 9 8 8 9 8 8 13 8 8

%e 9 9 9 10 12 10 9 10 9 9 10 9 9 9 10 9

%e 10 10 10 11 10 13 10 11 11 10 13 10 10 10 13 11

%e 11 11 11 12 11 11 11 12 12 11 11 11 12 11 11 12

%e 12 12 13 13 13 12 12 13 13 13 12 13 13 12 12 13

%p f:= proc(n) option remember; local k;

%p if n < 0 then return 0 fi;

%p f(n-1) + add(f(n-k),k=3..8)

%p end proc:

%p f(0):= 1:

%p map(f, [$1..60]); # _Robert Israel_, Jan 27 2019

%K nonn

%O 1,3

%A _R. H. Hardin_, Apr 24 2011