login
A332783
The number of permutations of {(n+1) 1's, (n+1) 2's, ..., (n+1) n's} with the property that k's are equally spaced for k=1..n and the interval of k+1 is less than or equal to the interval of k for k=1..n-1.
5
1, 4, 16, 104, 484, 4848, 25104, 300336, 2335296, 27953952, 198725952, 4731323904, 33020828928, 606237831936, 8936541384192, 174694058933760, 1628654065588224, 56338295740213248, 545177455792662528, 20766878061520306176, 340162958990367645696
OFFSET
1,2
EXAMPLE
Define the interval of k as b(k).
In case of n = 1.
| | b(1)
-----+--------+-----
1 | [1, 1] | [0]
In case of n = 2.
| | b(1),b(2)
-----+--------------------+----------
1 | [2, 2, 2, 1, 1, 1] | [0, 0]
2 | [2, 1, 2, 1, 2, 1] | [1, 1]
3 | [1, 2, 1, 2, 1, 2] | [1, 1]
4 | [1, 1, 1, 2, 2, 2] | [0, 0]
In case of n = 3.
| | b(1),b(2),b(3)
-----+--------------------------------------+---------------
1 | [3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] | [0, 0, 0]
2 | [3, 3, 3, 3, 2, 1, 2, 1, 2, 1, 2, 1] | [1, 1, 0]
3 | [3, 3, 3, 3, 1, 2, 1, 2, 1, 2, 1, 2] | [1, 1, 0]
4 | [3, 3, 3, 3, 1, 1, 1, 1, 2, 2, 2, 2] | [0, 0, 0]
5 | [3, 2, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1] | [2, 2, 2]
6 | [3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2] | [2, 2, 2]
7 | [2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1] | [2, 2, 2]
8 | [1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 3, 2] | [2, 2, 2]
9 | [2, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 3] | [2, 2, 2]
10 | [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3] | [2, 2, 2]
11 | [2, 2, 2, 2, 3, 3, 3, 3, 1, 1, 1, 1] | [0, 0, 0]
12 | [1, 1, 1, 1, 3, 3, 3, 3, 2, 2, 2, 2] | [0, 0, 0]
13 | [2, 2, 2, 2, 1, 1, 1, 1, 3, 3, 3, 3] | [0, 0, 0]
14 | [2, 1, 2, 1, 2, 1, 2, 1, 3, 3, 3, 3] | [1, 1, 0]
15 | [1, 2, 1, 2, 1, 2, 1, 2, 3, 3, 3, 3] | [1, 1, 0]
16 | [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] | [0, 0, 0]
PROG
(Ruby)
def search(a, num, d, k, n)
if num == 0
@cnt += 1
else
(k * n - k + 1).times{|i|
if a[i] == 0
(i + d + 1..k * n - k + 1).each{|j|
if (k - 1) * j - (k - 2) * i < k * n
if (1..k - 1).all?{|m| a[m * j - (m - 1) * i] == 0}
(0..k - 1).each{|m| a[m * j - (m - 1) * i] = num}
search(a, num - 1, j - i - 1, k, n)
(0..k - 1).each{|m| a[m * j - (m - 1) * i] = 0}
end
end
}
end
}
end
end
def A(k, n)
a = [0] * k * n
@cnt = 0
search(a, n, 0, k, n)
@cnt
end
def A332783(n)
(1..n).map{|i| A(i + 1, i)}
end
p A332783(5)
KEYWORD
nonn
AUTHOR
Seiichi Manyama, Feb 23 2020
EXTENSIONS
a(9)-a(17) from Bert Dobbelaere, Mar 08 2020
a(18)-a(21) from Max Alekseyev, Sep 26 2023
STATUS
approved