A343237 Triangle T obtained from the array A(n, k) = (k+1)^(n+1) - k^(n+1), n, k >= 0, by reading antidiagonals upwards.

1, 1, 1, 1, 3, 1, 1, 7, 5, 1, 1, 15, 19, 7, 1, 1, 31, 65, 37, 9, 1, 1, 63, 211, 175, 61, 11, 1, 1, 127, 665, 781, 369, 91, 13, 1, 1, 255, 2059, 3367, 2101, 671, 127, 15, 1, 1, 511, 6305, 14197, 11529, 4651, 1105, 169, 17, 1

Offset: 0

Author

Wolfdieter Lang, May 10 2021

Keywords

• nonn
• tabl
• easy

Comments

This is the row reversed version of the triangle A047969(n, m). The corresponding array A047969 is a(n, k) = A(k, n) (transposed of array A).

A(n-1, k-1) = k^n - (k-1)^n gives the number of n-digit numbers with digits from K = {1, 2, 3, ..., k} such that any digit from K, say k, appears at least once. Motivated by a comment in A005061 by Enrique Navarrete, the instance k=4 for n >= 1 (the column 3 in array A), and the d = 3 (sub)-diagonal sequence of T for m >= 0.

Examples

			The array A begins:
n\k  0  1   2    3     4     5     6      7      8      9 ...
-------------------------------------------------------------
0:   1  1   1    1     1     1     1      1      1      1 ...
1:   1  3   5    7     9    11    13     15     17     19 ...
2:   1  7  19   37    61    91   127    169    217    271 ...
3:   1 15  65  175   369   671  1105   1695   2465   3439 ...
4:   1 31 211  781  2101  4651  9031  15961  26281  40951 ...
5:   1 63 665 3367 11529 31031 70993 144495 269297 468559 ...
...
The triangle T begins:
n\m   0    1     2     3     4     5    6    7   8  9 10 ...
-------------------------------------------------------------
0:    1
1:    1    1
2:    1    3     1
3:    1    7     5     1
4:    1   15    19     7     1
5:    1   31    65    37     9     1
6:    1   63   211   175    61    11    1
7:    1  127   665   781   369    91   13    1
8:    1  255  2059  3367  2101   671  127   15   1
9:    1  511  6305 14197 11529  4651 1105  169  17  1
10:   1 1023 19171 58975 61741 31031 9031 1695 217 19  1
...
Combinatorial interpretation (cf. A005061 by _Enrique Navarrete_)
The three digits numbers with digits from K ={1, 2, 3, 4} having at least one 4 are:
j=1 (one 4): 114, 141, 411; 224, 242, 422; 334, 343, 433; 124, 214, 142, 241, 412, 421; 134, 314, 143, 341, 413, 431; 234, 243, 423. That is,  3*3 + 3!*3 = 27 = binomial(3, 1)*(4-1)^(3-1) = 3*3^2;
j=2 (twice 4):  144, 414, 441;  244, 424, 442;  344, 434, 443; 3*3 = 9 = binomial(3, 2)*(4-1)^(3-2) = 3*3;
j=3 (thrice 4) 444; 1 = binomial(3, 3)*(4-1)^(3-3).
Together: 27 + 9 + 1 = 37 = A(2, 3) = T(5, 3).
		

Crossrefs

Cf. A005061, A008292, A047969 (reversed), A045531 (central diagonal), A047970 (row sums of triangle).

Row sequences of array A (nexus numbers): A000012, A005408, A003215, A005917(k+1), A022521, A022522, A022523, A022524, A022525, A022526, A022527, A022528.

Column sequences of array A: A000012, A000225(n+1), A001047(n+1), A005061(n+1), A005060(n+1), A005062(n+1), A016169(n+1), A016177(n+1), A016185(n+1), A016189(n+1), A016195(n+1), A016197(n+1).

Programs

Maple

egf := exp(exp(x)*y + x)*(exp(x)*y - y + 1): ser := series(egf, x, 12):
cx := n -> series(n!*coeff(ser, x, n), y, 12):
Arow := n -> seq(k!*coeff(cx(n), y, k), k=0..9):
for n from 0 to 5 do Arow(n) od; # Peter Luschny, May 10 2021

Mathematica

A[n_, k_] := (k + 1)^(n + 1) - k^(n + 1); Table[A[n - k, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Amiram Eldar, May 10 2021 *)

Formula

Array A(n, k) = (k+1)^(n+1) - k^(n+1), n, k >= 0.

A(n-1, k-1) = Sum_{j=1} binomial(n, j)*(k-1)^(n-j) = Sum_{j=0} binomial(n, j)*(k-1)^(n-j) - (k-1)^n = (1+(k-1))^n - (k-1)^n = k^n - (k-1)^n (from the combinatorial comment on A(n-1, k-1) above).

O.g.f. row n of array A: RA(n, x) = P(n, x)/(1 - x)^n, with P(n, x) = Sum_{m=0..n} A008292(n+1, m+1)*x^m, (the Eulerian number triangle A008292 has offset 1) for n >= 0. (See the Oct 26 2008 comment in A047969 by Peter Bala). RA(n, x) = polylog(-(n+1), x)*(1-x)/x. (For P(n, x) see the formula by Vladeta Jovovic, Sep 02 2002.)

E.g.f. of e.g.f.s of the rows of array A: EE(x, y) = exp(x)*(1 + y*(exp(x) - 1))*exp(y*exp(x)), that is A(n, k) = [y^k/k!][x^n/n!] EE(x, y).

Triangle T(n, m) = A(n-m, m) = (m+1)^(n-m+1) - m^(n-m+1), n >= 0, m = 0, 1, ..., n.

E.g.f.: -(exp(x)-1)/(x*exp(x)*y-x). - Vladimir Kruchinin, Nov 02 2022