OFFSET
1,10
COMMENTS
For n >= 1, 0 <= k <= n-2, and 0 <= i <= n-1, b(n+1, k+1, i+1) is the (2i)th Betti number of the prepermutohedral variety X_k obtained by k iterated blowups of projective space P^n.
LINKS
Timothy Y. Chow, Table of n, a(n) for n = 1..385
Timothy Chow et al., A new generalization of Eulerian numbers, MathOverflow, 2025.
Mark Conger, A Refinement of the Eulerian Numbers, and the Joint Distribution of π(1) and Des(π) in S_n, arXiv:math/0508112 [math.CO], 2005.
Giovanni Gaiffi and Giovanni Interdonato, Generalizing Eulerian Numbers via Semipermutations: Topological and Combinatorial Aspects, arXiv:2601.17945v1, 25 Jan 2026. See references.
Jan-Li Lin, The geometry and combinatorics of some Hessenberg varieties related to the permutohedral variety, Elec. J. Comb. 31(3) (2024), P3.17.
FORMULA
Explicit formula for b(n, k, i) is given in MO link and PARI code below. - Max Alekseyev, Mar 14 2025
The recurrence b(n,k,i) = b(n,k-1,i) + (n choose k) Sum_{i=d-n+k}^{d-1} b(k-1,k-2,j) was conjectured by Ron Fertig and proved by Alex R. Miller.
b(n, n, k) equals the Eulerian number T(n, k) of A008292.
If n > 1 then b(n, n-1, k) also equals the Eulerian number T(n, k) of A008292.
Sum_{i} b(n, k, i) equals the falling factorial A068424.
Empirically, Sum_{k} b(n, k, i) seems to equal A381888.
EXAMPLE
For n = 4 and k = 2, there are 12 permutations of 2 chosen numbers in {1,2,3,4}; the number of descents is defined to be the number of descents in the permutation of the chosen numbers, plus the number of non-chosen numbers greater than the first chosen number. For example, 32 has 2 descents because 3 is greater than 2 and 4 (a non-chosen number) is greater than 3. The four other permutations of 2 chosen numbers with 2 descents are 31, 12, 13, 14.
The sequence is most naturally viewed as a sequence of squares of size 1x1, 2x2, 3x3, 4x4, etc.
1 [E(1)]
1 1
1 1 [E(2)]
1 1 1
1 4 1
1 4 1 [E(3)]
1 1 1 1
1 5 5 1
1 11 11 1
1 11 11 1 [E(4)]
1 1 1 1 1
1 6 6 6 1
1 16 26 16 1
1 26 66 26 1
1 26 66 26 1 [E(5)]
...
[E(n)] refers to row n of A008292.
MAPLE
beta := proc(n, k)
local b, p, plist, descents, s, i, r, R:
r := 1..n; R := {`$`(r)};
b := Array(r, fill=0);
plist := combinat:-permute(n, k):
for p in plist do
descents := 1:
s := R minus {op(p)}:
for i in s do
if i > p[1] then descents := descents + 1 end if:
end do:
for i to k-1 do
if p[i] > p[i+1] then descents := descents + 1 end if:
end do:
b[descents] := b[descents] + 1:
end do:
return b
end proc:
for n from 1 to 5 do seq(beta(n, k), k = 1..n) end do;
# After Max Alekseyev's PARI program:
b := (n, k, i) -> local p, t, j; add(add(binomial(n - p, t) * binomial(p - 1, n - k - t) * add(binomial(k, j)*(-1)^j*(i - t - j)^(n - t - p) * (i - 1 - t - j)^(k - n - 1 + t + p), j = 0..i-1-t), t = n+1-k-p..i-1), p = 1..n): seq(seq(seq(b(n, k, j), j = 1..n), k = 1..n), n = 1..6); # Peter Luschny, Mar 15 2025
PROG
(SageMath)
def beta(n: int, k: int) -> list[int]:
b = [0]*n
for p in Permutations(n, k):
descents = sum(int(not i in p and i > p[0]) for i in (1..n))
descents += sum(int(p[i-1] > p[i]) for i in (1..k-1))
b[descents] += 1
return b
def Trow(n) -> list[int]: return flatten([beta(n, k) for k in (1..n)])
for n in (1..6): print(f"{n}: ", Trow(n)) # Peter Luschny, Mar 11 2025
(PARI) { b(n, k, i) = sum(p=1, n, sum(t=n+1-k-p, i-1, my(l=n+1-t-p); binomial(n-p, t) * binomial(p-1, n-k-t) * sum(j=0, i-1-t, binomial(k, j) * (-1)^j * (i-t-j)^(l-1) * (i-1-t-j)^(k-l) )) ); } \\ Max Alekseyev, Mar 14 2025
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Timothy Y. Chow, Mar 04 2025
STATUS
approved