cp's OEIS Frontend

Related triangles may be found by varying the function f(x). If f(x) is a linear function, it can be parameterized as f(x) = a*x + b. With different values for a and b, the following triangles are obtained:

a\b 1.......2.......3.......4.......5.......6

-1 A144431

0 A007318 A038208 A038221

1 A008292 A256890 A257180 A257606 A257607

2 A060187 A257609 A257611 A257613 A257615

3 A142458 A257610 A257620 A257622 A257624 A257626

4 A142459 A257612 A257621

5 A142460 A257614 A257623

6 A142461 A257616 A257625

7 A142462 A257617 A257627

8 A167884 A257618

9 A257608 A257619

The row sums of these, and similarly constructed number triangles, are shown in the following table:

a\b 1.......2.......3.......4.......5.......6.......7.......8.......9

0 A000079 A000302 A000400

1 A000142 A001715 A001725 A049388 A049198

2 A000165 A002866 A002866 A051580 A051582

3 A008544 A051578 A037559 A051605 A051607 A051609

4 A001813 A047053 A000407 A034177 A051618 A051620 A051622

5 A047055 A008546 A008548 A034300 A034325 A051688 A051690

6 A047657 A049308 A047058 A034689 A034724 A034788 A053101 A053103

7 A084947 A144827 A049209 A045754 A034830 A034832 A034834 A053105

8 A084948 A144828 A147626 A051189 A034908 A034910 A034912 A034976 A053115

9 A084949 A144829 A147630 A049211 A045756 A035013 A035018 A035021 A035023

10 A051262 A035265 A035273 A035277

11 A254322

12 A145448

The formula can be further generalized to: t(n,m) = f(m+s)*t(n-1,m) + f(n-s)*t(n,m-1), where f(x) = a*x + b. The following table specifies triangles with nonzero values for s (given after the slash).

a\b 0 1 2 3

-2 A130595/1

-1

0

1 A110555/-1 A120434/-1 A144697/1 A144699/2

With the absolute value, f(x) = |x|, one obtains A038221/3, A038234/4, A038247/5, A038260/6, A038273/7, A038286/8, A038299/9 (with value for s after the slash).

If f(x) = A000045(x) (Fibonacci) and s = 1, the result is A010048 (Fibonomial).

In the notation of Carlitz and Scoville, this is the triangle of generalized Eulerian numbers A(r, s | alpha, beta) with alpha = beta = 2. Also the array A(2,1,4) in the notation of Hwang et al. (see page 31). - Peter Bala, Dec 27 2019

This is the case r = 3 of the r-Stirling numbers of the second kind. The 3-Stirling numbers of the second kind give the number of ways of partitioning the set {1,2,...,n} into k nonempty disjoint subsets with the restriction that the elements 1, 2 and 3 belong to distinct subsets. For remarks on the general case see A143494 (r = 2). The corresponding array of 3-Stirling numbers of the first kind is A143492. The theory of r-Stirling numbers of both kinds is developed in [Broder]. For 3-Lah numbers refer to A143498.

From Peter Bala, Sep 19 2008: (Start)

Let D be the derivative operator d/dx and E the Euler operator x*d/dx. Then x^(-3)*E^n*x^3 = Sum_{k = 0..n} T(n+3,k+3)*x^k*D^k.

The row generating polynomials R_n(x) := Sum_{k= 3..n} T(n,k)*x^k satisfy the recurrence R_(n+1)(x) = x*R_n(x) + x*d/dx(R_n(x)) with R_3(x) = x^3. It follows that the polynomials R_n(x) have only real zeros (apply Corollary 1.2. of [Liu and Wang]).

Relation with the 3-Eulerian numbers E_3(n,j) := A144697(n,j): T(n,k) = (3!/k!)*Sum_{j = n-k..n-3} E_3(n,j)*binomial(j,n-k) for n >= k >= 3.

(End)

T(n,k) = S(n,k,3), n>=k>=3, in Mikhailov's first paper, eq.(28) or (A3). E.g.f. column k from (A20) with k->3, r->k. Therefore, with offset [0,0], this triangle is the Sheffer triangle (exp(3*x),exp(x)-1) with e.g.f. of column no. m>=0: exp(3*x)*((exp(x)-1)^m)/m!. See one of the formulas given below. For Sheffer matrices see the W. Lang link under A006232 with the S. Roman reference, also found in A132393. - Wolfdieter Lang, Sep 29 2011

Let [n] denote the ordered set {1,2,...,n}. The symmetric group S_n consists of the injective mappings p:[n] -> [n]. Such a permutation p has an excedance at position i, 1 <= i < n, if p(i) > i. One well-known interpretation of the Eulerian numbers A(n,k) is that they count the permutations in the symmetric group S_n with k excedances. The triangle of Eulerian numbers is A008292 (but with an offset of 1 in the column numbering). We generalize this definition to restricted permutations as follows.

Let r be a nonnegative integer and 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 p has an excedance at position i, 1 <= i <= n-r, if p(i) > i. Then the r-Eulerian number, denoted by A(r;n,k), is defined as the number of permutations in Permute(n,n-r) having k excedances. Thus the current array of 2-Eulerian numbers gives the number of permutations in Permute(n,n-2) with k excedances. See the example section below for some numerical examples.

Clearly A(0;n,k) = A(n,k). The case r = 1 also produces the ordinary Eulerian numbers A(n,k). There is an obvious bijection from Permute(n,n) to Permute(n,n-1) that preserves the number of excedances of a permutation. Consequently, the 1-Eulerian numbers are equal to the 0-Eulerian numbers: A(1;n,k) = A(0;n,k) = A(n,k).

For other cases of r-Eulerian numbers see A144697 (r = 3), A144698 (r = 4) and A144699 (r = 5). There is also a concept of r-Stirling numbers of the first and second kinds - see A143491 and A143494. If we multiply the entries of the current array by a factor of 2 and then reverse the rows we obtain A120434.

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

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

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

From Peter Bala, Dec 27 2019: (Start)

This is the array A(1,1,3) in the notation of Hwang et al. (p. 25), where the authors remark that the r-Eulerian numbers were first studied by Shanlan Li (Duoji Bilei, Ch. 4), who gave the summation formulas

Sum_{i = 2..n+1} (i-1)*C(i,2) = C(n+3,4) + 2*C(n+2,4)

Sum_{i = 2..n+1} (i-1)^2*C(i,2) = C(n+4,5) + 7*C(n+3,5) + 4*C(n+2,5)

Sum_{i = 2..n+1} (i-1)^3*C(i,2) = C(n+5,6) + 18*C(n+4,6) + 33*C(n+3,6) + 8*C(n+2,6). (End)

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.

This is the case r = 4 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 4-Eulerian numbers are the number of permutations in Permute(n,n-4) with k excedances. For other cases see A008292 (r = 0 and r = 1), A144696 (r = 2), A144697 (r = 3) and A144699 (r = 5).

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

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

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

Row sums are: {1, 7, 56, 504, 5040, 55440, 665280, 8648640, 121080960, 1816214400,...}. The sequences A008292, A144696,A144697,A144698,A144699 and this one, form a matrix of polynomials that are used in data smoothing calculations.