login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A028246 Triangular array a(n,k) = (1/k)*Sum_{i=0..k} (-1)^(k-i)*C(k,i)*i^n; n >= 1, 1 <= k <= n, read by rows. 50
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 (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+1-j, n+1-i), e.g., if n = 3, M = [1 1 1; 3 1 0; 2 0 0]. Given a sequence s = [s(0)..s(n-1)], let b = [b(0)..b(n-1)] be its inverse binomial transform and let c = [c(0)..c(n-1)] = M^(-1)*transpose(b). Then s(k) = Sum_{i=0..n-1} b(i)*binomial(k,i) = Sum_{i=0..n-1} c(i)*k^i, k=0..n-1. - Gary W. Adamson, Nov 11 2001

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. - Gary W. Adamson, Aug 09 2008

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 + [1-exp(x t)]/t} = 1 + 1 x + (2 + t) x^2/2! + (6 + 6t + t^2) x^3/3! + ... gives row polynomials for A090582, the f-polynomials for the permutohedra (see A019538).

G(x,t-1) = 1 + 1 x + (1 + t) x^2 / 2! + (1 + 4t + t^2) x^3 / 3! + ... gives row polynomials for A008292, the h-polynomials 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 k-dimensional faces in the first barycentric subdivision of the standard n-dimensional simplex (apply Brenti and Welker, Lemma 2.1). For example, the barycentric subdivision of the 2-simplex (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+(1-t)(1-e^(-xt^2))] = (1-t) * 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 = [(1-u*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{[1-t(1+x)]/[(1-t)(1-tx)]} = [1/(1-t)]x + [(2t-t^2)/(1-t)^2]x^2/2 + [(3t^2-3t^3+t^4)/(1-t)^3)]x^3/3  + [(4t^3-6t^4+4t^5-t^6)/(1-t)^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(1-e^(-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)/(p-1)^(2+k).

  Hence G(n, x) = x/(1 - x)^(n+2)*Sum_{k=1..n} A008292(n,k)*x^(k-1).

  E.g., n=2: G(2, 1/p) = p*(1/(p-1)^2 + 3/(p-1)^3 + 2/(p-1)^4) = p^2*(1+p)/(p-1)^4; hence G(2, x) = x*(1+x)/(1-x)^4.

This works also backwards: from the o.g.f. to the e.g.f. of {S(n, m)}_{m>=0}. (End)

LINKS

Seiichi Manyama, Table of n, a(n) for n = 1..10000

V. S. Abramovich, Power sums of natural numbers, Kvant, no. 5 (1973), 22-25. (in Russian)

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, f-vectors of barycentric subdivisions, arXiv:math/0606356v1 [math.CO], Math. Z., 259(4), 849-865, 2008.

T. Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms

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 248-257.

G. H. E Duchamp, N. Hoang-Nghia, A. Tanasa, A word Hopf algebra based on the selection/quotient principle, Séminaire Lotharingien de Combinatoire 68 (2013), Article B68c.

H. Hasse, Ein Summierungsverfahren fuer die Riemannsche Zeta-Reihe.

Shi-Mei Ma, A family of two-variable 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), 175-176.

G. Rzadkowski, Bernoulli numbers and solitons revisited, Journal of Nonlinear Mathematical Physics, Volume 17, Issue 1, 2010.

G. J. Simmons, A combinatorial problem associated with a family of combination locks, Math. Mag., 37 (1964), 127-132 (but there are errors). The triangle is on page 129.

N. J. A. Sloane, Transforms

Wikipedia, Bernoulli number.

Wikipedia, Barycentric subdivision

FORMULA

E.g.f.: -log(1-y*(exp(x)-1)). - Vladeta Jovovic, Sep 28 2003

a(n, k) = S2(n, k)*(k-1)! 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 n-th 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)diff(P(n, t), t) for n>=1 (see the Riskin and Beckwith reference). - Emeric Deutsch, Aug 09 2005

From Gottfried Helms, Jul 12 2006: (Start)

Delta-matrix as can be read from H. Hasse's proof of a connection between the zeta-function 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 k-th 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(1-s) = x.

His theorem reads: s*zeta(1-s) = 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 k-th 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(n-1, i-1)/(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(n-1, 1)/3 + a(3, 3)*C(n-1, 2)/4 ] = [ (n+1)*n ] * [ 1/2 + (3/3)*C(n-1, 1) + (2/4)*C(n-1, 2) ] = ( n^2 + n ) * ( n -1 + [ C(n-1, 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(n-1,k) + (k-1)*a(n-1,k-1) with a(n,1) = 1 and a(n,n) = (n-1)!. - 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)(1-e^(-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 re-indexed 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(n-j,n-k). - Peter Luschny, Jul 12 2013

Matrix product A007318 * A131689. The n-th row polynomial R(n,x) = Sum_{k = 1..inf} k^(n-1)*(x/(1 + x))^k, valid for x in the open interval (-1/2,inf). Cf A038719. R(n,-1/2) = (-1)^(n-1)*(2^n - 1)*Bernoulli(n)/n. - Peter Bala, Jul 14 2014

a(n,k) = A141618(n,k) / C(n,k-1). - Tom Copeland, Oct 25 2014

For the row polynomials, A028246(n,x) = A019538(n-1,x) * (1+x). - Tom Copeland, Dec 28 2015

A248727 = A007318*(reversed A028246) = A007318*A130850 = A007318*A123125*A007318 = A046802*A007318. - Tom Copeland, Nov 14 2016

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 4032

... 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)^(k-i)*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(n-j, n-k), 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)^(k-i) Binomial[k, i]*i^n, {i, 0, k}]/k; Flatten[Table[a[n, k], {n, 10}, {k, n}]] (* Jean-Franç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), n-k))}; /* Michael Somos, Oct 02 2002 */

(Sage)

def A163626_row(n) :

    var('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 coefficientlist(A[0], x)

for i in (1..7) : print A163626_row(i)  # Peter Luschny, Jan 25 2012

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(n-1) for n >= 1.

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.

Sequence in context: A134436 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 20 17:39 EDT 2017. Contains 293648 sequences.