A390529 Weighted count of equivalence classes of words w of length n+1 over {a, b, c, d, A, *} having exactly n letters, exactly one *, an even number of lowercase a's, and weight (-1)^(A(w)), where A(w) is the number of uppercase letters A.

1, 5, 22, 95, 406, 1715, 7162, 29615, 121486, 495275, 2009602, 8124935, 32761366, 131834435, 529712842, 2125993055, 8525430046, 34166159195, 136858084882, 548012945975, 2193794127526, 8780404589555, 35137304693722, 140596281975695, 562526325893806, 2250528914325515

Offset

0,2

Comments

Two words are equivalent if they have the same set of lowercase positions, the same lowercase letters in those positions, and the same number of uppercase letters A (thus, permutations of A and * in the remaining positions are not distinguished).

This sequence is S(n, 0), where S(n,j) is the weighted count of the equivalence classes of words w of length N = n + 2*j + 1 over the alphabet {a, b, c, d, A, *}. Each word has exactly n letter positions, exactly 2*j+1 stars, an even number of lowercase a's among the lowercase letters, and weight (-1)^(A(w)), where A(w) is the number of uppercase letters A.

Essentially the same as A053154. - R. J. Mathar, Nov 27 2025

Links

Table of n, a(n) for n=0..25.

Akaly Tefera and Aklilu Zeleke, Combinatorial identities inspired by Knuth's old sum, Integers 26 (2026), Art. A68.

Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Formula

a(n) = Sum_{k=0..n} (2^(n-k)+1)*2^(n-k-1)*binomial(n+2*j+1, n-k)*(-1)^k, with j = 0.

From Stefano Spezia, Nov 17 2025: (Start)

a(n) = 2^n*(1 + 2^(n+1)) - (3^(n+1) + 1)/2.

G.f.: (1 - 5*x + 7*x^2)/((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 4*x)).

E.g.f.: exp(x)*(2*exp(x) - 3*exp(2*x) + 4*exp(3*x) - 1)/2. (End)

Example

a(0) = 1 since, for n = 0, the only equivalence class is * with weight 1 and 1*1 = 1.
a(1) = 5 since, for n = 1, the equivalence classes are b*, c*, d*, *b, *c, *d (all weight 1) and A* (weight -1), and 6*1 + 1*(-1) = 5.

Maple

S := (n, j) -> add((2^(n-k) + 1) * 2^(n-k-1) * binomial(n + 2*j + 1, n - k) * (-1)^k, k = 0..n):
a := n -> S(n, 0):
seq(a(n), n=0..Nmax);

Mathematica

a[n_]:=2^n*(1 + 2^(n+1)) - (3^(n+1) + 1)/2; Array[a, 26, 0] (* Stefano Spezia, Nov 17 2025 *)

Prog

(Python)
from math import comb
def a(n): return sum((2**(n-k)+1)*2**(n-k-1)*comb(n+1, n-k)*(-1)**k for k in range(n)) + (-1)**n
print([a(n) for n in range(26)]) # Michael S. Branicky, Nov 15 2025

Crossrefs

Cf. A390530.

Sequence in context: A128746 A049675 A053154 * A141222 A127360 A116415

Adjacent sequences: A390526 A390527 A390528 * A390530 A390531 A390532

Keyword

nonn,easy,changed

Author

Akalu Tefera and Aklilu Zeleke, Nov 09 2025

Extensions

More terms from Michael S. Branicky, Nov 15 2025

Status

approved