A378588 Triangle read by rows: T(n,k) is the number of maximal chains in the poset of all k-ary words of length <= n, ordered by B covers A iff A_i <= B_{i+k} for all i in A and some k >= 0.

1, 1, 2, 1, 5, 6, 1, 16, 22, 23, 1, 57, 94, 102, 103, 1, 226, 446, 507, 517, 518, 1, 961, 2308, 2764, 2855, 2867, 2868, 1, 4376, 12900, 16333, 17121, 17248, 17262, 17263, 1, 21041, 77092, 103666, 110487, 111739, 111908, 111924, 111925, 1, 106534, 489430, 701819, 761751, 773888, 775758, 775975, 775993, 775994, 1, 563961, 3282956, 5038344, 5578041, 5696293, 5716382, 5719046, 5719317, 5719337, 5719338

Offset: 1

Author

John Tyler Rascoe, Dec 01 2024

Keywords

• nonn
• tabl

Examples

			Triangle begins:
   k=1    2     3     4     5     6     7
 n=1 1;
 n=2 1,   2;
 n=3 1,   5,    6;
 n=4 1,  16,   22,   23;
 n=5 1,  57,   94,  102,  103;
 n=6 1, 226,  446,  507,  517,  518;
 n=7 1, 961, 2308, 2764, 2855, 2867, 2868;
 ...
T(3,3) = 6:
 () < (1) < (1,1) < (1,1,1),
 () < (1) < (1,1) < (1,2),
 () < (1) < (1,1) < (2,1),
 () < (1) < (2) < (1,2),
 () < (1) < (2) < (2,1),
 () < (1) < (2) < (3).
		

Crossrefs

Cf. A034841, A143672, A282698, A317145, column k=2 A378382, main diagonal A378608.

Programs

Python

def mchains(n,k):
    B,d1,S1 = [1,1],{(1,): 1},{(1,)}
    for i in range(n-1):
        d2,S2 = dict(),set()
        for j in S1:
            for x in [j+(1,), (1,)+j]+[j[:z]+tuple([j[z]+1])+j[z+1:] for z in range(len(j)) if j[z] < k]:
                if x not in S2: S2.add(x); d2[x] = d1[j]
                elif x != tuple([1]*(i+2)): d2[x] += d1[j]
        B.append(sum(d2.values())); d1 = d2; S1 = S2
    return B[:n+1]
def A378588_list(max_n):
    B = [mchains(max_n,i+1) for i in range(max_n)]
    return [[B[k][j+1] for k in range(j+1)] for j in range(max_n)]

Formula

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