

A028246


Triangular array a(n,k) = (1/k)*Sum_{i=0..k} (1)^(ki)*binomial(k,i)*i^n; n >= 1, 1 <= k <= n, read by rows.


56



1, 1, 1, 1, 3, 2, 1, 7, 12, 6, 1, 15, 50, 60, 24, 1, 31, 180, 390, 360, 120, 1, 63, 602, 2100, 3360, 2520, 720, 1, 127, 1932, 10206, 25200, 31920, 20160, 5040, 1, 255, 6050, 46620, 166824, 317520, 332640, 181440, 40320, 1, 511, 18660, 204630, 1020600, 2739240, 4233600, 3780000, 1814400, 362880
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

Let M = n X n matrix with (i,j)th entry a(n+1j, n+1i), e.g., if n = 3, M = [1 1 1; 3 1 0; 2 0 0]. Given a sequence s = [s(0)..s(n1)], let b = [b(0)..b(n1)] be its inverse binomial transform and let c = [c(0)..c(n1)] = M^(1)*transpose(b). Then s(k) = Sum_{i=0..n1} b(i)*binomial(k,i) = Sum_{i=0..n1} c(i)*k^i, k=0..n1.  Gary W. Adamson, Nov 11 2001
From Gary W. Adamson, Aug 09 2008: (Start)
Julius Worpitzky's 1883 algorithm generates Bernoulli numbers.
By way of example [Wikipedia]:
B0 = 1;
B1 = 1/1  1/2;
B2 = 1/1  3/2 + 2/3;
B3 = 1/1  7/2 + 12/3  6/4;
B4 = 1/1  15/2 + 50/3  60/4 + 24/5;
B5 = 1/1  31/2 + 180/3  390/4 + 360/5  120/6;
B6 = 1/1  63/2 + 602/3  2100/4 + 3360/5  2520/6 + 720/7;
...
Note that in this algorithm, odd n's for the Bernoulli numbers sum to 0, not 1, and the sum for B1 = 1/2 = (1/1  1/2). B3 = 0 = (1  7/2 + 13/3  6/4) = 0. The summation for B4 = 1/30. (End)
Pursuant to Worpitzky's algorithm and given M = A028246 as an infinite lower triangular matrix, M * [1/1, 1/2, 1/3, ...] (i.e., the Harmonic series with alternate signs) = the Bernoulli numbers starting [1/1, 1/2, 1/6, ...].  Gary W. Adamson, Mar 22 2012
From Tom Copeland, Oct 23 2008: (Start)
G(x,t) = 1/ {1 + [1exp(x t)]/t} = 1 + 1 x + (2 + t) x^2/2! + (6 + 6t + t^2) x^3/3! + ... gives row polynomials for A090582, the fpolynomials for the permutohedra (see A019538).
G(x,t1) = 1 + 1 x + (1 + t) x^2 / 2! + (1 + 4t + t^2) x^3 / 3! + ... gives row polynomials for A008292, the hpolynomials for permutohedra.
G[(t+1)x,1/(t+1)] = 1 + (1+ t) x + (1 + 3t + 2 t^2) x^2 / 2! + ... gives row polynomials for the present triangle. (End)
The Worpitzky triangle seems to be an apt name for this triangle.  Johannes W. Meijer, Jun 18 2009
If Pascal's triangle is written as a lower triangular matrix and multiplied by A028246 written as an upper triangular matrix, the product is a matrix where the (i,j)th term is (i+1)^j. For example,
1,0,0,0 1,1,1, 1 1,1, 1, 1
1,1,0,0 * 0,1,3, 7 = 1,2, 4, 8
1,2,1,0 0,0,2,12 1,3, 9,27
1,3,3,1 0,0,0, 6 1,4,16,64
So, numbering all three matrices' rows and columns starting at 0, the (i,j) term of the product is (i+1)^j.  Jack A. Cohen (ProfCohen(AT)comcast.net), Aug 03 2010
The Fi1 and Fi2 triangle sums are both given by sequence A000670. For the definition of these triangle sums see A180662. The mirror image of the Worpitzky triangle is A130850.  Johannes W. Meijer, Apr 20 2011
Let S_n(m) = 1^m + 2^m + ... + n^m. Then, for n >= 0, we have the following representation of S_n(m) as a linear combination of the binomial coefficients:
S_n(m) = Sum_{i=1..n+1} a(i+n*(n+1)/2)*C(m,i). E.g., S_2(m) = a(4)*C(m,1) + a(5)*C(m,2) + a(6)*C(m,3) = C(m,1) + 3*C(m,2) + 2*C(m,3).  Vladimir Shevelev, Dec 21 2011
Given the set X = [1..n] and 1 <= k <= n, then a(n,k) is the number of sets T of size k of subset S of X such that S is either empty or else contains 1 and another element of X and such that any two elemements of T are either comparable or disjoint.  Michael Somos, Apr 20 2013
Working with the row and column indexing starting at 1, a(n,k) gives the number of kdimensional faces in the first barycentric subdivision of the standard ndimensional simplex (apply Brenti and Welker, Lemma 2.1). For example, the barycentric subdivision of the 2simplex (a triangle) has 1 empty face, 7 vertices, 12 edges and 6 triangular faces giving row 4 of this triangle as (1,7,12,6). Cf. A053440.  Peter Bala, Jul 14 2014
See A074909 and above g.f.s for associations among this array and the Bernoulli polynomials and their umbral compositional inverses.  Tom Copeland, Nov 14 2014
An e.g.f. G(x,t) = exp[P(.,t)x] = 1/t  1/[t+(1t)(1e^(xt^2))] = (1t) * x + (2t + 3t^2  t^3) * x^2/2! + (6t^2  12t^3 + 7t^4  t^5) * x^3/3! + ... for the shifted, reverse, signed polynomials with the first element nulled, is generated by the infinitesimal generator g(u,t)d/du = [(1u*t)(1(1+u)t)]d/du, i.e., exp[x * g(u,t)d/du] u eval. at u=0 generates the polynomials. See A019538 and the G. Rzadkowski link below for connections to the Bernoulli and Eulerian numbers, a Ricatti differential equation, and a soliton solution to the KdV equation. The inverse in x of this e.g.f. is Ginv(x,t) = (1/t^2)*log{[1t(1+x)]/[(1t)(1tx)]} = [1/(1t)]x + [(2tt^2)/(1t)^2]x^2/2 + [(3t^23t^3+t^4)/(1t)^3)]x^3/3 + [(4t^36t^4+4t^5t^6)/(1t)^4]x^4/4 + ... . The numerators are signed, shifted A135278 (reversed A074909), and the rational functions are the columns of A074909. Also, dG(x,t)/dx = g(G(x,t),t) (cf. A145271). (Analytic G(x,t) added, and Ginv corrected and expanded on Dec 28 2015.)  Tom Copeland, Nov 21 2014
The operator R = x + (1 + t) + t e^{D} / [1 + t(1e^(D))] = x + (1+t) + t  (t+t^2) D + (t+3t^2+2t^3) D^2/2!  ... contains an e.g.f. of the reverse row polynomials of the present triangle, i.e., A123125 * A007318 (with row and column offset 1 and 1). Umbrally, R^n 1 = q_n(x;t) = (q.(0;t)+x)^n, with q_m(0;t) = (t+1)^(m+1)  t^(m+1), the row polynomials of A074909, and D = d/dx. In other words, R generates the Appell polynomials associated with the base sequence A074909. For example, R 1 = q_1(x;t) = (q.(0;t)+x) = q_1(0;t) + q__0(0;t)x = (1+2t) + x, and R^2 1 = q_2(x;t) = (q.(0;t)+x)^2 = q_2(0:t) + 2q_1(0;t)x + q_0(0;t)x^2 = 1+3t+3t^2 + 2(1+2t)x + x^2. Evaluating the polynomials at x=0 regenerates the base sequence. With a simple sign change in R, R generates the Appell polynomials associated with A248727.  Tom Copeland, Jan 23 2015
For a natural refinement of this array, see A263634.  Tom Copeland, Nov 06 2015
From Wolfdieter Lang, Mar 13 2017: (Start)
The e.g.f. E(n, x) for {S(n, m)}_{m>=0} with S(n, m) = Sum_{k=1..m} k^n, n >= 0, (with undefined sum put to 0) is exp(x)*R(n+1, x) with the exponential row polynomials R(n, x) = Sum_{k=1..n} a(n, k)*x^k/k!. E.g., e.g.f. for n = 2, A000330: exp(x)*(1*x/1!+3*x^2/2!+2*x^3/3!).
The o.g.f. G(n, x) for {S(n, m)}_{m >=0} is then found by Laplace transform to be G(n, 1/p) = p*Sum_{k=1..n} a(n+1, k)/(p1)^(2+k).
Hence G(n, x) = x/(1  x)^(n+2)*Sum_{k=1..n} A008292(n,k)*x^(k1).
E.g., n=2: G(2, 1/p) = p*(1/(p1)^2 + 3/(p1)^3 + 2/(p1)^4) = p^2*(1+p)/(p1)^4; hence G(2, x) = x*(1+x)/(1x)^4.
This works also backwards: from the o.g.f. to the e.g.f. of {S(n, m)}_{m>=0}. (End)
a(n,k) is the number of ktuples of pairwise disjoint and nonempty subsets of a set of size n.  Dorian Guyot, May 21 2019
From Rajesh Kumar Mohapatra, Mar 16 2020: (Start)
a(n1,k) is the number of chains of length k in a partially ordered set formed from subsets of an nelement set ordered by inclusion such that the first term of the chains is either the empty set or an nelement set.
Also, a(n1,k) is the number of distinct klevel rooted fuzzy subsets of an nset ordered by set inclusion. (End)
The relations on p. 34 of Hasan (also p. 17 of Franco and Hasan) agree with the relation between A019538 and this entry given in the formula section.  Tom Copeland, May 14 2020


