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