login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A130534 Triangle T(n,k), 0<=k<=n, read by rows, giving coefficients of the polynomial (x+1)(x+2)...(x+n), expanded in increasing powers of x. T(n,k) is also the unsigned Stirling number |s(n+1,k+1)|, denoting the number of permutations on n+1 elements that contain exactly k+1 cycles. 60
1, 1, 1, 2, 3, 1, 6, 11, 6, 1, 24, 50, 35, 10, 1, 120, 274, 225, 85, 15, 1, 720, 1764, 1624, 735, 175, 21, 1, 5040, 13068, 13132, 6769, 1960, 322, 28, 1, 40320, 109584, 118124, 67284, 22449, 4536, 546, 36, 1, 362880, 1026576, 1172700, 723680, 269325, 63273 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
This triangle is an unsigned version of the triangle of Stirling numbers of the first kind, A008275, which is the main entry for these numbers. - N. J. A. Sloane, Jan 25 2011
Or, triangle T(n,k), 0<=k<=n, read by rows given by [1,1,2,2,3,3,4,4,5,5,6,6,...] DELTA [1,0,1,0,1,0,1,0,1,0,1,0,...] where DELTA is the operator defined in A084938.
Reversal of A094638.
Equals A132393*A007318, as infinite lower triangular matrices. - Philippe Deléham, Nov 13 2007
From Johannes W. Meijer, Oct 07 2009: (Start)
The higher order exponential integrals E(x,m,n) are defined in A163931. The asymptotic expansion of the exponential integrals E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + n*(n+1)/x^2 - n*(n+1)*(n+2)/x^3 + ... ), see Abramowitz and Stegun. This formula follows from the general formula for the asymptotic expansion, see A163932. We rewrite E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + (n^2+n)/x^2 - (2*n+3*n^2+n^3)/x^3 + (6*n+11*n^2+6*n^3+n^4)/x^3 - ...) and observe that the T(n,m) are the polynomials coefficients in the denominators. Looking at the a(n,m) formula of A028421, A163932 and A163934, and shifting the offset given above to 1, we can write T(n-1,m-1) = a(n,m) = (-1)^(n+m)*stirling1(n,m), see the Maple program.
The asymptotic expansion leads for values of n from one to eleven to known sequences, see the cross-references. With these sequences one can form the triangles A008279 (right hand columns) and A094587 (left hand columns).
See A163936 for information about the o.g.f.s. of the right hand columns of this triangle.
(End)
The number of elements greater than i to the left of i in a permutation gives the i-th element of the inversion vector. (Skiena-Pemmaraju 2003 p. 69.) T(n,k) is the number of n-permutations that have exactly k 0's in their inversion vector. See evidence in Mathematica code below. - Geoffrey Critzer, May 07 2010
T(n,k) counts the rooted trees with k+1 trunks in forests of "naturally grown" rooted trees with n+2 nodes. This corresponds to sums of coefficients of iterated derivatives representing vectors, Lie derivatives, or infinitesimal generators for flow fields and formal group laws. Cf. links in A139605. - Tom Copeland, Mar 23 2014
A refinement is A036039. - Tom Copeland, Mar 30 2014
From Tom Copeland, Apr 05 2014: (Start)
With initial n=1 and row polynomials of T as p(n,x)=x(x+1)...(x+n-1), the powers of x correspond to the number of trunks of the rooted trees of the "naturally-grown" forest referred to above. With each trunk allowed m colors, p(n,m) gives the number of such non-plane colored trees for the forest with each tree having n+1 vertices.
p(2,m) = m + m^2 = A002378(m) = 2*A000217(m) = 2*first subdiag of |A238363|.
p(3,m) = 2m + 3m^2 + m^3 = A007531(m+2) = 3*A007290(m+2) = 3*(second subdiag A238363).
p(4,m) = 6m + 11m^2 + 6m^3 + m^4 = A052762(m+3) = 4*A033487(m) = 4*third subdiag.
From the Joni et al. link, p(n,m) also represents the disposition of n distinguishable flags on m distinguishable flagpoles.
The chromatic polynomial for the complete graph K_n is the falling factorial, which encodes the colorings of the n vertices of K_n and gives a shifted version of p(n,m).
E.g.f. for the row polynomials: (1-y)^(-x).
(End)
A relation to derivatives of the determinant |V(n)| of the n X n Vandermonde matrix V(n) in the indeterminates c(1) thru c(n):
|V(n)| = Product_{1<=j<k<=n} (c(j)-c(k)). Let W(n,x) = |V(n)|*(c(1)c(2)...c(n))^x, then p(n,x) = W^(-1)[c(1)d/dc(1)...c(n)d/dc(n)]W. This is a variant of the Cayley identity. See Chervov link, p. 47. - Tom Copeland, Apr 10 2014
From Peter Bala, Jul 21 2014: (Start)
Let M denote the lower unit triangular array A094587 and for k = 0,1,2,... define M(k) to be the lower unit triangular block array
/I_k 0\
\ 0 M/
having the k x k identity matrix I_k as the upper left block; in particular, M(0) = M. Then the present triangle equals the infinite matrix product M(0)*M(1)*M(2)*... (which is clearly well-defined). See the Example section. (End)
For the relation of this rising factorial to the moments of Viennot's Laguerre stories, see the Hetyei link p. 4. - Tom Copeland, Oct 01 2015
Can also be seen as the Bell transform of n! without column 0 (and shifted enumeration). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016
REFERENCES
Sriram Pemmaraju and Steven Skiena, Computational Discrete Mathematics, Cambridge University Press, 2003, pp. 69-71. [Geoffrey Critzer, May 07 2010]
LINKS
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972, Chapter 5, pp. 227-251. [From Johannes W. Meijer, Oct 07 2009]
A. Chervov, Decomplexification of the Capelli identities and holomorphic factorization, arxiv 1203.5759 [math.QA], Mar 2012. [Tom Copeland, Apr 10 2014]
Martin Griffiths, Generating Functions for Extended Stirling Numbers of the First Kind, Journal of Integer Sequences, 17 (2014), #14.6.4.
G. Hetyei, Meixner polynomials of the second kind and quantum algebras representing su(1,1), arXiv preprint arXiv:0909.4352 [math.QA], 2009.
S. Joni, G. Rota, and B. Sagan, From Sets to Functions: Three Elementary Examples, Discrete Mathematics, vol. 37, no. 2-3, pp. 193-202, 1981. [Tom Copeland, Apr 05 2014]
Matthieu Josuat-Verges, A q-analog of Schläfli and Gould identities on Stirling numbers, Preprint, arXiv:1610.02965 [math.CO], 2016.
Marin Knežević, Vedran Krčadinac, and Lucija Relić, Matrix products of binomial coefficients and unsigned Stirling numbers, arXiv:2012.15307 [math.CO], 2020.
Lucas Sá and Antonio M. García-García, The Wishart-Sachdev-Ye-Kitaev model: Q-Laguerre spectral density and quantum chaos, arXiv:2104.07647 [hep-th], 2021.
FORMULA
T(0,0)=1, T(n,k)=0 if k>n or if n<0, T(n,k)=T(n-1,k-1)+n*T(n-1,k). T(n,0)=n!=A000142(n). T(2*n,n)=A129505(n+1). Sum_{k, 0<=k<=n}T(n,k)=(n+1)!=A000142(n+1). Sum_{k, 0<=k<=n}T(n,k)^2=A047796(n+1). T(n,k)=|Stirling1(n+1,k+1)|, see A008275. (x+1)(x+2)...(x+n)=Sum_{k, 0<=k<=n}T(n,k)*x^k. [Corrected by Arie Bos, Jul 11 2008]
Sum_{k, 0<=k<=n}T(n,k)*x^k = A000007(n), A000142(n), A000142(n+1), A001710(n+2), A001715(n+3), A001720(n+4), A001725(n+5), A001730(n+6), A049388(n), A049389(n), A049398(n), A051431(n) for x = -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 respectively. - Philippe Deléham, Nov 13 2007
For 1<=k<=n, let A={a1,a2,...,ak} denote a size-k subset of {1,2,...,n}. Then T(n,n-k)=sum(product(ai)) where the sum is over all subsets A and the product is over i=1,..,k. For example, T(4,1)=50 since (1)(2)(3)+(1)(2)(4)+(1)(3)(4)+(2)(3)(4)=50. - Dennis P. Walsh, Jan 25 2011
The preceding formula means T(n,k) = sigma_{n-k}(1,2,3,..,n) with the (n-k)-th elementary symmetric function sigma with the indeterminates chosen as 1,2,...,n. See the Oct 24 2011 comment in A094638 with sigma called there a. - Wolfdieter Lang, Feb 06 2013.
n-th row of the triangle = top row of M^n, where M is the production matrix:
1, 1
1, 2, 1
1, 3, 3, 1
1, 4, 6, 4, 1
...
- Gary W. Adamson, Jul 08 2011
Exponential Riordan array [1/(1 - x), log(1/(1 - x))]. Recurrence: T(n+1,k+1) = Sum_{i=0..n-k} (n + 1)!/(n + 1 - i)!*T(n-i,k). - Peter Bala, Jul 21 2014
EXAMPLE
Triangle T(n,k) begins:
n\k 0 1 2 3 4 5 6 7 8 ...
n=0: 1
n=1: 1 1
n=2: 2 3 1
n=3: 6 11 6 1
n=4: 24 50 35 10 1
n=5: 120 274 225 85 15 1
n=6: 720 1764 1624 735 175 21 1
n=7: 5040 13068 13132 6769 1960 322 28 1
n=8: 40320 109584 118124 67284 22449 4536 546 36 1
n=9: 362880, 1026576, 1172700, 723680, 269325, 63273, 9450, 870, 45, 1;
n=10: 3628800, 10628640, 12753576, 8409500, 3416930, 902055, 157773, 18150, 1320, 55, 1.
[Reformatted and extended by Wolfdieter Lang, Feb 05 2013]
T(3,2) = 6 because there are 6 permutations of {1,2,3,4} that have exactly 2 0's in their inversion vector:{1, 2, 4, 3}, {1, 3, 2, 4}, {1, 3, 4, 2}, {2, 1, 3, 4},{2, 3, 1, 4}, {2, 3, 4, 1}. The respective inversion vectors are: {0, 0, 1},{0, 1, 0}, {0, 2, 0}, {1, 0, 0}, {2, 0, 0}, {3, 0, 0}. - Geoffrey Critzer, May 07 2010
T(3,1)=11 since there are exactly 11 permutations of {1,2,3,4} with exactly 2 cycles, namely, (1)(234),(1)(243),(2)(134),(2)(143),(3)(124),(3)(142),
(4)(123),(4)(143),(12)(34),(13)(24), and (14)(23). - Dennis P. Walsh, Jan 25 2011
From Peter Bala, Jul 21 2014: (Start)
With the arrays M(k) as defined in the Comments section, the infinite product M(0*)M(1)*M(2)*... begins
/ 1 \/1 \/1 \ / 1 \
| 1 1 ||0 1 ||0 1 | | 1 1 |
| 2 2 1 ||0 1 1 ||0 0 1 |... = | 2 3 1 |
| 6 6 3 1 ||0 2 2 1 ||0 0 1 1 | | 6 11 6 1 |
|24 24 12 4 1||0 6 6 3 1||0 0 2 2 1| |24 50 35 10 1|
|... ||... ||... | |... |
(End)
MAPLE
with(combinat): A130534 := proc(n, m): (-1)^(n+m)*stirling1(n+1, m+1) end proc: seq(seq(A130534(n, m), m=0..n), n=0..10); # Johannes W. Meijer, Oct 07 2009, revised Sep 11 2012
# The function BellMatrix is defined in A264428.
# Adds (1, 0, 0, 0, ..) as column 0 (and shifts the enumeration).
BellMatrix(n -> n!, 9); # Peter Luschny, Jan 27 2016
MATHEMATICA
Table[Table[ Length[Select[Map[ToInversionVector, Permutations[m]], Count[ #, 0] == n &]], {n, 0, m - 1}], {m, 0, 8}] // Grid (* Geoffrey Critzer, May 07 2010 *)
rows = 10;
t = Range[0, rows]!;
T[n_, k_] := BellY[n, k, t];
Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 22 2018, after Peter Luschny *)
PROG
(Haskell)
a130534 n k = a130534_tabl !! n !! k
a130534_row n = a130534_tabl !! n
a130534_tabl = map (map abs) a008275_tabl
-- Reinhard Zumkeller, Mar 18 2013
CROSSREFS
See A008275, which is the main entry for these numbers; A094638 (reversed rows).
From Johannes W. Meijer, Oct 07 2009: (Start)
Row sums equal A000142.
The asymptotic expansions lead to A000142 (n=1), A000142(n=2; minus a(0)), A001710 (n=3), A001715 (n=4), A001720 (n=5), A001725 (n=6), A001730 (n=7), A049388 (n=8), A049389 (n=9), A049398 (n=10), A051431 (n=11), A008279 and A094587.
Cf. A163931 (E(x,m,n)), A028421 (m=2), A163932 (m=3), A163934 (m=4), A163936.
(End)
Cf. A136662.
Sequence in context: A138771 A121748 A174893 * A008275 A107416 A105613
KEYWORD
nonn,tabl
AUTHOR
Philippe Deléham, Aug 09 2007
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)