|
| |
|
|
A136126
|
|
Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,k+n} having excedance set {1,2,...,k} (the empty set for k=0), 0 <= k <= n-1.
|
|
10
|
|
|
|
1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 15, 31, 15, 1, 1, 31, 115, 115, 31, 1, 1, 63, 391, 675, 391, 63, 1, 1, 127, 1267, 3451, 3451, 1267, 127, 1, 1, 255, 3991, 16275, 25231, 16275, 3991, 255, 1, 1, 511, 12355, 72955, 164731, 164731, 72955, 12355, 511, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
The excedance set of a permutation p in S_n is the set of indices i such that p(i) > i.
T(a+b-1,b-1)*(-1)^(a+b-1) = Sum_{k=0..} F(a,b,k)*(-1)^k where F(a,b,k) is the number of connected subgraphs of K(a,b) (the complete bipartite graph) with k edges. F(n,n,k) is A255192(n,k). - Thomas Dybdahl Ahle, Feb 18 2015 [The sum starts with k=0, and F(n,n,k) is A255192(n,k), but there seems to be no A255192(n,0). Is there no upper k-summation limit? - Wolfdieter Lang, Mar 15 2015]
This array also arises from a problem about {0,1}-matrices. Symmetric array read by antidiagonals: A(n,k) (n >= 1, k >= 0) = number of n X k matrices of 0's and 1's satisfying two conditions: (i) no column is entirely 0; (ii) no 0 has simultaneously a 1 above it and another 1 to its left.
Equivalently (see the Steingrímsson-Williams reference) A(n,k) is the number of permutations p_1...p_{n+k} on {1,...,n+k} for which p_1 >= 1, ..., p_n >= n, p_{n+1} < n+1,..., p_{n+k} < n+k. Then A(n,k) = A(k+1,n-1), for n >= 1 and k >= 0.
For example, the seven 2 X 2 matrices satisfying (i) and (ii) are
00 01 10 10 11 11 11
11 11 01 11 00 01 11
and the seven permutations of {1, 2, 3, 4} satisfying the other definition are
1423, 2413, 3412, 3421, 4213, 4312, 4321.
(End)
|
|
|
LINKS
|
Julius Worpitzky, Studien über die Bernoullischen und Eulerschen Zahlen, Journal für die reine und angewandte Mathematik. 94:203-232, 1883.
|
|
|
FORMULA
|
T(n,k) = Sum_{i=1..k+1} (-1)^(k+1-i)*i!*i^(n-1-k)*Stirling2(k+1,i) (0 <= k <= n-1).
G.f.: A(x,y) = x*y*Sum_{n>=1} n! * x^n*Product_{k=1..n} (1 + y + k*x*y) / (1 + (1+y)*k*x + k^2*x^2*y). - Paul D. Hanna, Feb 01 2013
T(n,k-1) = Sum_{i=0..k, m=0..i} binomial(i,m)*(-1)^(k-m)*i^(n-k)*m^k (1 <= k <= n). - Thomas Dybdahl Ahle, Feb 18 2015
Let W(n,k) = k!*Stirling2(n+1, k+1) denote the Worpitzky numbers, then A(n,k) = Sum_{j=0..k} (-1)^(k-j)*W(k,j)*(j+1)^(n+1) enumerates the square array. - Peter Luschny, Mar 14 2018
Assume the missing first row (1,0,0,...) of the array which Ayyer and Bényi call the 'poly-Bernoulli numbers of type C'. Then T(n, k) = p_{n}(k) where p_{n}(x) = Sum_{k=0..n} (-1)^(n-k)*(k+1)^x*Sum_{j=0..n} E1(n,j)*binomial(n-j, n-k), and E1(n, k) are the Eulerian numbers of first order. This reflects the Worpitzky approach to the Bernoulli numbers. This formula can alternatively be written as: T(n, k) = Sum_{j=0..k} (-1)^(k-j)*(j+1)^n*A028246(k+1, j+1). - Peter Luschny, Apr 29 2021
|
|
|
EXAMPLE
|
T(4,2) = 7 because 3412, 4312, 2413, 2314, 2431, 3421 and 4321 are the only permutations of {1,2,3,4} with excedance set {1,2}.
Triangle starts:
1;
1, 1;
1, 3, 1;
1, 7, 7, 1;
1, 15, 31, 15, 1;
1, 31, 115, 115, 31, 1;
1, 63, 391, 675, 391, 63, 1;
1, 127, 1267, 3451, 3451, 1267, 127, 1;
1, 255, 3991, 16275, 25231, 16275, 3991, 255, 1;
...
Formatted as a square array A(n,k) with 0 <= k <= n:
1, 1, 1, 1, 1, 1, 1, 1, ... [A000012]
1, 3, 7, 15, 31, 63, 127, 255, ... [A000225]
1, 7, 31, 115, 391, 1267, 3991, 12355, ... [A091344]
1, 15, 115, 675, 3451, 16275, 72955, 316275, ... [A091347]
1, 31, 391, 3451, 25231, 164731, 999391, 5767051, ... [A091348]
1, 63, 1267, 16275, 164731, 1441923, 11467387, 85314915, ...
1, 127, 3991, 72955, 999391, 11467387, 116914351, 1096832395, ...
|
|
|
MAPLE
|
with(combinat): T:=proc(n, k) if k < n then add((-1)^(k+1-i)*factorial(i)*i^(n-1-k)* stirling2(k+1, i), i=1..k+1) else 0 end if end proc: for n to 10 do seq(T(n, k), k=0..n-1) end do; # yields sequence in triangular form
# Alternatively as a square array:
A := (n, k) -> add((-1)^(k-j)*j!*Stirling2(k+1, j+1)*(j+1)^(n+1), j=0..k);
seq(print(seq(A(n, k), k=0..7)), n=0..6); # Peter Luschny, Mar 14 2018
# Using the exponential generating function as given by Arakawa & Kaneko:
gf := polylog(-t, 1-exp(-x))/(exp(x)-1):
ser := series(gf, x, 12): c := n -> n!*coeff(ser, x, n):
seq(lprint(seq(subs(t=k, c(n)), n=0..8)), k=0..8); # Peter Luschny, Apr 29 2021
# Using recurrence relations:
A := proc(n, k) option remember; local j; if n = 0 then return k^n fi;
add(binomial(k+1, j+1)*A(n-1, k-j), j = 0..k) end:
for n from 0 to 7 do lprint(seq(A(n, k), k=0..8)) od; # Peter Luschny, Apr 19 2024
|
|
|
MATHEMATICA
|
T[n_, k_] := Sum[(-1)^(k + 1 - i)*i!*i^(n - 1 - k)*StirlingS2[k + 1, i], {i, 1, k + 1}];
|
|
|
PROG
|
(PARI) {T(n, k)=polcoeff(polcoeff( x*y*sum(m=0, n, m!*x^m*prod(k=1, m, (1+y+k*x*y)/(1+(1+y)*k*x+k^2*x^2*y +x*O(x^n))) ), n, x), k, y)} \\ Paul D. Hanna, Feb 01 2013
for(n=1, 10, for(k=1, n, print1(T(n, k), ", ")); print(""))
(PARI) tabl(nn) = {default(seriesprecision, nn+1); pol = log(1/(1-(exp(x)-1)*(exp(y)-1))) + O(x^nn); for (n=1, nn-1, poly = n!*polcoeff(pol, n, x); for (k=1, n, print1(k!*polcoeff(poly, k, y), ", "); ); print(); ); } \\ Michel Marcus, Apr 17 2015
|
|
|
CROSSREFS
|
Cf. A000225, A028246, A091344, A091347, A091348, A092552, A136127, A152884, A255192, A329369, A371761.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Definition corrected. Changed "T(n,k) is the number of permutations of {1,2,...,n}..." to "T(n,k) is the number of permutations of {1,2,...,k+n}..." - Karel Casteels (kcasteel(AT)sfu.ca), Feb 17 2010
|
|
|
STATUS
|
approved
|
| |
|
|
