Rust for Embedded Systems: Current State, Challenges and Open

Ayushi Sharma

Purdue University, USA

Shashank Sharma

Purdue University, USA

Santiago Torres-Arias

Purdue University, USA

Aravind Machiry

Purdue University, USA

Embedded software is used in safety-critical systems such as medical devices and autonomous vehicles, where software defects, including security vulnerabilities, have severe consequences.
Most embedded codebases are developed in unsafe languages, specifically C/C++, and are riddled with memory safety vulnerabilities.
To prevent such vulnerabilities, , a performant memory-safe systems language, provides an optimal choice for developing embedded software.
interoperability enables developing  applications on top of existing C codebases.
Despite this, even the most resourceful organizations continue to develop embedded software in C/C++.

This paper performs the first systematic study to holistically understand the current state and challenges of using  for embedded systems.
Our study is organized across three research questions.
We collected a dataset of   embedded software spanning various categories and  SAST tools.
We performed a systematic analysis of our dataset and surveys with  developers to investigate our research questions.
We found that existing  software support is inadequate, SAST tools cannot handle certain features of  embedded software, resulting in failures, and the prevalence of advanced types in existing  software makes it challenging to engineer interoperable code.
In addition, we found various challenges faced by developers in using  for embedded systems development.

§ INTRODUCTION

Our dependence on embedded devices ( IoT devices), has significantly increased, controlling various aspects of our daily lives, including homes <cit.>, transportation <cit.>, traffic management <cit.>, and the distribution of vital resources like food <cit.> and power <cit.>. The adoption of these devices has seen rapid and extensive growth, with an estimated count of over 50 billion devices <cit.>.
Vulnerabilities in these devices have far-reaching consequences <cit.> due to the pervasive and interconnected nature of these devices, as exemplified by the infamous Mirai botnet <cit.>.

Most embedded software are developed in “unsafe” (i.e., not memory-safe) languages, specifically C/C++, because of the low memory footprint, good performance, and the availability of extensive support software.
It is well-known that software developed in unsafe languages are prone to security vulnerabilities, especially memory safety vulnerabilities <cit.>.
Likewise, embedded systems are riddled with security vulnerabilities <cit.>.
The most recent URGENT/11 <cit.> vulnerabilities in VxWorks that affected millions of medical <cit.>, SCADA systems <cit.>, and industrial controllers <cit.> are all because of memory safety (spatial) violations.

Automated memory-safety retrofitting techniques <cit.> based on compile-time instrumentation add significant overhead (both space and runtime) and are inapplicable to resource-constrained embedded systems.
Traditional memory-safe languages, such as Java, also have high overhead.

<cit.> is a memory-safe language that is shown to have comparable performance as native code.
Furthermore,  can easily interoperate with existing unsafe codebases <cit.>, enabling incremental adoption.
team has a special focus on embedded systems <cit.>, and several works <cit.> demonstrate the feasibility of engineering a complete embedded software stack in .
Furthermore,  popularity is rising <cit.>, and it is now adopted in Linux kernel <cit.> and Android <cit.>.
Unfortunately, embedded systems are continuing to be developed in C.
Even the most resourceful organizations, such as Microsoft, continue to develop embedded systems in C, as demonstrated by their recent Azure RTOS <cit.>, a complete embedded RTOS.
Previous works <cit.> investigated the challenges of adopting  for regular software.
However, no work tries to understand factors affecting the use of  for embedded systems development.

In this paper, we perform the first systematic study to holistically understand the issues in using  for developing embedded systems.
Specifically, we explored the following research questions:

* RQ1: Software Support. How effective (quantity and quality) is the existing  software support for embedded system development?

* RQ2: Interoperability of . How well can  interoperate with existing C codebases, and what are its challenges?

* RQ3: Developers Perspective. What challenges do developers face in using  for embedded system development?

We collected a dataset of   embedded software spanning various categories and  SAST tools.
We performed a systematic analysis of our dataset and surveys with  developers to investigate our research questions.
Our study revealed several interesting findings and challenges for using  for embedded systems.
A few interesting findings include the following:
The existing  software support is inadequate.
Embedded crates use more unsafe blocks than non-embedded crates.
The superior type-system of  makes it challenging to engineer interoperable embedded systems code.
Many developers consider the  documentation poorly organized and want the documentation to contain more examples.
In summary, the following are our contributions:

* We perform a systematic study of the  software ecosystem to support the use of  for embedded applications and highlight opportunity areas for adoption (software).

* We develop mechanisms to shed light on automated approaches to convert C-based RTOS to -based RTOS (systems).

* We performed a large-scale developer survey that highlights the challenges for slow adoption of  for embedded applications (human aspects).

* Our findings shed light on challenges in adopting  for embedded systems, insights into open problems, and possible research directions.

§ BACKGROUND

This section provides the necessary background information for the rest of our work.

§.§ Embedded Systems

Embedded systems are designed to perform a designated set of tasks in a resource-constrained environment and on battery-powered devices.
There are several ways to categorize embedded systems.
Previous work <cit.> categorizes embedded systems based on underlying OS.
(a) Type-1 systems have feature-rich general-purpose OS retrofitted for embedded systems.
(b) Type-2 systems or constrained devices <cit.> use specialized embedded OS, which are usually designed as RTOS,  WEMO Light controller <cit.> running FreeRTOS <cit.>.
(c) Type-3 systems do not use OS abstractions and are rarely used in commercial products.
Previous work <cit.> shows consumer IoT devices, such as door knobs and temperature controllers, are mostly Type-2, which we primarily focus on.

Type-2 systems execute on battery-powered and resource-constrained MCU.
These systems have a lot of diversity in terms of hardware (MCU and peripherals) and supported software <cit.>.
For instance, there are 31 different RTOS <cit.>.
To handle this diversity, Type-2 systems have a layered design <cit.> (illustrated in fig:background in Appendix).
Application logic is implemented in tasks managed by an RTOS.

Several libraries provide common functionalities and can be integrated with RTOS,  embedded networks stacks <cit.> provide TCP/IP functionality.
These libraries are specialized for embedded systems and, unlike regular libraries ( libxml), embedded libraries are self-contained and do not have any external dependencies ( libc).

Execution Semantics
The application and all the layers are compiled into a single monolithic binary and flashed onto the on-chip flash memory.
On reset, the contents of the memory are loaded into RAM, and execution starts from a pre-defined address, start or reset address.

In the main function, developers write code to create tasks and register for necessary events, such as interrupts and enter into a continuous loop ( while(1)) to avoid termination.
The tasks get scheduled per the scheduling policy, and handlers get triggered on corresponding events.

is a programming language created by Mozilla to build efficient and safe low-level software <cit.>.
is targeted to achieve performance comparable to programs written in C while avoiding many safety issues in C, including concurrency and memory safety bugs.
This section provides a brief overview of 's safety features.
We recommend the 's official book <cit.> for a comprehensive understanding of these features.

Features and Safety Guarantees
has several features, such as scopes, borrowing rules <cit.>, single ownership <cit.>, and lifetimes <cit.>, which force developers to follow certain practices enabling verification of memory safety properties (mostly) at compile time.
For instance, all read-write variables should be explicitly marked as mutable ( mut).
provides both spatial and temporal memory safety. We provide a discussion of these guarantees in apdx:rustsafetyguarentees

features can be too restrictive in a few cases.
For instance,  requires all global variables to be read-only, disallows mut.
Similarly, we may need to call a C library function, which is also not allowed.
provides unsafe blocks <cit.> to relax these restrictions and enable interaction with external language (or foreign) functions.
Arbitrary regions of code can be enclosed in a unsafe directive, and such code will be permitted certain (otherwise disallowed) actions, such as modifying a mutable global variable, dereferencing a raw pointer, calling an unsafe or external method, etc.

FFI Support
supports easy interaction with functions written in foreign languages through its FFI <cit.>.
Specifically, such functions need to be annotated with special attributes, which enables the  compiler to generate appropriate code respecting the ABI of the target language.

Build System and Package Management
uses an integrated and easy-to-use build system and package manager called Cargo <cit.>, which downloads library packages, called crates, as needed, during builds.
Developers specify the build configuration along with all dependencies in a  file <cit.> — an organized key-value text file.
Rust has an official community package registry called <crates.io> <cit.>, which has (on 30 June 2023) more than 116K crates (libraries) – a 200% increase over the last two years.

no_std Attribute <cit.>
This crate-level attribute avoids linking the entire standard module and results in small binaries.
Embedded software in  should use this attribute to produce a self-contained binary independent of OS abstractions.

§ MOTIVATION

Our analysis (details in apdx:rtosbugstudy) of security vulnerabilities in various RTOS (an important class of embedded software) for the past ten years shows that 59 (54.2%) of them are memory corruption vulnerabilities, spatial or temporal memory issues.

Need for Memory Safety and
It is important to use memory-safe languages to prevent such vulnerabilities.
, a memory-safe language with its superior performance, has been considered best suited for C system codebases.
Also,  has been increasingly adopted by large organizations such as Google <cit.> and Microsoft <cit.> and is used in mainstream operating systems.
also has a specific embedded system focus <cit.>, and many resources exist that encourage the adoption of  to embedded systems. Despite this, many embedded systems are still developed in C.
For instance, Microsoft recently released Azure RTOS <cit.>, an RTOS for embedded systems, which is completely developed in C.
It is important to holistically understand what aspects hinder the adoption of  to embedded systems and its challenges.
Unfortunately, no systematic studies exist.

§ STUDY METHODOLOGY

Our study aims to perform a holistic analysis to understand various aspects regarding using  for embedded systems.
Specifically, we aim to answer the following research questions:

* RQ1: Software Support (subsec:adoptabilityofrust): How good is the software support for developing  based embedded systems?

* RQ2: Interoperability (subsec:rq3interop): How well can  based embedded software interoperate with C codebase?

* RQ3: Developers Perspective (sec:rq4developerspers): What is developers' perspective on using  for embedded systems?

§.§ Embedded Software Dataset

We aim to collect a comprehensive dataset of  embedded software.
As explained in subsec:embeddedsystems, embedded systems are usually
powered by an RTOS, which provides the necessary library and scheduling support for various application components.
We used a two-pronged approach to collect  dataset.

* Crawling <crates.io>: As mentioned in subsec:rustbackground, <crates.io> is the official repository for all  crates ( libraries).
We crawled the entire repository (on ) and got all the crates that could be compiled using the latest version of  (  compiler).
We classify a crate as embedded if it contains certain tags ( and ) and is no_std compatible.

* Well-known Sources:
We crawled the official wiki of -embedded project <cit.> and collected all the embedded crates.
We collected  RTOS from <arewertosyet.com>, which maintains a list of usable  RTOS.
These can be either  wrappers to the underlying C-based implementation (non-native) or could be completely developed (native) in .
We selected representative RTOS in each category by filtering out those that cannot be complied using a stable version of .
We also collected other popular C/C++ based RTOS from <osrtos.com>, which maintains the list of all popular RTOS released to date.
We selected well-maintained ( has build instructions) and compilable RTOS.

Summary We de-duplicated crates from various sources, which resulted in a total of  embedded () and  non-embedded () crates, respectively.
For  RTOS, our analysis resulted in a total of  non-native (),  , RIOT-OS, Zephyr and  native () RTOS,   , RTIC.
Our analysis also resulted in a total of  C/C++ RTOS (). The tab:cratetypes and tab:c2rustblinky (in Appendix) show the summary of our embedded dataset across different categories.

§ LIMITATIONS AND THREATS TO VALIDITY

We acknowledge the following limitations and threats to validity:

* Our findings are based on the analysis of the collected dataset and SAST tools.
The dataset and the tools may not be representative enough. We tried to avoid this by collecting crates and tools from diverse sources.

* We did not analyze all the alerts raised by various SAST tools (subsec:sasttools).
Consequently, using these alerts to assess the quality of crates could be exaggerated because of potential false positives.

* Our RQ2 (subsubsec:rustinteroprocrwc) observations are based on limited scenarios and may not be generalizable.
However, the developer survey (in subsec:devexperienceusingrust) confirmed our findings, reducing the risk.

