A143493 Unsigned 4-Stirling numbers of the first kind.

1, 4, 1, 20, 9, 1, 120, 74, 15, 1, 840, 638, 179, 22, 1, 6720, 5944, 2070, 355, 30, 1, 60480, 60216, 24574, 5265, 625, 39, 1, 604800, 662640, 305956, 77224, 11515, 1015, 49, 1, 6652800, 7893840, 4028156, 1155420, 203889, 22680, 1554, 60, 1, 79833600

Offset: 4

Author

Peter Bala, Aug 20 2008

Keywords

• easy
• nonn
• tabl

Comments

See A049459 for a signed version of the array. The unsigned 4-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, 3 and 4 belong to distinct cycles. This is the case r = 4 of the unsigned r-Stirling numbers of the first kind. For other cases see abs(A008275) (r = 1), A143491 (r = 2) and A143492 (r = 3). See A143496 for the corresponding triangle of 4-Stirling numbers of the second kind.

The theory of r-Stirling numbers of both kinds is developed in [Broder]. For details of the related 4-Lah numbers see A143499.

With offset n=0 and k=0, this is the Sheffer triangle (1/(1-x)^4,-log(1-x)) (in the umbral notation of S. Roman's book this would be called Sheffer for (exp(-4*t),1-exp(-t))). See the e.g.f given below. Compare also with the e.g.f. for the signed version A049459. - Wolfdieter Lang, Oct 10 2011

With offset n=0 and k=0: triangle T(n,k), read by rows, given by (4,1,5,2,6,3,7,4,8,5,9,6,...) DELTA (1,0,1,0,1,0,1,0,1,0,1,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 31 2011

Examples

			Triangle begins
  n\k|     4     5     6     7     8     9
  ========================================
  4  |     1
  5  |     4     1
  6  |    20     9     1
  7  |   120    74    15     1
  8  |   840   638   179    22     1
  9  |  6720  5944  2070   355    30     1
  ...
T(6,5) = 9. The 9 permutations of {1,2,3,4,5,6} with 5 cycles such that 1, 2, 3 and 4 belong to different cycles are: (1,5)(2)(3)(4)(6), (1,6)(2)(3)(4)(5), (2,5)(1)(3)(4)(6), (2,6)(1)(3)(4)(5), (3,5)(1)(2)(4)(6), (3,6)(1)(2)(4)(5), (4,5)(1)(2)(3)(6), (4,6)(1)(2)(3)(5) and (5,6)(1)(2)(3)(4).
		

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 [math.CO], 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

Cf. A001715 - A001719 (column 4 - column 8), A001720 (row sums), A008275, A049459 (signed version), A143491, A143492, A143496, A143499.

Programs

Maple

with combinat: T := (n, k) -> (n-4)! * add(binomial(n-j-1,3)*abs(stirling1(j,k-4))/j!,j = k-4..n-4): for n from 4 to 13 do seq(T(n, k), k = 4..n) end do;

Formula

T(n,k) = (n-4)! * Sum_{j = k-4 .. n-4} C(n-j-1,3)*|stirling1(j,k-4)|/j!.

Recurrence relation: T(n,k) = T(n-1,k-1) + (n-1)*T(n-1,k) for n > 4, with boundary conditions: T(n,3) = T(3,n) = 0 for all n; T(4,4) = 1; T(4,k) = 0 for k > 4.

Special cases:

T(n,4) = (n-1)!/3!.

T(n,5) = (n-1)!/3!*(1/4 + ... + 1/(n-1)).

T(n,k) = sum {4 <= i_1 < ...< i_(n-k) < n} (i_1*i_2* ...*i_(n-k)). For example, T(7,5) = Sum_{4 <= i < j < 7} (i*j) = 4*5 + 4*6 + 5*6 = 74.

Row g.f.: Sum_{k = 4..n} T(n,k)*x^k = x^4*(x+4)*(x+5)* ... *(x+n-1).

E.g.f. for column (k+4): Sum_{n = k..inf} T(n+4,k+4)*x^n/n! = 1/k!*1/(1-x)^4 * (log(1/(1-x)))^k.

E.g.f.: (1/(1-t))^(x+4) = Sum_{n = 0..inf} Sum_{k = 0..n} T(n+4,k+4)*x^k*t^n/n! = 1 + (4+x)*t/1! + (20+9*x+x^2)*t^2/2! + .... This array is the matrix product St1 * P^3, 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!/4! ( A001720 ). The alternating row sums are (n-2)!/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+4,i) = |f(n,i,3)|, for n=1,2,...;i=0...n. - Milan Janjic, Dec 21 2008