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
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
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
Comments