§ RELATED WORK

We covered the most relevant related works at appropriate places (sec:background, <ref>) in the manuscript. In this section, we cover the other relevant works.

Rust Studies:
Several works <cit.> evaluate various aspects of  from the usability perspective.
Fulton  <cit.> surveyed and interviewed  developers to understand challenges and barriers to adoption.
Similarly, Zeng   <cit.> performed a mixed-methods study of  related forums to identify common challenges and corresponding solutions.
However, other works assess specific aspects of .
Astrauskas  <cit.> focused on identifying common uses of unsafe blocks.
Whereas, Qin  <cit.> focused on identifying challenges in using concurrency constructs and identified common causes of concurrency issues in  code.
Similarly, Mindermann  <cit.> exclusively studied the usability of 's cryptography APIs, providing crucial recommendations for developing these APIs to enhance usability and reduce misuse.

All the existing works focus on regular software. However, embedded systems with a layered architecture and extreme diversity in hardware and software pose unique challenges (subsec:embeddedsystems).
Pinho   <cit.> and Ashmore   <cit.> evaluated the feasibility of using  for safety critical systems (a class of embedded systems).
Specifically, using evaluation criteria for programming languages, aligning with the standards set by RTCA DO-178C, they demonstrated that  meets all the criteria.
Levy  <cit.> focused on using  for kernel development and shared their firsthand experience in creating a kernel for low-power MCU.
They also demonstrated <cit.> the feasibility of using  to engineer common kernel building blocks with only a few unsafe blocks. This paper assesses the applicability and challenges of using  for embedded system software, such as RTOS, by performing a systematic analysis and developer study.

Embedded Systems Vulnerabilities:
Several works <cit.> try to understand vulnerabilities in embedded systems and analyze challenges and possible solutions for effective vulnerability detection.
Several techniques are designed for vulnerability detection in embedded systems and IoT devices.
These techniques use various approaches ranging from static analysis <cit.>, symbolic execution <cit.>, and rehosting-based dynamic analysis <cit.> or fuzzing <cit.>.
In this work, we do not propose any new techniques but rather use state-of-the-art tools (subsec:sasttools) to assess various aspects of  embedded software.

§ CONCLUSIONS

We performed a systematic analysis and a comprehensive (with  developers) survey to understand the current state and challenges in using  for embedded systems development.
Our findings provide insights into the current state and expose open problems and potential improvements that can facilitate easy adoption of  for embedded system development.

§ MCU ANALYZED

We referred to the developer manual of the following MCU to compute the size statistics.

* MC9S12HZ256

* MC9S12XS256

* MC9S12E128

* MC9S12Q128

* MCF52223

* MCF51JM

* MCF51AG

* MSP430G2553I

* MSP430F

* MSP430X33X

* MSP432P401R

* ESP8266EX

* TMPM4GQF15XBG

* TMPM4GRF20XBG

* TMPM4KMFYAFG

* TMPM4MMFYAFG

* AT89C51AC3

* LPC1768

* LPC2148

* nRF52840

* STM32F0

* STM32F1

* PIC16F87XA

* PIC18F2455

* PIC24FJ64GA004

* PIC12F629

* ATtiny13A

* ATtiny25

* ATtiny45

* ATTiny85

* ATTiny2313A

* ATTiny4313

* ATmega328P

§ DEVELOPER SURVEY

§.§ Solicitation Methodology

In order to conduct the developer survey for this study, a systematic solicitation methodology was employed to gather responses from a diverse range of participants in the Rust and embedded systems communities. The solicitation process involved posting the survey on various forums, Discord servers, and mailing lists associated with Rust and relevant RTOS and platforms.

To ensure a broad reach and participation, the survey was prominently shared on platforms such as Rust Reddit, which proved to be a valuable source of responses. Additionally, the survey was disseminated through public mailing lists of prominent RTOS and platforms, including Zephyr, Raspberry Pi, and ChibiOS. These mailing lists provided an opportunity to engage with developers who have expertise and experience in embedded systems development.

§.§ Survey Questions

* How familiar are you with embedded systems programming?

* Not familiar

* Beginner

* Intermediate

* Advanced

* Expert

* Which languages you often use to develop embedded applications? (select all that apply)

* C/ Embedded C/ C++

* Rust

* Python

* Java

* Assembly

* Other

* How many years of experience do you have in embedded programming?

* Less than a year

* 1-3 years

* 3-5 years

* 5-10 years

* More than 10 years

* Have you worked with any Real-Time Operating Systems (RTOSes)?

* Yes, have used them in multiple projects

* Yes, but have not used them extensively

* No

* Which RTOSes have you worked with in the past? (select all that apply)

* FreeRTOS

* Zephyr

* VxWorks

* C/OS

* Other (Text)

* Approximately how many embedded software projects have you developed/contributed to?

* Less than 5

* 5-10

* 10-50

* 50-100

* More than 100

* Have you worked with Rust before?

* Yes

* No

* How many years of experience do you have with programming in Rust?

* Less than a year

* 1-3 years

* 3-5 years

* 5-10 years

* More than 10 years

* Which of the following is not primitive type in Rust?

* i32

* String

* ()

* char

* Given the code snippet:

let mut a: i32 = 1;

Which of the following is correct

* 'a' can be reassigned to a new value of any type later in program

* 'a' can be reassigned to a new value of same type later in program

* 'a' cannot be shadow copied

* Reassigning a value of same type to 'a' later in the program, will throw an error

* Code will not compile properly

* Which of the following statements is true about Rust ownership and borrowing?

* At any given time, you can have either one mutable reference OR any number of immutable references.

* At any given time, you can have one mutable reference AND any number of immutable references

* At any given time, we can have any number of mutable AND immutable references

* At any given time we can have one immutable reference AND any number of mutable references

* At any given time, we can either have one immutable reference OR any number of mutable references.

* How many applications have you developed using Rust programming language (Approximately)?

* 1-5

* 5-20

* 20-50

* More than 50

* How many lines of Rust code have you written (Approximately)

* Less than 100

* 100-1K

* 1K-5K

* 5K-10K

* More than 10K

* Have you ever used rust for embedded development?

* Yes

* No

* Do you currently use Rust for embedded development?

* Yes

* No

* Which programming language are you currently using for embedded development

* C/ C++

* Python

* Java

* Other (Text)

If not using rust for embedded

* Have you ever considered using Rust for embedded systems development?

* Yes

* No

* What are your primary reasons for not considering Rust for embedded systems development? (select all that apply)

* Lack of experience with Rust

