Turning an informal proof about palindromes into a formal proof

Question

No. of dots: $k$

No. of slots: $n$

If the dots are placed in every combination within the slots, how many palindromes will there be? The dots cannot be superimposed on each other, which means $k \lt n$.

$$n,k,x,y \in \Bbb N$$

$$\text{No. palindromes} = \begin{cases} \displaystyle {n \div 2 \choose \ k \div 2}, & n = 2x, \ k = 2y \\[2ex] \displaystyle{\lfloor n \div 2 \rfloor\choose k \div 2}, & n = 2x +1, \ k = 2y \\[2ex] \displaystyle{\lfloor n \div 2 \rfloor \choose \lfloor k \div 2\rfloor}, & n = 2x +1, \ k = 2y + 1 \\[2ex] 0, & n =2x, \ k = 2y +1 \end{cases}$$

This is what I've got. I'm pretty sure it's correct, but I have no formal proof. I think I have an informal proof:

For a combination of dots in the slots to make a palindrome, the two halves of the string of slots must be mirror images. That means we're dealing with the halves of $n$ and $k$, as for every arrangement of dots there is on one half of the string, there is only one possible arrangement on the other half (that arrangement being the mirror image). As such, if both $n$ and $k$ are even, the number of palindromes will be equal $n/2 \choose k/2$.

If $n$ is odd, but $k$ is even, then none of the dots may take the central slot. This is because it would then mean an uneven number of dots $2y -1$ would be distributed over an even number of slots $2x +1 -1$. In such a case, there will always be one more or one less on one of the halves. As such, no dot can be placed in the central slot. This reduced the amount of available slots from $n/2$ to $(n-1)/2$ or just $\lfloor n/2 \rfloor$. That means the number of palindromes in this case is $\lfloor n/2 \rfloor \choose k/2$.

If both $n$ and $k$ are odd, then a dot must occupy the central slot. That removes both a slot and a dot from the previously odd number of slots and dots (respectively), meaning we're left with an even number of dots distributed onto an even number of slots. Thus, the number of palindromes is $\lfloor n/2 \rfloor \choose \lfloor k/2 \rfloor$.

If $n$ is even but $k$ is odd, then there is no central slot to remove a dot, meaning there are no palindromes.

If this is correct, how can I make it into a formal proof? If it is incorrect, where did I go wrong?

EDIT: Forgot to add the rule that the dots cannot overlap. There can never be $3$ dots distributed over $2$ slots.

Answer 1

My take would be to talk about $n$-bit strings that are palindromes containing $k$ ones. Now to become more formal, let: $$ P_{(n,k)} $$ denote the number of $n$-bit strings that are palindromes containing $k$ ones. Now consider the parities of $n$ or $k$, and observe that we have (given $k\leq n$): $$ \begin{align} P_{(2x,2y)}&=\binom xy\\ P_{(2x+1,2y)}&=P_{(2x,2y)}\\ P_{(2x+1,2y+1)}&=P_{(2x,2y)}\\ P_{(2x,2y+1)}&=0\\ \end{align} $$ by the arguments you already gave. Note how this notation suggests that the two cases in the middle actually reduce to the first case. Reductions are always to your benefit, since then you do not have to solve the same subproblem again!

Answer 2

In general, when we want to prove a formula about the size of a set, $S,$ we

1. First want a good formal definition of the set, $S,$ and then
2. Find a bijection between that set and a set that is easier to count.

---

Definition: A (binary) word of length $n$ is a function $f:\{1,2,\dots,n\}\to\{0,1\}.$

The weight if a binary word is the number of values $i$ which go to $1.$ Formally $w(f)=|\{i\mid f(i)=1\}|.$

A palindrome is a binary word $p$ of length $n$ such that $p(i)=p(n+1-i)$ for all $i\in \{1,2,\dots, n\}.$

Let $P_{n,k}$ be the palindromes of length $n$ and weight $k.$

Show: If $p$ is a palindrome of even length $n$ and weight $k,$ then $k$ must be even.

So, for $P_{n,k}$ not empty, at least one of $k,n-k$ must be even.

Now, if $k,n-k$ are not both odd, consider the set:

$$T_{n,k}=\{S\subseteq\{1,2,\dots,\lfloor n/2\rfloor\mid |S|=\lfloor k/2\rfloor\}$$

We define a bijection $\phi:P_{n,k}\to T_{n,k}.$ Specifically: $$\phi(p)=\{i\in\{1,\dots,\lfloor n/2\rfloor\}\mid p(i)=1\}$$

Proving this is a bijection takes two cases, when $k$ is odd, or when $k$ is even. This is really the heart of your proof.

But we know $$|T_{n,k}|=\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor}$$ so this is the value of $|P_{n,k}|.$

---

Another approach is to show a bijection:

$$P_{n,k}\cup P_{n,k-2}\to P_{n+2,k}.$$ If we think of palindromes written as strings, then this amounts to sending $p\in P_{n,k}$ to $0p0$ and $p\in P_{n,k-2}$ to $1p1.$

This gives a recursive formula for $|P_{n,k}|,$ which lets you prove your formula inductive, starting with $n=1,2$ and then inductive show that if true for $n,$ then true for $n+2.$

---

If we consider alphabets of more letters, then we need to replace "weight" with "signature."

A word of length $n$ in an $m$-letter alphabet is a function $f:\{1,\dots,n\}\to \{0,\dots,m-1\}.$ Palindromes of this sort are defined the same. The signature of a word is defined as a tuple $(n_0,n_1,dots,n_{m-1})$ which counts the number of occurrences each letter in the word. Necessarily, $\sum n_i=n.$

Given a signature $(n_i)$ of non-negative integers and $n=\sum n_i,$ the number of palindromes with signature $(n_i)$ is zero if more than one $n_i$ is odd, and otherwise computed as a multinomial $$\binom{\lfloor n/2\rfloor}{\lfloor n_0/2\rfloor,\dots,\lfloor n_{m-1}/2\rfloor}$$

---

This displays why the way of looking at it in terms of the parity of $k$ and $n-k,$ rather $k,n,$ is the heart of the thing. In any palindrome with any size alphabet, you can have at most one letter occur an odd number of times.