Combinatorics Homework: Calculating Possible Combinations with Set A and B

[iScience]

Homework Statement

set {A} : 26 elements <--- let's call this number n

set {B}: 24 elements <--- let's call this number m

goal: i want to know the number of possible combinations i will have if i start by replacing one element in {A} with an element in {B}, then i want to know the number of possible combinations of elements i can have if i replace two elements in {A} with any two elements in {B}. i want to do this all the way up to 24 replacements.

Homework Equations

this is what I'm trying to ultimately find.

The Attempt at a Solution

1 replacement: $$ n*m$$
(since the number of elements you can replace in set A is n, and for each replaced element, there are m possible numbers in B you can replace them with)

2 replacements: $$n!(n-1)!*m(m-1)$$
(the n terms on the left deal with the placement of the A elements getting replaced. ie how many different ways can you arrange two elements throughout {A}

$$a_{1}a_{2}$$
$$a_{1}a_{3}$$
$$a_{1}a_{4}$$
$$...$$
$$a_{1}a_{n}$$
...
$$a_{2}a_{3}$$
$$a_{2}a_{4}$$
$$a_{2}a_{5}$$
etc..

and the m terms on the left: basically after you pick a b_element for any particular arrangement, you have now have b-1 elements to choose from.
)

m replacements: $$ n!(n-1)!(n-2)!(n-3)!...(n-m)!*m(m-1)(m-2)(m-3)...(1) = Π(n-i)!*m!$$

i'm very suspicious of my answer because it yields numbers that seem too big to be true

 

[haruspex]

I don't understand how you are getting products of factorials. The sets are unordered, no? E.g. For 2 swaps, you just want the number of pairs you can select from each set.

 

[Ray Vickson]

Homework Statement

set {A} : 26 elements <--- let's call this number n

set {B}: 24 elements <--- let's call this number m

goal: i want to know the number of possible combinations i will have if i start by replacing one element in {A} with an element in {B}, then i want to know the number of possible combinations of elements i can have if i replace two elements in {A} with any two elements in {B}. i want to do this all the way up to 24 replacements.

Homework Equations

this is what I'm trying to ultimately find.

The Attempt at a Solution

1 replacement: $$ n*m$$
(since the number of elements you can replace in set A is n, and for each replaced element, there are m possible numbers in B you can replace them with)

2 replacements: $$n!(n-1)!*m(m-1)$$
(the n terms on the left deal with the placement of the A elements getting replaced. ie how many different ways can you arrange two elements throughout {A}

$$a_{1}a_{2}$$
$$a_{1}a_{3}$$
$$a_{1}a_{4}$$
$$...$$
$$a_{1}a_{n}$$
...
$$a_{2}a_{3}$$
$$a_{2}a_{4}$$
$$a_{2}a_{5}$$
etc..

and the m terms on the left: basically after you pick a b_element for any particular arrangement, you have now have b-1 elements to choose from.
)

m replacements: $$ n!(n-1)!(n-2)!(n-3)!...(n-m)!*m(m-1)(m-2)(m-3)...(1) = Π(n-i)!*m!$$

i'm very suspicious of my answer because it yields numbers that seem too big to be true

For two replacements, you want to swap pairs from A with pairs from B, so the number you want should be $N_2 = C(n,2) C(m,2)$, where $C(a,b)$ is the binomial coefficient "a choose b". Thus, you should have $N_2 = n(n-1) m(m-1)/4$. Your computation counted the choices from A and B way too many times.

For $k$ interchanges, you want to swap all possible $k$-tuples from A and B.

 

[iScience]

I don't understand how you are getting products of factorials. The sets are unordered, no? E.g. For 2 swaps, you just want the number of pairs you can select from each set.

Thus, you should have N2=n(n−1)m(m−1)/4N_2 = n(n-1) m(m-1)/4. Your computation counted the choices from A and B way too many times.

i think i see why you wrote the n terms that way; perhaps this might clear things up. with the n terms, which deal with the placements of the b terms, I'm trying to find the number of combinations of a terms. like this:

$$a_{1}a_{2}$$
$$a_{1}a_{3}$$
$$a_{1}a_{4}$$
...
$$a_{1}a_{n}$$

$$a_{2}a_{3}$$
$$a_{2}a_{4}$$
$$a_{2}a_{5}$$
...
$$a_{2}a_{n}$$

$$a_{3}a_{4}$$
$$a_{3}a_{5}$$
$$a_{3}a_{6}$$
...
$$a_{3}a_{n}$$

$$a_{n-1}a_{n}$$

i need to count each of these separately. so not just any a term and another a term (in which case i can see how n(n-1) would appear)