* Organization constraints (E.g., My company doesn't allow as the existing frameworks are all in C)

* Not convinced of Rust's benefits for embedded systems

* Lack of community support for Rust in embedded systems

* Other (Please specify)

* What specific concerns do you have about Rust's benefits for embedded systems development? (select all that apply)

* Performance concerns

* Lack of support for specific hardware platforms

* More tedious development process

* Difficulty integrating with existing codebases

* Other (Please specify)

* Why don’t you use Rust for embedded systems? (select all that apply)

* Organization constraints (E.g., My company doesn’t allow as the existing frameworks are all in C)

* Steep Learning Curve

* Lack of community support for Rust in embedded systems

* Other (Please specify)

* Why are you not using Rust? (select all that apply)

* Organization constraints (E.g., My company doesn’t allow as the existing frameworks are all in C)

* Steep Learning Curve

* Lack of community support for Rust in embedded systems

* Other (Please specify)

* Are you interested in learning Rust for embedded systems?

* Yes

* No

* What benefits do you perceive from your current programming language for embedded systems development compared to Rust?

* Better library and tool support

* Familiarity with language/ Easier to learn and use

* Portability

* Better performance

* Low-level control over hardware

* Other (Please specify)

* How important is memory safety in embedded systems development to you?

* Very important

* Somewhat important

* Not very important

* Not at all important

* How do you ensure memory safety in your embedded programs with the language you use?

* Manual memory management

* Use of static analysis tools

* Use of run-time checks or garbage collection

* Other (Please specify)

* How long have you been using Rust for embedded systems?

* Less than 6 months

* 6 months to 1 year

* 1 year to 2 years

* More than 2 years

* Lines of code in embedded programming using Rust(approx)?

* Less than 100

* 100-1K

* 1K-5K

* 5K-10K

* More than 10K

* How was their learning/coding experience for developing embedded systems with Rust?

* Very easy

* Somewhat easy

* Moderate difficulty

* Very difficult

* What motivates you to learn Rust for Embedded systems? (select all that apply)

* Better performance

* Safety and reliability

* Familiarity with Rust

* Other (Please specify)

* Is rust documentation helpful for embedded development?

* It is helpful

* It is somewhat helpful

* Technicalities are missing

* Less examples

* Other (Please specify)

* What can make them more helpful for developers (select all of that apply)?

* Better organization of information

* Improved search functionality

* Other (Please specify)

* Do you often have to refer to external documentation to find solutions for issues?

* Yes, frequently

* Yes, occasionally

* Rarely

* How familiar are you with embedded systems programming?

* Not familiar

* Beginner

* Intermediate

* Advanced

* Expert

* Which languages you often use to develop embedded applications? (select all that apply)

* C/ Embedded C/ C++

* Rust

* Python

* Never

* Not sure

* Which sources have helped you in your rust embedded journey? (select all that apply)

* Official Rust documentation

* Third-party blogs and tutorials

* Online forums and communities

* Other (Please specify)

* How do you find the support for Rust in the embedded systems community?

* Excellent

* Good

* Average

* Poor

* Very poor

* Have you written user level embedded applications in rust?

* Yes

* No

* Do you prefer writing user level embedded applications in rust?

* Yes, always

* Yes, sometimes

* No, prefer other languages

* Mention the other programming language for embedded user applications and the possible reasons? (select all that apply)

* C - widely used, mature, efficient

* C++ - object-oriented, high-performance

* Python - easy to learn, rapid development

* Java - platform-independent, easy to use

* Other (Please specify)

* Why not Rust for embedded system's application development? (select all that apply)

* Lack of resources (eg library support for the hardware)

* Performance issues

* Other programming languages better suited

* Other (please specify)

* Have you written kernel level code using rust for embedded systems?

* Yes

* No

* Do you prefer writing kernel level code for embedded systems in rust?

* Yes, always

* Yes, sometimes

* No, prefer other languages

* What programming languages do you use for embedded kernel development? (select all that apply)

* C

* Embedded C

* C++

* Assembly

* Other (Please specify)

* Why not Rust for embedded system's kernel development? (select all that apply)

* Technical difficulties (difficulty in translating the embedded kernel concepts)

* Steep learning curve

* Limited library and tool support

* Other (Please specify)

* How satisfied are you with the availability of resources and crates provided by Rust for embedded systems, such as hardware interaction and drivers?

* Very satisfied

* Somewhat satisfied

* Neutral

* Somewhat dissatisfied

* Very dissatisfied

* Is rust toolchain for embedded development easy to use?

* Yes, very easy

* Somewhat easy

* Moderately difficult

* Very difficult

* What makes it easier for you to use Rust toolchain for embedded development compared to other programming languages? (select all that apply)

* Better documentation

* More intuitive tools

* Wider community support

* Better integration with hardware

* Other (Please specify)

* Could you help us know the possible reasons of difficulty in use?

* Poor documentation

* Incomplete or buggy tools

* Lack of community support

* Difficulty integrating with hardware

* Other (Please specify)

* Do you feel that there are enough resources or crates in Rust to deal with embedded systems, such as hardware interaction, drivers, etc.?

* Yes, there are plenty of resources available

* No, there are not enough resources available

* I am not sure

* How often do you encounter compatibility issues with libraries when using Rust for embedded systems?

* Very frequently

* Occasionally

* Rarely

* Never

* Are you familiar with Rust's interoperability with C?

* Yes

* Somewhat

* No

* Do you feel interoperability would help you code better in Rust

* Yes

* No

* Have you ever used Rust and C together in a project?

* Yes

* No

* In what scenarios have you used Rust and C together? (check all that apply)

* Calling C code from Rust

* Calling Rust code from C

* Other (Please specify)

* What challenges have you faced while using Rust and C together? (check all that apply)

* Managing memory allocation and deallocation between Rust and C

* Handling different data types between Rust and C

* Debugging issues with interoperation between Rust and C

* None

* Other (Please specify)

* How do you perceive the impact of Rust's interoperability with C on improving the safety of existing C codebases?

* Yes, it significantly helps to make the existing C codebases safer with ease.

* Somewhat, it helps in building safer codebases, but requires significant effort.

* No, it doesn't improve the safety of existing C codebases

* Which IDE do you prefer for Rust programming language?

* Visual Studio Code/Rust analyzer

* IntelliJ Rust

* Others (Please specify)

* How useful are rust compiler warning/error messages?

* Not useful

* Slightly useful

* Moderately useful

* Very useful

* Extremely useful

* Do you feel the chosen programming language support testing of functionalities in a developer-friendly manner (Is it easy to debug the programs)?

* Yes, it is very easy

* It is somewhat easy

* It is moderately difficult

* It is very difficult

* Not sure

* How much time do you spend debugging your Rust embedded applications?

* Less than 25% of development time

* 25%-50% of development time

* 50%-75% of development time

* More than 75% of development time

* Have you encountered any performance issues when using Rust for embedded systems?

* Yes

* No

* I am not sure

* Have you ever evaluated the performance of Rust compared to the other programming languages common in the field of embedded development?

* Yes, and Rust outperformed other languages.

* Yes, and Rust performed similarly to other languages.

* Yes, but other languages outperformed Rust.

* No, I have not evaluated the performance of Rust compared to other languages in embedded development.

* How likely are you to recommend rust to other developers for use in embedded systems?

* Very likely

* Somewhat likely

* Neutral

* Somewhat unlikely

* Very unlikely

* Have you ever used any other programming language before Rust in embedded system development?

* Yes

* No

* Have you noticed any significant improvements in development time or code quality since switching to Rust for embedded systems?

* Yes, significant improvements

* Some improvements

* No noticable improvements

* It has actually slowed down development

* Have you encountered any performance issues when using Rust for embedded systems ?

* Yes

* No

* I am not sure

* Compared to the other programming languages you have used for embedded programming, how well does Rust integrate with hardware?

* Much better integration than other languages

* Somewhat better integration than other languages

* About the same level of integration as other languages

* Worse integration than other languages

* Is there anything else you would like to share or any other thoughts you have regarding Rust for embedded programming?

§ ADDITIONAL BACKGROUND

§.§ Bug Study

To understand common security issues in embedded systems, we collected publicly reported vulnerabilities from the CVE database <cit.> across various RTOS — the important component of type-2 systems.

We focused on vulnerabilities with the necessary technical details to understand the root cause; this resulted in a total of 109 vulnerabilities.
We manually categorized each of them according to their root cause, tab:bugsinrtos shows the categorization.
There are 25 (22.9%) application-specific vulnerabilities that any programming language cannot prevent.
However, there are 59 (54.2%) memory corruption vulnerabilities, spatial or temporal memory issues.

§.§  Safety Guarantees

Spatial Safety. lst:rustspatialsafety shows an example where spatial safety issues (out-of-bounds access) are detected in  both at compile time and run time.
At Line 12, the variable x can be greater than 2, potentially accessing out-of-bounds of the array a.
Each array has an associated length, and  inserts checks to verify that all indexes into an array are valid.
also prevents accessing uninitialized variables (Line 18 in lst:rustspatialsafety) by powerful compile-time analysis to check that a variable is always initialized before access.
uses its type system and runtime checks to detect null-ptr dereferences.

Temporal Safety. lst:rusttemporarlsafety shows a snippet demonstrating  ownership features and how it prevents temporal issues, specifically use-after-free.
's ownership feature requires that every object has only one owner.
An object will be released (or dropped) when the owner goes out of scope.
Ownership of an object will be transferred to another variable on assignments. from the owner.
For instance, x = y, the ownership of the object pointed by y will be transferred to x.
Also,  allows borrowing, wherein a variable can have a read-only reference to an object (without owning it), Line 4 and 8 in lst:rusttemporarlsafety.
The borrow checker ensures that the lifetime of all references is more than that of the objects they point to and thus prevents use-after-free.
In lst:rusttemporarlsafety, z can be a reference (Line 8) to object O2 (allocated at Line 6), whose owner is x.
The object O2 will freed after the if at Line 10 because the owner (x) goes out-of-scope.
But, z can hold a reference to O2, which we try to access at Line 13 (a potential use-after-free).
The borrow checker detects and throws a compiler error as the lifetime of O2 (referenced by z) is shorter, ends at Line 10.

[xleftmargin=0.5cm, escapeinside=||, fontsize=, linenos]rust
use std::io;
fn main()
// read-only
let a = [1, 2, 3];
// read-write (mutable)
let mut il = String::new();
.read_line(   mut il)
.expect("Failed to read line");
let x: usize = il.trim().parse().expect("Invalid");
// Potential out-of-bounds
println!(":?", a[x]); ||||
let b;
if x > 1
b = 4;

// Uninitialized variable access.
println!("Value of b: ", b); ||||

Example demonstrating how  prevents spatial safety issues () at compile time () and run time ().

[xleftmargin=0.5cm, escapeinside=||, fontsize=, linenos]rust
use std::io;
fn main()
let y = "HELLO".to_string(); // O1
let mut z =    y;
if (...)
let x = "Hello".to_string(); // O2
// z is a reference to O2 owned by x
z =    x;
// x goes out of scope, and O2 gets dropped.

// z might be referencing O2 (a freed object)
// Potential use-after-free
println!("", z); ||||

Snippet demonstrating how  prevents temporal safety issues (use-after-free).

§  COMPILATION FAILURES

Refer tab:qratesfailed for categorization of  tool failures.

§ BUGS EXAMPLES

§  INTEROPERABILITY

§.§ Incompatible FFI Types

The superior  type system has several types that are not supported in C. For instance, vec <cit.>, one of the most commonly used  types, is not supported in C.
Consequently, functions ( sum_vec in lst:incompatiblerustfunction) accepting parameters of these unsupported C types cannot be invoked from C.
Although  cbindgen automates the creation of C declarations, it cannot handle these unsupported C types.
Developers need to write certain wrapper functions that convert C-supported types into appropriate  types ( wrapper_sum_vec in lst:incompatiblerustfunction).

§.§.§ Calling C function from  ( $\rightarrow$ C)

Consider the simple C function add as shown in lst:ccodeadd.
We need to follow the below steps to invoke add from  code:

* First, we need to provide the FFI signature of the function add (as shown in lst:callingcfromrust), so that  compiler knows that the function is implemented in a foreign language. Developers can use bindgen <cit.> tool, which automatically generates FFI signatures from C header files.

* Second, we should link with the library containing the function's implementation to get the final executable.

The fig:bindgenfig illustrates these steps.

§.§.§ Calling  function from C (C $\rightarrow$ )

Developers need to follow the below steps to call a  function from C:

* The  function should be annotated to allow external calls.
Specifically, as shown in lst:rustfunctioncallableinc, it should be annotated with pub unsafe extern "C" and no_mangle (to avoid name mangling and enable linking).
Also, developers need to compile the  code into a static library ( ).

* In the C domain, the  function should be declared as extern (lst:ccodewhichrust), and the  library should be linked to get the final executable.
Developers can use cbindgen <cit.> to generate C declarations from external  functions ( pub extern "C").


# Explicit formulae for generalized Stirling and Eulerian numbers

Josef Küstner∗ Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-
Platz 1, A-1090 Vienna, Austria<EMAIL_ADDRESS>
###### Abstract.

In this article we generalize the $q$-difference operator due to Carlitz in
order to derive explicit sum formulae for several extensions of Stirling
numbers of the second kind, including complete homogeneous symmetric
functions, complementary symmetric functions, $r$-Whitney numbers and elliptic
analogues of rook, Stirling and Lah numbers. Furthermore, we generalize
Carlitz’ $q$-Eulerian numbers to a Lagrange polynomial extension. We define
them by generalizing Worpitzky’s identity appropriately, and derive a
recursion and an explicit sum formulae. Special cases include $r$-Whitney
Eulerian numbers and elliptic Eulerian numbers.

###### Key words and phrases:

Stirling numbers, rook numbers, Lah numbers, Eulerian numbers, difference
operator, $q$-analogues, elliptic hypergeometric series

###### 2010 Mathematics Subject Classification:

Primary 05A10; Secondary 05A30, 05E05, 05A15, 11B65, 11B83, 11B73, 33E05

∗ The author was partially supported by Austrian Science Fund FWF
10.55776/P32305.

##  1\. Introduction

The classical _Stirling numbers of the second kind_ , $S(n,k)$, count set
partitions of an $n$-elementary set into $k$ non-empty sets. They fulfil the
recurrence relation

$\displaystyle S(n,k)$ $\displaystyle=0,\qquad\text{for $k<0$ or $k>n$},$
(1.1a) $\displaystyle S(0,0)$ $\displaystyle=1,$ (1.1b) and, for $k\geq 0$,
$\displaystyle S(n+1,k)$ $\displaystyle=S(n,k-1)+kS(n,k).$ (1.1c)

Given a nonnegative integer $n$ and a variable $z$, we define the
corresponding _falling factorial_ as

$z\downarrow_{n}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}z(z-1)\cdots(z-n+1)$

for $n>0$ and $z\downarrow_{0}=1$. Then, $S(n,k)$ are the connection
coefficients in

$\displaystyle z^{n}=\sum_{k=0}^{n}S(n,k)z\downarrow_{k}.$ (1.2)

Let $E_{z}$ be the shift operator that shifts a polynomial $p(z)$ by
$E_{z}p(z)=p(z+1)$ and $\Delta$ be the difference operator $\Delta=E_{z}-I$.
Then it is a classical result that we can derive an explicit formula for
$S(n,k)$ from (1.2) by applying the $k$-th power of the difference operator
$\Delta$ to both sides of the equation to obtain

$\displaystyle
S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}.$ (1.3)

We recommend [10, 25] for further reading on the theory of difference
operators.

Following Carlitz [5, 6], we can define _$q$ -Stirling numbers of the second
kind_, $S_{q}(n,k)$, by

$[z]_{q}^{n}=\sum_{k=0}^{n}q^{\binom{k}{2}}S_{q}(n,k)[z]_{q}[z-1]_{q}\dots[z-k+1]_{q},$
(1.4)

where

$[z]_{q}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\frac{1-q^{z}}{1-q}$
(1.5)

is the $q$-number of $z$. We define _$q$ -falling factorials_ by

$z\downarrow_{n}^{q}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}z(z-[1]_{q})\cdots(z-[n-1]_{q}),\text{
for $n>0$,}\quad z\downarrow_{0}^{q}=1,$ (1.6)

and use the identity

$[m]_{q}-[n]_{q}=[m-n]_{q}q^{n}$

to reformulate equation (1.4) as

$[z]_{q}^{n}=\sum_{k=0}^{n}S_{q}(n,k)[z]_{q}\downarrow_{k}^{q}.$ (1.7)

One can derive from this relation that $S_{q}(n,k)$ satisfies

$\displaystyle S_{q}(n,k)$ $\displaystyle=0,\qquad\text{for $k<0$ or $k>n$},$
(1.8a) $\displaystyle S_{q}(0,0)$ $\displaystyle=1,$ (1.8b) and, for $k\geq
0$, $\displaystyle S_{q}(n+1,k)$
$\displaystyle=S_{q}(n,k-1)+[k]_{q}S_{q}(n,k).$ (1.8c)

In order to derive an explicit sum formula for these numbers, Carlitz
generalizes the difference operator $\Delta$ by the recursive definition

$\displaystyle\Delta_{q}p(z)$ $\displaystyle=p(z+1)-p(z),$ (1.9a)
$\displaystyle\Delta_{q}^{n+1}p(z)$
$\displaystyle=\Delta_{q}^{n}p(z+1)-q^{n}\Delta_{q}^{n}p(z)$ (1.9b) for $n>0$,
or explicitly by $\displaystyle\Delta_{q}^{n}$
$\displaystyle=\prod_{i=1}^{n}(E_{z}-q^{n-i}).$ (1.9c)

