2,2

Essentially the same as A136124 but with column numbers differing by one. See A049444 for a signed version of this array. The unsigned 2-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 and 2 belong to distinct cycles. This is the particular case r = 2 of the unsigned r-restricted Stirling numbers of the first kind, which count the number of permutations of the set {1,2,...,n} into k disjoint cycles, with the restriction that the numbers 1, 2, ..., r belong to distinct cycles. The case r = 1 gives the usual unsigned Stirling numbers of the first kind, abs(A008275); for other cases see A143492 (r = 3) and A143493 (r = 4). The corresponding 2-restricted Stirling numbers of the second kind can be found in A143494.

In general, the lower unitriangular array of unsigned r-restricted Stirling numbers of the first kind (with suitable offsets in the row and column indexing) equals the matrix product St1 * P^(r-1), where St1 is the array of unsigned Stirling numbers of the first kind, abs(A008275) and P is Pascal's triangle, A007318. The theory of r-restricted Stirling numbers of both kinds is developed in [Broder]. For details of the related r-restricted Lah numbers see A143497.

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-2)! * sum {j = k-2 .. n-2} (n-j-1)*|stirling1(j,k-2)|/j!. Recurrence relation: T(n,k) = T(n-1,k-1) + (n-1)*T(n-1,k) for n > 2, with boundary conditions: T(n,1) = T(1,n) = 0, for all n; T(2,2) = 1; T(2,k) = 0 for k > 2. Special cases: T(n,2) = (n-1)!; T(n,3) = (n-1)!*(1/2 + 1/3 + ... + 1/(n-1)). T(n,k) = sum {2 <= i_1 < ...< i_(n-k) < n} (i_1*i_2* ...*i_(n-k)). For example, T(6,4) = sum {2 <= i < j < 6} (i*j) = 2*3 + 2*4 + 2*5 + 3*4 + 3*5 + 4*5 = 71. Row g.f.: sum {k = 2..n} T(n,k)*x^k = x^2*(x+2)*(x+3)* ... *(x+n-1). E.g.f. for column (k+2): sum {n = k..inf} T(n+2,k+2)*x^n/n! = 1/k!*1/(1-x)^2* (ln(1/(1-x)))^k. E.g.f.: (1/(1-t))^(x+2) = sum {n = 0..inf} sum {k = 0..n} T(n+2,k+2)*x^k*t^n/n! = 1 + (2+x)*t/1! + (6+5x+x^2)*t^2/2! + ... . This array is the matrix product St1 * P, 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!/2 ( A001710 ). 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-1,i) = |f(n,i,2)|, for n=1,2,...;i=0...n. [From Milan R. Janjic (agnus(AT)blic.net), Dec 21 2008]

Triangle begins

n\k|.....2.....3.....4.....5.....6.....7

========================================

2..|.....1

3..|.....2.....1

4..|.....6.....5.....1

5..|....24....26.....9.....1

6..|...120...154....71....14.....1

7..|...720..1044...580...155....20.....1

...

T(4,3) = 5. The permutations of {1,2,3,4} with 3 cycles such that 1 and 2 belong to different cycles are: (1)(2)(3 4), (1)(3)(24), (1)(4)(23), (2)(3)(14) and (2)(4)(13). The remaining possibility (3)(4)(12) is not allowed.

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

Cf. A001705 - A001709 (column 3 - column 7), A001710 (row sums), A008275, A049444 (signed version), A136124, A143492, A143493, A143494, A143497.

Sequence in context: A121575 A049444 A136124 this_sequence A070918 A113381 A118980

Adjacent sequences: A143488 A143489 A143490 this_sequence A143492 A143493 A143494

easy,nonn,tabl

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