Counting words whose letters have parity condition

Question

How many words exist, such that the total number of each letter has a given parity?

Let $N := \{1,\dots,n\}$. I regard the set $N^r$, that is, the set of all words of length $r$ with the "letters" $1$, $\dots$, $n$.

Then I choose a subset of $A \subseteq \{1,\dots,n\}$ and regard the set $T_A$, which is defined as follows:

$T_A$ consists of all words $i = (i_1,\dots,i_r) \in N^r$, such that:

• for all $a \in A$, the letter $a$ occurs an odd number of times (that is, $\# \{k : i_k = a\}$ is odd).
• for all $a \in \{1,\dots,n\}\backslash A$, the letter $a$ occurs an even number of times.

(That is, the subset $A$ specifies which letters in a word occur in total with an odd parity.)

Is there any formula $F$, depending on $r$, $n$, and $\#A$, which gives the cardinality $\# T_A$ ?

---

I got a recursive formula for $F$ which leads to a difference equation in two variables (which I couldn't solve up to now with the usual methods for solving difference equations).

Since the problem is simple to explain, I hope that it remainds on a related problem which is solved yet. It would be great if someone takes delight in it, or, at most, has an idea :-) Thanks a lot for your time.

---

A little example:

Let $n = 2$, $r = 3$ and $A = \{1\}$.

Question: In how many $3$-tuples appears the entry $1$ odd times?

Answer: In $4$, since \begin{align*} T_A &= \{i \in N^r : 1 \text{ appears $1$ or $3$ times in $i$}\}\\ &= \{(1,2,2),(2,1,2),(2,2,1),(1,1,1)\}. \end{align*}

Answer 1

Though I haven't figured out a compact solution yet, I do have a thought on how to make the recursive solution more approachable (Dynamic Programming), so I want to share it with you.

First of all, we need a 3-dimension matrix, let's call it M, and the three of its inputs dimensions are: number of even letters #EVEN, number of odd letters #ODD, and total number of letters r. Its output is the number of words that have #EVEN even letters, #ODD odd letters, and r total letters.
let denote it M[#ODD, #EVEN, r]

I will give you the base cases as examples. It is easy to tell that when we have 1 odd letter, 0 even letter, and 1, 3, 5 ... total letter, the number of combinations for words is #A (all we need to do is to select one odd letter out of #A letters). Similarly, when we have 0 odd letter, 1 even letter, and 2, 4, 6 ... total letter, the number of combination for words is n - #A (select one even letter out of n - #A).
Notations are:
M[1, 0, 1] = #A . M[1, 0, 3] = #A .
...
M[0, 1, 2] = n - #A . M[0, 1, 4] = n - #A .
...

Now, we update the matrix in this manner: each time we only increment one odd number or one even number based on the previous results. Say if we want to calculate M[a, b, r], then M[a, b, r] = $$M[a - 1, b, r - 1] \cdot \binom{r}{1} + M[a - 1, b, r - 3] \cdot \binom{r}{3} + ... + M[a, b - 1, r - 2] \cdot \binom{r}{2} + M[a, b - 1, r - 4] \cdot \binom{r}{4} + ...$$

To make a brief explanation, suppose from the previous step, we have r - k letters for the word, and now we want to add a single letter that occur k times, then all we need to do is to find k places (from the target word with a total of r places) to insert the letter.

Also, notice that there are a few infeasible places. For instance, for an arbitrary set of a, b, r, where a + 2b > r or a and r are not both even or odd, then it is impossible to find a word with length r while having a odd letters and b even letters, in this case, fill in the matrix M[a, b, r] = 0.

You can keep updating this matrix until you have all information you need for a word of length r, then you will just sum up the matrix values with third dimension equals to r: $$\#T = \Sigma_{a, b}{M[a, b, r]}$$

I am not good at combinatoric's formulae, so I can't get the exact solution. If you can code this up in a programming language, you can eventually get this problem solved. Hopefully my answer can give you an idea on how to proceed.

Answer 2

Use generating functions throughout. Call the number of characters (alphabet size) $m$, number the characters $1, \dotsc, m$, call the length of the string $n$.

First, to find out the number of words with exactly $k$ characters which appear an odd number of times, we'll use the principle of inclusion and exclusion. Following Wilf's "generatingfunctionology" (Academic Press, 1994), call the number of words that have at least $r$ of the letters appearing an odd number of times $N_r$, and the number of words that contain exactly $t$ letters an odd number of times $e_t$. The respective generating functions are $N(z) = \sum_r N_r z^r$ and $E(z) = \sum_t e_t z^t$; they are related by $E(z) = N(z - 1)$. Thus we have:

$\begin{align*} e_k &= [z^k] E(z) \\ &= [z^k] N(z - 1) \\ &= [z^k] \sum_r N_r \sum_j (-1)^{r - j} \binom{r}{j} z^j \\ &= \sum_r (-1)^{r - k} \binom{k}{r} N_r \end{align*}$

Now, the generating function with $z_i$ counting the number of letters $i$ of a string of length $n$ is just: $\begin{align*} (z_1 + z_2 + \dotsb + z_m)^n &= \sum_{k_1 + k_2 + \dotsb + k_m = n} \binom{n}{k_1, k_2, \dotsc, k_m} z_1^{k_1} z_2^{k_2} \dotsm z_m^{k_m} \end{align*}$

The multinomial coefficient is:

$\begin{align*} \binom{n}{k_1, k_2, \dotsc, k_m} &= \frac{n!}{k_1! \, k_2! \, \dotsm \, k_m!} \end{align*}$

Say you want only cases in which $k_1$ is odd, this gives the sum:

$\begin{align*} \sum_{\substack{k_1 + k_2 + \dotsb + k_m = n \\\\ k_1 \text{ odd}}} \binom{n}{k_1, k_2, \dotsc, k_m} z_1^{k_1} z_2^{k_2} \dotsm z_m^{k_m} &= \frac{1}{2} \left( \sum_{k_1 + k_2 + \dotsb + k_m = n} \binom{n}{k_1, k_2, \dotsc, k_m} z_1^{k_1} z_2^{k_2} \dotsm z_m^{k_m} - \sum_{k_1 + k_2 + \dotsb + k_m = n} \binom{n}{k_1, k_2, \dotsc, k_m} (-z_1)^{k_1} z_2^{k_2} \dotsm z_m^{k_m} \right) \\ \end{align*}$

Thus, evaluating this mess at $z_1 = z_2 = \dotsb = z_m = 1$ gives you the total number of words in which letter $1$ appears an odd number of times:

$\begin{align*} \frac{1}{2} ((1 + 1 + \dotsb + 1)^n - (-1 + 1 + \dotsb + 1)^n) &= \frac{m^n - (m - 2)^n}{2} \end{align*}$

There are $m$ letters that could be odd, so for one letter an odd number of times is:

$\begin{align*} \binom{m}{1} \frac{m^n - (m - 2)^n}{2} \end{align*}$

For the general case, if any $r$ letters appear an odd number of times each, by a similar argument you get:

$\begin{align*} N_r &= \binom{m}{r} \frac{m^n - (m - 2 r)^n}{2} \end{align*}$

Plugging this into the expression for $e_k$ above:

$\begin{align*} e_k &= \sum_r (-1)^{r - k} \binom{k}{r} N_r \\ &= \sum_r (-1)^{r - k} \binom{k}{r} \binom{m}{r} \frac{m^n - (m - 2 r)^n}{2} \end{align*}$

No much hope to simplify this much further...

Answer 3

Thank you all for your answers and your comments. Each of them is very helpful!

Caprikuarius and vonbrand, your formulas base on a generalisation of the problem, allowing also letters whose parity doesn't matter. I think that this generalisation is very helpful, many thanks.

I apologize to use my old notation: Let $n$ be the total number of letters and $r$ be the length of the words in question. Let $F(n,r,k)$ be the number of words that contain the first $k$ letters an odd number of times and the latter $n-k$ letters an even number of times.

---

First of all, I shortly repeat the trick with multinomial coefficients of vonbrand:

• $\frac12 \big((z_1 + \dots + z_n)^r + ((-z_1) + \dots + z_n)^r\big)(1,\dots,1)$ is the number of words, such that $1$ appears an even number of times.

• $\frac12 \big((z_1 + \dots + z_n)^r - ((-z_1) + \dots + z_n)^r\big)(1,\dots,1)$ is the number of words, such that $1$ appears an odd number of times.

---

Basing on this trick, I tried to use a general "symmetrisation" of these expressions. For an example, suppose $n = k = 2$. By duplicating the formula above and by setting $(-z_2)$ instead of $z_2$ in the duplicate, we get \begin{align*} F(2,r,2) &= \frac14 \big([(z_1 + z_2)^r - ((-z_1) + z_2)^r] - [(z_1 + (-z_2))^r - ((-z_1) + (-z_2))^r]\big)(1,\dots,1). \end{align*}

Following this principle of nesting, we get in general

\begin{align*} F(n,r,k) &= \frac{1}{2^n} \left[\sum_{(a_1,\dots,a_n) \in \{0,1\}^n} (-1)^{a_1}\cdot \ldots \cdot (-1)^{a_k} \, \cdot \, \big((-1)^{a_1}z_1 + \ldots + (-1)^{a_n}z_n\big)^r\right](1,\dots,1)\\ &= \frac{1}{2^n} \sum_{(a_1,\dots,a_n) \in \{0,1\}^n} (-1)^{a_1}\cdot \ldots \cdot (-1)^{a_k} \, \cdot \, \big((-1)^{a_1} + \ldots + (-1)^{a_n}\big)^r. \end{align*} Reformulating this formula, we finally get

\begin{align*} F(n,r,k) &= \frac{1}{2^n} \sum_{m = 0}^k\sum_{l = 0}^{n-k} (-1)^m\binom{k}{m}\binom{n-k}{l}\, \big(n - 2(m+l)\big)^r. \end{align*}

The formula should be correct, as it can be proven that it meets the requirements.

---

To compare, we have $e_k = \binom{n}{k} \cdot F(n,r,k)$, where $e_k$ (cf. vonbrand) is the number of words that contain exactly $k$ letters an odd number of times.

In particular, I wonder whether this equation holds with the formula of vonbrand.

At a first glance, it seems not to be the case, since for $n = r = k = 2$, we have $F(2,2,2) = 2$ (which is correct), but $e_2 = -8 \neq \binom{2}{2} \cdot F(2,2,2)$, where \begin{align*} e_k = \sum_{m = 0}^{n}(-1)^{m - k}\binom{k}{m}\binom{n}{m}\frac{n^r - (n-2m)^r}{2}. \end{align*}

---

The formula should also have the following recursive properties: \begin{align*} F(n,r+1,k) = \begin{cases} k\cdot F(n,r,k-1) + (n-k)\cdot F(n,r,k+1), & 1 \leq k \leq n-1,\\ n\cdot F(n,r,n-1), & k = n,\\ n\cdot F(n,r,1), & k = 0.\\ \end{cases} \end{align*} This can be seen as follows: A letter which is added at the $(r+1)$-th position changes its parity. By way of example, if the parity of letter $m$ is even in a word with $r-1$ letters, then it gets odd by adding the lettern $m$ on the $(r+1)$-th position. Since there are $k$ letters in total which are odd, there are $k$ possibilities to choose $m$ as the letter whose parity was even "before".

---