A381349 Triangle read by rows: T(n,k) is the number of distinct tuples E each corresponding to some k-ary word W = (w_1, ..., w_n), where E is a tuple (e_1, ..., e_{n-1}) with e_i being the number of pairs of equal letters (w_j,w_k) in W such that j + i = k.

1, 1, 2, 1, 3, 4, 1, 6, 9, 10, 1, 10, 22, 26, 27, 1, 20, 54, 73, 78, 79, 1, 36, 163, 249, 269, 275, 276, 1, 72, 447, 791, 915, 942, 949, 950, 1, 135, 1350, 3136, 3776, 3899, 3934, 3942, 3943, 1, 272, 4088, 11315, 14849, 15650, 15811, 15855, 15864, 15865

Offset: 1

Author

John Tyler Rascoe, Feb 21 2025

Keywords

• nonn
• tabl

Comments

Two different words of the same length can have the same corresponding E tuple.

Examples

			Triangle begins:
    k=1   2    3    4    5    6    7
  n=1 1;
  n=2 1,  2;
  n=3 1,  3,   4;
  n=4 1,  6,   9,  10;
  n=5 1, 10,  22,  26,  27;
  n=6 1, 20,  54,  73,  78,  79;
  n=7 1, 36, 163, 249, 269, 275, 276;
  ...
Considering the pairs of equal letters in W = (1,3,3,1) there is 1 pair with no letters between them, 0 pairs with a single letter between them, and 1 pair seperated by two letters, giving E = (1,0,1).
T(4,2) = 6 counts the following values of E each listed with a corresponding word:
     E        W
  (3,2,1) (1,1,1,1)
  (2,1,0) (1,1,1,2)
  (2,0,0) (1,1,2,2)
  (1,0,1) (1,2,2,1)
  (1,1,1) (2,1,2,2)
  (0,2,0) (2,1,2,1)
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..78 (terms through row 12)
• Michael S. Branicky, Python Program

Crossrefs

Cf. A000312, (empirical column k=2) A006606, A120910, A226873.

Programs

Python

from itertools import combinations_with_replacement, permutations
def pairs(m): return tuple([sum(1 for j in range(len(m)-i) if m[j] == m[j+i]) for i in range(1,len(m))])
def A381349(n,k):
    S = set()
    for y in combinations_with_replacement(range(1,k+1),n-1):
        S.update(z for z in permutations((1,)+y))
    return len({pairs(i) for i in S})

Python

# see links for a different algorithm
from sympy.utilities.iterables import multiset_permutations
from itertools import combinations, combinations_with_replacement
def E(w):
    return tuple(sum(1 for j, k in combinations(range(len(w)), 2) if w[j] == w[k] and j+i == k) for i in range(len(w)))
def row(n): # generator of row n
    v, S = 0, set()
    for k in range(1, n+1):
        for c in combinations_with_replacement(range(1, k+1), n-k):
            if len(c) > 0 and c[0] == 2: break
            S.update(E(e) for e in multiset_permutations(tuple(range(1, k+1))+c))
        yield len(S)
print([e for n in range(1, 9) for e in row(n)]) # Michael S. Branicky, Feb 26 2025

Formula

T(n,k) = T(n,n) for k > n.

From Michael S. Branicky, Feb 25 2025: (Start)

T(n, 2) = A006606(n).

T(n, n-1) = T(n, n-2) + n-1, arising from E's of permutations of 1, ..., n-2, n-1, n-1.

T(n, n) = T(n, n-1) + 1, arising from E(1, ... , n) = (0, ..., 0). (End)

Extensions

a(37) and beyond from Michael S. Branicky, Feb 25 2025