Find the number of combination of 'n' together of '3n' letters
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Find the number of ways of selecting n letters from 3n letters which contains 'n' a s , 'n' b s and the rest n letters are distinct from each other.
From the language of the problem I can easily understood that we need to select n letters.
I will categorize it into three category using
$C(n,r) = fracn!(n-r)!r!$
I will use $C(n, r_1)*C(n, r_2)*C(n, r_3)$,
$ r_1$ =a group, $ r_2$ =b group & $ r_3$ =unlike group
Where $ r_1+ r_2 + r_3 =n$ I presume that i am on the right approach but I am not able to proceed hence forth.
combinatorics permutations
 |Â
show 10 more comments
up vote
1
down vote
favorite
Find the number of ways of selecting n letters from 3n letters which contains 'n' a s , 'n' b s and the rest n letters are distinct from each other.
From the language of the problem I can easily understood that we need to select n letters.
I will categorize it into three category using
$C(n,r) = fracn!(n-r)!r!$
I will use $C(n, r_1)*C(n, r_2)*C(n, r_3)$,
$ r_1$ =a group, $ r_2$ =b group & $ r_3$ =unlike group
Where $ r_1+ r_2 + r_3 =n$ I presume that i am on the right approach but I am not able to proceed hence forth.
combinatorics permutations
1
Not sure this is clear. What does "$n$ together of $3n$ letters" mean? Also, what does "the rest unlike" mean? Do you mean that the rest are neither $a$ nor $b$ or do you mean that the rest are all distinct (presumably from $a,b$ and from each other)? Perhaps you could work the problem explicitly for, say, $n=2$ to illustrate what you have in mind.
â lulu
Aug 19 at 11:35
I copied the question from a source using copy and paste option. What i understood that we have to select n letters from 3n letters which has n a n b and n different letters.
â Samar Imam Zaidi
Aug 19 at 11:37
I already framed the formula and then from that step forward I am not able to solve it
â Samar Imam Zaidi
Aug 19 at 11:39
Perhaps it is a translation issue....that phrasing doesn't sound like it was written by an English speaker. Nor do I understand your formula. As I say, it would help if you would write out the case of $n=2$ explicitly...to illustrate your view of the question, if nothing else.
â lulu
Aug 19 at 11:40
@lulu Suppose n=2, We have a,a,b,b,c,d. Then what is the number of ways of selecting two letters
â Samar Imam Zaidi
Aug 19 at 11:41
 |Â
show 10 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Find the number of ways of selecting n letters from 3n letters which contains 'n' a s , 'n' b s and the rest n letters are distinct from each other.
From the language of the problem I can easily understood that we need to select n letters.
I will categorize it into three category using
$C(n,r) = fracn!(n-r)!r!$
I will use $C(n, r_1)*C(n, r_2)*C(n, r_3)$,
$ r_1$ =a group, $ r_2$ =b group & $ r_3$ =unlike group
Where $ r_1+ r_2 + r_3 =n$ I presume that i am on the right approach but I am not able to proceed hence forth.
combinatorics permutations
Find the number of ways of selecting n letters from 3n letters which contains 'n' a s , 'n' b s and the rest n letters are distinct from each other.
From the language of the problem I can easily understood that we need to select n letters.
I will categorize it into three category using
$C(n,r) = fracn!(n-r)!r!$
I will use $C(n, r_1)*C(n, r_2)*C(n, r_3)$,
$ r_1$ =a group, $ r_2$ =b group & $ r_3$ =unlike group
Where $ r_1+ r_2 + r_3 =n$ I presume that i am on the right approach but I am not able to proceed hence forth.
combinatorics permutations
edited Aug 19 at 11:47
asked Aug 19 at 11:31
Samar Imam Zaidi
1,180316
1,180316
1
Not sure this is clear. What does "$n$ together of $3n$ letters" mean? Also, what does "the rest unlike" mean? Do you mean that the rest are neither $a$ nor $b$ or do you mean that the rest are all distinct (presumably from $a,b$ and from each other)? Perhaps you could work the problem explicitly for, say, $n=2$ to illustrate what you have in mind.
â lulu
Aug 19 at 11:35
I copied the question from a source using copy and paste option. What i understood that we have to select n letters from 3n letters which has n a n b and n different letters.
â Samar Imam Zaidi
Aug 19 at 11:37
I already framed the formula and then from that step forward I am not able to solve it
â Samar Imam Zaidi
Aug 19 at 11:39
Perhaps it is a translation issue....that phrasing doesn't sound like it was written by an English speaker. Nor do I understand your formula. As I say, it would help if you would write out the case of $n=2$ explicitly...to illustrate your view of the question, if nothing else.
â lulu
Aug 19 at 11:40
@lulu Suppose n=2, We have a,a,b,b,c,d. Then what is the number of ways of selecting two letters
â Samar Imam Zaidi
Aug 19 at 11:41
 |Â
