Finding Permutations with Repetitions: n, x, a, b, c, d

[Big-Daddy]

Homework Statement

I have n elements, of which I take x and arrange them, with repetitions allowed (i.e. if one of my elements is A, and x=3, then {A,A,A} would be an acceptable permutation). Among the original n elements is the letter A, present a times, and the letter B, present b times; of these, I have selected among my x, the letter A c times, and the letter B d times. Of my x elements now, how many permutations are there? Assume the other elements are present only once each in n.

Homework Equations

nPr=n!/(n-r)!
nCr=n!((n-r)!r!)
Permutations with repetition = x^x

The Attempt at a Solution

I'm thinking something like C(n-a-b,x-c-d) to account for the number of ways to choose, multiplied by (x-c-d+2)^x to account for perms. But I could be on the completely wrong track here.

 

[Ray Vickson]

Homework Statement

I have n elements, of which I take x and arrange them, with repetitions allowed (i.e. if one of my elements is A, and x=3, then {A,A,A} would be an acceptable permutation). Among the original n elements is the letter A, present a times, and the letter B, present b times; of these, I have selected among my x, the letter A c times, and the letter B d times. Of my x elements now, how many permutations are there? Assume the other elements are present only once each in n.

Homework Equations

nPr=n!/(n-r)!
nCr=n!((n-r)!r!)
Permutations with repetition = x^x

The Attempt at a Solution

I'm thinking something like C(n-a-b,x-c-d) to account for the number of ways to choose, multiplied by (x-c-d+2)^x to account for perms. But I could be on the completely wrong track here.

I'm not sure I understand what *you* mean by permutations. For example, the string AAA can be considered as having just one permutation (thinking in the usual way) or as having six permutations (if we regard the three 'A's as being distinguished---for example, by painting them different colors). So, would you count that as one or as six?

 

[Big-Daddy]

I'm not sure I understand what *you* mean by permutations. For example, the string AAA can be considered as having just one permutation (thinking in the usual way) or as having six permutations (if we regard the three 'A's as being distinguished---for example, by painting them different colors). So, would you count that as one or as six?

No, the three A's are indistinguishable. What I'm saying is, let's say we have a set {a,b,c,d,e} and want to find the number of ways to arrange 3 of these, with repetition, from this set. Then we're looking at everything from {a,a,a} to {a,a,b} to {a,b,a}, through to the end. How many arrangements are there? Simply 3⁵ (number of spaces to be filled ^ number of elements to fill the spaces). Because repetition is allowed, we use ^ rather than the usual ! with factorials.

The problem I asked is trickier and I can't answer because there are also indistinguishable elements. i.e. not only can I have {a} as many times as I want (up to my x, which is 3 in this case: {a,a,a}) in my solution, but it is actually present in the original set multiple times and is indistinguishable.

 

[Ray Vickson]

No, the three A's are indistinguishable. What I'm saying is, let's say we have a set {a,b,c,d,e} and want to find the number of ways to arrange 3 of these, with repetition, from this set. Then we're looking at everything from {a,a,a} to {a,a,b} to {a,b,a}, through to the end. How many arrangements are there? Simply 3⁵ (number of spaces to be filled ^ number of elements to fill the spaces). Because repetition is allowed, we use ^ rather than the usual ! with factorials.

The problem I asked is trickier and I can't answer because there are also indistinguishable elements. i.e. not only can I have {a} as many times as I want (up to my x, which is 3 in this case: {a,a,a}) in my solution, but it is actually present in the original set multiple times and is indistinguishable.

You spoke of two different versions: in your OP you mentioned A and B plus others, but in your response you mentioned only A plus others. So, let's take this last case: you want to choose n things (I use n instead of x), of which you can have repeated A's and other singly-chosen things. Presumably you are allowed to have all A's or none, so you need at least n distinct "others" (because if you do not have any A's you need all n others to be distinct). So, assume there are m >= n distinct "others". The answer will actually depend on the specific value of m, so if we fix n and have two different m's we will have two different answers. (That makes sense, since if I choose one thing from a set of m distinct things, the number of choices will be m---the larger m, the more possibilities.)

What is the number of different choices of k A's and (n-k) others? Using C(a,b) and P(a,b) to denote numbers of combinations or permutations of b things from a set of a things, we have that the number we want is f(n,k) = C(n,k)*P(m,n-k). To see this, note that C(n,k) is the number of different strings of the form AOAAOO... consisting of k A's and n-k O's. For each such string there are P(m,n-k) permutations of the n-k "others" to fill the spaces occupied by O's.