LINKS

Seiichi Manyama, Table of n, a(n) for n = 1..10000
V. S. Abramovich, Power sums of natural numbers, Kvant, no. 5 (1973), 2225. (in Russian)
P. Bala, Deformations of the Hadamard product of power series
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
H. Belbachir, M. Rahmani, B. Sury, Sums Involving Moments of Reciprocals of Binomial Coefficients, J. Int. Seq. 14 (2011) #11.6.6.
Hacene Belbachir and Mourad Rahmani, Alternating Sums of the Reciprocals of Binomial Coefficients, Journal of Integer Sequences, Vol. 15 (2012), #12.2.8.
F. Brenti and V. Welker, fvectors of barycentric subdivisions, arXiv:math/0606356v1 [math.CO], Math. Z., 259(4), 849865, 2008.
Patibandla Chanakya, Putla Harsha, Generalized Nested Summation of Powers of Natural Numbers, arXiv:1808.08699 [math.NT], 2018. See Table 1.
T. Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms
Colin Defant, Troupes, Cumulants, and StackSorting, arXiv:2004.11367 [math.CO], 2020.
E. Delucchi, A. Pixton and L. Sabalka. Face vectors of subdivided simplicial complexes arXiv:1002.3201v3 [math.CO], Discrete Mathematics, Volume 312, Issue 2, January 2012, Pages 248257.
G. H. E Duchamp, N. HoangNghia, A. Tanasa, A word Hopf algebra based on the selection/quotient principle, arXiv:1207.6522 [math.CO], 20122013; Séminaire Lotharingien de Combinatoire 68 (2013), Article B68c.
M. Dukes, C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.
Nick Early, Honeycomb tessellations and canonical bases for permutohedral blades, arXiv:1810.03246 [math.CO], 2018.
S. Franco and A. Hasan, Graded Quivers, Generalized Dimer Models and Toric Geometry , arXiv preprint arXiv:1904.07954 [hepth], 2019
A. Hasan, Physics and Mathematics of Graded Quivers, dissertation, Graduate Center, City University of New York, 2019.
H. Hasse, Ein Summierungsverfahren für die Riemannsche ZetaReihe, Math. Z. 32, 458464 (1930).
ShiMei Ma, A family of twovariable derivative polynomials for tangent and secant, El J. Combinat. 20(1) (2013), P11.
A. Riskin and D. Beckwith, Problem 10231, Amer. Math. Monthly, 102 (1995), 175176.
G. Rzadkowski, Bernoulli numbers and solitons revisited, Journal of Nonlinear Mathematical Physics, Volume 17, Issue 1, 2010.
John K. Sikora, On Calculating the Coefficients of a Polynomial Generated Sequence Using the Worpitzky Number Triangles, arXiv:1806.00887 [math.NT], 2018.
G. J. Simmons, A combinatorial problem associated with a family of combination locks, Math. Mag., 37 (1964), 127132 (but there are errors). The triangle is on page 129.
N. J. A. Sloane, Transforms
Sam Vandervelde, The Worpitzky Numbers Revisited, Amer. Math. Monthly, 125:3 (2018), 198206.
Wikipedia, Bernoulli number.
Wikipedia, Barycentric subdivision
David C. Wood, The computation of polylogarithms (2014).


