How many permutations of the integers 1, 2, …, n are there such that every integer (last excluded) is followed by (not necessarily immediately) by an integer which differs from it by 1?
For example if n=4 the permutation 1432 is an acceptable one, while 2431 is not.
clc,clearvars
for n=3:9
p=perms(1:n);
ct=0;
for w=1:length(p)
s=p(w,:);
good=true;
for i=2:n-1
if ~ismember(s(i)+1,s(i+1:end)) && ~ismember(s(i)-1,s(i+1:end))
good=false;
break
end
end
if good
ct=ct+1;
end
end
disp([n ct])
end
finds
n count
3 4
4 8
5 16
6 32
7 64
8 128
9 256
The count seems to be 2^(n-1)
|
|
Posted by Charlie
on 2023-10-30 12:08:50 |
computer exploration -- no proof -- spoiler
