2
$\begingroup$

I've been struggling with the following exercise:

Find the number of sequences of length $2n$ that can be formed with digits from set $A={1,2, ... ,n}$ where every digit has to appear exactly twice in the sequence and no two adjacent elements are alike.

I know that I must use inclusion/exclusion formula, but I don't know exactly how. I am able to count the total number of such sequences, neglecting that the adjacent digits mustn't be the same. What should I do next? I can't fit it to the inclusion/exclusion formula.

Thanks for help in advance!

$\endgroup$
  • $\begingroup$ Take the number of all possible sequences minus the number of those that are not allowed. The set of not allowed ones can be written as the union of several sets. So to count the not allowed sequences you can use inclusion-exclusion. $\endgroup$ – S. M. Roch Mar 19 '18 at 17:20
  • 1
    $\begingroup$ What is the source of this problem? A near duplicate appeared a while ago. $\endgroup$ – lulu Mar 19 '18 at 17:21
  • $\begingroup$ I've seen a "duplicate" but isn't this solution too long and troublesome? $\endgroup$ – mrrobot1337 Mar 19 '18 at 17:23
  • $\begingroup$ Give me an example of some elements that are in this union you are talking about. I thought It'll be easier to just count those that are not allowed straight. Like get the number of places, on which we can put two congruent elements, then multiply it by number of elements we can choose from, then place any elements in the places that are left. That would give us the number of "restricted" sequences $\endgroup$ – mrrobot1337 Mar 19 '18 at 17:27
  • $\begingroup$ Please identify the source of the problem. When duplicate problems of this sort show up in close order, it frequently means that the question is taken from an ongoing competition or exam. $\endgroup$ – lulu Mar 19 '18 at 17:28
3
$\begingroup$

Each admissible $f:\>[2n]\to[n]$ induces a pairing of $[2n]$ whereby no two adjacent numbers are paired. Denote by ${\cal P}_n$ the set and by $a_n$ the number of such unlabeled pairings of $[2n]$. Given a $w\in{\cal P}_n$ there are $n!$ functions $f:\>[2n]\to[n]$ inducing this $w$, hence there are $n!\, a_n$ admissible functions in all.

In order to determine the $a_n$ I set up a certain generating function scheme, and with the help of Mathematica arrived at the following table: $$(a_n)_{1\leq n\leq10}\quad=\quad (0, 1, 5, 36, 329, 3655, 47844, 721315, 12310199, 234615096)\ .$$ This sequence is listed in OEIS under A278990 and A000806; the second of these is mentioning the problem at hand. In the first reference one finds without proof the following simple recursion for the $a_n$: $$a_1=0,\qquad a_2=1,\qquad a_n=(2n-1)a_{n-1}+a_{n-2}\ .\tag{1}$$ The rest of this answer is devoted to a selfcontained combinatorial proof of $(1)$.

enter image description here

We represent the pairings $w$ as rows of $2n$ colored balls, whereby the colors just serve to identify the pairs and are not to be interpreted as function values. Consider a $w\in{\cal P}_n$ with the leftmost ball red. We distinguish three cases (see the figure):

(i) The second red ball is between two balls of different colors or at the end of the row. In this case we can remove the two red balls and obtain an admissible $w'\in{\cal P}_{n-1}$. Conversely: Given any admissible $w'\in{\cal P}_{n-1}$ we can prepend it by a red ball and insert the second red ball after any of the $2n-2$ balls in $w'$. The result is a $w\in{\cal P}_n$ of the type considered here.

(ii) The second red ball is between two balls of the same color (say blue), whereby there is a ball of a third color immediately to the right of the first red ball. In this case we remove the two blue balls and obtain an admissible $w'\in{\cal P}_{n-1}$. Conversely: Given any admissible $w'\in{\cal P}_{n-1}$ with the leftmost ball red we can place two blue balls immediately to the left and the right of the second red ball. The result is a $w\in{\cal P}_n$ of the type considered here. (This brings us from $2n-2$ to $2n-1$ on the RHS of $(1)$.)

(iii) The arrangement $w$ starts with two interlaced pairs red/blue/red/blue. In this case we remove these four balls and obtain an admissible $w'\in{\cal P}_{n-2}$. Conversely: Given any admissible $w'\in{\cal P}_{n-2}$ we can prepend it with a quadruple red/blue/red/blue and obtain a $w\in{\cal P}_n$ of the type considered here. (This accounts for the last term on the RHS of $(1)$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.