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.

1, 4, 16, 104, 484, 4848, 25104, 300336, 2335296, 27953952, 198725952, 4731323904, 33020828928, 606237831936, 8936541384192, 174694058933760, 1628654065588224, 56338295740213248, 545177455792662528, 20766878061520306176, 340162958990367645696

Offset

1,2

Links

Table of n, a(n) for n=1..21.

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)

Crossrefs

Cf. A104442, A332762, A332784, A322178, A332748, A332752, A332773.

Sequence in context: A245155 A334750 A094637 * A332773 A203716 A330537

Adjacent sequences: A332780 A332781 A332782 * A332784 A332785 A332786

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