FORMULA

E.g.f.: log(1y*(exp(x)1)).  Vladeta Jovovic, Sep 28 2003
a(n, k) = S2(n, k)*(k1)! where S2(n, k) is a Stirling number of the second kind (cf. A008277). Also a(n,k) = T(n,k)/k, where T(n, k) = A019538.
Essentially same triangle as triangle [1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, ...] DELTA [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] where DELTA is Deléham's operator defined in A084938, but the notation is different.
Sum of terms in nth row = A000629(n)  Gary W. Adamson, May 30 2005
The row generating polynomials P(n, t) are given by P(1, t)=t, P(n+1, t) = t(t+1)(d/dt)P(n, t) for n >= 1 (see the Riskin and Beckwith reference).  Emeric Deutsch, Aug 09 2005
From Gottfried Helms, Jul 12 2006: (Start)
Deltamatrix as can be read from H. Hasse's proof of a connection between the zetafunction and Bernoulli numbers (see link below).
Let P = lower triangular matrix with entries P[row,col] = binomial(row,col).
Let J = unit matrix with alternating signs J[r,r]=(1)^r.
Let N(m) = column matrix with N(m)(r) = (r+1)^m, N(1)> natural numbers.
Let V = Vandermonde matrix with V[r,c] = (r+1)^c.
V is then also N(0)N(1)N(2)N(3)... (indices r,c always beginning at 0).
Then Delta = P*J * V and B' = N(1)' * Delta, where B is the column matrix of Bernoulli numbers and ' means transpose, or for the single kth Bernoulli number B_k with the appropriate column of Delta,
B_k = N(1)' * Delta[ *,k ] = N(1)' * P*J * N(k).
Using a single column instead of V and assuming infinite dimension, H. Hasse showed that in x = N(1) * P*J * N(s), where s can be any complex number and s*zeta(1s) = x.
His theorem reads: s*zeta(1s) = Sum_{n>=0..inf} (n+1)^1*delta(n,s), where delta(n,s) = Sum_{j=0..n} (1)^j * binomial(n,j) * (j+1)^s.
(End)
The kth row (k>=1) contains a(i, k) for i=1 to k, where a(i, k) satisfies Sum_{i=1..n} C(i, 1)^k = 2 * C(n+1, 2) * Sum_{i=1..k} a(i, k) * C(n1, i1)/(i+1). E.g., Row 3 contains 1, 3, 2 so Sum_{i=1..n} C(i, 1)^3 = 2 * C(n+1, 2) * [ a(1, 3)/2 + a(2, 3)*C(n1, 1)/3 + a(3, 3)*C(n1, 2)/4 ] = [ (n+1)*n ] * [ 1/2 + (3/3)*C(n1, 1) + (2/4)*C(n1, 2) ] = ( n^2 + n ) * ( n 1 + [ C(n1, 2) + 1 ]/2 ) = C(n+1, 2)^2. See A000537 for more details ( 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ... ).  André F. Labossière, Sep 22 2003
a(n,k) = k*a(n1,k) + (k1)*a(n1,k1) with a(n,1) = 1 and a(n,n) = (n1)!.  Johannes W. Meijer, Jun 18 2009
Rephrasing the Meijer recurrence above: Let M be the (n+1)X(n+1) bidiagonal matrix with M(r,r) = M(r,r+1) = r, r >= 1, in the two diagonals and the rest zeros. The row a(n+1,.) of the triangle is row 1 of M^n.  Gary W. Adamson, Jun 24 2011
From Tom Copeland, Oct 11 2011: (Start)
With e.g.f.. A(x,t) = G[(t+1)x,1/(t+1)]1 (from 2008 comment) = 1 + 1/[1(1+t)(1e^(x))] = (1+t)x + (1+3t+2t^2)x^2/2! + ..., the comp. inverse in x is
B(x,t)= log(t/(1+t)+1/((1+t)(1+x))) = (1/(1+t))x  ((1+2t)/(1+t)^2)x^2/2 + ((1+3t+3t^2)/(1+t)^3)x^3/3 + .... The numerators are the row polynomials of A074909, and the rational functions are (omitting the initial constants) signed columns of the reindexed Pascal triangle A007318.
Let h(x,t)= 1/(dB/dx) = (1+x)(1+t(1+x)), then the row polynomial P(n,t) = (1/n!)(h(x,t)*d/dx)^n x, evaluated at x=0, A=exp(x*h(y,t)*d/dy) y, eval. at y=0, and dA/dx = h(A(x,t),t), with P(1,t)=1+t. (Series added Dec 29 2015.)(End)
Let <n,k> denote the Eulerian numbers A173018(n,k), then T(n,k) = Sum_{j=0..n} <n,j>*binomial(nj,nk).  Peter Luschny, Jul 12 2013
Matrix product A007318 * A131689. The nth row polynomial R(n,x) = Sum_{k >= 1} k^(n1)*(x/(1 + x))^k, valid for x in the open interval (1/2, inf). Cf A038719. R(n,1/2) = (1)^(n1)*(2^n  1)*Bernoulli(n)/n.  Peter Bala, Jul 14 2014
a(n,k) = A141618(n,k) / C(n,k1).  Tom Copeland, Oct 25 2014
For the row polynomials, A028246(n,x) = A019538(n1,x) * (1+x).  Tom Copeland, Dec 28 2015
A248727 = A007318*(reversed A028246) = A007318*A130850 = A007318*A123125*A007318 = A046802*A007318.  Tom Copeland, Nov 14 2016
nth row polynomial R(n,x) = (1+x) o (1+x) o ... o (1+x) (n factors), where o denotes the black diamond multiplication operator of Dukes and White. See example E11 in the Bala link.  Peter Bala, Jan 12 2018
From Dorian Guyot, May 21 2019: (Start)
Sum_{i=0..k} binomial(k,i) * a(n,i) = (k+1)^n.
Sum_{k=0..n} a(n,k) = 2*A000670(n).
(End)
With all offsets 0, let A_n(x;y) = (y + E.(x))^n, an Appell sequence in y where E.(x)^k = E_k(x) are the Eulerian polynomials of A123125. Then the row polynomials of this entry, A028246, are given by x^n * A_n(1 + 1/x;0). Other specializations of A_n(x;y) give A046802, A090582, A119879, A130850, and A248727.  Tom Copeland, Jan 24 2020


