combinatorics: number of words


by techmologist
Tags: combinatorics, number, words
techmologist
techmologist is offline
#1
Mar19-09, 04:47 PM
P: 254
ere me now.

I'm trying to figure out how many words of length r having exactly k distinct letters can be made with an alphabet of size n. Call this number a_k,r. It satisfies the recursion

[tex]a_{k,r} = ka_{k,r-1} + (n-k+1)a_{k-1,r-1}[/tex]

[tex]a_{1,r} = n[/tex] for r >= 1
[tex]a_{k,r} = 0[/tex] for r < k

My best effort so far is to use a generating function as follows

[tex]f_k(x) = \sum_{r=1}^{\infty}a_{k,r}x^r[/tex]

and use the recursion formula to get

[tex]f_k(x) = \frac{(n-k+1)x}{1-kx}f_{k-1}(x) = \frac{x^{k-1}(n-1)(n-2)...(n-k+1)}
{(1-x)(1-2x)...(1-kx)}f_1(x)[/tex]

or since f_1(x) = n/(1-x),

[tex]f_k(x) = \frac{(k-1)!\left(^n_{k-1} \right)x^{k-1}}{(1-x)(1-2x)...(1-kx)}[/tex]

I'm having a well difficult time getting the coefficient of x^r (which would be a_k,r) in the expansion of this. Is there a way to simplify it so you don't have k nested sums? thanks.
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
ThirstyDog
ThirstyDog is offline
#2
Mar19-09, 05:56 PM
P: 34
I am trying to follow your approach and the f's confuse me: the problem I have is that
[tex] f_{k}(1) = \sum_{r=1}^{\infty} a_{k,r} \geq 1, [/tex]
but by your recursion relation we have
[tex] \frac{f_{k}(1)}{f_{k-1}(1)} = \frac{n-k+1}{1-k}. [/tex]
The right hand side must be positive while the left must be negative. This means either I have misunderstood something or you have...

I am sure some combinatorist has got a simply answer for this... but pending them stating what it is here is a way to at least reduce the problem.

First find how many ways to pick k distinct letters from the alphabet with n letters (order of picking not important). Consider these letters as a sub-alphabet.

From this sub-alphabet you will need to create words that are length r and use every letter. If you find this number then you can multiply by the previous to obtain the answer.

Please tell me if you find a simple answer and\or which one of us made the mistake.
techmologist
techmologist is offline
#3
Mar20-09, 08:15 PM
P: 254
Yes, the series expansion for the f_k's is only valid for |x| < 1/k. But
your suggested way of doing it is a lot better. For an alphabet of k letters,
the number b_k,r of r-letter words which have all k letters is k^r minus the number
of words in which at least one of the letters is absent. I calculated the
latter using the sieve principle as

# of r-letter words missing at least 1 of the k letters =


[tex]\left( ^{k}_{1} \right)(k-1)^r - \left( ^{k}_{2} \right)(k-2)^r +...+
(-1)^{k}\left( ^{k}_{k-1} \right)
= \sum_{j=1}^{k-1}(-1)^{j-1}\left( ^{k}_{j} \right)(k-j)^r[/tex]

Then subtracting this from k^r gives

[tex]b_{k,r} =\sum_{j=0}^{k-1}(-1)^{j}\left( ^{k}_{j} \right)(k-j)^r [/tex]

As you said, to generalize this to n > k letters in the alphabet, multiply
b_k,r by choose(n,k) to get

[tex]a_{k,r} = \left( ^{n}_{k} \right)b_{k,r}[/tex]

For the special case k = r, this should simplify to


[tex]a_{r,r} = r!\left( ^{n}_{r} \right)[/tex]

I've been trying to verify by induction that

[tex]\sum_{j=0}^{r-1}(-1)^{j}\left( ^{r}_{j} \right)(r-j)^r = r![/tex]
but I can't seem to do it. It seems to be true though, if you plug in small
numbers for r. Thanks for the tip! At least I'm making progress now. If you know of a way to simplify the above answer further, please show it.

Eero
Eero is offline
#4
Mar21-09, 06:08 AM
P: 10

combinatorics: number of words


[tex]\sum_{j=0}^{r-1}(-1)^{j}\\( ^{r}_{j} \\)(r-j)^r = r![/tex]

This expression is easy to prove by considering the r-th derivative
of (1-e^x)^r at x=0
techmologist
techmologist is offline
#5
Mar21-09, 11:01 PM
P: 254
Quote Quote by Eero View Post
[tex]\sum_{j=0}^{r-1}(-1)^{j}\\( ^{r}_{j} \\)(r-j)^r = r![/tex]

This expression is easy to prove by considering the r-th derivative
of (1-e^x)^r at x=0
Very cool. Thanks :)


Register to reply

Related Discussions
Simple Combinatorics: What are odds of picking same number? General Math 5
Combinatorics Precalculus Mathematics Homework 5
combinatorics Calculus & Beyond Homework 7
combinatorics Introductory Physics Homework 7
Combinatorics Introductory Physics Homework 3