Hot answers tagged

6

The question can be rephrased as: How many different sums $n_a+n_b+n_c+n_d+n_e+n_f+n_g=5$ are there for nonnegative integers $n_a,n_b,n_c,n_d,n_e,n_f,n_g$? E.g. possibility $2+0+1+1+1+0+0=5$ corresponds with word "aacde". This can be solved with stars and bars.


4

The second method does not take care of the fact that items are distinct. Assume items are $A,B,C,D,E,F$ In the second method, you counted $(1,5)$ as just one. In fact, it can be $A~~(B,C,D,E,F)\\ B~~(A,C,D,E,F)\\ C~~(A,B,D,E,F)\\ D~~(A,B,C,E,F)\\ E~~(A,B,C,D,F)\\ F~~(A,B,C,D,E)$ i.e., this (1,5) alone can happen in 6 different ways. Each of the other ...


4

$$\binom{2^n-1}{k} = \frac{(2^n-1)(2^n-2)(2^n-3)\cdots(2^n-k)}{1\cdot 2\cdot 3\cdots k} $$ and $2^n-a$ is divisible by exactly as many factors of $2$ as $a$ is. This means that every factor of $2$ in the numerator is matched by a factor of $2$ in the denominator. After cancelling those, what's left in the numerator must be an odd number, and you can't get ...


3

Your first method correctly counts the number of ways of distributing six different things to the two boys. Your second method is wrong because it does not take account of the fact that the items are different. Your second method (if you do it correctly) would give the number of ways of dividing six identical things between two people. (I think with the ...


3

For the first part or your question: Write $b=a+1+i$ and $c=(a+1+i)+1+j=a+2+i+j$ where $i,j\ge0$. Then $$a+b+c=a+(a+1+i)+(a+2+i+j)=3a+2i+j+3,$$ and you can restate the question as the number of solutions to $$3a+2i+j=n-3$$ where $a,i,j\ge0$. This is the coefficient of $x^{n-3}$ in $$\underbrace{(1+x^3+x^6+\cdots)}_{\text{contribution of } a}\cdot\...


3

Expanding $(x+y)(x+y)(x+y)$ amounts to adding up all the ways you can pick three factors to multiply together. For example, you could pick an $x$ from the first $(x+y)$, a $y$ from the second $(x+y)$, and another $x$ from the third $(x+y)$ to get $xyx=x^2 y$. You are right, the only possible products we can get are $x^3$, $x^2 y$, $xy^2$, and $y^3$. However,...


3

You can just go through the various partitions of $5$: $$\{5\},\{4,1\},\{3,2\},\{3,1,1\},\{2,2,1\},\{2,1,1,1\},\{1,1,1,1,1\}$$ and work out the choices for each; respectively: $$7, 7\cdot 6, 7\cdot 6, 7 {6\choose 2}, 7{6\choose 2}, 7 {6\choose 3},{7\choose 5}$$ and add those possibilities together. Alternatively you can think of placing 6 "...


3

Kummers theorem: The maximum power of the prime $p$ that divides $\binom{n}{k}$ is equal to the number of carries when adding $n-k$ and $k$ in base $p$. Clearly if $a$ and $b$ add up to $111\dots 1$ in binary there can't be any carries, since the digit in the position of the first carry is always $0$.


3

As each box must have at least two balls, let them first be filled with two balls each. Then, we have five balls left. The ways in which five can be expresses as the sum of three non-negative integers (where order does not matter) are: $$5+0+0$$ $$4+1+0$$ $$3+2+0$$ $$3+1+1$$ $$2+2+1$$ Each represents a way in which the remaining balls can be put into the ...


3

Select one of the $5$ non-particular students who will stand to the left of the rightmost particular student, and one of the remaining $4$ non-particular students who will stand to the right of the leftmost particular student. Permute the remaining $6$ students in $6!$ ways and place the two preselected non-particular students as planned, for a total of $5\...


2

See Lucas's theorem on binomial coefficients. More generally, for any prime $p$, $\displaystyle {{p^n-1} \choose k}$ is never divisible by $p$ when $0 \le k \le p^n-1$.


2

Have you heard of the binary number system? It is like decimal but for cool kids. Basically the numbers that can be formed in the way you are asking using $2^0,2^1\dots 2^n$ are precisely $\{0,1,2,\dots ,2^{n+1}-1\}$. Lets prove it: The proof is by induction. The base case is trivial, clearly the combinations of $\{1\}$ are $\{0,1\}$. Inductive step: We ...


2

As Gerry Myerson pointed out in the comment, it is an application of Hall's theorem. The statement in terms of systems of distinct representatives is the following: Given a universe $U$ of $n$ elements and a collection of $n$ sets, we want to pick one element from each set so that all elements are covered. Then a sufficient condition is that the union of any ...


2

HINT: If you remove the edge $\{1,2\}$ from such a tree, you get a pair of trees, the subtrees rooted at $1$ and at $2$; call these $T_1$ and $T_2$. You can split the remaining three vertices, $3,4$, and $5$, arbitrarily between $T_1$ and $T_2$. For $k=0,1,2,3$, how many ways are there to assign $k$ of these three vertices to $T_1$ (and the rest to $T_2$)? ...


2

Do you mean different or distinct items ? First you gave the solution for different and then you find the one for distinct. The last option is again a stars and bars exercise ! Here, it is theorem 2 with n = 6 and k = 2 , then we get ${\tbinom {n+k-1}{k-1}} = {\tbinom {7}{1}} = 7$ When you write that the number of choices is $2^6$ for only distinct items, ...


1

Let $A(e_1,e_2)$ be the number of spanning subtrees of $K_n$ containing both $e_1$ and $e_2$. We want to minimize $A(e_1,e_2)$. If $e_1$ and $e_2$ are adjacent then we can count exactly how many trees have $e_1$ and $e_2$. To do this contract those edges into a single vertex $v$, for each spanning tree in the new graph with $n-2$ vertices there are $3^{d(v)...


1

Count the number of ways $5$ balls can be placed in $7$ bins marked $a-g$, using stars and bars A result of $\;\;\fbox{2}\fbox{0}\fbox{0}\fbox{1}\fbox{0}\fbox{1}\fbox{1}\;$, e.g. means obtaining $aadfg$. Thus $\binom{5+7-1}{7-1}$ ways


1

Hint:Find the no. of ways 2 particular students will be always together and twice the no. of ways 3 particular students will be always together.Subtract the 2nd from 1st.Subtract the result from the no. of all possible permutations.


1

Use stars to represent the five non-particular students and bars to represent the three particular students. Then a feasible seating arrangement involves choosing three positions from the six that are either between two stars or at the end. For instance, $$ \star | \star \star \star | \star | $$ The number of ways to do this is $\binom{6}{3}$. Now ...


1

In formula $(7)$ of this answer, it is shown that the number of factors of $p$ in $\binom{n}{k}$ for a prime $p$ is $$ \frac{\sigma_p(k)+\sigma_p(n-k)-\sigma_p(n)}{p-1}\tag{1} $$ where $\sigma_p(k)$ is the sum of the digits in the base-$p$ expansion of $k$. This is also the number of carries performed when adding $n-k$ and $k$ in base-$p$. Since all the base-...



Only top voted, non community-wiki answers of a minimum length are eligible