Applying $\Delta_{q}^{k}$ to both sides of $\eqref{eqn:qstirling_con}$,
Carlitz derives ([6, Equation (3.3)])

$\displaystyle
S_{q}(n,k)=\frac{q^{-\binom{k}{2}}}{[k]_{q}!}\sum_{j=0}^{k}(-1)^{j}q^{\binom{j}{2}}{\begin{bmatrix}k\\\
j\end{bmatrix}}_{q}[k-j]_{q}^{n},$ (1.10)

where the _$q$ -factorials_ are defined by

$[n]_{q}!\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\prod_{i=1}^{n}[i]_{q}\quad\text{for
$n>0$ and}\quad[0]_{q}!=1,$ (1.11)

and the $q$-binomial coefficient is defined as

${\begin{bmatrix}n\\\
k\end{bmatrix}}_{q}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\frac{[n]_{q}!}{[k]_{q}![n-k]_{q}!}.$
(1.12)

In [15], Kereskényiné Balogh and Schlosser study an elliptic analogue of
Carlitz’ $q$-Stirling numbers of the second kind. We introduce _elliptic
falling factorials_ by the definition

$z\downarrow_{n}^{a,b;q,p}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}z(z-[1]_{a,b;q,p})\cdots(z-[n-1]_{a,b;q,p}),$

and $z\downarrow_{0}^{a,b;q,p}=1$, where $[z]_{a,b;q,p}$ is the elliptic
number of $z$, which will be defined in the next section. Then, the _elliptic
Stirling numbers of the second kind_ , $S_{a,b;q,p}(n,k)$, can be defined by
the relation

$[z]_{a,b;q,p}^{n}=\sum_{k=0}^{n}S_{a,b;q,p}(n,k)[z]_{a,b;q,p}\downarrow_{k}^{a,b;q,p}.$
(1.13)

In [32], Schlosser and Yoo study elliptic Stirling numbers of the second kind
in the context of rook theory. They ask for a generalization of the explicit
sum formula (1.10) to $S_{a,b;q,p}(n,k)$ and work out special cases for $0\leq
k\leq 3$. Furthermore, the authors suggest using an appropriate extension of
the $q$-difference operator $\Delta_{q}$ to achieve this goal.

In this article, we deduce an explicit formula for $S_{a,b;q,p}(n,k)$
analogous to (1.10) by using the fact that elliptic Stirling numbers of the
second kind are a specialization of the complete homogeneous symmetric
functions $h_{k}$. An explicit sum-formula for $h_{k}$ is well-known, and we
obtain a formula for $S_{a,b;q,p}(n,k)$ as a special case. Furthermore, we
will generalize Carlitz’ $q$-difference operator appropriately to deduce a new
operator proof of the formula for $h_{k}$. Special cases also contain Stirling
numbers of type $B$ and $(q,r)$-Whitney numbers of the second kind.

We show that this operator proof can be generalized to prove explicit sum
formulae for more general polynomials, including elliptic rook numbers and Lah
numbers.

Another very interesting number sequence linked to Stirling numbers is the
Eulerian number sequence. They were also generalized to the $q$-case by
Carlitz [7] but an elliptic extension of these numbers has not been defined so
far. In Section 6 we study a generalization of Eulerian numbers similarly to
the generalization of Stirling numbers of the second kind and derive explicit
summation formulae. As special cases, we obtain elliptic Eulerian numbers and
a $q$-analogue of $r$-Whitney Eulerian numbers.

##  2\. Elliptic Stirling numbers

In the past 15 years, several authors have studied elliptic function analogues
of $q$-analogues of combinatorial objects and special combinatorial numbers
[1, 2, 3, 17, 27, 28, 29, 32]. This has led to interesting extensions of
weight functions assigned to several combinatorial models like lattice paths,
lozenge tilings or rook placements. This study is closely connected to the
theory of elliptic hypergeometric series, which naturally extends the theory
of basic hypergeometric series. An introduction to elliptic hypergeometric
series can be found in [13, Chapter 11], [16] and [24]. In [15] and [32],
elliptic analogues of Stirling numbers, Lah numbers, and rook numbers were
introduced. A main goal of this article is to find explicit summation formulae
of these analogues. In this section, we will recall the most important
notations and identities for the theory of elliptic functions.

We begin by defining the _modified Jacobi theta function_ as

$\theta(x;p)\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\prod_{j\geq
0}\left((1-p^{j}x)(1-\frac{p^{j+1}}{x})\right),\quad\theta(x_{1},\dots,x_{\ell};p)=\prod_{k=1}^{\ell}\theta(x_{k};p),$

where $x,x_{1},\dots,x_{\ell}\neq 0$ and $|p|<1$. The modified Jacobi theta
function satisfies some fundamental relations [34, cf. p. 451, Example 5],
like the inversion formula

$\displaystyle\theta(x;p)=-x\theta(1/x;p),$ (2.1a) the quasi-periodicity
relation $\displaystyle\theta(px;p)=-\frac{1}{x}\theta(x;p),$ (2.1b) and the
three-term identity
$\displaystyle\theta(xy,x/y,uz,u/z;p)=\theta(uy,u/y,xz,x/z;p)+\frac{x}{z}\theta(zy,z/y,ux,u/x;p).$
(2.1c)

An _elliptic function_ is a function of a complex variable that is meromorphic
and doubly periodic, and it is well known that elliptic functions can be
written as quotients of modified Jacobi theta functions [24, 34].

An example, which we will use throughout this article, is the _elliptic
number_ of a complex number $z$,

$\displaystyle[z]_{a,b;q,p}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\frac{\theta(q^{z},aq^{z},bq,aq/b;p)}{\theta(q,aq,bq^{z},aq^{z}/b;p)}.$
(2.2)

Here, $a$ and $b$ are two additional parameters.111This definition follows the
definition in [30] and corresponds to the definition in [32] subject to the
substitution $b\mapsto bq^{-1}$. The elliptic number is a generalization of
the $q$-number: Taking the limit $p\rightarrow 0$, then $a\rightarrow 0$ and
then $b\rightarrow 0$, one recovers the $q$-analogue $[z]_{q}$.

The function $[z]_{a,b;q,p}$ is elliptic in $a$, $b$, $q$ and $q^{z}$ each
with the same multiplicative period $p$ (see also [32, Remark 4]).

We also define the elliptic weight

$W_{a,b;q,p}(k)\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\frac{\theta(aq^{2k+1},b,bq,a/b,aq/b;p)}{\theta(aq,bq^{k},bq^{k+1},aq^{k}/b,aq^{k+1}/b;p)}q^{k},$
(2.3)

which is again an elliptic function and reduces to $q^{k}$ by taking the limit
$p\rightarrow 0$, $a\rightarrow 0$ and $b\rightarrow 0$ (in this order).

As an application of the three-term identity (2.1c) we obtain the following
factorization for the elliptic number for complex values $y$ and $z$ [32,
Equation (3.8b)]:

$\displaystyle[y+z]_{a,b;q,p}=[y]_{a,b;q,p}+W_{a,b;q,p}(y)[z]_{aq^{2y},bq^{y};q,p}.$
(2.4)

In this article we will also use the relations ([32, Equation (3.3b)])

$W_{a,b;q,p}(k+j)=W_{a,b;q,p}(j)W_{aq^{2j},bq^{j};q,p}(k)$ (2.5)

and ([17, Corollary 4.3])

$[-k]_{a,b;q,p}=-W_{a,b;q,p}(-1)[k]_{1/a,b/a;q,p}.$ (2.6)

Now we are ready to define elliptic Stirling numbers of the second kind.
Recall the definition of _elliptic falling factorials_

$z\downarrow_{n}^{a,b;q,p}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}z(z-[1]_{a,b;q,p})\cdots(z-[n-1]_{a,b;q,p})\quad\text{and}\quad
z\downarrow_{0}^{a,b;q,p}=1.$

and the definition of _elliptic Stirling numbers of the second kind_ ,
$S_{a,b;q,p}(n,k)$,

$[z]_{a,b;q,p}^{n}=\sum_{k=0}^{n}S_{a,b;q,p}(n,k)[z]_{a,b;q,p}\downarrow_{k}^{a,b;q,p}.$
(2.7)

Note that each factor $[z]_{a,b;q,p}-[j]_{a,b;q,p}$ in the elliptic falling
factorial of $[z]_{a,b;q,p}$ factorizes to

$\displaystyle[z]_{a,b;q,p}-[j]_{a,b;q,p}=W_{a,b;q,p}(j)[z-j]_{aq^{2j},bq^{j};q,p}$

by (2.4).222 This definition is slightly different to the definition in [15].
The original definition is obtained by multiplying $S_{a,b;q,p}(n,k)$ with
$\prod_{j=0}^{k-1}W_{a,b;q,p}(j)$, but it turns out that it is convenient to
stick to the definition (1.13).

From (1.13) one can deduce the following recurrence relation for
$S_{a,b;q,p}(n,k)$:

$\displaystyle S_{a,b;q,p}(n,k)$ $\displaystyle=0,\qquad\text{for $k<0$ or
$k>n$},$ (2.8a) $\displaystyle S_{a,b;q,p}(0,0)$ $\displaystyle=1,$ (2.8b)
and, for $k\geq 0$, $\displaystyle S_{a,b;q,p}(n+1,k)$
$\displaystyle=S_{a,b;q,p}(n,k-1)+[k]_{a,b;q,p}S_{a,b;q,p}(n,k).$ (2.8c)

In the next section, we will focus on a generalization of elliptic Stirling
numbers, the complete homogeneous symmetric functions, before we return to the
elliptic case.

##  3\. Complete homogeneous symmetric functions

Complete homogeneous symmetric functions,
$h_{k}(a_{0},a_{1},a_{2},\dots,a_{n})$, are defined by

$h_{k}(a_{0},a_{1},a_{2},\dots,a_{n})=\sum_{0\leq j_{1}\leq j_{2}\leq\dots\leq
j_{k}\leq n}a_{j_{1}}a_{j_{2}}\dots a_{j_{k}}.$

We introduce a generalization of falling factorials and factorials for a
series of variables $\textbf{a}=a_{0},a_{1},a_{2},\dots$ (following [26]) as

$z\downarrow_{0}^{\textbf{a}}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}1,\quad
z\downarrow_{n}^{\textbf{a}}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\prod_{i=0}^{n-1}(z-a_{i})\quad\text{and}\quad{a}_{n}!\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}a_{n}\downarrow_{n}^{\textbf{a}}.$
(3.1)

It is a well-known fact that $h_{k}$ satisfies the relation

$\displaystyle
z^{n}=\sum_{k=0}^{n}h_{n-k}(a_{0},a_{1},\dots,a_{k})z\downarrow_{k}^{\textbf{a}}.$
(3.2)

This equation appears, for example, in [26, Theorem 2.2] and [12, p. 208]. By
setting $a_{i}=[i]_{q}$ for all $i\geq 0$ and $z=[z]_{q}$ in this equation, we
obtain the generating function (1.7) of Carlitz’ $q$-Stirling numbers of the
second kind. This leads to the specialization

$S_{q}(n,k)=h_{n-k}([0]_{q},[1]_{q},\dots,[k]_{q}),$

which is also well known and appeared, for example, recently in [26].

By setting $a_{i}=[i]_{a,b;q,p}$ for all $i$ and $z=[z]_{a,b;q,p}$ in (3.2),
we obtain the generating function for elliptic Stirling numbers of the second
kind (1.13), therefore

$\displaystyle
S_{a,b;q,p}(n,k)=h_{n-k}([0]_{a,b;q,p},[1]_{a,b;q,p},\dots,[k]_{a,b;q,p}).$
(3.3)

By multiplying both sides of (3.2) with $z$ it follows that