EXAMPLE

The triangle a(n, k) starts:
n\k 1 2 3 4 5 6 7 8 9
1: 1
2: 1 1
3: 1 3 2
4: 1 7 12 6
5: 1 15 50 60 24
6: 1 31 180 390 360 120
7: 1 63 602 2100 3360 2520 720
8: 1 127 1932 10206 25200 31920 20160 5040
9: 1 255 6050 46620 166824 317520 332640 181440 40320
... [Reformatted by Wolfdieter Lang, Mar 26 2015]

Row 5 of triangle is {1,15,50,60,24}, which is {1,15,25,10,1} times {0!,1!,2!,3!,4!}.
From Vladimir Shevelev, Dec 22 2011: (Start)
Also, for power sums, we have
S_0(n) = C(n,1);
S_1(n) = C(n,1) + C(n,2);
S_2(n) = C(n,1) + 3*C(n,2) + 2*C(n,3);
S_3(n) = C(n,1) + 7*C(n,2) + 12*C(n,3) + 6*C(n,4);
S_4(n) = C(n,1) + 15*C(n,2) + 50*C(n,3) + 60*C(n,4) + 24*C(n,5); etc.
(End)
For X = [1,2,3], the sets T are {{}}, {{},{1,2}}, {{},{1,3}}, {{},{1,2,3}}, {{},{1,2},{1,2,3}}, {{},{1,3},{1,2,3}} and so a(3,1)=1, a(3,2)=3, a(3,3)=2.  Michael Somos, Apr 20 2013