Finally, the total number of different choices is the sum of the f(n,k) for k from 0 to n. I don't think this has any nice closed-form formula involving elementary functions. For example, Maple 11 obtains the sum as
$$\frac{m! \,e^{-1/2}}{ (m-n)! (m+1-n)} \left[ (m+1) W\left(\frac{m+n}{2},\frac{1+m-n}{2},1\right) - (n-1) W\left(1-\frac{m+n}{2},\frac{1+m-n}{2},1\right) \right]$$
where $W$ is a so-called Whittaker M-function.

Your other problem, where you allow both multiple A's and B's can be done similarly.

 

[Big-Daddy]

You spoke of two different versions: in your OP you mentioned A and B plus others, but in your response you mentioned only A plus others. So, let's take this last case: you want to choose n things (I use n instead of x), of which you can have repeated A's and other singly-chosen things. Presumably you are allowed to have all A's or none, so you need at least n distinct "others" (because if you do not have any A's you need all n others to be distinct). So, assume there are m >= n distinct "others". The answer will actually depend on the specific value of m, so if we fix n and have two different m's we will have two different answers. (That makes sense, since if I choose one thing from a set of m distinct things, the number of choices will be m---the larger m, the more possibilities.)

What is the number of different choices of k A's and (n-k) others? Using C(a,b) and P(a,b) to denote numbers of combinations or permutations of b things from a set of a things, we have that the number we want is f(n,k) = C(n,k)*P(m,n-k). To see this, note that C(n,k) is the number of different strings of the form AOAAOO... consisting of k A's and n-k O's. For each such string there are P(m,n-k) permutations of the n-k "others" to fill the spaces occupied by O's.

Finally, the total number of different choices is the sum of the f(n,k) for k from 0 to n. I don't think this has any nice closed-form formula involving elementary functions. For example, Maple 11 obtains the sum as
$$\frac{m! \,e^{-1/2}}{ (m-n)! (m+1-n)} \left[ (m+1) W\left(\frac{m+n}{2},\frac{1+m-n}{2},1\right) - (n-1) W\left(1-\frac{m+n}{2},\frac{1+m-n}{2},1\right) \right]$$
where $W$ is a so-called Whittaker M-function.

Your other problem, where you allow both multiple A's and B's can be done similarly.

Huh. I am not even sure if we're talking about the same problem anymore! Let me re-express.

My final goal is to solve the following:

A word has n letters, in which one of those letters is present a times and another is present b times (all other letters are present only once). How many arrangements of x letters are there from this word, allowing repetitions of the letters in the arrangements?

If we did not allow repetitions of the letters in the arrangements (so the basic form of the permutation is n!/(n-r)!, i.e. P(n,r)) then this would be expressed by Ʃ(s=0 to b)Ʃ(r=0 to a) of (C(n-a-b,x-r-s)*(x!(r!s!))). What the purpose of this thread is, is to find a function f(n,a,b,x,r,s) such that Ʃ(s=0 to a)Ʃ(r=0 to b) of f(n,a,b,x,r,s) represents the solution to my new problem. Thus, I need to work out how many arrangements there are of the x letters, when among them r letters (out of x) are that which was originally present a times (out of n), and s letters (out of x) are that which was originally present b times (out of n).

I introduced the problem here originally: https://www.physicsforums.com/showthread.php?t=689756 solving two simpler cases. However the help appears to have run out when I moved to this one!

I don't need an elementary formula. A sum is perfectly fine and my final goal. However I do not believe it is as simple as you suggest to write f(n,a,b,x,r,s). (Change the notation if you wish but be aware of the context of the problem - n is the total number of elements whereas x is the number we are choosing from n and then arranging, such that x≤n; similarly r≤a, s≤b)

 

[Ray Vickson]

Huh. I am not even sure if we're talking about the same problem anymore! Let me re-express.

My final goal is to solve the following:

A word has n letters, in which one of those letters is present a times and another is present b times (all other letters are present only once). How many arrangements of x letters are there from this word, allowing repetitions of the letters in the arrangements?

If we did not allow repetitions of the letters in the arrangements (so the basic form of the permutation is n!/(n-r)!, i.e. P(n,r)) then this would be expressed by Ʃ(s=0 to b)Ʃ(r=0 to a) of (C(n-a-b,x-r-s)*(x!(r!s!))). What the purpose of this thread is, is to find a function f(n,a,b,x,r,s) such that Ʃ(s=0 to a)Ʃ(r=0 to b) of f(n,a,b,x,r,s) represents the solution to my new problem. Thus, I need to work out how many arrangements there are of the x letters, when among them r letters (out of x) are that which was originally present a times (out of n), and s letters (out of x) are that which was originally present b times (out of n).

I introduced the problem here originally: https://www.physicsforums.com/showthread.php?t=689756 solving two simpler cases. However the help appears to have run out when I moved to this one!

