A381706 Three-dimensional array of the number b(n, k, i) of permutations of k chosen numbers in {1,2,...,n} with i-1 descents, n >= 1, 1 <= k <= n, 1 <= i <= n.
1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 4, 1, 1, 1, 1, 1, 1, 5, 5, 1, 1, 11, 11, 1, 1, 11, 11, 1, 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, 1, 1, 1, 1, 1, 1, 1, 7, 7, 7, 7, 1, 1, 22, 37, 37, 22, 1, 1, 42, 137, 137, 42, 1
Offset: 1
Examples
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.
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.
- J.-L. Lin, The geometry and combinatorics of some Hessenberg varieties related to the permutohedral variety, The Electronic Journal of Combinatorics, Volume 31, Issue 3 (2024), Research Paper #P3.17.
Programs
-
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 -
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 -
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
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.
Comments