so maybe..

first set: (n-1) terms

second set: (n-2) terms

...$$\Sigma{(n-i)} (i: 1~(n-1))$$
would this be more correct?in case i misunderstood you, and the above was actually that you were calculating.. how are you getting a factor of n(n-1)/4 for the n terms??

 

[Ray Vickson]

i think i see why you wrote the n terms that way; perhaps this might clear things up. with the n terms, which deal with the placements of the b terms, I'm trying to find the number of combinations of a terms. like this:

$$a_{1}a_{2}$$
$$a_{1}a_{3}$$
$$a_{1}a_{4}$$
...
$$a_{1}a_{n}$$

$$a_{2}a_{3}$$
$$a_{2}a_{4}$$
$$a_{2}a_{5}$$
...
$$a_{2}a_{n}$$

$$a_{3}a_{4}$$
$$a_{3}a_{5}$$
$$a_{3}a_{6}$$
...
$$a_{3}a_{n}$$

$$a_{n-1}a_{n}$$

i need to count each of these separately. so not just any a term and another a term (in which case i can see how n(n-1) would appear)

so maybe..

first set: (n-1) terms

second set: (n-2) terms

...$$\Sigma{(n-i)} (i: 1~(n-1))$$
would this be more correct?in case i misunderstood you, and the above was actually that you were calculating.. how are you getting a factor of n(n-1)/4 for the n terms??

I just used well-known results: the number of pairs of the form $a_i a_j$, with $i < j$, is just $C(n,2)$.

This assumes---as you do---that order does not matter, so we only count $a_1 a_2$ and $a_2 a_1$ once, not twice. This is because when dealing with sets, the order does not matter.

There are similar formulas for finding the number of distinct $k$-tuples $a_{i_1} a_{i_2} \ldots a_{i_k}$ with $1 \leq i_1 < i_2 < \cdots < i_k \leq n$, assuming all the $a_i$ are different (so we don't have sets "with repetitions"). I am surprised that your textbook does not have this formula; it is just the formula for the number of subsets of cardinality $k$ in a set of cardinality $n$. Anyway, it is available on-line; see, eg., http://cims.nyu.edu/~kiryl/teaching/dm/les070103.pdf .

 

[iScience]

thanks for the site.

but I'm still having trouble understanding the combination/permutation formulas.i looked at the derivations for them and it still doesn't make sense to me.

combination formula:
$$C(n,r) = \frac{n!}{r!(n-r)!}$$

say we have an n choose r situation ie just the combination, where n=5, r=3.

what are the number of possible sets we can make with three elements from five values?

if i do this: $$n(n-1)(n-2)(n-3)$$

i'm doing the following: take any element from the five values, and put it in the first element, take any remaining value and stick it in the second element, and etc.

so here lies my confusion; while doing n*(n-1)(n-2)...etc i see nothing in this method that restricts you to put the first chosen value in the first element. you could have just as well put the first chosen value in the second or third element. and the freedom to do that would imply that it's a set right? so why divide by r! ?

what am i missing?

 

[Ray Vickson]

thanks for the site.

but I'm still having trouble understanding the combination/permutation formulas.i looked at the derivations for them and it still doesn't make sense to me.

combination formula:
$$C(n,r) = \frac{n!}{r!(n-r)!}$$

say we have an n choose r situation ie just the combination, where n=5, r=3.

what are the number of possible sets we can make with three elements from five values?

if i do this: $$n(n-1)(n-2)(n-3)$$

i'm doing the following: take any element from the five values, and put it in the first element, take any remaining value and stick it in the second element, and etc.

so here lies my confusion; while doing n*(n-1)(n-2)...etc i see nothing in this method that restricts you to put the first chosen value in the first element. you could have just as well put the first chosen value in the second or third element. and the freedom to do that would imply that it's a set right? so why divide by r! ?

what am i missing?

You are double-counting, or worse.

For A = {1,2,3,4,5}, how many subsets of size 2 are there? List them all:
12, 13, 14, 15, 23, 24, 25, 34, 35, 45---10 altogether. Note that 10 = 5*4/2 = C(5,2). In your count "5*4 = 20" you have listed each pair twice; once as 'ab' and again as 'ba'.

What are the subsets of size 3? Here they are:
123, 124, 125, 134, 135, 145, 234, 235, 245, 345---10 altogether. Again, 10 = 5*4*3/(3*2) = C(5,3). In your count "5*4*3 = 60" you have counted each triple 6 times; for example, you have counted each of the choices 123, 132, 213, 231, 312, 321 separately, but they are really only one subset and so should not be counted separately.

 

[iScience]

i get it!

thanks ray