I don't need an elementary formula. A sum is perfectly fine and my final goal. However I do not believe it is as simple as you suggest to write f(n,a,b,x,r,s). (Change the notation if you wish but be aware of the context of the problem - n is the total number of elements whereas x is the number we are choosing from n and then arranging, such that x≤n; similarly r≤a, s≤b)

OK, I think I get it now. We have N (you called it n) objects, of which 'a' are A and 'b' are B and the remaining c = N-a-b are unique elements (others). We select n (you called it x) elements, and want to know the total number of different arrangements.

To start, let $f(k_a,k_b)$ be the number of arrangements in which we have k_a A's and k_b B's (the rest being "others"). We have
$$f(k_a,k_b) = C(n,k_a)C(n-k_a,k_b)P(c,n-k_a-k_b), \; 0 \leq k_a \leq a, 0 \leq k_b \leq b, k_a+k_b \leq n, k_a + k_b \geq n-c$$
We need to sum this over all allowed $k_a, k_b.$

 

[Big-Daddy]

OK, I think I get it now. We have N (you called it n) objects, of which 'a' are A and 'b' are B and the remaining c = N-a-b are unique elements (others). We select n (you called it x) elements, and want to know the total number of different arrangements.

To start, let $f(k_a,k_b)$ be the number of arrangements in which we have k_a A's and k_b B's (the rest being "others"). We have
$$f(k_a,k_b) = C(n,k_a)C(n-k_a,k_b)P(c,n-k_a-k_b), \; 0 \leq k_a \leq a, 0 \leq k_b \leq b, k_a+k_b \leq n, k_a + k_b \geq n-c$$
We need to sum this over all allowed $k_a, k_b.$

Thanks for the response.

This looks good. How would we extend it if there were 3 repeated elements (a, b, c, each with k_a, k_b and k_c selected in your n)? c=N-a-b-c, the restraints all just add +k_c, k_c≤c. The bit that confuses me is what to do with $$C(n,k_a)C(n-k_a,k_b)$$ to incorporate more repeated elements.

 

[Ray Vickson]

Thanks for the response.

This looks good. How would we extend it if there were 3 repeated elements (a, b, c, each with k_a, k_b and k_c selected in your n)? c=N-a-b-c, the restraints all just add +k_c, k_c≤c. The bit that confuses me is what to do with $$C(n,k_a)C(n-k_a,k_b)$$ to incorporate more repeated elements.

Just use the "multinomial coefficient"
$${n \choose k_1,k_2, \ldots, k_r} = \frac{n!}{k_1! k_2! \cdots k_r!},\:( k_1 + k_2 + \cdots + k_r = n)$$
which is the number of combinations of $k_1$ things of type 1, $k_2$ things of type 2, etc., and $k_r$ things of type r, chosen from a set of $n$ things, and where we have $k_1 + k_2 + \cdots + k_r = n$. It is also equal to the number of distinct strings containing $k1$ A1's $k_2$ A2's, etc, up to $k_r$ Ar's (that is, strings of type A1A1A3A2A2A3A1A3A3... A1). You can prove this for yourself by using the ordinary binomial successively: There are C(n,k_1) strings of k_1 A1's and n-k_1 others. Then, among the n-k_1 places for the others, there are C(n-k_1,k_2) ways of placing k+2 A2's, etc. This gives you C(n,k_1)*C(n-k_1,k_2)*C(n-k_1-k)2,k_3)... . When you expand this out you get the multinomial.

 

[Big-Daddy]

Just use the "multinomial coefficient"
$${n \choose k_1,k_2, \ldots, k_r} = \frac{n!}{k_1! k_2! \cdots k_r!},\:( k_1 + k_2 + \cdots + k_r = n)$$
which is the number of combinations of $k_1$ things of type 1, $k_2$ things of type 2, etc., and $k_r$ things of type r, chosen from a set of $n$ things, and where we have $k_1 + k_2 + \cdots + k_r = n$. It is also equal to the number of distinct strings containing $k1$ A1's $k_2$ A2's, etc, up to $k_r$ Ar's (that is, strings of type A1A1A3A2A2A3A1A3A3... A1). You can prove this for yourself by using the ordinary binomial successively: There are C(n,k_1) strings of k_1 A1's and n-k_1 others. Then, among the n-k_1 places for the others, there are C(n-k_1,k_2) ways of placing k+2 A2's, etc. This gives you C(n,k_1)*C(n-k_1,k_2)*C(n-k_1-k)2,k_3)... . When you expand this out you get the multinomial.

Ah now I see! So we might just write our final function:

$$f(k_a,k_b) = \frac{n!}{k_a! k_b!} P(c,n-k_a-k_b), \; 0 \leq k_a \leq a, 0 \leq k_b \leq b, k_a+k_b \leq n, k_a + k_b \geq n-c$$

Then sum over all k_a, k_b, and that's that?