$\displaystyle z^{n+1}$
$\displaystyle=\sum_{k=0}^{n}h_{n-k}(a_{0},a_{1},\dots,a_{k})z\downarrow_{k}^{\textbf{a}}(z-a_{k}+a_{k})$
$\displaystyle=\sum_{k=0}^{n}h_{n-k}(a_{0},a_{1},\dots,a_{k})z\downarrow_{k+1}^{\textbf{a}}+\sum_{k=0}^{n}a_{k}h_{n-k}(a_{0},a_{1},\dots,a_{k})z\downarrow_{k}^{\textbf{a}}$
$\displaystyle=\sum_{k=0}^{n+1}\big{(}h_{n-k+1}(a_{0},a_{1},\dots,a_{k-1})+a_{k}h_{n-k}(a_{0},a_{1},\dots,a_{k})\big{)}z\downarrow_{k}^{\textbf{a}}$

and we can derive the recursion

$\displaystyle h_{n-k}(a_{0},a_{1},\dots,a_{k})$ $\displaystyle=0\quad\text{
for $k<0$ or $k>n$},$ (3.4a) $\displaystyle h_{0}(a_{0})$ $\displaystyle=1$
(3.4b) and, for $k\geq 0$, $\displaystyle h_{n-k+1}(a_{0},a_{1},\dots,a_{k})$
$\displaystyle=h_{n-k+1}(a_{0},a_{1},\dots,a_{k-1})+a_{k}h_{n-k}(a_{0},a_{1},\dots,a_{k})$
(3.4c)

analogous to (1.1), (1.8) and (2.8).

The complete homogeneous symmetric functions can be computed by the following
explicit formula (cf. [14], where this formula was obtained as a special case
of a Schur function identity, or [33, Exercise 7.4]).

######  Theorem 3.1.

Let $n,k$ be nonnegative integers, $a_{0},a_{1},\dots,a_{k}$ be variables and
$h_{n}(a_{0},\dots,a_{k})$ the $n$-th complete homogeneous symmetric function
in $k+1$ variables. We then have

$h_{n}(a_{0},\dots,a_{k})=\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\
i\neq j\end{subarray}}^{k}(a_{j}-a_{i})^{-1}\Big{)}a_{j}^{n+k}.$ (3.5)

By setting $a_{i}=i$, respectively $a_{i}=[i]_{q}$, for all $i$ and doing some
small manipulations, we recover the sum-formulae for $S(n,k)$ in (1.3) and
$S_{q}(n,k)$ in (1.10), respectively.

To complete the task of finding an explicit formula for $S_{a,b;q,p}(n,k)$,
described by Schlosser and Yoo [32], we set $a_{i}=[i]_{a,b;q,p}$, change the
indices according to (3.3) and reverse the order of summation, to obtain the
following corollary.

######  Corollary 3.2.

Let $n,k$ be nonnegative integers, $[n]_{a,b;q,p}$ be the elliptic number of
$n$ and $S_{a,b;q,p}(n,k)$ be the elliptic Stirling numbers of the second kind
defined by (1.13). We then have

$S_{a,b;q,p}(n,k)=\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\ i\neq
k-j\end{subarray}}^{k}(W_{a,b;q,p}(i)[k-j-i]_{aq^{2i},bq^{i};q,p})^{-1}\Big{)}[k-j]_{a,b;q,p}^{n}.$
(3.6)

This formula reduces to (1.10) by taking the limits $p\rightarrow 0$, then
$a\rightarrow 0$ and then $b\rightarrow 0$.

######  Remark 3.3.

In contrast to (1.3) and (1.10) it seems that there appears no binomial
coefficient in the sum-formula for $h_{k}$ (3.5), but we can define an
a-binomial coefficient for $0\leq k\leq n$ as

${\begin{bmatrix}n\\\
k\end{bmatrix}}_{\textbf{a}}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}(-1)^{n-k}\frac{a_{n}!}{\prod_{\begin{subarray}{c}i=0\\\
i\neq
k\end{subarray}}^{n}(a_{k}-a_{i})}=(-1)^{n-k+1}\prod_{\begin{subarray}{c}i=0\\\
i\neq k\end{subarray}}^{n-1}\frac{a_{n}-a_{i}}{a_{k}-a_{i}}$

From (3.5) we obtain

$h_{n}(a_{0},\dots,a_{k})=\frac{1}{a_{k}!}\sum_{j=0}^{k}(-1)^{k-j}{\begin{bmatrix}k\\\
j\end{bmatrix}}_{\textbf{a}}a_{j}^{n+k}.$ (3.7)

This binomial coefficient fulfils the recurrence relation

${\begin{bmatrix}n+1\\\
k\end{bmatrix}}_{\textbf{a}}=\prod_{j=0}^{n-1}\frac{a_{n+1}-a_{j+1}}{a_{n}-a_{j}}{\begin{bmatrix}n\\\
k\end{bmatrix}}_{\textbf{a}}+E_{\textbf{a}}{\begin{bmatrix}n\\\
k-1\end{bmatrix}}_{\textbf{a}},$ (3.8)

for $0<k<n+1$, where $E_{\textbf{a}}$ is an operator that maps all $a_{i}$ to
$a_{i+1}$. However, we chose not to use this notation in this work.

##  4\. A generalized difference operator

We consider functions $f(z;\textbf{x})$ in the variables $z$ and
$\textbf{x}=x_{0},x_{1},x_{2}\dots$ and recall the generalized notation for
the falling factorial and the factorial according to $z$ and x as follows:

$z\downarrow_{0}^{\textbf{x}}=1,\quad
z\downarrow_{n}^{\textbf{x}}=\prod_{i=0}^{n-1}(z-x_{i})\quad\text{for $n>0$
and}\quad{x}_{n}!=x_{n}\downarrow_{n}^{\textbf{x}}.$ (4.1)

We define the _shift operator_ $E_{z,\textbf{x}}$ as
$E_{z,\textbf{x}}f(z;x_{0},x_{1},x_{2}\dots)=f(z+1;x_{1},x_{2},x_{3}\dots)$.
For example,

$E_{z,\textbf{x}}\frac{z-x_{1}+a_{2}}{x_{k}-x_{2}}=\frac{z+1-x_{2}+a_{2}}{x_{k+1}-x_{3}}.$

The _difference operator_ $\Delta_{\textbf{x}}^{n}$ is recursively defined by

$\displaystyle\Delta_{\textbf{x}}f(z,\textbf{x})$
$\displaystyle=E_{z,\textbf{x}}f(z,\textbf{x})-f(z,\textbf{x}),$ (4.2a)
$\displaystyle\Delta_{\textbf{x}}^{n+1}f(z,\textbf{x})$
$\displaystyle=E_{z,\textbf{x}}\Delta_{\textbf{x}}^{n}f(z,\textbf{x})-\Big{(}\prod_{j=0}^{n-1}\frac{x_{n+1}-x_{j+1}}{x_{n}-x_{j}}\Big{)}\Delta_{\textbf{x}}^{n}f(z,\textbf{x})$
(4.2b) for $n>0$, or explicitly by $\displaystyle\Delta_{\textbf{x}}^{n}$
$\displaystyle=\prod_{i=0}^{n-1}\Big{(}E_{z,\textbf{x}}-\prod_{j=0}^{n-i-2}\frac{x_{n-i}-x_{j+1}}{x_{n-i-1}-x_{j}}\Big{)}.$
(4.2c)

It follows by induction on $n$ (and (3.8)) that

$\displaystyle\Delta_{\textbf{x}}^{n}=\sum_{k=0}^{n}{x}_{n}!\Big{(}\prod_{\begin{subarray}{c}i=0\\\
i\neq k\end{subarray}}^{n}(x_{k}-x_{i})^{-1}\Big{)}E_{z,\textbf{x}}^{k}.$
(4.3)

We are now ready to prove the explicit formula for
$h_{n}(a_{0},a_{1},\dots,a_{k})$.

###### Proof of Theorem 3.1.

Let $C_{k}$ be the connection coefficients in

$f(z)=\sum_{k=0}^{n}C_{k}a_{z}\downarrow_{k}^{\textbf{a}},$ (4.4)

where $f(z)$ is a polynomial in $a_{z}$ of degree at most $n$ and independent
of the variables x. Then the $C_{k}$ are independent of $z$ and x. We apply
$\Delta_{\textbf{x}}^{j}$ to both sides of (4.4) and set $z=0$ and
$x_{i}=a_{i}$ for $i\geq 0$ afterwards to obtain

$\Delta_{\textbf{x}}^{j}f(z)\big{|}_{z=0,x_{i}=a_{i}}=\sum_{k=0}^{n}C_{k}\Delta_{\textbf{x}}^{j}a_{z}\downarrow_{k}^{\textbf{a}}\big{|}_{z=0,x_{i}=a_{i}}$

since $C_{k}$ is independent of $z$ and $x_{i}$. The above notation means that
we set $z=0$ and $x_{i}=a_{i}$ for $i\geq 0$ after applying the operators to
both sides. Evaluating the operator on the right hand side gives

$\Delta_{\textbf{x}}^{j}a_{z}\downarrow_{k}^{\textbf{a}}=\sum_{s=0}^{j}{x}_{j}!\prod_{\begin{subarray}{c}i=0\\\
i\neq s\end{subarray}}^{j}(x_{s}-x_{i})^{-1}\prod_{i=0}^{k-1}(a_{z+s}-a_{i}).$

In this expression we can set $z=0$ and $x_{i}=a_{i}$ for $i\geq 0$ to obtain

$\displaystyle\Delta_{\textbf{x}}^{j}a_{z}\downarrow_{k}^{\textbf{a}}\big{|}_{z=0,x_{i}=a_{i}}=\sum_{s=0}^{j}{a}_{j}!\frac{\prod_{i=0}^{k-1}(a_{s}-a_{i})}{\prod_{\begin{subarray}{c}i=0\\\
i\neq s\end{subarray}}^{j}(a_{s}-a_{i})}.$

We want to show that this sum simplifies to $\delta_{j,k}{a}_{j}!$, where
$\delta$ is the Kronecker delta.

Suppose $0\leq j<k$. Then we have a factor $(a_{s}-a_{s})=0$ in the numerator
of each summand, and the sum vanishes.

For $k=j$ the sum reduces to $a_{k}!$ by the same argument.

Suppose $k<j\leq n$. Then,

$\displaystyle\sum_{s=0}^{j}{a}_{j}!\frac{\prod_{i=0}^{k-1}(a_{s}-a_{i})}{\prod_{\begin{subarray}{c}i=0\\\
i\neq
s\end{subarray}}^{j}(a_{s}-a_{i})}=\sum_{s=k}^{j}{a}_{j}!\frac{\prod_{i=0}^{k-1}(a_{s}-a_{i})}{\prod_{\begin{subarray}{c}i=0\\\
i\neq
s\end{subarray}}^{j}(a_{s}-a_{i})}=\sum_{s=k}^{j}{a}_{j}!\prod_{\begin{subarray}{c}i=k\\\
i\neq s\end{subarray}}^{j}(a_{s}-a_{i})^{-1}.$

In order to prove

$\sum_{s=k}^{j}{a}_{j}!\prod_{\begin{subarray}{c}i=k\\\ i\neq
s\end{subarray}}^{j}(a_{s}-a_{i})^{-1}=0$

for $k<j$, we assume $a_{j}\downarrow_{k}^{\textbf{a}}\neq 0$ (otherwise the
equation would be true as well) and divide both sides by
$a_{j}\downarrow_{k}^{\textbf{a}}$. By a simple computation we arrive at the
equivalent equation

$\sum_{s=k}^{j-1}\prod_{\begin{subarray}{c}i=k\\\ i\neq
s\end{subarray}}^{j-1}\frac{(a_{j}-a_{i})}{(a_{s}-a_{i})}=1.$

The sum on the left side can be seen as a polynomial in $a_{j}$ of degree
$j-k-1$ which is equal to $1$ in the $j-k$ values
$a_{k},a_{k+1},\dots,a_{j-1}$ inserted for $a_{j}$. In fact, it is the
Lagrange interpolation polynomial for the function $f(a_{j})=1$. Therefore,
the equality holds and we have proven the case $k<j$.

In summary, we have shown that