MAPLE

a := (n, k) > add((1)^(ki)*binomial(k, i)*i^n, i=0..k)/k;
seq(print(seq(a(n, k), k=1..n)), n=1..10);
T := (n, k) > add(eulerian1(n, j)*binomial(nj, nk), j=0..n):
seq(print(seq(T(n, k), k=0..n)), n=0..9); # Peter Luschny, Jul 12 2013


MATHEMATICA

a[n_, k_] = Sum[(1)^(ki) Binomial[k, i]*i^n, {i, 0, k}]/k; Flatten[Table[a[n, k], {n, 10}, {k, n}]] (* JeanFrançois Alcover, May 02 2011 *)


PROG

(PARI) {T(n, k) = if( k<0  k>n, 0, n! * polcoeff( (x / log(1 + x + x^2 * O(x^n) ))^(n+1), nk))}; /* Michael Somos, Oct 02 2002 */
(PARI) {T(n, k) = stirling(n, k, 2)*(k1)!}; \\ G. C. Greubel, May 31 2019
(Sage)
def A163626_row(n) :
x = polygen(ZZ, 'x')
A = []
for m in range(0, n, 1) :
A.append((x)^m)
for j in range(m, 0, 1):
A[j  1] = j * (A[j  1]  A[j])
return list(A[0])
for i in (1..7) : print(A163626_row(i)) # Peter Luschny, Jan 25 2012
(Sage) [[stirling_number2(n, k)*factorial(k1) for k in (1..n)] for n in (1..10)] # G. C. Greubel, May 30 2019
(MAGMA) [[StirlingSecond(n, k)*Factorial(k1): k in [1..n]]: n in [1..10]]; // G. C. Greubel, May 30 2019
(GAP) Flat(List([1..10], n> List([1..n], k> Stirling2(n, k)* Factorial(k1) ))) # G. C. Greubel, May 30 2019


