A028246 Triangular array a(n,k) = (1/k)*Sum_{i=0..k} (-1)^(k-i)*binomial(k,i)*i^n; n >= 1, 1 <= k <= n, read by rows.
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
Offset: 1
Examples
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
References
- Ki Hang Kim, Boolean Matrix Theory and Applications, Marcel Dekker, New York and Basel (1982).
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)
- Peter Bala, Deformations of the Hadamard product of power series
- Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
- Melike Baykal-Gürsoy, Marcelo Figueroa-Candia, and Zhe Duan, Completion times of jobs on two-state service processes and their asymptotic behavior, Probability in the Engineering and Information Sciences (2024), 1-29. See p. 23.
- H. Belbachir, M. Rahmani, and 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.
- Patibandla Chanakya and Putla Harsha, Generalized Nested Summation of Powers of Natural Numbers, arXiv:1808.08699 [math.NT], 2018. See Table 1.
- Tom Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms
- Colin Defant, Troupes, Cumulants, and Stack-Sorting, 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 248-257.
- G. H. E Duchamp, N. Hoang-Nghia, and A. Tanasa, A word Hopf algebra based on the selection/quotient principle, arXiv:1207.6522 [math.CO], 2012-2013; Séminaire Lotharingien de Combinatoire 68 (2013), Article B68c.
- M. Dukes and 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 [hep-th], 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 Zeta-Reihe, Math. Z. 32, 458-464 (1930).
- Guy Louchard, Werner Schachinger, and Mark Daniel Ward, The number of distinct adjacent pairs in geometrically distributed words: a probabilistic and combinatorial analysis, arXiv:2203.14773 [math.PR], 2022. See p. 5.
- Shi-Mei Ma, A family of two-variable derivative polynomials for tangent and secant, El J. Combinat. 20(1) (2013), P11.
- Richard J. Mathar, Integrals Associated with the Digamma Integral Representation, arXiv:2308.14154 [math.GM], 2023. See p. 5.
- Rajesh Kumar Mohapatra and Tzung-Pei Hong, On the Number of Finite Fuzzy Subsets with Analysis of Integer Sequences, Mathematics (2022) Vol. 10, No. 7, 1161.
- 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.
- 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), 127-132 (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), 198-206.
- Wikipedia, Bernoulli number.
- Wikipedia, Barycentric subdivision
- David C. Wood, The computation of polylogarithms (2014).
Crossrefs
Dropping the column of 1's gives A053440.
Without the k in the denominator (in the definition), we get A019538. See also the Stirling number triangle A008277.
Row sums give A000629(n-1) for n >= 1.
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(n-1) (column k=1), A000225(n-1) (column k=2), A028243(n-1) (column k=3), A028244(n-1) (column k=4), A028245(n-1) (column k=5), for n > 0.
Diagonal gives A000142(n-1), for n >=1.
Next-to-last diagonal gives A001710,
Programs
-
GAP
Flat(List([1..10], n-> List([1..n], k-> Stirling2(n,k)* Factorial(k-1) ))); # G. C. Greubel, May 30 2019
-
Magma
[[StirlingSecond(n,k)*Factorial(k-1): k in [1..n]]: n in [1..10]]; // G. C. Greubel, May 30 2019
-
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 *) -
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 */ -
PARI
{T(n,k) = stirling(n,k,2)*(k-1)!}; \\ G. C. Greubel, May 31 2019 -
Python
# Assuming offset (n, k) = (0, 0). def T(n, k): if k > n: return 0 if k == 0: return 1 return k*T(n - 1, k - 1) + (k + 1)*T(n - 1, k) for n in range(9): print([T(n, k) for k in range(n + 1)]) # Peter Luschny, Apr 26 2022 -
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(k-1) for k in (1..n)] for n in (1..10)] # G. C. Greubel, May 30 2019
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)(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)
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)
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 denote the Eulerian numbers A173018(n,k), then T(n,k) = Sum_{j=0..n} *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} 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
A248727 = A007318*(reversed A028246) = A007318*A130850 = A007318*A123125*A007318 = A046802*A007318. - Tom Copeland, Nov 14 2016
n-th 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
The row generating polynomials R(n,x) = Sum_{i=1..n} a(n,i) * x^i satisfy the recurrence equation R(n+1,x) = R(n,x) + Sum_{k=0..n-1} binomial(n-1,k) * R(k+1,x) * R(n-k,x) for n >= 1 with initial value R(1,x) = x. - Werner Schulte, Jun 17 2021
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
Comments