Words With 2 N

How many type of words through $2n$ letters deserve to be produced if I have an alphabet with $n$ letters and each of the letters need to happen precisely twice in the word, however no 2 consecutive letters are equal?

Thanks!


*

*

There is no easy closed formula for this (I think no recognized closed formula at all), but one deserve to provide a formula as a amount by making use of inclusion-exclusion.

You watching: Words with 2 n

First think about such orderings wright here the pairs of similar letters are distinguishable. Then $displaystyle sum_k=0^n (-1)^k2^k(2n-k)!inomnk$ provides the variety of such such orderings by inclusion-exemption (tbelow are $(2n-k)!$ ways for $k$ given pairs to be together (by merging the those pairs right into single elements) and the remainder arbitrarily ordered, $2^k$ ways to order within those offered pairs, and $inomnk$ methods to pick those $k$ pairs). By splitting by $2^n$ to remove the ordering of pairs of the same facets we can obtain the formula $displaystyle frac12^nsum_k=0^n (-1)^k2^k(2n-k)!inomnk$.


Share
Cite
Follow
answered Nov 25 "13 at 12:52
*

universalsetuniversalset
7,9891717 silver badges3131 bronze badges
$endgroup$
Add a comment |
1
$egingroup$
As mentioned in the comments, this sequence appears in the OEIS (A114938), and is a unique situation of an extra general result discovered somewhere else on this site (e.g., right here and here).

The OEIS gives the outcome as a sum:$$A_n=sum_k=0^nfrac(-1)^n-k(n+k)!2^knchoosek\=frac12^nsum_k=0^n(-2)^k(2n-k)!nchoosek,$$where the second variation is acquired from the initially by changing $k ightarrow n-k$ in the summation. To derive this from the even more general expression, we write$$A_n=int_0^infty (q_2(x))^n , exp(-x),dx,$$wbelow $$q_2(x) = sum_i=1^2 frac(-1)^2-ii! 2-1 choose i-1x^i=frac12x(x-2);$$so$$A_n=frac12^nint_0^inftyx^n(x-2)^ne^-xdx=frac12^nsum_k=0^n(-2)^knchoosekint_0^inftyx^2n-ke^-xdx,$$wbelow the binomial growth was used to $(-2+x)^n$. Because one can conveniently examine that $int_0^inftyx^a e^-xdx=a!$ (by repetitive integration by parts, for instance), the two expressions coincide.

See more: Montage Book Review S - The Falling In Love Montage


Share
Cite
Follow
edited Apr 13 "17 at 12:21
*

Community♦
1
answered Nov 25 "13 at 16:27
*

mjqxxxxmjqxxxx
36.5k22 gold badges4545 silver badges9797 bronze badges
$endgroup$
Add a comment |
0
$egingroup$
initially of all if you desire to discover the variety of words in which no two same letters are equal then it is identical to findingthe full variety of words that have the right to be made with the letters minus the variety of words in which consecutive letters are existing.

you can quickly discover the total words that have the right to be made via the letters to be $$frac2n!(2!)^n$$currently to find the no. of words that in which letters are consecutive.

initially think about a pair $xx$ is created in the word with no other exact same aspects consecutive. Consider the set $xx$ as a solitary facet which is cost-free to traverse to any kind of position in between the remaining $2n-2$ elements.

then the set $xx$ have the right to be put in any kind of of the easily accessible $2n-1$ positions.At the exact same time the remaining $2n-2$ aspects can itself be rearranged $frac(2n-2)!(2!)^n-1$

therefore the complete no. of ways a pair of letters have the right to end up being consecutive is$$frac(2n-2)!*(2n-1)(2!)^n-1$$$$= frac(2n-1)!(2!)^n-1$$currently extend this for even more variety of sets from $1$ to $n$.

you will certainly find the last answer foras $k$ runs from $1$ $ o$ $n$ is$$ frac2n!(2!)^n-sum frac(2n-k)!(2!)^n-k$$