A049458 Generalized Stirling number triangle of first kind.
1, -3, 1, 12, -7, 1, -60, 47, -12, 1, 360, -342, 119, -18, 1, -2520, 2754, -1175, 245, -25, 1, 20160, -24552, 12154, -3135, 445, -33, 1, -181440, 241128, -133938, 40369, -7140, 742, -42, 1, 1814400, -2592720, 1580508, -537628
Offset: 0
Examples
1; -3, 1; 12, -7, 1; -60, 47, -12, 1; 360, -342, 119, -18, 1; s(2,x) = 12-7*x+x^2. S1(2,x) = -x+x^2 (Stirling1 polynomial).
References
- Mitrinovic, D. S.; Mitrinovic, R. S.; Tableaux d'une classe de nombres relies aux nombres de Stirling. Univ. Beograd. Pubi. Elektrotehn. Fak. Ser. Mat. Fiz. No. 77 1962, 77 pp.
Links
- Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
Crossrefs
Programs
-
Haskell
a049458 n k = a049458_tabl !! n !! k a049458_row n = a049458_tabl !! n a049458_tabl = map fst $ iterate (\(row, i) -> (zipWith (-) ([0] ++ row) $ map (* i) (row ++ [0]), i + 1)) ([1], 3) -- Reinhard Zumkeller, Mar 11 2014
-
Maple
A049458_row := n -> seq((-1)^(n-k)*coeff(expand(pochhammer(x+3, n)), x, k), k=0..n): seq(print(A049458_row(n)),n=0..8); # Peter Luschny, May 16 2013
-
Mathematica
t[n_, k_] := (-1)^(n - k)*Coefficient[ Pochhammer[x + 3, n], x, k]; Table[t[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 17 2013, after Peter Luschny *)
Formula
a(n, m)= a(n-1, m-1) - (n+2)*a(n-1, m), n >= m >= 0; a(n, m) := 0, n
Triangle (signed) = [ -3, -1, -4, -2, -5, -3, -6, -4, -7, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...]; triangle (unsigned) = [3, 1, 4, 2, 5, 3, 6, 4, 7, 5, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...]; where DELTA is Deléham's operator defined in A084938 (unsigned version in A143492).
E.g.f.: (1+y)^(x-3). - Vladeta Jovovic, May 17 2004
If we define f(n,i,a)=sum(binomial(n,k)*stirling1(n-k,i)*product(-a-j,j=0..k-1),k=0..n-i), then T(n,i) = f(n,i,3), for n=1,2,...;i=0...n. - Milan Janjic, Dec 21 2008
Extensions
Second formula corrected by Philippe Deléham, Nov 09 2008
A143492 Unsigned 3-Stirling numbers of the first kind.
1, 3, 1, 12, 7, 1, 60, 47, 12, 1, 360, 342, 119, 18, 1, 2520, 2754, 1175, 245, 25, 1, 20160, 24552, 12154, 3135, 445, 33, 1, 181440, 241128, 133938, 40369, 7140, 742, 42, 1, 1814400, 2592720, 1580508, 537628, 111769, 14560, 1162, 52, 1, 19958400
Offset: 3
Comments
See A049458 for a signed version of this array. The unsigned 3-Stirling numbers of the first kind count the permutations of the set {1,2,...,n} into k disjoint cycles, with the restriction that the elements 1, 2 and 3 belong to distinct cycles. This is the case r = 3 of the unsigned r-Stirling numbers of the first kind. For other cases see abs(A008275) (r = 1), A143491 (r = 2) and A143493 (r = 4). See A143495 for the corresponding 3-Stirling numbers of the second kind. The theory of r-Stirling numbers of both kinds is developed in [Broder]. For details of the related 3-Lah numbers see A143498.
With offset n=0 and k=0, this is the Sheffer triangle (1/(1-x)^3, -log(1-x)) (in the umbral notation of S. Roman's book this would be called Sheffer for (exp(-3*t), 1-exp(-t))). See the e.g.f given below. Compare also with the e.g.f. for the signed version A049458. - Wolfdieter Lang, Oct 10 2011
With offset n=0 and k=0 : triangle T(n,k), read by rows, given by (3,1,4,2,5,3,6,4,7,5,8,6,...) DELTA (1,0,1,0,1,0,1,0,1,0,1,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 31 2011
Examples
Triangle begins
n\k|.....3.....4.....5.....6.....7.....8
========================================
3..|.....1
4..|.....3.....1
5..|....12.....7.....1
6..|....60....47....12.....1
7..|...360...342...119....18.....1
8..|..2520..2754..1175...245....25.....1
...
T(5,4) = 7. The permutations of {1,2,3,4,5} with 4 cycles such that 1, 2 and 3 belong to different cycles are: (14)(2)(3)(5), (15)(2)(3)(4), (24)(1)(3)(5), (25)(1)(3)(4), (34)(1)(2)(5), (35)(1)(2)(4) and (45)(1)(2)(3).
Links
- Broder Andrei Z., The r-Stirling numbers, Discrete Math. 49, 241-259 (1984)
- A. Dzhumadildaev and D. Yeliussizov, Path decompositions of digraphs and their applications to Weyl algebra, arXiv preprint arXiv:1408.6764v1, 2014. [Version 1 contained many references to the OEIS, which were removed in Version 2. - _N. J. A. Sloane_, Mar 28 2015]
- Askar Dzhumadil’daev and Damir Yeliussizov, Walks, partitions, and normal ordering, Electronic Journal of Combinatorics, 22(4) (2015), #P4.10.
- Erich Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 No. 1-3, 33-51 (2001).
- Michael J. Schlosser and Meesue Yoo, Elliptic Rook and File Numbers, Electronic Journal of Combinatorics, 24(1) (2017), #P1.31.
Crossrefs
Programs
-
Maple
with combinat: T := (n, k) -> (n-3)! * add(binomial(n-j-1,2)*abs(stirling1(j,k-3))/j!,j = k-3..n-3): for n from 3 to 12 do seq(T(n, k), k = 3..n) end do;
Formula
T(n,k) = (n-3)! * Sum_{j = k-3 .. n-3} C(n-j-1,2)*|Stirling1(j,k-3)|/j!.
Recurrence relation: T(n,k) = T(n-1,k-1) + (n-1)*T(n-1,k) for n > 3, with boundary conditions: T(n,2) = T(2,n) = 0, for all n; T(3,3) = 1; T(3,k) = 0 for k > 3.
Special cases:
T(n,3) = (n-1)!/2! for n >= 3.
T(n,4) = (n-1)!/2!*(1/3 + ... + 1/(n-1)) for n >= 3.
T(n,k) = Sum_{3 <= i_1 < ... < i_(n-k) < n} (i_1*i_2* ...*i_(n-k)). For example, T(6,4) = Sum_{3 <= i < j < 6} (i*j) = 3*4 + 3*5 + 4*5 = 47.
Row g.f.: Sum_{k = 3..n} T(n,k)*x^k = x^3*(x+3)*(x+4)* ... *(x+n-1).
E.g.f. for column (k+3): Sum_{n = k..inf} T(n+3,k+3)*x^n/n! = 1/k!*1/(1-x)^3 * (log(1/(1-x)))^k.
E.g.f.: (1/(1-t))^(x+3) = Sum_{n = 0..inf} Sum_{k = 0..n} T(n+3,k+3)*x^k*t^n/n! = 1 + (3+x)*t/1! + (12+7*x+x^2)*t^2/2! + ....
This array is the matrix product St1 * P^2, where St1 denotes the lower triangular array of unsigned Stirling numbers of the first kind, abs(A008275) and P denotes Pascal's triangle, A007318. The row sums are n!/3! ( A001715 ). The alternating row sums are (n-2)!.
If we define f(n,i,a) = sum(binomial(n,k)*Stirling1(n-k,i)*product(-a-j,j=0..k-1),k=0..n-i), then T(n,i) = |f(n,i,3)|, for n=1,2,...;i=0...n. - Milan Janjic, Dec 21 2008
Comments