show 10 more comments
1
Not sure this is clear. What does "$n$ together of $3n$ letters" mean? Also, what does "the rest unlike" mean? Do you mean that the rest are neither $a$ nor $b$ or do you mean that the rest are all distinct (presumably from $a,b$ and from each other)? Perhaps you could work the problem explicitly for, say, $n=2$ to illustrate what you have in mind.
â lulu
Aug 19 at 11:35
I copied the question from a source using copy and paste option. What i understood that we have to select n letters from 3n letters which has n a n b and n different letters.
â Samar Imam Zaidi
Aug 19 at 11:37
I already framed the formula and then from that step forward I am not able to solve it
â Samar Imam Zaidi
Aug 19 at 11:39
Perhaps it is a translation issue....that phrasing doesn't sound like it was written by an English speaker. Nor do I understand your formula. As I say, it would help if you would write out the case of $n=2$ explicitly...to illustrate your view of the question, if nothing else.
â lulu
Aug 19 at 11:40
@lulu Suppose n=2, We have a,a,b,b,c,d. Then what is the number of ways of selecting two letters
â Samar Imam Zaidi
Aug 19 at 11:41
1
1
Not sure this is clear. What does "$n$ together of $3n$ letters" mean? Also, what does "the rest unlike" mean? Do you mean that the rest are neither $a$ nor $b$ or do you mean that the rest are all distinct (presumably from $a,b$ and from each other)? Perhaps you could work the problem explicitly for, say, $n=2$ to illustrate what you have in mind.
â lulu
Aug 19 at 11:35
Not sure this is clear. What does "$n$ together of $3n$ letters" mean? Also, what does "the rest unlike" mean? Do you mean that the rest are neither $a$ nor $b$ or do you mean that the rest are all distinct (presumably from $a,b$ and from each other)? Perhaps you could work the problem explicitly for, say, $n=2$ to illustrate what you have in mind.
â lulu
Aug 19 at 11:35
I copied the question from a source using copy and paste option. What i understood that we have to select n letters from 3n letters which has n a n b and n different letters.
â Samar Imam Zaidi
Aug 19 at 11:37
I copied the question from a source using copy and paste option. What i understood that we have to select n letters from 3n letters which has n a n b and n different letters.
â Samar Imam Zaidi
Aug 19 at 11:37
I already framed the formula and then from that step forward I am not able to solve it
â Samar Imam Zaidi
Aug 19 at 11:39
I already framed the formula and then from that step forward I am not able to solve it
â Samar Imam Zaidi
Aug 19 at 11:39
Perhaps it is a translation issue....that phrasing doesn't sound like it was written by an English speaker. Nor do I understand your formula. As I say, it would help if you would write out the case of $n=2$ explicitly...to illustrate your view of the question, if nothing else.
â lulu
Aug 19 at 11:40
Perhaps it is a translation issue....that phrasing doesn't sound like it was written by an English speaker. Nor do I understand your formula. As I say, it would help if you would write out the case of $n=2$ explicitly...to illustrate your view of the question, if nothing else.
â lulu
Aug 19 at 11:40
@lulu Suppose n=2, We have a,a,b,b,c,d. Then what is the number of ways of selecting two letters
â Samar Imam Zaidi
Aug 19 at 11:41
@lulu Suppose n=2, We have a,a,b,b,c,d. Then what is the number of ways of selecting two letters
â Samar Imam Zaidi
Aug 19 at 11:41
 |Â
