A365096 Array G(M,S), where M are the permutations of the first K integers and S is the size of a list of distinct items, (k = 1, 2, ..., S >= k) to be read by antidiagonals (see definition in Comments).

1, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 4, 4, 3, 2, 1, 4, 4, 4, 2, 2, 1, 3, 3, 4, 2, 2, 3, 1, 3, 3, 6, 4, 4, 3, 3, 1, 6, 6, 2, 6, 4, 4, 4, 2, 1, 6, 6, 2, 6, 6, 6, 4, 2, 1, 1, 10, 10, 6, 4, 4, 6, 6, 4, 4, 2, 1, 10, 10, 5, 4, 4, 4, 2, 6, 6, 3, 2, 1, 12

Offset

1,5

Comments

G(M,S) is defined as follows:

1. Given:

* M, a permutation of the K integers 0..k-1 called M, where K >= 1.

* S, the number of distinct, ordered integers, where S >= K.

2. Form S' as the array of integers 0..S-1 inclusive. This is the initial ordering S0'.

3. Form groups:

* Form group group[0] by concatenating every K-th item of S' starting from index 0

* Form group group[1] by concatenating every K-th item of S' starting from index 1

...

* Form group group[K-1] by concatenating every K-th item of S' starting from index K-1

4. Concatenate groups:

* Concatenate all the groups[] in the order given by M to form the first partial result P(1)

P(1) = concatenate_left_to_right(group[i] for i in M)

5. Repetition:

* Substituting P for S', repeat the above process from 3, until the order of items in P equals the initial order S0'.

6. Result:

* G(M, S) = the number of repetitions needed of steps 3 through 5.

M is tabulated as the lexicographically ordered permutations of K integers counted from zero, for K = 1, 2,...

Array begins:

M = (0): 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,...

M = (0, 1): 1,2,2,4,4,3,3,6,6,10,10,12,12,4,4,8,8,18,18,6,...

M = (1, 0): 2,2,4,4,3,3,6,6,10,10,12,12,4,4,8,8,18,18,6,6,...

M = (0, 1, 2): 1,3,4,4,6,2,2,6,5,5,11,6,6,15,16,16,52,4,4,38,...

M = (0, 2, 1): 2,2,2,4,6,6,4,4,4,21,3,3,30,4,4,90,18,18,24,5,...

M = (1, 0, 2): 2,2,4,4,6,4,4,4,21,21,3,30,30,8,90,90,18,24,24,10,...

M = (1, 2, 0): 3,3,4,6,6,4,6,6,5,11,11,6,15,15,16,52,52,4,38,38,...

M = (2, 0, 1): 3,4,4,6,2,2,6,5,5,11,6,6,15,16,16,52,4,4,38,11,...

M = (2, 1, 0): 2,2,4,6,6,4,4,4,21,3,3,30,4,4,90,18,18,24,5,5,...

It appears that the Abulsme function A105272 is given by A105272(n,k) == G(M,S) when M is the sorting of integers 0..K-1 from highest to lowest, and S is n.

(Python):

def A105272(n, k):

return A365096(range(k)[::-1], n)

Links

Donald 'Paddy' McCarthy, Table of n, a(n) for n = 1..5050

Donald S. McCarthy "Paddy3118", The Godeh Series, Python, and OEIS

Example

Given M = (0, 1) and S = 2:
  k = 2, the number of elements of M
  S0' = S' = [0, 1]
    S' = P(1) = [0, 1]
  == S0' after repetitions = 1
Given M = (0, 1) and S = 3:
  k = 2, the number of elements of M
  S0' = S' = [0, 1, 2]
    S' = P(1) = [0, 2, 1]
    S' = P(2) = [0, 1, 2]
  == S0' after repetitions = 2
Given M = (0, 1) and S = 4:
  k = 2, the number of elements of M
  S0' = S' = [0, 1, 2, 3]
    S' = P(1) = [0, 2, 1, 3]
    S' = P(2) = [0, 1, 2, 3]
  == S0' after repetitions = 2
Given M = (0, 1) and S = 5:
  k = 2, the number of elements of M
  S0' = S' = [0, 1, 2, 3, 4]
    S' = P(1) = [0, 2, 4, 1, 3]
    S' = P(2) = [0, 4, 3, 2, 1]
    S' = P(3) = [0, 3, 1, 4, 2]
    S' = P(4) = [0, 1, 2, 3, 4]
  == S0' after repetitions = 4

Prog

(Python)
def G(m: list[int], s: int) -> int:
    k = len(m)
    assert s >= k
    assert set(range(k)) == set(m), \
           f"Sequence m of length {k} should contain a permutation of all the " \
           f"numbers 0..{k-1} inclusive."
    s_init = list(range(s))
    n, s = 0, None
    while s != s_init:
        if n == 0:
            s = s_init
        n += 1
        s = sum((s[offset::k] for offset in m),
                start=[])
    return n

Crossrefs

Cf. A000012 (row 1), A024222 (rows 2 and 3), A118960 (rows 5 and 9), A120280 (rows 15 and 33), A120363 (rows 57 and 153), A120654 (rows 273 and 873).

Cf. A105272.

Sequence in context: A055174 A096369 A332289 * A102297 A269570 A243759

Adjacent sequences: A365093 A365094 A365095 * A365097 A365098 A365099

Keyword

nonn,tabl

Author

Donald 'Paddy' McCarthy, Aug 21 2023

Status

approved