Eulerian numbers and polynomials

Counting permutations by descents or excedances: Eulerian numbers and polynomials, refined, multiset and generalized Eulerian polynomials, associated Stirling–Eulerian numbers, Worpitzky's identity, gamma-positivity and Hankel determinants of Eulerian polynomials, Bell permutations by weak excedances.

• Associated Stirling–Eulerian numbers
• Bell permutations and weak excedances
• Eulerian numbers of multiset permutations
• General arithmetical Eulerian polynomials
• Generalized Eulerian polynomials and gamma-positivity
• Hankel determinants of Eulerian polynomials
• Refined Eulerian polynomials

TheoremWorpitzky identity for multiset permutations#✓fully proved

Let \(m\) and \(x\) be natural numbers, let \(k_1, \dots, k_m\) be natural numbers with sum \(K = k_1 + \dots + k_m\), and for \(p \ge 1\) let \(a_p\) be the number of words \(w_1 w_2 \cdots w_K\) over the alphabet \(\{1, \dots, m\}\) in which each letter \(i\) occurs exactly \(k_i\) times and which have exactly \(p - 1\) descents, that is, indices \(j\) with \(1 \le j < K\) and \(w_j > w_{j+1}\). Then

\[\prod_{i=1}^{m} \binom{x + k_i - 1}{k_i} = \sum_{p=1}^{\max(1, K)} \binom{x + K - p}{K} a_p.\]

Here subtraction of natural numbers is truncated at \(0\).

theorem worpitzky_identity_multiset (m : ℕ) (k : Fin m → ℕ) (x : ℕ) :
    Finset.prod Finset.univ (fun i => Nat.choose (x + k i - 1) (k i)) =
      Finset.sum (Finset.Icc 1 (max 1 (Finset.sum Finset.univ (fun a => k a)))) (fun p =>
        Nat.choose (x + Finset.sum Finset.univ (fun a => k a) - p)
            (Finset.sum Finset.univ (fun a => k a)) *
          Nat.card { w : Fin (Finset.sum Finset.univ (fun a => k a)) → Fin m //
            (∀ i,
              Fintype.card
                  { j : Fin (Finset.sum Finset.univ (fun a => k a)) // w j = i } = k i) ∧
            (Finset.univ.filter
                (fun j : Fin (Finset.sum Finset.univ (fun a => k a)) =>
                  ∃ h : j.val + 1 < Finset.sum Finset.univ (fun a => k a),
                    w j > w ⟨j.val + 1, h⟩)).card + 1 = p })

Sources

• A. Dzhumadil'daev and D. Yeliussizov, Power Sums of Binomial Coefficients, Journal of Integer Sequences 16 (2013), Article 13.1.4, Theorem Worpitzky, lines 212-217, https://cs.uwaterloo.ca/journals/JIS/VOL16/Yeliussizov/dzhuma6.tex, quoting A. S. Dzhumadil'daev, Worpitzky identity for multipermutations, Mat. Zametki 90 (2011), 464-466.

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.