OFFSET
1,8
COMMENTS
Treating each row of the triangle as a statistical distribution, the expectation can be derived heuristically. The probability that a block of length k is increasing is 1/k!, so by linearity of expectation, there are approximately n/k! such blocks of length k (including those contained within longer increasing blocks). Modeling the occurrences of these blocks as approximately independent, rare events, the probability that no block of length k exists is approximately e^(-n/k!).
The expected number of ascents transitions from many to none at about the k such that e^(-n/k!) = 1, so k! ~ n. Using Stirling's original approximation k! ~ sqrt(2*Pi)*((k+1/2)/e)^(k+1/2), k ~ log(n/sqrt(2*Pi)) / W_0(log(n/sqrt(2*Pi))/e) - 1/2 (where W_0 is the principal branch of the Lambert W function). Since W_0(x) = log(x) - log(log(x)) + o(1), a cruder asymptotic is k ~ log(n)/log(log(n)).
LINKS
Alois P. Heinz, Rows n = 0..141, flattened
Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013.
Peter Luschny, Maple and Python implementation of A397303.
Natalia L. Skirrow, Stirling's approximations.
FORMULA
Sum_{k=1..n} T(n,k) = (n-1)!.
T(n,1) = [n=1].
T(n,n-1) = n-2 for n>=2.
T(n,k) = (k^2 + k - 1) * n!/k! for (n+1)/2 <= k <= n-2.
Let y_k(x) = Sum_{n>=0} x^(k*n)/(k*n)! - x^(k*n+1)/(k*n+1)!.
y_k(x) = Sum_{j=0..k-1} (1-w^j)*e^(w^j*x)/k, with w = e^(2*Pi*i/k).
E.g.f. of k-th column: log(y_k(x) / y_{k+1}(x)), for k >= 2.
EXAMPLE
n\k| 1 2 3 4 5 6 7 8 9 10
---+---------------------------------------------
1 | 1
2 | 0 1
3 | 0 1 1
4 | 0 3 2 1
5 | 0 9 11 3 1
6 | 0 39 57 19 4 1
7 | 0 189 363 133 29 5 1
8 | 0 1107 2623 1030 232 41 6 1
9 | 0 7281 21439 9080 2088 369 55 7 1
10 | 0 54351 194545 88909 20755 3690 550 71 8 1
MAPLE
b:= proc(u, o, t, k) option remember; `if`(u+o=0, 1,
`if`(t<k, add(b(u+j-1, o-j, t+1, k), j=1..o), 0)+
add(b(u-j, o+j-1, 1, k), j=1..u))
end:
T:= (n, k)-> b(0, n-1, 1, k)-`if`(k>1, b(0, n-1, 1, k-1), 0):
seq(seq(T(n, k), k=1..n), n=1..11); # Alois P. Heinz, Jun 21 2026
PROG
(Python)
from math import comb
from itertools import count, chain
from functools import cache
C = [1]
class col_cache(object):
def __init__(c, k):
c.clock = count(1)
c.k = k
c.b = [0]
__iter__ = lambda c: chain(c.b, c.more())
def more(c):
for n in c.clock:
if n > len(C):
C.append([0] * n)
m = n-1
C[m][0] = C[m][m] = 1
for k in range(1, m): C[m][k] = C[m-1][k-1] + C[m-1][k]
new = (-1 if n%c.k==1 else int(not n%c.k)) + (n>1 and C[n-1][1]*c.b[-1])
for i in range(c.k, n, c.k):
new -= C[n-1][i]*c.b[-i]
if i < n-1: new += C[n-1][i+1]*c.b[~i]
c.b.append(new)
yield new
def __getitem__(c, i):
if i >= len(c.b):
for j in range(len(c.b), i+1): next(c.more())
return c.b[i]
logy = cache(lambda k: col_cache(k))
A397303 = lambda n, k: int(n==1) if k==1 else logy(k)[n] - logy(k+1)[n]
print([[A397303(n, k) for k in range(1, n+1)] for n in range(1, 8)])
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Natalia L. Skirrow, Jun 20 2026
STATUS
approved