4,2

See A049459 for a signed version of the array. The unsigned 4-restricted Stirling numbers of the first kind count the number of 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-restricted 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-restricted Stirling numbers of the second kind.

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

Broder Andrei Z., The r-Stirling numbers, Discrete Math. 49, 241-259 (1984)

Neuwirth Erich, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 No. 1-3, 33-51 (2001)

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* (ln(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+9x+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. [From Milan R. Janjic (agnus(AT)blic.net), Dec 21 2008]

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 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).

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;

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

Sequence in context: A078939 A135891 A049459 this_sequence A062137 A143497 A144354

Adjacent sequences: A143490 A143491 A143492 this_sequence A143494 A143495 A143496

easy,nonn,tabl

Peter Bala (pbala(AT)toucansurf.com), Aug 20 2008