$\frac{\Delta_{\textbf{x}}^{j}f(z)}{{a}_{j}!}\big{|}_{z=0,x_{i}=a_{i}}=C_{j}.$

To prove the theorem, we take $f(z)=a_{z}^{n}$ to obtain

$C_{k}=\frac{\Delta_{\textbf{x}}^{k}a_{z}^{n}}{{a}_{k}!}\big{|}_{z=0,x_{i}=a_{i}}=\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\
i\neq j\end{subarray}}^{k}(a_{j}-a_{i})^{-1}\Big{)}a_{j}^{n}.$ (4.5)

By comparing (4.4) with (3.2) (where $z$ is replaced by $a_{z}$) we finally
arrive at

$h_{n}(a_{0},\dots,a_{k})=\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\
i\neq j\end{subarray}}^{k}(a_{j}-a_{i})^{-1}\Big{)}a_{j}^{n+k}.\qed$

######  Remark 4.1 (Specializations).

Besides the elliptic and $q$-Stirling numbers, there are several interesting
specializations of $h_{n}(a_{0},a_{1},\dots,a_{k})$. For example, we obtain
$(q,r)$-Whitney numbers of the second kind, $W_{m,r}[n,k]_{q}$ (see for
example [11] or [19] for $q=1$), by

$W_{m,r}[n,k]_{q}q^{-kr-m\binom{k}{2}}=W_{m,r}^{\ast}[n,k]_{q}=h_{n-k}([r]_{q},[m+r]_{q},[2m+r]_{q},\dots,[km+r]_{q}).$

Then, Theorem 3.1 reduces to [11, Equation (12)].

Remmel and Wachs defined a $(p,q)$-analogue of these numbers, the shifted
Stirling numbers of the second kind. We obtain the $(p,q)$-shifted Stirling
numbers of the second kind, $S_{n,k}^{r,m}(p,q)$ [23, Equation (28)], by

$S_{n,k}^{r,m}(p,q)=h_{n-k}([r]_{p,q},[m+r]_{p,q},[2m+r]_{p,q},\dots,[km+r]_{p,q}),$

which are a $(p,q)$-analogue of $r$-Whitney numbers. Then, one can check by a
careful computation that Theorem 3.1 reduces to [23, Theorem 13].

An elliptic analogue of $S_{n,k}^{r,m}(p,q)$ was defined by Schlosser and Yoo
[32] and can be obtained by specializing

$S_{a,b;q,p}^{r,m}(n,k)=h_{n-k}([r]_{a,b;q,p},[m+r]_{a,b;q,p},[2m+r]_{a,b;q,p},\dots,[km+r]_{a,b;q,p}),$

up to a power of elliptic weights (comparable to the remark in footnote 2).

##  5\. More general cases

The proof of Theorem 3.1 can be adapted to any polynomial $f$ in $a_{z}$ of
degree at most $n$ which is independent of the variables x. Let $C$ and
$c_{1},c_{2},\dots,c_{n}$ be complex numbers. If we take
$f(z)=c_{0}(a_{z}-c_{1})(a_{z}-c_{2})\cdots(a_{z}-c_{n})$, then (4.4) becomes

$c_{0}\prod_{i=1}^{n}(a_{z}-c_{i})=\sum_{k=0}^{n}C_{n,k}a_{z}\downarrow_{k}^{\textbf{a}},$
(5.1)

and, following the proof of Theorem 3.1, the coefficients have the explicit
form

$C_{n,k}=\frac{\Delta_{\textbf{x}}^{k}f(z)}{{a}_{k}!}\big{|}_{z=0,x_{i}=a_{i}}=c_{0}\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\
i\neq
j\end{subarray}}^{k}(a_{j}-a_{i})^{-1}\Big{)}\prod_{i=1}^{n}(a_{j}-c_{i}).$
(5.2)

If we see $a_{0},a_{1},\dots,a_{n}$ as complex numbers, then $C_{n,k}$ is the
change of basis coefficient between the two series of polynomials over
$\mathbb{C}$

$\Big{(}c_{0}\prod_{i=1}^{n}(a_{z}-c_{i})\Big{)}_{n\geq
0}\qquad\text{and}\qquad\Big{(}\prod_{i=0}^{n-1}(a_{z}-a_{i})\Big{)}_{n\geq
0}.$

From (5.1) we can derive the recurrence relations

$\displaystyle C_{n,k}$ $\displaystyle=0,\qquad\text{for $k<0$ or $k>n$ },$
(5.3a) $\displaystyle C_{0,0}$ $\displaystyle=c_{0},$ (5.3b) and, for $k\geq
0$, $\displaystyle C_{n+1,k}$
$\displaystyle=C_{n,k-1}+(a_{k}-c_{n+1})C_{n,k}.$ (5.3c)

######  Remark 5.1.

Note that the results discussed in this section are well-studied in other
contexts. For $c_{0}=1$, the coefficient $C_{n,k}$ is equal to the
complementary symmetric function
$\operatorname{comp}_{k}(\\{c_{1},c_{2},\dots,c_{n}|a_{0},a_{1},\dots,a_{k}\\})$
defined over hybrid sets in [12]. This can be seen by comparing (5.1) with
[12, Corollary 2].

We can also see the results from the perspective of Newton polynomials and
divided differences. The falling factorials
$z\downarrow_{n}^{\textbf{x}}=\prod_{i=0}^{n-1}(z-x_{i})$ are also known as
Newton polynomials, and (4.5) is the explicit formula for the divided
differences of $z^{n}$ (see for example [20, p. 7]). By linearity, this
formula extends to arbitrary polynomials in $z$, yielding (5.2).

###  5.1. Rook numbers

In [32], Schlosser and Yoo define the $k$-th elliptic rook number,
$r_{k}(a,b;q,p;B)$, for a Ferrers board

$B=B(b_{1},b_{2},\dots,b_{n})=\\{(i,j):1\leq i\leq n,1\leq j\leq b_{i}\\}$

as the sum of specific elliptic weights for rook placements of $B$. We neglect
the details here and only focus on the following algebraic expression. The
authors obtain the following generating function for the elliptic rook numbers
[32, Theorem 12]:

$\prod_{i=1}^{n}[z-i+1+b_{i}]_{aq^{2(i-1-b_{i})},bq^{i-1-b_{i}};q,p}\\\
=\sum_{k=0}^{n}r_{n-k}(a,b;q,p;B)\prod_{j=1}^{k}[z-j+1]_{aq^{2(j-1)},bq^{j-1};q,p}.$
(5.4)

We can reformulate this equation by using (2.4) as

$\prod_{i=1}^{n}W_{a,b;q,p}(i-1-b_{i})^{-1}([z]_{a,b;q,p}-[i-1-b_{i}]_{a,b;q,p})\\\
=\sum_{k=0}^{n}r_{n-k}(a,b;q,p;B)\Big{(}\prod_{j=1}^{k}W_{a,b;q,p}(j-1)^{-1}\Big{)}[z]_{a,b;q,p}\downarrow_{k}^{a,b;q,p}.$
(5.5)

Comparing this expression with (5.1) yields

$r_{n-k}(a,b;q,p;B)=\sum_{j=0}^{k}\frac{W_{a,b;q,p}(j)}{W_{a,b;q,p}(k)}\frac{\prod_{i=1}^{n}[j-i+b_{i}+1]_{aq^{2(i-1-b_{i})},bq^{i-1-b_{i}};q,p}}{\prod_{\begin{subarray}{c}i=0\\\
i\neq j\end{subarray}}^{k}[j-i]_{aq^{2i};bq^{i};q,p}}$ (5.6)

as a special case of (5.2) with $c_{0}=\prod_{i=1}^{n}W_{a,b;q,p}(i-1-b_{i})$,
$a_{i}=[i]_{a,b;q,p}$, $c_{i}=[i-1-b_{i}]_{a,b;q,p}$ and

$C_{n,k}=r_{n-k}(a,b;q,p;B)\prod_{j=1}^{k}W_{a,b;q,p}(j-1)^{-1}.$

These elliptic rook numbers generalize elliptic Stirling numbers of the second
kind, which can be recovered by considering the staircase Ferrers board
$B(1,2,3,\dots,n-1)$ (with the original definition of elliptic Stirling
numbers).

In the case of $p\to 0$, $b\to 0$ and $B=[n+r-1]\times[n-r]$ the identity
(5.6) can be evaluated in closed form by virtue of the $q$-Pfaff–Saalschütz
summation, thus yielding a closed form of the respective $r$-restricted
$a;q$-Lah numbers (compare to [31, Subsection 3.1.1]).

###  5.2. Lah numbers

Another interesting board considered in [32] is
$B(b_{1},b_{2},\dots,b_{n})=B(n-1,n-1,\dots,n-1)$. In this case, the elliptic
rook numbers are equal to elliptic Lah numbers, defined in [15]. We will again
use a slightly different definition (up to a power of elliptic weights). We
introduce _elliptic rising factorials_ by the definition

$z\uparrow_{n}^{a,b;q,p}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}z(z-[-1]_{a,b;q,p})\cdots(z-[-n+1]_{a,b;q,p}),$

for $n>0$ and $z\uparrow_{0}^{a,b;q,p}=1$, and define _elliptic Lah numbers_ ,
$L_{a,b;q,p}(n,k)$, by

$[z]_{a,b;q,p}\uparrow_{n}^{a,b;q,p}=\sum_{k=0}^{n}L_{a,b;q,p}(n,k)[z]_{a,b;q,p}\downarrow_{k}^{a,b;q,p}.$
(5.7)

They fulfil the recurrence relation

$\displaystyle L_{a,b;q,p}(n,k)$ $\displaystyle=0,\qquad\text{for $k<0$ or
$k>n$ },$ (5.8a) $\displaystyle L_{a,b;q,p}(0,0)$ $\displaystyle=1,$ (5.8b)
and, for $k\geq 0$, $\displaystyle L_{a,b;q,p}(n+1,k)$
$\displaystyle=L_{a,b;q,p}(n,k-1)+W_{a,b;q,p}(-n)[n+k]_{aq^{-2n},bq^{-n};q,p}L_{a,b;q,p}(n,k).$
(5.8c)

We derive the explicit expression

$L_{a,b;q,p}(n,k)=\sum_{j=0}^{k}\frac{\prod_{i=1}^{n}([j]_{a,b;q,p}-[-n+i]_{a,b;q,p})}{\prod_{\begin{subarray}{c}i=0\\\
i\neq j\end{subarray}}^{k}([j]_{a,b;q,p}-[i]_{a,b;q,p})}$ (5.9)

by comparing (5.7) with (5.4) or directly with (5.1).

##  6\. Eulerian numbers

The _Eulerian numbers_ , $A(n,k)$, play an important role in combinatorics. We
follow the notation of Carlitz [7] and define Eulerian numbers by the
recurrence relation

$\displaystyle A(n,k)$ $\displaystyle=0,\qquad\text{for $k<0$ or $k>n$},$
(6.1a) $\displaystyle A(0,0)$ $\displaystyle=1,$ (6.1b) and, for $k\geq 0$,
$\displaystyle A(n+1,k)$ $\displaystyle=(n-k+2)A(n,k-1)+kA(n,k).$ (6.1c)

The Eulerian numbers can also be defined as the connection coefficients in the
identity

$\displaystyle z^{n}=\sum_{k=0}^{n}A(n,k)\binom{z+k-1}{n},$ (6.2)

which is known as Worpitzky’s identity. Besides several other properties,
Eulerian numbers can be expressed by the explicit sum formula

$\displaystyle A(n,k)=\sum_{j=0}^{k}(-1)^{j}\binom{n+1}{j}(k-j)^{n}.$ (6.3)

We recommend [21] for an introduction to Eulerian numbers.

Carlitz introduced a $q$-analogue of Eulerian numbers [7], the _$q$ -Eulerian
numbers_, $A_{q}(n,k)$, and defined them as the connection coefficients in

$\displaystyle[z]_{q}^{n}=\sum_{k=0}^{n}A_{q}(n,k){\begin{bmatrix}z+k-1\\\
n\end{bmatrix}}_{q}.$ (6.4)

