A350529 Square array read by antidiagonals downwards: T(n,k) is the number of sequences of length n with terms in 1..k such that no iterated difference is zero, n, k >= 0.

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 1, 4, 6, 2, 0, 0, 1, 5, 12, 10, 2, 0, 0, 1, 6, 20, 32, 16, 2, 0, 0, 1, 7, 30, 72, 86, 26, 2, 0, 0, 1, 8, 42, 138, 256, 232, 42, 2, 0, 0, 1, 9, 56, 234, 624, 906, 622, 68, 2, 0, 0

Offset

0,8

Comments

For fixed n, T(n,k) is a quasi-polynomial of degree n in k. For example, T(4,k) = k^4 - (116/27)*k^3 + (25/3)*k^2 + b(k)*k + c(k), where b and c are periodic with period 6.

Links

Pontus von Brömssen, Antidiagonals n = 0..20, flattened

Example

  n\k|  0  1  2   3     4      5       6        7         8         9         10
  ---+--------------------------------------------------------------------------
   0 |  1  1  1   1     1      1       1        1         1         1          1
   1 |  0  1  2   3     4      5       6        7         8         9         10
   2 |  0  0  2   6    12     20      30       42        56        72         90
   3 |  0  0  2  10    32     72     138      234       368       544        770
   4 |  0  0  2  16    86    256     624     1278      2370      4030       6462
   5 |  0  0  2  26   232    906    2790     6900     15096     29536      53678
   6 |  0  0  2  42   622   3180   12366    36964     95494    215146     443464
   7 |  0  0  2  68  1662  11116   54572   197294    601986   1562274    3652850
   8 |  0  0  2 110  4426  38754  240278  1051298   3788268  11325490   30041458
   9 |  0  0  2 178 11774 134902 1056546  5595236  23814458  82024662  246853482
  10 |  0  0  2 288 31316 469306 4643300 29762654 149631992 593798912 2027577296
For n = 4 and k = 3, the following T(4,3) = 16 sequences are counted: 1212, 1213, 1312, 1313, 1323, 2121, 2131, 2132, 2312, 2313, 2323, 3121, 3131, 3132, 3231, 3232.

Prog

(Python)
def A350529_col(k, nmax):
    d = []
    c = [0]*(nmax+1)
    while 1:
        if not d or all(d[-1]):
            c[len(d)] += 1 + (bool(d) and 2*d[0][0] != k+1)
            if len(d) < nmax:
                d.append([0])
                for i in range(len(d)-1):
                    d[-1].append(d[-1][-1]-d[-2][i])
        while d and d[-1][0] == k:
            d.pop()
        if not d or len(d) == 1 and 2*d[0][0] >= k: return c
        for i in range(len(d)):
            d[-1][i] += 1

Crossrefs

Cf. A200154, A350364, A350530.

Rows: A000012 (n=0), A001477 (n=1), A002378 (n=2), A055232 (terms of row n=3 divided by 2).

Columns: A000007 (k=0), A019590 (k=1), A040000 (k=2), A054886 (k=3).

Sequence in context: A217315 A217593 A353434 * A322279 A350365 A331923

Adjacent sequences: A350526 A350527 A350528 * A350530 A350531 A350532

Keyword

nonn,tabl

Author

Pontus von Brömssen, Jan 03 2022

Status

approved