CROSSREFS

Dropping the column of 1's gives A053440. See also A008277.
Without the k in the denominator (in the definition), we get A019538. See also the Stirling number triangle A008277.
Cf. A087127, A087107, A087108, A087109, A087110, A087111, A084938 A075263.
Row sums give A000629(n1) for n >= 1.
Cf. A027642, A002445.  Gary W. Adamson, Aug 09 2008
Appears in A161739 (RSEG2 triangle), A161742 and A161743.  Johannes W. Meijer, Jun 18 2009
Binomial transform is A038719. Cf. A053440, A131689.
Cf. A007318, A008292, A046802, A074909, A090582, A123125, A130850, A135278, A141618, A145271, A163626, A248727, A263634.
Cf. A119879.
From Rajesh Kumar Mohapatra, Mar 29 2020: (Start)
A000007(n1) (column k=1), A000225(n1) (column k=2), A028243(n1) (column k=3), A028244(n1) (column k=4), A028245(n1) (column k=5), for n > 0.
Diagonal gives A000142(n1), for n >=1.
Nexttolast diagonal gives A001710,
Third, fourth, fifth, sixth, seventh external diagonal respectively give A005460, A005461, A005462, A005463, A005464. (End)
Sequence in context: A306226 A186370 A163626 * A082038 A143774 A196842
Adjacent sequences: A028243 A028244 A028245 * A028247 A028248 A028249


KEYWORD

nonn,easy,nice,tabl


AUTHOR

N. J. A. Sloane, Doug McKenzie (mckfam4(AT)aol.com)


EXTENSIONS

Definition corrected by Li Guo, Dec 16 2006
Typo in link corrected by Johannes W. Meijer, Oct 17 2009
Error in title corrected by Johannes W. Meijer, Sep 24 2010
Edited by M. F. Hasler, Oct 29 2014


STATUS

approved