He derives from this relation that $A_{q}(n,k)$ satisfies

$\displaystyle A_{q}(n,k)$ $\displaystyle=0,\qquad\text{for $k<0$ or $k>n$ },$
(6.5a) $\displaystyle A_{q}(0,0)$ $\displaystyle=1,$ (6.5b) and, for $k\geq
0$, $\displaystyle A_{q}(n+1,k)$
$\displaystyle=[n-k+2]_{q}A_{q}(n,k-1)+q^{n-k+1}[k]_{q}A_{q}(n,k)$ (6.5c)

and the explicit formula (see [7, Equation (5.5), corrected])

$\displaystyle
A_{q}(n,k)=q^{\binom{n-k+1}{2}-\binom{k}{2}}\sum_{j=0}^{k}(-1)^{j}q^{\binom{j}{2}}{\begin{bmatrix}n+1\\\
j\end{bmatrix}}_{q}[k-j]_{q}^{n}.$ (6.6)

###  6.1. Generalized Eulerian numbers

It turns out that it is possible to generalize Carlitz’ $q$-Eulerian numbers
similarly to the generalizations in the previous sections to elliptic Eulerian
numbers and a Laurent polynomial analogue. We begin by extending a to
variables with negative index by
$\textbf{a}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\dots,a_{-2},a_{-1},a_{0},a_{1},a_{2},\dots$
and define generalized Eulerian numbers, $A_{\textbf{a}}(n,k)$, as the
connection coefficients in

$\displaystyle
z^{n}=\sum_{k=0}^{n}A_{\textbf{a}}(n,k)\prod_{i=1}^{n}\frac{z-a_{i-k}}{a_{n-k+1}-a_{i-k}}.$
(6.7)

This definition was chosen due to the fact that these coefficients can be
characterized by a nice recursion, and we will derive a simple explicit sum
formula for $A_{\textbf{a}}(n,k)$.

Note that $A_{\textbf{a}}(n,k)=0$ for $k<0$ or $k>n$ and
$A_{\textbf{a}}(0,0)=1$. We can derive a recursion for $A_{\textbf{a}}(n,k)$
by using the identity

$z=\frac{a_{n-k+1}(z-a_{-k})-a_{-k}(z-a_{n-k+1})}{a_{n-k+1}-a_{-k}}$ (6.8)

and we introduce the notation

$P(n,k)\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\prod_{i=1}^{n+1}\frac{a_{n-k+2}-a_{i-k}}{a_{n-k+1}-a_{i-1-k}}.$
(6.9)

By multiplying $z$ to both sides of (6.7) using (6.8) we obtain

$\displaystyle z^{n+1}$
$\displaystyle=\sum_{k=0}^{n}A_{\textbf{a}}(n,k)\Big{(}\prod_{i=1}^{n}\frac{z-a_{i-k}}{a_{n-k+1}-a_{i-k}}\Big{)}\frac{a_{n-k+1}(z-a_{-k})-a_{-k}(z-a_{n-k+1})}{a_{n-k+1}-a_{-k}}$
$\displaystyle=\sum_{k=0}^{n}A_{\textbf{a}}(n,k)a_{n-k+1}\prod_{i=0}^{n}\frac{z-a_{i-k}}{a_{n-k+1}-a_{i-k}}$
$\displaystyle\qquad-\sum_{k=0}^{n}A_{\textbf{a}}(n,k)a_{-k}\prod_{i=0}^{n}\frac{z-a_{i-k+1}}{a_{n-k+1}-a_{i-k}}$
$\displaystyle=\sum_{k=1}^{n+1}A_{\textbf{a}}(n,k-1)a_{n-k+2}\prod_{i=1}^{n+1}\frac{z-a_{i-k}}{a_{n-k+2}-a_{i-k}}$
$\displaystyle\qquad-\sum_{k=0}^{n}A_{\textbf{a}}(n,k)a_{-k}\Big{(}\prod_{i=1}^{n+1}\frac{a_{n-k+2}-a_{i-k}}{a_{n-k+1}-a_{i-1-k}}\Big{)}\prod_{i=1}^{n+1}\frac{z-a_{i-k}}{a_{n-k+2}-a_{i-k}}$
$\displaystyle=\sum_{k=0}^{n+1}\Big{(}a_{n-k+2}A_{\textbf{a}}(n,k-1)-a_{-k}P(n,k)A_{\textbf{a}}(n,k)\Big{)}\prod_{i=1}^{n+1}\frac{z-a_{i-k}}{a_{n-k+2}-a_{i-k}}.$

By comparing the last sum with the definition of $A_{\textbf{a}}(n+1,k)$ in
(6.7) we obtain the recursive description for the generalized Eulerian numbers

$\displaystyle A_{\textbf{a}}(n,k)$ $\displaystyle=0,\qquad\text{for $k<0$ or
$k>n$},$ (6.10a) $\displaystyle A_{\textbf{a}}(0,0)$ $\displaystyle=1,$
(6.10b) and, for $k\geq 0$, $\displaystyle A_{\textbf{a}}(n+1,k)$
$\displaystyle=a_{n-k+2}A_{\textbf{a}}(n,k-1)-a_{-k}P(n,k)A_{\textbf{a}}(n,k).$
(6.10c)

Note that in comparison to the generalized Stirling, Lah and rook numbers,
$A_{\textbf{a}}(n,k)$ is not a polynomial in the variables a due to the factor
$P(n,k)$ in the recursion. However, $P(n,k)$ factorizes to $1$ or a power of
$q$ in the following specializations.

######  Remark 6.1 (Specializations).

By setting $a_{i}=i$ for all $i\in\mathbb{Z}$, we obtain $P(n,k)=1$ and
$A_{\textbf{a}}(n,k)$ reduces to the ordinary Eulerian numbers $A(n,k)$.

By setting $a_{i}=[i]_{q}$ for all $i\in\mathbb{Z}$, we obtain
$P(n,k)=q^{n+1}$, $a_{-k}=[-k]_{q}=-q^{-k}[k]_{q}$, thus we can see by
comparing the recursion formulae (6.10) and (6.5) (or by comparing the
definitions) that $A_{\textbf{a}}(n,k)$ reduces to Carlitz’ $q$-Eulerian
numbers $A_{q}(n,k)$.

We study more specializations in Section 6.3.

###  6.2. Explicit formula for $A_{\textbf{a}}(n,k)$

In this subsection, we derive an explicit formula for the generalized Eulerian
numbers.

######  Theorem 6.2.

For $n\geq 0$ and $0\leq k\leq n$ there holds

$A_{\textbf{a}}(n,k)=\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\
i\neq
k-j\end{subarray}}^{n}\frac{a_{n-k+1}-a_{i-k}}{a_{-j}-a_{i-k}}\Big{)}a_{-j}^{n}.$
(6.11)

###### Proof.

We begin by letting $f(z)$ be a polynomial in $a_{z}$ of degree at most $n$
and let $C_{n,k}$ be the connection coefficients in

$f(z)=\sum_{k=0}^{n}C_{n,k}\prod_{i=1}^{n}\frac{a_{z}-a_{i-k}}{a_{n-k+1}-a_{i-k}}$
(6.12)

and we claim that

$C_{n,k}=\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\ i\neq
k-j\end{subarray}}^{n}\frac{a_{n-k+1}-a_{i-k}}{a_{-j}-a_{i-k}}\Big{)}f(-j).$
(6.13)

We prove this claim by inserting (6.12) into the right side of (6.13) to
derive

$\displaystyle\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\ i\neq
k-j\end{subarray}}^{n}\frac{a_{n-k+1}-a_{i-k}}{a_{-j}-a_{i-k}}\Big{)}f(-j)$
$\displaystyle=\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\ i\neq
k-j\end{subarray}}^{n}\frac{a_{n-k+1}-a_{i-k}}{a_{-j}-a_{i-k}}\Big{)}\sum_{l=0}^{n}C_{n,l}\prod_{i=1}^{n}\frac{a_{-j}-a_{i-l}}{a_{n-l+1}-a_{i-l}}$
$\displaystyle=\sum_{l=0}^{n}C_{n,l}\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\
i\neq
k-j\end{subarray}}^{n}\frac{a_{n-k+1}-a_{i-k}}{a_{-j}-a_{i-k}}\Big{)}\prod_{i=1}^{n}\frac{a_{-j}-a_{i-l}}{a_{n-l+1}-a_{i-l}}$
$\displaystyle=\sum_{l=0}^{k}C_{n,l}\sum_{j=l}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\
i\neq
k-j\end{subarray}}^{n}\frac{a_{n-k+1}-a_{i-k}}{a_{-j}-a_{i-k}}\Big{)}\prod_{i=1}^{n}\frac{a_{-j}-a_{i-l}}{a_{n-l+1}-a_{i-l}}$

We prove that the last expression is equal to $C_{n,k}$ by showing that

$\sum_{j=l}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\ i\neq
k-j\end{subarray}}^{n}\frac{a_{n-k+1}-a_{i-k}}{a_{-j}-a_{i-k}}\Big{)}\prod_{i=1}^{n}\frac{a_{-j}-a_{i-l}}{a_{n-l+1}-a_{i-l}}=\delta_{k,l}$
(6.14)

for $0\leq l\leq k\leq n$. First, we factor out

$\frac{\prod_{i=k-l+1}^{n}(a_{n-k+1}-a_{i-k})}{\prod_{i=1}^{n}(a_{n-l+1}-a_{i-l})}\sum_{j=l}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\
i\neq
k-j\end{subarray}}^{k-l}\frac{a_{n-k+1}-a_{i-k}}{a_{-j}-a_{i-k}}\Big{)}\prod_{i=1}^{k-l}(a_{-j}-a_{i+n-k})$
(6.15)

to obtain that the sum in this expression is the Lagrange interpolation
polynomial of the polynomial

$g(z)=\prod_{i=1}^{k-l}(z-a_{i+n-k}),$

for the $k-l+1$ values $a_{-l},a_{-l-1},\dots,a_{-k}$ inserted for $z$ and $z$
is replaced by $a_{n-k+1}$. Since $g(z)$ is a polynomial in the variable $z$
of degree $k-l$, the Lagrange polynomial and $g(z)$ are equal, such that
(6.15) is equal to

$\frac{\prod_{i=k-l+1}^{n}(a_{n-k+1}-a_{i-k})}{\prod_{i=1}^{n}(a_{n-l+1}-a_{i-l})}\prod_{i=1}^{k-l}(a_{n-k+1}-a_{i+n-k})=\delta_{k,l}.$
(6.16)

We therefore proved (6.14) and (6.13). By comparing (6.12) with (6.7) and
setting $f(z)=a_{z}^{n}$, we complete the proof of the theorem. ∎

###  6.3. Specializations

In the literature, several generalizations of Eulerian numbers and
$q$-Eulerian numbers were studied. It appears that some generalizations are
special cases of $A_{\textbf{a}}(n,k)$.

For example, the _$r$ -Whitney Eulerian numbers_ [18, 22] satisfy (see [22,
Equation (6)])

$\displaystyle A_{m,r}(n,k)$ $\displaystyle=0,\qquad\text{for $k<0$ or
$k>n$},$ (6.17a) $\displaystyle A_{m,r}(0,0)$ $\displaystyle=1,$ (6.17b) and,
for $k\geq 0$, $\displaystyle A_{m,r}(n+1,k)$
$\displaystyle=(m(n-k+2)-r)A_{m,r}(n,k-1)+(mk+r)A_{m,r}(n,k).$ (6.17c)

The $r$-Whitney Eulerian numbers reduce to classical Eulerian numbers for
$(m,r)=(1,0)$ and to the $q$-Eulerian numbers due to Brenti [4] for
$(m,r)=(q+1,1)$. By comparing (6.17) with (6.10) one can see that setting
$a_{i}=mi-r$ in $A_{\textbf{a}}(n,k)$ yields $A_{m,r}(n,k)$, since the
polynomials $P(n,k)$ reduce to $1$ in this case. Furthermore, for $z=mx-r$ the
Worpitzky identity (6.7) reduces to

