

A094638


Triangle read by rows: T(n,k) =s(n,n+1k), where s(n,k) are the signed Stirling numbers of the first kind (1<=k<=n; in other words, the unsigned Stirling numbers of the first kind in reverse order).


56



1, 1, 1, 1, 3, 2, 1, 6, 11, 6, 1, 10, 35, 50, 24, 1, 15, 85, 225, 274, 120, 1, 21, 175, 735, 1624, 1764, 720, 1, 28, 322, 1960, 6769, 13132, 13068, 5040, 1, 36, 546, 4536, 22449, 67284, 118124, 109584, 40320, 1, 45, 870, 9450, 63273, 269325, 723680, 1172700
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

Triangle of coefficients of the polynomial (x+1)(x+2)...(x+n), expanded in decreasing powers of x.  T. D. Noe, Feb 22 2008
T(n,k) is the number of deco polyominoes of height n and having k columns. A deco polyomino is a directed columnconvex polyomino in which the height, measured along the diagonal, is attained only in the last column. Example: T(2,1)=1 and T(2,2)=1 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, having, respectively, 1 and 2 columns.  Emeric Deutsch, Aug 14 2006
Sum(k*T(n,k), k=1..n) = A121586.  Emeric Deutsch, Aug 14 2006
Let the triangle U(n,k), 0<=k<=n, read by rows, given by [1,0,1,0,1,0,1,0,1,0,1,...] DELTA [1,1,2,2,3,3,4,4,5,5,6,...] where DELTA is the operator defined in A084938 ; then T(n,k)=U(n1,k1).  Philippe Deléham, Jan 06 2007
From Tom Copeland, Dec 15 2007: (Start)
Consider c(t) = column vector(1, t, t^2, t^3, t^4, t^5,...).
Starting at 1 and sampling every integer to the right, we obtain (1,2,3,4,5,...). And T * c(1) = (1, 1*2, 1*2*3, 1*2*3*4,...), giving n! for n>0. Call this sequence the right factorial (n+)!.
Starting at 1 and sampling every integer to the left, we obtain (1,0,1,2,3,4,5,...). And T * c(1) = (1, 1*0, 1*0*1, 1*0*1*2,...) = (1, 0, 0, 0, ...), the left factorial (n)!.
Sampling every other integer to the right, we obtain (1,3,5,7,9,...). T * c(2) = (1, 1*3, 1*3*5, ...) = (1,3,15,105,945,...), giving A001147 for n>0, the right double factorial, (n+)!!.
Sampling every other integer to the left, we obtain (1,1,3,5,7...). T * c(2) = (1, 1*1, 1*1*3, 1*1*3*5,...) = (1,1,3,15,105,945,...) = signed A001147, the left double factorial, (n)!!.
Sampling every 3 steps to the right, we obtain (1,4,7,10,...). T * c(3) = (1, 1*4, 1*4*7,...) = (1,4,28,280,...), giving A007559 for n>0, the right triple factorial, (n+)!!!.
Sampling every 3 steps to the left, we obtain (1,2,5,8,11,...), giving T * c(3) = (1, 1*2, 1*2*5, 1*2*5*8,...) = (1,2,10,80,880,...) = signed A008544, the left triple factorial, (n)!!!.
The list partition transform A133314 of [1,T * c(t)] gives [1,T * c(t)] with all odd terms negated; e.g., LPT[1,T*c(2)] = (1,1,1,3,15,105,945,...) = (1,A001147). And e.g.f. for [1,T * c(t)] = (1xt)^(1/t).
The above results hold for t any real or complex number. (End)
Let R_n(x) be the real and I_n(x) the imaginary part of product(x+I*k,k=0..n). Then, for n=1,2,..., we have R_n(x)=sum((1)^k*stirling1(n+1,n+12*k)*x^(n+12*k),k=0..floor((n+1)/2)), I_n(x)=sum((1)^(k+1)*stirling1(n+1,n2*k)*x^(n2*k),k=0..floor(n/2)).  Milan Janjic, May 11 2008
T(n,k) is also the number of permutations of n with "reflection length" k (i.e., obtained from 12..n by k not necessarily adjacent transpositions). For example, when n=3, 132, 213, 321 are obtained by one transposition, while 231 and 312 require two transpositions.  Kyle Petersen, Oct 15 2008
From Tom Copeland, Nov 02 2010: (Start)
[x^(y+1) D]^n = x^(n*y) [T(n,1)(xD)^n + T(n,2)y (xD)^(n1) + ... + T(n,n)y^(n1)(xD)], with D the derivative w.r.t. x.
E.g., [x^(y+1) D]^4 = x^(4*y) [(xD)^4 + 6 y(xD)^3 + 11 y^2(xD)^2 + 6 y^3(xD)].
(xD)^m can be further expanded in terms of the Stirling numbers of the second kind and operators of the form x^j D^j. (End)
With offset 0, 0<=k<=n: T[n,k) is the sum of products of each size k subset of {1,2,...,n}. For example, T(3,2) = 11 because there are three subsets of size two: {1,2},{1,3},{2,3}. 1*2+1*3+2*3=11.  Geoffrey Critzer, Feb 04 2011
The Kn11, Fi1 and Fi2 triangle sums link this triangle with two sequences, see the crossrefs. For the definitions of these triangle sums see A180662. The mirror image of this triangle is A130534.  Johannes W. Meijer, Apr 20 2011
T(n+1,k+1) is the elementary symmetric function a_k(1,2,...,n), n>=0, k>=0, (a_0(0):=1). See the T. D. Noe and Geoffrey Critzer comments given above. For a proof see the Stanley reference, p. 19, Second Proof.  Wolfdieter Lang, Oct 24 2011
Let g(t)=1/d[log(P(j+1,t))]/dt (see Tom Copeland's 2007 formulas). The Mellin transform (t to s) of t*Dirac[g(t)] gives sum(n=1 to j) n^(s), which as j tends to infinity gives the Riemann zeta fct. for Re(s) > 1. Dirac(x) is the Dirac delta fct. The complex contour integral along a circle of radius 1 centered at z=1 of z^s/g(z) gives the same result.  Tom Copeland, Dec 02 2011
Rows are coefficients of the polynomial expansions of the Pochhammer symbol, or rising factorial, Pch(n,x) = (x+n1)!/(x1)!. Expansion of Pch(n,xD) = Pch(Bell(.,:xD:)) in a polynomial with terms :xD:^k=x^kD^k gives the Lah numbers A008297. Bell(n,x) are the unsigned Bell polynomials or Stirling polynomials of the second kind A008277.  Tom Copeland, Mar 01 2014


REFERENCES

R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1997.


LINKS

T. D. Noe, Rows n=1..51 of triangle, flattened
E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 2942.
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.C. Raoult, Springer 1992, pp. 2448. Added Mar 01 2014
F. Bergeron, Philippe Flajolet and Bruno Salvy, Varieties of increasing trees, HAL, Rapport De Recherche Inria. Added Mar 01 2014
Tom Copeland, Addendum to Mathemagical Forests
FindStat  Combinatorial Statistic Finder, The absolute length of a permutation
F. Hivert, J.C. Novelli and J.Y. Thibon, The Algebra of Binary Search Trees, Theoretical Computer Science, 339 (2005), 129165.
R. Mestrovic, Lucas' theorem: its generalizations, extensions and applications (18782014), arXiv preprint arXiv:1409.3820, 2014


FORMULA

With P(n,t) = sum(k=0,...,n1) T(n,k+1) * t^k = 1*(1+t)*(1+2t)...(1+(n1)*t) and P(0,t)=1, exp[P(.,t)*x] = (1tx)^(1/t) . T(n,k+1) = (1/k!) (D_t)^k (D_x)^n [ (1tx)^(1/t)  1 ] evaluated at t=x=0. (1tx)^(1/t)  1 is the e.g.f. for a plane mary tree when t=m1. See Bergeron et al. in "Varieties of Increasing Trees".  Tom Copeland, Dec 09 2007
First comment and formula above rephrased as o.g.f. for row n: Product_{i=0...n} (1+i*x).  Geoffrey Critzer, Feb 04 2011
nth row polynomials with alternate signs are the characteristic polynomials of the (n1)x(n1) matrices with 1's in the superdiagonal, (1,2,3,...) in the main diagonal, and the rest zeros. For example, the characteristic polynomial of [1,1,0; 0,2,1; 0,0,3] is x^3  6*x^2 + 11*x  6.  Gary W. Adamson, Jun 28 2011
E.g.f.: A(x,y) = x*y/(1  x*y)^(1 + 1/y) = Sum_{n>=1,k=1..n} T(n,k)*x^n*y^k/(n1)!.  Paul D. Hanna, Jul 21 2011
With F(x,t) = (1t*x)^(1/t)  1 an e.g.f. for the row polynomials P(n,t) of A094638 with P(0,t)=0, G(x,t)= [1(1+x)^(t)]/t is the comp. inverse in x. Consequently, with H(x,t) = 1/ (dG(x,t)/dx) = (1+x)^(t+1),
P(n,t) = [(H(x,t)*d/dx)^n] x evaluated at x=0; i.e.,
F(x,t) = exp[x*P(.,t)] = exp[x*H(u,t)*d/du] u, evaluated at u = 0.
Also, dF(x,t)/dx = H(F(x,t),t).  Tom Copeland, Sep 20 2011


EXAMPLE

Triangle starts:
1;
1,1;
1,3,2;
1,6,11,6;
1,10,35,50,24;


MAPLE

with(combinat): T:=(n, k)>abs(stirling1(n, n+1k)): for n from 1 to 10 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form. # Emeric Deutsch, Aug 14 2006


MATHEMATICA

Table[CoefficientList[Series[Product[1 + i x, {i, 1, n}], {x, 0, 20}], x], {n, 0, 6}] (* Geoffrey Critzer, Feb 04 2011 *)


PROG

(PARI) {T(n, k)=if(n<1k>n, 0, (n1)!*polcoeff(polcoeff(x*y/(1  x*y+x*O(x^n))^(1 + 1/y), n, x), k, y))} /* Paul D. Hanna, Jul 21 2011 */
(Maxima) create_list(abs(stirling1(n+1, nk+1)), n, 0, 10, k, 0, n); / * Emanuele Munarini, Jun 01 2012 */
(Haskell)
a094638 n k = a094638_tabl !! (n1) !! (k1)
a094638_row n = a094638_tabl !! (n1)
a094638_tabl = map reverse a130534_tabl
 Reinhard Zumkeller, Aug 01 2014


CROSSREFS

Cf. A000108, A014137, A001246, A033536, A000984, A094639, A006134, A082894, A002897, A079727.
Cf. A000142 equals row sums.  Johannes W. Meijer, Jun 08 2009
Triangle sums (see the comments): A124380 (Kn11), A001710 (Fi1, Fi2).  Johannes W. Meijer, Apr 20 2011
Cf. A121586, A130534.
Sequence in context: A193593 A181853 A008276 * A196844 A196843 A143778
Adjacent sequences: A094635 A094636 A094637 * A094639 A094640 A094641


KEYWORD

easy,nonn,tabl


AUTHOR

André F. Labossière, May 17 2004


EXTENSIONS

Edited by Emeric Deutsch, Aug 14 2006


STATUS

approved



