login
Array read by ascending antidiagonals: A(n, k) is the number of paths of length k in Z^n from the origin to points such that x1+x2+...+xn = k with x1,...,xn > 0.
2

%I #23 Apr 19 2024 11:31:18

%S 1,0,1,0,2,1,0,0,6,1,0,0,6,14,1,0,0,0,36,30,1,0,0,0,24,150,62,1,0,0,0,

%T 0,240,540,126,1,0,0,0,0,120,1560,1806,254,1,0,0,0,0,1800,8400,5796,

%U 510,1

%N Array read by ascending antidiagonals: A(n, k) is the number of paths of length k in Z^n from the origin to points such that x1+x2+...+xn = k with x1,...,xn > 0.

%C T(n, k) can also be seen as the number of ordered partitions of k items into n nonempty buckets.

%C T(n, n) = n!, which is readily seen because to go from the origin to a point in Z^n a distance n away, with at least one step taken in each dimension, the first step can be in any of n dimensions, the second step in any of n-1 dimensions, and so on.

%C This array is the image of Pascal's triangle A007318 under the Akiyama-Tanigawa transformation. See the Python program. - _Peter Luschny_, Apr 19 2024

%F A(n,k) = Sum_{i=1..n} (-1)^(n-i) * binomial(n,i) * i^k

%e n\k 1 2 3 4 5 6 7 8 9 10

%e --------------------------------------------------

%e 1| 1 1 1 1 1 1 1 1 1 1

%e 2| 0 2 6 14 30 62 126 254 510 1022

%e 3| 0 0 6 36 150 540 1806 5796 18150 55980

%e 4| 0 0 0 24 240 1560 8400 40824 186480 818520

%e 5| 0 0 0 0 120 1800 16800 126000 834120 5103000

%e 6| 0 0 0 0 0 720 15120 191520 1905120 16435440

%e 7| 0 0 0 0 0 0 5040 141120 2328480 29635200

%e 8| 0 0 0 0 0 0 0 40320 1451520 30240000

%e 9| 0 0 0 0 0 0 0 0 362880 16329600

%e 10| 0 0 0 0 0 0 0 0 0 3628800

%t A[n_,k_] := Sum[(-1)^(n-i) * i^k * Binomial[n,i], {i,1,n}]

%o (Python)

%o # The Akiyama-Tanigawa algorithm for the binomial generates the rows.

%o # Adds row(0) = 0^k and column(0) = 0^n.

%o def ATBinomial(n, len):

%o A = [0] * len

%o R = [0] * len

%o for k in range(len):

%o R[k] = binomial(k, n)

%o for j in range(k, 0, -1):

%o R[j - 1] = j * (R[j] - R[j - 1])

%o A[k] = R[0]

%o return A

%o for n in range(11): print([n], ATBinomial(n, 11)) # _Peter Luschny_, Apr 19 2024

%Y Cf. A000918 (n=2), A001117 (n=3), A000919 (n=4), A001118 (n=5), A000920 (n=6).

%Y Cf. A135456 (n=7), A133068 (n=8), A133360 (n=9), A133132 (n=10).

%Y Cf. A371064, A007318.

%Y See A019538 and A131689 for other versions.

%K nonn,tabl

%O 1,5

%A _Shel Kaphan_, Mar 28 2024