$(mx-r)^{n}=\sum_{k=0}^{n}A_{m,r}(n,k)\binom{x+k-1}{n}$

which is in fact different to the Worpitzky identity given in [22, Theorem 5].
The explicit formula (6.11) yields [22, Theorem 6].

A $q$-analogue of the $r$-Whitney Eulerian numbers, $A_{q}^{m,r}(n,k)$, can be
obtained by setting $a_{i}=[mi-r]_{q}$. From (6.10) we obtain the recursion

$\displaystyle A_{q}^{m,r}(n,k)$ $\displaystyle=0,\qquad\text{for $k<0$ or
$k>n$ },$ (6.18a) $\displaystyle A_{q}^{m,r}(0,0)$ $\displaystyle=1,$ (6.18b)
and, for $k\geq 0$, $\displaystyle A_{q}^{m,r}(n+1,k)$
$\displaystyle=[m(n-k+2)-r]_{q}A_{q}^{m,r}(n,k-1)$
$\displaystyle+q^{m(n+1)-mk-r}[mk+r]_{q}A_{q}^{m,r}(n,k),$ (6.18c)

For $z=[mx-r]_{q}$ the Worpitzky identity (6.7) reduces to

$[mx-r]_{q}^{n}=\sum_{k=0}^{n}A_{q}^{m,r}(n,k){\begin{bmatrix}x+k-1\\\
n\end{bmatrix}}_{q^{m}}$ (6.19)

and from (6.11) we obtain the explicit formula

$A_{q}^{m,r}(n,k)=\sum_{j=0}^{k}(-1)^{j}q^{m\binom{n-j+1}{2}-n(m(k-j)+r)}{\begin{bmatrix}n+1\\\
j\end{bmatrix}}_{q^{m}}[m(k-j)+r]_{q}^{n}.$ (6.20)

For $(m,r)=(1,0)$ this reduces to Carlitz’ $q$-Eulerian numbers (6.4). The
case $(m,r)=(m,1)$ was studied in [9] as a $q$-Eulerian number analogue for
the wreath product $C_{r}\wr\mathfrak{S}_{n}$. For the case $(m,r)=(2,1)$ we
get the $q$-Eulerian numbers of type $B$ [8].

###  6.4. Elliptic Eulerian numbers

One of the main motivations of this article was to introduce an elliptic
analogue of Carlitz’ $q$-Eulerian numbers. We will obtain such an analogue by
specializing $A_{\textbf{a}}(n,k)$ in the obvious way. We define _elliptic
Eulerian numbers_ $A_{a,b;q,p}(n,k)$ by specializing $a_{i}=[i]_{a,b;q,p}$ in
$A_{\textbf{a}}(n,k)$ to obtain the recurrence relation

$\displaystyle A_{a,b;q,p}(n,k)$ $\displaystyle=0,\qquad\text{for $k<0$ or
$k>n$},$ (6.21a) $\displaystyle A_{a,b;q,p}(0,0)$ $\displaystyle=1,$ (6.21b)
and, for $k\geq 0$, $\displaystyle A_{a,b;q,p}(n+1,k)$
$\displaystyle=[n-k+2]_{a,b;q,p}A_{\textbf{a}}(n,k-1)$
$\displaystyle\quad+W_{a,b;q,p}(-1)[k]_{1/a,b/a;q,p}P_{a,b;q,p}(n,k)A_{\textbf{a}}(n,k),$
(6.21c)

where

$P_{a,b;q,p}(n,k)=W_{aq^{-2k},bq^{-k};q,p}(n+1)\prod_{i=1}^{n+1}\frac{[n-i+2]_{aq^{2(i-k)},bq^{i-k};q,p}}{[n-i+2]_{aq^{2(i-k-1),bq^{i-k-1};q,p}}},$

where we used (2.5) and (2.6). For the elliptic Eulerian numbers the
generalized Worpitzky identity

$[z]_{a,b;q,p}^{n}=\sum_{k=0}^{n}A_{\textbf{a}}(n,k)\prod_{i=1}^{n}\frac{[z-i+k]_{aq^{2(i-k)},bq^{i-k};q,p}}{[n-i+1]_{aq^{2(i-k)},bq^{i-k};q,p}}$
(6.22)

holds and from Theorem 6.2 we obtain the explicit sum-formula

$\displaystyle A_{a,b;q,p}$
$\displaystyle=\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\ i\neq
k-j\end{subarray}}^{n}\frac{[n-i+1]_{aq^{2(i-k)},bq^{i-k};q,p}}{[k-j-i]_{aq^{2(i-k)},bq^{i-k};q,p}}\Big{)}[-j]_{a,b;q,p}^{n}$
(6.23)
$\displaystyle=(-1)^{n}W_{a,b;q,p}(-1)^{n}\sum_{j=0}^{k}\Big{(}\prod_{\begin{subarray}{c}i=0\\\
i\neq
j\end{subarray}}^{n}\frac{[n-i+1]_{aq^{2(i-k)},bq^{i-k};q,p}}{[j-i]_{aq^{2(i-k)},bq^{i-k};q,p}}\Big{)}[k-j]_{a,b;q,p}^{n}.$
(6.24)

An _elliptic analogue of the $r$-Whitney Eulerian numbers_,
$A_{a,b;q,p}^{m,r}(n,k)$, can be obtained by specializing
$a_{i}=[mi-r]_{a,b;q,p}$ in $A_{\textbf{a}}(n,k)$. We omit the details here.

##  7\. Acknowledgements

This work is based on research which is a part of the author’s doctoral thesis
at the University of Vienna [16]. The author is grateful to Ilse Fischer, Hans
Höngesberg, Michael Schlosser and Meesue Yoo for helpful and inspiring
discussions.

## References

  * [1] Nantel Bergeron, Cesar Ceballos, and Josef Küstner.  Elliptic and $q$-analogs of the Fibonomial numbers.  SIGMA Symmetry Integrability Geom. Methods Appl., 16:Paper No. 076, 16 pp., 2020.
  * [2] Dan Betea.  Elliptically distributed lozenge tilings of a hexagon.  SIGMA Symmetry Integrability Geom. Methods Appl., 14:Paper No. 032, 39 pp., 2018.
  * [3] Alexei Borodin, Vadim Gorin, and Eric M. Rains.  $q$-Distributions on boxed plane partitions.  Selecta Math. (N.S.), 16(4):731–789, 2010.
  * [4] Francesco Brenti.  $q$-Eulerian polynomials arising from Coxeter groups.  European J. Combin., 15(5):417–441, 1994.
  * [5] Leonard Carlitz.  On abelian fields.  Trans. Amer. Math. Soc., 35(1):122–136, 1933.
  * [6] Leonard Carlitz.  $q$-Bernoulli numbers and polynomials.  Duke Math. J., 15:987–1000, 1948.
  * [7] Leonard Carlitz.  $q$-Bernoulli and Eulerian numbers.  Trans. Amer. Math. Soc., 76:332–350, 1954.
  * [8] Chak-On Chow and Ira M. Gessel.  On the descent numbers and major indices for the hyperoctahedral group.  Adv. in Appl. Math., 38(3):275–301, 2007.
  * [9] Chak-On Chow and Toufik Mansour.  A Carlitz identity for the wreath product $C_{r}\wr\mathfrak{S}_{n}$.  Adv. in Appl. Math., 47(2):199–215, 2011.
  * [10] Johann Cigler.  Operatormethoden für $q$-Identitäten.  Monatsh. Math., 88(2):87–105, 1979.
  * [11] Roberto B. Corcino, Jay M. Ontolan, and Maria Rowena S. Lobrigas.  Explicit formulas for the first form $(q,r)$-Dowling numbers and $(q,r)$-Whitney–Lah numbers.  Eur. J. Pure Appl. Math., 14(1):65–81, 2021.
  * [12] Ernesto Damiani, Ottavio M. D’Antona, and Daniel E. Loeb.  The complementary symmetric functions: connection constants using negative sets.  Adv. Math., 135(2):207–219, 1998.
  * [13] George Gasper and Mizan Rahman.  Basic Hypergeometric Series.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2nd edition, 2004.
  * [14] Robert A. Gustafson and Stephen C. Milne.  Schur functions, Good’s identity, and hypergeometric series well poised in ${SU}(n)$.  Adv. in Math., 48(2):177–188, 1983.
  * [15] Zsófia Kereskényiné Balogh and Michael J. Schlosser.  Elliptic stirling numbers of the second and first kind.  In preparation.
  * [16] Josef Küstner.  Elliptic Combinatorics of Lattice Paths, Domino Tilings and Rook Placements.  University of Vienna, 2022.  PhD Thesis.
  * [17] Josef Küstner, Michael J. Schlosser, and Meesue Yoo.  Lattice paths and negatively indexed weight-dependent binomial coefficients.  Annals of Combinatorics, 27:1–39, 2023.
  * [18] Toufik Mansour, José L. Ramírez, Mark Shattuck, and Sergio N. Villamarín.  Some combinatorial identities of the $r$-Whitney-Eulerian numbers.  Appl. Anal. Discrete Math., 13(2):378–398, 2019.
  * [19] István Mező.  A new formula for the Bernoulli polynomials.  Results Math., 58(3-4):329–335, 2010.
  * [20] Louis M. Milne-Thomson.  The Calculus Of Finite Differences.  Macmillan And Company., Limited, 1933.  PhD Thesis.
  * [21] T. Kyle Petersen.  Eulerian numbers.  Birkhäuser/Springer, New York, 2015.  With a foreword by Richard Stanley.
  * [22] José L. Ramírez, Sergio N. Villamarín, and Diego Villamizar.  Eulerian numbers associated with arithmetical progressions.  Electron. J. Combin., 25(1):Paper No. 1.48, 12 pp., 2018.
  * [23] Jeffrey B. Remmel and Michelle L. Wachs.  Rook theory, generalized Stirling numbers and $(p,q)$-analogues.  Electron. J. Combin., 11(1):Research Paper 84, 48 pp., 2004.
  * [24] Hjalmar Rosengren.  Elliptic hypergeometric functions.  In Howard S. Cohl and Mourad E. H. Ismail, editors, Lectures on Orthogonal Polynomials and Special Functions, pages 213–279. Cambridge University Press, Cambridge, 2020.
  * [25] Gian-Carlo Rota, editor.  Finite operator calculus.  Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1975.  With the collaboration of P. Doubilet, C. Greene, D. Kahaner, A. Odlyzko and R. Stanley.
  * [26] Bruce E. Sagan and Joshua P. Swanson.  $q$-Stirling numbers in type B.  European Journal of Combinatorics, 118:103899, 2024.
  * [27] Michael J. Schlosser.  Elliptic enumeration of nonintersecting lattice paths.  J. Combin. Theory Ser. A, 114(3):505–521, 2007.
  * [28] Michael J. Schlosser.  A noncommutative weight-dependent generalization of the binomial theorem.  Sém. Lothar. Combin., 81:Art. B81j, 24 pp., 2020.
  * [29] Michael J. Schlosser.  An elliptic extension of the multinomial theorem.  Preprint, arXiv:2307.12921, 2023.
  * [30] Michael J. Schlosser, Koushik Senapati, and Ali K. Uncu.  Log-concavity results for a biparametric and an elliptic extension of the $q$-binomial coefficients.  Int. J. Number Theory, 17(3):787–804, 2021.
  * [31] Michael J. Schlosser and Meesue Yoo.  Basic hypergeometric summations from rook theory.  In Analytic number theory, modular forms and $q$-hypergeometric series, volume 221 of Springer Proc. Math. Stat., pages 677–692. Springer, Cham, 2017.
  * [32] Michael J. Schlosser and Meesue Yoo.  Elliptic rook and file numbers.  Electron. J. Combin., 24(1):Paper No. 1.31, 47 pp., 2017.
  * [33] Richard P. Stanley.  Enumerative Combinatorics 2.  Cambridge Univ. Press, Cambridge, 2001.
  * [34] Heinrich Weber.  Elliptische Functionen und algebraische Zahlen.  Vieweg-Verlag, Braunschweig, 1891.