show 10 more comments
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
You've already provided the answer in a comment: $(n+2)2^n-1$.
Here's an algebraic proof: There are $k+1$ ways to select $k$ a's and b's, and then there are $binom nk$ ways to choose the distinct letters you don't select. Thus the desired count is
begineqnarray*
sum_k=0^n(k+1)binom nk
&=&
left[fracpartialpartial qsum_k=0^nbinom nkq^k+1right]_q=1
\
&=&
left[fracpartialpartial qleft(q(1+q)^nright)right]_q=1
\
&=&
2^n+n2^n-1;.
endeqnarray*
Here's a combinatorial proof: The selections without b's correspond to the $2^n$ subsets of the $n$ distinct letters. (Add the right number of a's to such a subset, and you get a unique selection without b's.) Now consider the selections with at least one b. Each contains a proper subset $S$ of the $n$ distinct letters, and the number of elements not contained in $S$ is the number of choices for the non-zero number of b's to add. Thus, the choice of the non-zero number of b's corresponds to distinguishing one of the distinct letters not contained in $S$. Thus, the selections with at least one b are in bijection with the ways to distinguish one of the distinct letters ($n$ choices) and to choose a subset of the remaining distinct letters ($2^n-1$ choices). Hence the total number of selections is $2^n+n2^n-1$.
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
You've already provided the answer in a comment: $(n+2)2^n-1$.
Here's an algebraic proof: There are $k+1$ ways to select $k$ a's and b's, and then there are $binom nk$ ways to choose the distinct letters you don't select. Thus the desired count is
begineqnarray*
sum_k=0^n(k+1)binom nk
&=&
left[fracpartialpartial qsum_k=0^nbinom nkq^k+1right]_q=1
\
&=&
left[fracpartialpartial qleft(q(1+q)^nright)right]_q=1
\
&=&
2^n+n2^n-1;.
endeqnarray*
Here's a combinatorial proof: The selections without b's correspond to the $2^n$ subsets of the $n$ distinct letters. (Add the right number of a's to such a subset, and you get a unique selection without b's.) Now consider the selections with at least one b. Each contains a proper subset $S$ of the $n$ distinct letters, and the number of elements not contained in $S$ is the number of choices for the non-zero number of b's to add. Thus, the choice of the non-zero number of b's corresponds to distinguishing one of the distinct letters not contained in $S$. Thus, the selections with at least one b are in bijection with the ways to distinguish one of the distinct letters ($n$ choices) and to choose a subset of the remaining distinct letters ($2^n-1$ choices). Hence the total number of selections is $2^n+n2^n-1$.
add a comment |Â
up vote
1
down vote
accepted
You've already provided the answer in a comment: $(n+2)2^n-1$.
Here's an algebraic proof: There are $k+1$ ways to select $k$ a's and b's, and then there are $binom nk$ ways to choose the distinct letters you don't select. Thus the desired count is
begineqnarray*
sum_k=0^n(k+1)binom nk
&=&
left[fracpartialpartial qsum_k=0^nbinom nkq^k+1right]_q=1
\
&=&
left[fracpartialpartial qleft(q(1+q)^nright)right]_q=1
\
&=&
2^n+n2^n-1;.
endeqnarray*
Here's a combinatorial proof: The selections without b's correspond to the $2^n$ subsets of the $n$ distinct letters. (Add the right number of a's to such a subset, and you get a unique selection without b's.) Now consider the selections with at least one b. Each contains a proper subset $S$ of the $n$ distinct letters, and the number of elements not contained in $S$ is the number of choices for the non-zero number of b's to add. Thus, the choice of the non-zero number of b's corresponds to distinguishing one of the distinct letters not contained in $S$. Thus, the selections with at least one b are in bijection with the ways to distinguish one of the distinct letters ($n$ choices) and to choose a subset of the remaining distinct letters ($2^n-1$ choices). Hence the total number of selections is $2^n+n2^n-1$.
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
You've already provided the answer in a comment: $(n+2)2^n-1$.
Here's an algebraic proof: There are $k+1$ ways to select $k$ a's and b's, and then there are $binom nk$ ways to choose the distinct letters you don't select. Thus the desired count is
begineqnarray*
sum_k=0^n(k+1)binom nk
&=&
left[fracpartialpartial qsum_k=0^nbinom nkq^k+1right]_q=1
\
&=&
left[fracpartialpartial qleft(q(1+q)^nright)right]_q=1
\
&=&
2^n+n2^n-1;.
endeqnarray*
Here's a combinatorial proof: The selections without b's correspond to the $2^n$ subsets of the $n$ distinct letters. (Add the right number of a's to such a subset, and you get a unique selection without b's.) Now consider the selections with at least one b. Each contains a proper subset $S$ of the $n$ distinct letters, and the number of elements not contained in $S$ is the number of choices for the non-zero number of b's to add. Thus, the choice of the non-zero number of b's corresponds to distinguishing one of the distinct letters not contained in $S$. Thus, the selections with at least one b are in bijection with the ways to distinguish one of the distinct letters ($n$ choices) and to choose a subset of the remaining distinct letters ($2^n-1$ choices). Hence the total number of selections is $2^n+n2^n-1$.
You've already provided the answer in a comment: $(n+2)2^n-1$.
Here's an algebraic proof: There are $k+1$ ways to select $k$ a's and b's, and then there are $binom nk$ ways to choose the distinct letters you don't select. Thus the desired count is
begineqnarray*
sum_k=0^n(k+1)binom nk
&=&
left[fracpartialpartial qsum_k=0^nbinom nkq^k+1right]_q=1
\
&=&
left[fracpartialpartial qleft(q(1+q)^nright)right]_q=1
\
&=&
2^n+n2^n-1;.
endeqnarray*
Here's a combinatorial proof: The selections without b's correspond to the $2^n$ subsets of the $n$ distinct letters. (Add the right number of a's to such a subset, and you get a unique selection without b's.) Now consider the selections with at least one b. Each contains a proper subset $S$ of the $n$ distinct letters, and the number of elements not contained in $S$ is the number of choices for the non-zero number of b's to add. Thus, the choice of the non-zero number of b's corresponds to distinguishing one of the distinct letters not contained in $S$. Thus, the selections with at least one b are in bijection with the ways to distinguish one of the distinct letters ($n$ choices) and to choose a subset of the remaining distinct letters ($2^n-1$ choices). Hence the total number of selections is $2^n+n2^n-1$.
answered Aug 19 at 14:38
joriki
165k10180331
165k10180331
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2887615%2ffind-the-number-of-combination-of-n-together-of-3n-letters%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
Not sure this is clear. What does "$n$ together of $3n$ letters" mean? Also, what does "the rest unlike" mean? Do you mean that the rest are neither $a$ nor $b$ or do you mean that the rest are all distinct (presumably from $a,b$ and from each other)? Perhaps you could work the problem explicitly for, say, $n=2$ to illustrate what you have in mind.
â lulu
Aug 19 at 11:35
I copied the question from a source using copy and paste option. What i understood that we have to select n letters from 3n letters which has n a n b and n different letters.
â Samar Imam Zaidi
Aug 19 at 11:37
I already framed the formula and then from that step forward I am not able to solve it
â Samar Imam Zaidi
Aug 19 at 11:39
Perhaps it is a translation issue....that phrasing doesn't sound like it was written by an English speaker. Nor do I understand your formula. As I say, it would help if you would write out the case of $n=2$ explicitly...to illustrate your view of the question, if nothing else.
â lulu
Aug 19 at 11:40
@lulu Suppose n=2, We have a,a,b,b,c,d. Then what is the number of ways of selecting two letters
â Samar Imam Zaidi
Aug 19 at 11:41