cp's OEIS Frontend

For a signed version of this triangle see A062138. This is the case r = 3 of the unsigned r-Lah numbers L(r;n,k). The unsigned 3-Lah numbers count the partitions of the set {1,2,...,n} into k ordered lists with the restriction that the elements 1, 2 and 3 belong to different lists. For other cases see A105278 (r = 1), A143497 (r = 2 and comments on the general case) and A143499 (r = 4).

The unsigned 3-Lah numbers are related to the 3-Stirling numbers: the lower triangular array of unsigned 3-Lah numbers may be expressed as the matrix product St1(3) * St2(3), where St1(3) = A143492 and St2(3) = A143495 are the arrays of 3-Stirling numbers of the first and second kind respectively. An alternative factorization for the array is as St1 * P^4 * St2, where P denotes Pascal's triangle, A007318, St1 is the triangle of unsigned Stirling numbers of the first kind, abs(A008275) and St2 denotes the triangle of Stirling numbers of the second kind, A008277.

This is the case r = 5 of the r-Eulerian numbers, denoted by A(r;n,k), defined as follows. Let [n] denote the ordered set {1,2,...,n} and let r be a nonnegative integer. Let Permute(n,n-r) denote the set of injective maps p:[n-r] -> [n], which we think of as permutations of n numbers taken n-r at a time. Clearly, |Permute(n,n-r)| = n!/r!. We say that the permutation p has an excedance at position i, 1 <= i <= n-r, if p(i) > i. Then the r-Eulerian number A(r;n,k) is defined as the number of permutations in Permute(n,n-r) with k excedances. Thus the 5-Eulerian numbers count the permutations in Permute(n,n-5) with k excedances. For other cases see A008292 (r = 0 and r = 1), A144696 (r = 2), A144697 (r = 3) and A144698 (r = 4).

An alternative interpretation of the current array due to [Strosser] involves the 5-excedance statistic of a permutation (see also [Foata & Schutzenberger, Chapitre 4, Section 3]). We define a permutation p in Permute(n,n-5) to have a 5-excedance at position i (1 <=i <= n-5) if p(i) >= i + 5.

Given a permutation p in Permute(n,n-5), define ~p to be the permutation in Permute(n,n-5) that takes i to n+1 - p(n-i-4). The map ~ is a bijection of Permute(n,n-5) with the property that if p has (resp. does not have) an excedance in position i then ~p does not have (resp. has) a 5-excedance at position n-i-4. Hence ~ gives a bijection between the set of permutations with k excedances and the set of permutations with (n-k) 5-excedances. Thus reading the rows of this array in reverse order gives a triangle whose entries count the permutations in Permute(n,n-5) with k 5-excedances.

Example: Represent a permutation p:[n-5] -> [n] in Permute(n,n-5) by its image vector (p(1),...,p(n-5)). In Permute(12,7) the permutation p = (1,2,4,12,3,6,5) does not have an excedance in the first two positions (i = 1 and 2) or in the final three positions (i = 5, 6 and 7). The permutation ~p = (8,7,10,1,9,11,12) has 5-excedances only in the first three positions and the final two positions.

a(n) enumerates the possibilities for distributing n beads, n>=1, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and k=6 indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as beadless cords contribute a factor 1 in the counting, e.g., a(0):= 1*1 =1. See A000255 for the description of a fixed cord with beads. This produces for a(n) the exponential (aka binomial) convolution of the subfactorial sequence {A000166(n)} and the sequence {A001725(n+5) = (n+5)!/5!}. See the necklaces and cords problem comment in A000153. Therefore the recurrence with inputs holds. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010).

We discovered that the numbers that appear in the lower left triangle of the ED2 array A167560 (m <= n) behave in a regular way, see the formula below. This rather simple regularity doesn't show up in the upper right triangle of the ED2 array (m > n).

If in the partition array M31hat(6):=A145356 entries belonging to partitions with the same parts number m are summed one obtains this triangle of numbers S1hat(6). In the same way the signless Stirling1 triangle |A008275| is obtained from the partition array M_2 = A036039.

The first columns are A001725(n+4), A145359, A145360,...

We get this scaled version of triangle A162990 by dividing the coefficients in the left hand columns by their 'top-values' and then taking the square root.

T(n,k) = A173333(n+1,k+1), 1 <= k <= n. - Reinhard Zumkeller, Feb 19 2010

T(n,k) = A094587(n+1,k+1), 1 <= k <= n. - Reinhard Zumkeller, Jul 05 2012

Triangle T(n,k), 0 <= k <= n, read by rows, given by [ -2, 1, -1, 2, 0, 3, 1, 4, 2, 5, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Aug 23 2006

From Wolfdieter Lang, Jun 23 2011: (Start)

The row polynomials s(n,x):=Sum_{k=0..n} T(n,k)*x^k satisfy risefac(x-2,n)=s(n,x), with the rising factorials risefac(x-2,n):=Product_{j=0..n-1} (x-2+j), n >= 1, risefac(x-2,0)=1. Compare this with the formula risefac(x,n)=|S1|(n,x), with the row polynomials |S1|(n,x) of A132393 (unsigned Stirling1).

This is the third triangle of an a-family of Sheffer arrays, call them |S1|(a), with e.g.f. of the row polynomials |S1|(a;x;z) = ((1-z)^a)*exp(-x*log(1-z)). In the notation showing the column e.g.f.s this is Sheffer ((1-z)^a,-log(1-z)). In the umbral notation (see the Roman reference, given under A094645) this is called Sheffer for (exp(a*t),1-exp(-t)). For a=0 this becomes the unsigned Stirling1 triangle |S1|(0) = A132393 with row polynomials |S1|(0;n,x) =: s1(n,x).

E.g.f. column number k (with leading zeros): ((1-x)^a)*((-log(1-x))^k)/k!, k >= 0.

E.g.f. for row sums is (1-x)^(a-1), and the e.g.f. for the alternating row sums is (1-x)^(a+1).

Row polynomial recurrence:

|S1|(a;n,x)=(x+(n-1-a))*|S1|(a;n-1,m), |S1|(a;0,x)=1.

Meixner identity (see the reference under A060338):

|S1|(a;n,x) - |S1|(a;n,x-1) = n*|S1|(a;n-1,x), n >= 1,

Also (from the corollary 3.7.2 on p. 50 of the Roman reference): |S1|(a;n,x) = (x-a)*|S1|(a;n-1,x+1), n >= 1.

Recurrence: |S1|(a;n,k) = |S1|(a;n-1,k-1) + (n-(a+1))*|S1|(a;n-1,k); |S1|(a;n,k)=0 if n < m, |S1|(a;n,-1)=0, |S1|(a;0,0)=1.

Connection to |Stirling1|=|S1|(0):

|S1|(a;n,k) = Sum_{p=0..a} |S1|(a;a,p)*abs(Stirling1(n-a,k-p)), n >= a.

The exponential convolution identity is

|S1|(a;n,x+y) = Sum_{k=0..n} binomial(n,k)*|S1|(a;k,y)*s1(n-k,x), n >= 0, with symmetry x <-> y.

The Sheffer a- and z-sequences are (see the W. Lang link under A006232): Sha(a;n)=A164555(n)/A027642(n) (independent of a) with e.g.f. x/(1-exp(-x)), and the z-sequence has e.g.f. (exp(a*x)-1)/(exp(-x)-1).

The inverse Sheffer matrix has e.g.f. exp(a*z)*exp(x*(1-exp(-z))), in short notation (exp(a*z),1-exp(-z)),

(or in umbral notation ((1-t)^a,-log(1-t))).

(End)