Combinatorics and Graph Theory

Number of Non—Zero Coefficients of (1 + X^a + X^b)^n Over F_p

Authors: Andy Zhuang
Comments: 8 Pages.

The paper studies explicit formulas for (N_p(n;a,b)), the count of coefficients that remain non--zero modulo a prime (p) in the trinomial power ((1+x^{a}+x^{b})^{n}) with (0<a<b<p). Leveraging Lucas’ digit—wise criterion and the matrix--automaton framework of Amdeberhan--Stanley, we first prove a emph{carryu2011free theorem}: if every baseu2011(p) digit of (n) does not exceed (bigllfloor (p-1)/b bigrfloor) and the generated $x$-exponents do not overlap at every digit position, then no crossu2011digit carries occur and the exponents are unique for each digit position. This leads to (N_p(n;a,b)) being factorized as (prod_{l}binom{n_l+2}{2}), where $n_l$ are digits of $n$ under base-$p$.The paper next derives a upper bound (N_p(n;a,b)le 3^{,w_p(n)}), where (w_p(n)) is the sum of the baseu2011(p) digits of (n), and shows that equality holds precisely when every digit of (n) is (0) or (1). Worked examples—including the case ((1+x+x^{3})^{n}) over (mathbb{F}_7)—demonstrate the formulas in practice, and the discussion shows our contributions within earlier studies on automatic sequences and multinomial Lucas theorems.
Category: Combinatorics and Graph Theory