The number of ways of selection of $n$ things out of $3n$ things of which $n$ are of one kind alike and $n$ are of second type alike and rest are different: Options are  A) $n2^{n-1}$  B) $(n+2)2^{n-1}$  I want a detailed solution.
124091
No. of ways to choose $n$ things from $n$ alike "a" things $n$ alike "b" things and $n$ different things.  Answer is $(n+2)2^{n-1}$. But how to prove it..?
27551
I was going through .Suppose that there are n persons who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as his/her number. Let us assume that the first person takes hat i. There are n − 1 ways for the first person to make such a choice. There are now two possibilities, depending on whether or not person i takes hat 1 in return:  A) Person i does not take the hat 1. This case is equivalent to solving the problem with n − 1 persons and n − 1 hats: each of the remaining n − 1 people has precisely 1 forbidden choice from among the remaining n − 1 hats (i's forbidden choice is hat 1).  B) Person i takes the hat 1. Now the problem reduces to n − 2 persons and n − 2 hats.  From this, the following relation is derived: !n = (n - 1) (!(n-1) + !(n-2))  I have a hard time understanding point B and the equation derived. I was trying to understand with an example of 4 people named A, B, C and D and the corresponding hats A, B, C and D. Everyone of them are supposed to wear any hat except their own matching hat i.e. A can wear B, C or D.  If suppose A wears B hat so we will be left with only 3 people and 3 hats. So I can understand "(n-1)!(n-1)" part but what i didn't understand is part B(marked above). Can anyone help?
8071
I have tried to solve it for the case when $n=1,2,3,4$ which i found that there is only one group for $n=1$, one group for $n=2,$ one group for$ n=3 $ and two groups for $ n=4$, then my question come, if i were given a number $n$ which is larger, how do i know how many different groups are there?  (I treat two isomorphic groups as the same group in this question.)
38222
An exercise in the first chapter of Discrete Mathematics, Elementary and Beyond asks for a proof of the following identity:   $$ {n \choose 2} + {n+1 \choose 2} = n^2 $$  The algebraic solution is obvious to me, but less so the combinatorial logic. I think the right-hand side relates to choosing one of n elements twice in a row to produce a set of two elements, including the possibility of duplicate elements (for instance, one could choose the nth element twice in a row). However, given that the sets discussed thus far do contain duplicate elements, it's odd to then interpret n^2 as a representation of such a set. I'm not too sure what the two parts of the left side mean when taken together, either. How can I think about this intuitively based on the combinatorial meanings of the individual terms?
41538
What is the number of ways to select ten distinct letters from the alphabet $\{a, b, c, \ldots, z\}$, if no two consecutive letters can be selected?   There are a couple of formulas that I could use, but I am not sure how to use them.     The number of combinations of a given length that use elements from a given set, allowing repetition and with no missing elements in other words, each element of the given set occurs at least once in each combination: $\binom{k-1}{n-1}$ where where $n$ is the number of elements in the given set and $k$ is the length of the combination.   OR     The number of combinations of a given length that use elements from a given set, allowing repetition: $\binom{n+k-1}{n-1}=\binom{n+k-1}{k}$ where $n$ is number of elements in the given set and $k$ is the length of the combination.   Please help me understand what I should do and how to go about solving this question?
38682
Find the number of permutations in $S_n$ such as 1 and 2 belong to one cycle.
40571
I pick a random subset $S$ of $\{1,\ldots,N\}$, and you have to guess what it is. After each guess $G$, I tell you the number of elements in $G \cap S$. How many guesses do you need?
29781
I have the following problem: A class has 20 students, 16 females, 4 males. Find all possibilities of choosing 6 students so that at least one is male.  I did the following, pick one male from the 4, you have 4 possibilities, then you are left with 19 students, pick 5, so I get 4*${19}\choose{5}$ possibilities.  However, one can notice that if you want no one to be male, then the possibilities are ${16}\choose{6}$, so, one could argue that the solution is instead ${20}\choose{6}$ - ${16}\choose{6}$.  So, which is solution is correct, and why?  $$4* {{19}\choose{5}}$$  or $${{20}\choose{6}} - {{16}\choose{6}}$$
2521
Let's have 2 numbers, N and K, where K divides N. The number of K-combinations from a given set S of N elements is a well known formula. Let's concatenate N/K groups (resulting in N elements) such as the resulting set is N. How many possibilities are there, i.e. what's the formula?  For instance:    N=4, K=2, C(4, 2) = 6 {1,2},{1,3},{1,4},{2,3},{2,4},{3,4}   The 3 possibilities are:     {1,2},{3,4}   {1,3},{2,4}   {1,4},{2,3}   I generated these combinations and I think the number goes like this:  (4, 2): 3 (6, 3): 10 (6, 2): 15 (10, 5): 126 (9, 3): 280 (10, 2): 945 (14, 7): 1716 (12, 4): 5775 (15, 5): 126126 (15, 3): 1401400   Apparently, the result always divides with (N-1).
64845
In how many ways can we choose $r$ numbers from $\{1,2,3,...,n\}$,   In a way where we have no consecutive numbers in the set? (like $1,2$)
81042
let $n \gt 1$ be an integer, and consider $n$ people; $P_1, P_2,..., P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people  determine $A_1, A_2, A_3$  So I have  $A_1 = 1$ way $A_2 = 4$ way $A_3 = 12$ way  But I am not sure if this is right... Can anyone confirm?  edit:  My way of getting this is  $A_1 = 1 $ because {P1} only has 1 way to sort  $A_2 = 4$ because {P1,P2} = {P1,P2},{P2,P1},{P1P2},{P2P1}  etc.
119731
I am mainly confused about my reasoning/solution  Problem: I have a bag of numbers ranging from $1,2... n$. I randomly choose a number and then I throw out all numbers less than that. Then I keep choosing numbers until I've found the largest one. What's the expected number of things I have chosen?  My Argument: I expect on average to have chosen a number of $n/2$ on each pick. Hence, everytime I choose a number, I expect to discard half of them. Hence, the $E(X) = \log_2(n)$  Note that I devised this problem as an equivalent one while trying to solve the "cluster of cars on one long road" question. If this is not equivalent, please let me know but I am confident that it is. As a result of this equivalency, I know my solution is incorrect. However, I cannot pinpoint where the issue arises.
29506
says that the number of different monomials of degree $M$ in $N$ variables is $$\frac{(M+N-1)!}{M!(N-1)!}\; .$$ Can anyone explain why this is true?
30844
If $n$ distinct things are arranged in a circle, then what are the number of ways selecting three of these things so that no two of them are next to each other?
56753
Assume that there are $n$ people line up to get into $m$ different clubs. How many ways to do it if each people is different and order of people in the line matters.  Sol. Clearly, each people has $m$ different choices for clubs. So there are $m^n$ ways of choosing clubs. Now we count number of different lines. Let $x_i$ be the number of people lining to get to the club $i$, $1 \leq i \leq m$, $x_i \geq 0$.  Then $$x_1 + x_2 + ... + x_m = n$$ with $x_i$ non-negative integers. So there are ${m+n-1}\choose{n-1}$ ways, ignore order in each line. So there are ${m+n-1}\choose{n-1}$$ x_1!x_2!...x_n!$ possible lines.  The answer is weird since it is in $x_1, ...,x_n$ terms, and I think it is wrong. However, I am not sure how to fix it.  Any help please ?
47902
How do I calculate the number of options for $k$ different balls in $n$ cells, with at least $1$ ball in each cell?   Lets say $6$ different balls in $3$ different cells, with at least $1$ ball in each cell.   like this:  $$x_1+x_2+x_3 = 6$$  I would like to see an explanation please and not just the answer.  Thanks!
11846
Fix $n\in P$. In how many ways (as a function of n) can one choose a composition $\alpha$ of n, and then choose a composition of each part of $\alpha$?