[seqfan] permutations p in S_n such that m <= |p(i)-p(i+1)| <=M for i from 1 to n-1.
W. Edwin Clark
wclark at mail.usf.edu
Sat Mar 27 20:18:04 CET 2010
The following sequences were suggested by a question from an anonymous
engineer concerning frequency hopping algorithms. Actually he was just
interested in finding a permutation p of n channel frequencies such that
for fixed m < M, m <= |p(i)-p(i+1)| <=M for i from 1 to n-1. That is, you
want to switch to a nearby frequency but one not too far away. Anyhow
it makes a nice sequence to determine the number of such permutations
of {1,...,n} for fixed m<M
Call the sequence depending on m<M: s(m,M)
I have submitted the sequences (see below) for 0 < m < M < 6 except
for s(1,2) which is the only sequence of this type I find in the OEIS, namely
http://www.research.att.com/~njas/sequences/A003274
For n > 1 this is double A069241(n)
which is the number of Hamiltonian paths in the graph on vertices {1,...,n},
with i adjacent to j iff 1 <= |i-j|<=2; for which Knuth has provided a
recursion.
This graph theory interpretation obviously can be generalized to s(m,M).
Perhaps some member of this list can generalize Knuth's recursion
to s(m,M) or the graph analogue?
Using a clever Maple program enumerating permutations for s(m,M)
sent to me by Alois Heinz we have the following sequences---
devoting only several minutes to each sequence. Still it would be nice
to have a recursion.
s(1,3) = [1, 2, 6, 24, 72, 180, 428, 1042, 2512, 5912, 13592, 30872,
69560, 155568, 345282, 761312, 1669612, 3645236]
s(1,4) = [1, 2, 6, 24, 120, 480, 1632, 5124, 15860, 50186, 158808,
496472, 1526736, 4627392, 13908192]
s(1,5) = [1, 2, 6, 24, 120, 720, 3600, 15600, 61872, 236388, 901748,
3509106, 13716168, 53327912]
s(2,3) = [1, 0, 0, 2, 10, 12, 8, 12, 30, 72, 106, 128, 186, 316, 546,
836, 1186, 1756, 2720, 4224, 6366, 9374, 13932, 20958, 31470,
46820]
s(2,4) = [1, 0, 0, 2, 14, 60, 152, 256, 464, 1124, 3114, 8324, 20166,
44958, 97666, 217792, 501356, 1163776]
s(2,5) = [1, 0, 0, 2, 14, 90, 462, 1668, 4496, 11332, 31718, 100258,
336142, 1123212, 3614554]
s(3,4) = [1, 0, 0, 0, 0, 2, 14, 12, 0, 0, 0, 0, 30, 104, 112, 48, 40,
48, 112, 400, 964, 1276, 1202, 1280, 1714, 3004, 6120]
s(3,5) = [1, 0, 0, 0, 0, 2, 28, 144, 292, 272, 160, 272, 844, 3888,
15830, 49080, 113468, 208224, 352112]
s(4,5) = [1, 0, 0, 0, 0, 0, 0, 2, 18, 12, 0, 0, 0, 0, 0, 0, 30, 136,
112, 0, 0, 0, 0, 0, 0, 400, 1348, 1352]
--Edwin Clark
More information about the SeqFan
mailing list