This is directly analogous to the general solution for permutations with repetitions not allowed, in which case the solution was (using your notation):

$$f(k_a,k_b) = \frac{n!}{k_a! k_b!} C(c,n-k_a-k_b), \; 0 \leq k_a \leq a, 0 \leq k_b \leq b, k_a+k_b \leq n, k_a + k_b \geq n-c$$

 

[Ray Vickson]

Ah now I see! So we might just write our final function:

$$f(k_a,k_b) = \frac{n!}{k_a! k_b!} P(c,n-k_a-k_b), \; 0 \leq k_a \leq a, 0 \leq k_b \leq b, k_a+k_b \leq n, k_a + k_b \geq n-c$$

Then sum over all k_a, k_b, and that's that?

This is directly analogous to the general solution for permutations with repetitions not allowed, in which case the solution was (using your notation):

$$f(k_a,k_b) = \frac{n!}{k_a! k_b!} C(c,n-k_a-k_b), \; 0 \leq k_a \leq a, 0 \leq k_b \leq b, k_a+k_b \leq n, k_a + k_b \geq n-c$$

No: f(k_a,k_b) is not what you wrote in your first expression (you can check for yourself if the second one is OK); the correct expression would be
$$f(k_a,k_b) = \frac{n!}{k_a! k_b! (n-k_a-k_b)!} P(c,n-k_a-k_b).$$ We get other (n-ka-kb)! in the denominator because we really have three types: A, B and other, so in the notation of my previous post k_3 = n - k_a - k_b. This is really no different from saying that that the number of combinations involving k A's and (n-k) others is n!/[k! (n-k)!]; we need both k! and (n-k)! in the denominator. Roughly speaking, the factorialants in the denominator must add up to the numerator.

 

[Big-Daddy]

No: f(k_a,k_b) is not what you wrote in your first expression (you can check for yourself if the second one is OK); the correct expression would be
$$f(k_a,k_b) = \frac{n!}{k_a! k_b! (n-k_a-k_b)!} P(c,n-k_a-k_b).$$ We get other (n-ka-kb)! in the denominator because we really have three types: A, B and other, so in the notation of my previous post k_3 = n - k_a - k_b. This is really no different from saying that that the number of combinations involving k A's and (n-k) others is n!/[k! (n-k)!]; we need both k! and (n-k)! in the denominator. Roughly speaking, the factorialants in the denominator must add up to the numerator.

Obviously if

$$\frac{n!}{k_a! k_b! (n-k_a-k_b)!}$$

is what we are looking at then inevitably n=n-k_a-k_b+k_a+k_b=n. That's not an approximation, it's clear from the formulation. Am I correct in thinking this is an exact count? And, if we had three repeated elements a, b and c, we could easily rewrite it:

$$f(k_a,k_b,k_c) = \frac{n!}{k_a! k_b! k_c! (n-k_a-k_b-k_c)!} P(N-a-b-c,n-k_a-k_b-k_c).$$

making it clear how the formula could be expressed for any number of repeated elements.

 

[Ray Vickson]

Obviously if

$$\frac{n!}{k_a! k_b! (n-k_a-k_b)!}$$

is what we are looking at then inevitably n=n-k_a-k_b+k_a+k_b=n. That's not an approximation, it's clear from the formulation. Am I correct in thinking this is an exact count? And, if we had three repeated elements a, b and c, we could easily rewrite it:

$$f(k_a,k_b,k_c) = \frac{n!}{k_a! k_b! k_c! (n-k_a-k_b-k_c)!} P(N-a-b-c,n-k_a-k_b-k_c).$$

making it clear how the formula could be expressed for any number of repeated elements.

Yes, you've got it. The quantity $n!/[k_a! k_b! k_c! (n-k_a-k_b-k_c)!]$ is the number of ways of putting k_a A's, k_b B's, k_c C's into n boxes and thus leaving (n-k_a - k_b - k_c) empty boxes into which all the unique "others" will go.

 

[Big-Daddy]

Yes, you've got it. The quantity $n!/[k_a! k_b! k_c! (n-k_a-k_b-k_c)!]$ is the number of ways of putting k_a A's, k_b B's, k_c C's into n boxes and thus leaving (n-k_a - k_b - k_c) empty boxes into which all the unique "others" will go.

Thanks very much for guiding me through this.

Can we look at a fourth and final variant on the problem?

A word has N letters, in which one of those letters is present a times and another is present b times (all other letters are present only once). How many combinations of n letters are there from this word, allowing repetitions of the letters in the selection?

This is analogous to the problem we've just been working with, except it uses combinations rather than permutations. If we take k_a letters from the one with a and k_b letters from the one with b, and we get f(k_a,k_b) (using your notation) then we just need to sum that over all values of k_a and k_b from 0 to a and 0 to b respectively.