Tag Info

New answers tagged

0

This is the argument by Jack D'Aurizio spelled out. Use the multinomial theorem $$ (x_{1} + \dots + x_{m})^{n} = \sum_{k_1 + \dots + k_{m} = n} \binom{n}{k_1, k_2, \dots, k_{m}} x_{1}^{k_{1}} \dots x_{m}^{k_{m}} $$ and set all $x_{1} = 1$.


0

Note: I'd like to present a two-step approach to solve this nice problem. We will see the resulting generating function is the one stated by @RusMay. We also take a look at small examples as simple plausability check. It's a two-step approach because I'd like to start with a simpler problem in order to be well prepared for the more challenging problem ...


0

The LHS is the number of ways to partion n entities into m sets that can be done by asking individiual element one by one where it wants to go from a list of m subsets that we can form beforehand. Thus ways now would be m for first element, sm for second element and so on. So total ways would be $\prod_1^nm=m^n$.


2

Or to look at it another way. There is only one 9 digit number with this condition 123456789. What about 8 digits?: there are nine answers 12345678, 12345679, 12345689, 12345789, 12346789, 12356789, 12456789, 13456789, 23456789. So all I have done is strike out each digit in turn. $9\times 1$ digit = 9 possibilities. For 7 digits, you need to strike out 2 ...


7

Hint: Once you've picked six different digits, there is only one way to arrange them to satisfy the conditions given.


2

Hints : The diagonal elements have to be $0$ If the lower left triangle is given, the upper right triangle is determined by $a_{ij}=-a_{ji}$


3

Since the prime factorization of $$210=2\cdot 3\cdot 5\cdot 7$$ What we have to basically do is find out the number of ways we distribute these factors among the four variables $x_1,x_2,x_3$ and $x_4$. We can distribute each factor among the $4$ variables by ${4\choose 1}=4$ ways. Hence, the answer is $$4^4=256$$ Also considering negative numbers, we can ...


3

The diagonal line will cross $b$ squares and $l$ squares, but for $\gcd(l,b)$ occasions will accomplish the transition through a corner. Thus the total number of squares with a portion of the diagonal will be $l+b-\gcd(l,b)$. For the illustration, $l=8, b=12$ and the diagonal goes through $\gcd(12,8)=4$ corners for a total of $12+8-4=16$ squares cut.


1

Calling the requested number $f(l,b)$, and putting $d=\gcd(l,b)$, one has $f(l,b)=d f(\frac ld,\frac bd)$. This is because cutting the diagonal into $d$ pieces of equal length, the subdivision points are lattice points (in fact they are precisely the lattice points on the diagonal), and all $d$ pieces are similar. This reduces the problem to the case where ...


1

Hint. By your first condition we have $$S=A_1\cup A_2\cup\cdots\cup A_{101}\ .$$ The inclusion/exclusion formula for $101$ sets is $$\eqalign{ N=|S| &=|A_1|+|A_2|+\cdots+|A_{101}|\cr &\qquad {}-|A_1\cap A_2|-\cdots\cr &\qquad {}+|A_1\cap A_2\cap A_3|+\cdots\cr &\qquad {}-|A_1\cap A_2\cap A_3\cap A_4|+\cdots\cr &\qquad ...


1

Hint. Put a rook on the board, say on a corner square. Can you make a series of rook moves that traverses every square on the board once and only once, and returns to its starting point? Now what can you say about the set of edges that the rook crosses?


0

The theoretical minimum is achieved when each square has exactly two red edges and no edge that is in the border is painted red. In this case $64$ edges must be colored. Prove it is possible. Here is a coloring that works:


0

b) It seems the following. For each non-negative integer $n$ let $a(n)$ be the number of words from $A$ (that is, containing a substring “abbc”) of length $n$. Then it is easy to check that the sequence $\{a(n)\}$ satisfies the following recurrence (a*): $$a(n)=3a(n-1)-a(n-4)+3^{n-4}$$ for all $n\ge 4$ and the initial conditions $a(0)=a(1)=a(2)=a(3)=0$. ...


0

For illustrative purposes suppose that there are $3$ types of candy and just the two of us picking. The generating function for my outcomes is simply $1+x_1^2+x_2^2+x_3^2$: the term $1$ corresponds to my picking no candy at all, and for $k=1,2,3$ the term $x_k^2$ corresponds to my picking $2$ candies of type $k$. Those four outcomes are the only possible ...


0

Suppose there are $m$ blocks of size $k$ and $n$ of size $3$, then $6n=\binom{v}{2}-m\binom{k}{2}$, notice $\binom{v}{2}$ is congruent to $1\bmod 3$. Unless $k$ is congruent to $2\bmod 3$ we shall have $\binom{k}{2}$ is a multiple of three. This would mean $\binom{v}{2}-m\binom{k}{2}$ would not be a multiple of $3$, and $n$ would then not be an integer.


0

Right, so far. The total number of outcomes, our total probability space, is $(6\times 2)^5$, because each of 5 people can independently have $6\times 2$ results; so we multiply that five times (ie: take it to the 5th power). $$|U|=(6\times 2)^5 = 12^5$$ Now if we want the first favoured space of nobody rolls a six, the we reduce the outcomes each person ...


0

** How many outcomes are in the event where nobody rolls a six? If they can't roll a six, there are 5 other numbers to roll, and either coin-flip is still allowed. So each person has $2\times 5=10$ possible outcomes. Since there are 5 people, there are $10^5$ possible outcomes. ** How many outcomes are in the event where at least one person rolls a six? ...


2

Note that any two distinct elements $5^{p_1} 13^{q_1} 31^{r_1}$ and $5^{p_2} 13^{q_2} 31^{r_2}$ are incomparable (neither divides the other) if $p_1 + q_1 + r_1 = p_2 + q_2 + r_2$. So a mutually incomparable set is given by $$ S_n = \left\{5^p 13^q 31^r \;\big\vert\; p+q+r=n;\; 0\le p,q,r \le 200\right\} $$ for any $n$. The size of this set is maximal when ...


1

Your answer to part 1 is correct. For part 2, you must place the balls so that there is one empty box, one box with two balls, and the remaining balls will have one ball each. There are $n$ ways to pick the empty box, and $n-1$ ways to then pick the box with two balls. We can now fill the $n$ spaces for the balls with the $n$ balls in any order you wish. ...


0

The argument in 1. is quite elegant. Another way to see this is that the probability to put the first ball in an empty box is $1$, for the second it is $(1 - 1/n)$, for the third it is $1 - 2/n$. The searched for probability is thus the product and this is exactly what you found in a different way that I actually like better. For 2. you need to consider ...


1

It is surely sufficient to remove $n$ numbers: we can remove all $n$ even numbers. Then all numbers that are left are odd, so the sum of any two of them is even and in particular not one of the numbers left. To show that we need to remove at least $n$ numbers, consider the largest number $M$ that remains. We distinguish two cases: $M = 2\ell+1$ is odd. We ...


3

if $a=1$, for the rest $9$ places, $1$ can be taken anywhere, and also the rest $8$ places must be $0$ or the sum would exceed $2$. Also if $a=2$, then the rest $9$ places must be $0$, or sum would exceed $2$. Hence there are $9+1=10$ such numbers.


1

number of ways of distributing n identical balls into k persons is given by $n+k-1\choose n$.wiki number of ways of distributing n identical balls into m persons so that each of the m person gets at least one ball and the remaining k-m person gets $0$ ball,is given by ${k \choose m}*{n-1\choose m-1}$. Can you proceed now?


1

The stars and bars technique can be used here. There are $\binom{n+k-1}{k-1}$ ways to distribute the balls. Suppose that $1\le m\le k$. There are $\binom{k}m$ ways to choose a subset of the $k$ to receive balls, and there are $\binom{n-1}{m-1}$ ways to distribute the balls to that subset in such a way that everyone receives at least one ball. Thus, the ...


2

Your approach makes the error of "double counting": a configuration that has $k$ balls in the first bucket and in the second is counted twice. You could try by using inclusion-exclusion, but the result would probably be complicated. A simple approximation, it should work for $m\to \infty$ , $n/m \to t$ constant The model can be approximated as $m$ iid ...


1

We wish to find the number of solutions in the positive integers of the equation $$x_1 + x_2 + x_3 + x_4 = 32$$ subject to the restriction that $x_4 \leq 25$. We can reduce this to the equivalent problem in the non-negative integers by making the substitutions $y_i = x_i - 1$, $1 \leq i \leq 4$. \begin{align*} x_1 + x_2 + x_3 + x_4 & = 32\\ y_1 + ...


2

Once you have decided how many balls go into each of the different bins, there is only one way to distribute the balls. For instance, let's say $n = 4$ and $k = 3$. Then if we want two balls in bin $1$, no balls in bin $2$, and two balls in bin $3$, then we must have ball $1$ and $2$ in bin $1$ and ball $3$ and $4$ in bin $3$. That means that this is a stars ...


1

We can use the stars and bars (see here) to count the ways we can divide $6$ balls between $3$ children if every children must receive at least 1 ball. For any pair of positive integers $n$ and $k$, the number of distinct $k$-tuples of positive integers whose sum is $n$ is given by the binomial coefficient $$ {n-1\choose k-1}. $$ Hence, the answer to the ...


1

If the balls are identical, first give each child one ball. Then lay the three remaining balls in a row with two "dividers". How many ways can you arrange these three balls and two dividers?


1

Give a ball to each chlid. Now you are left with the problem of how many ways to give 3 balls to 3 children. This is equal to the number of non-negative integer solutions of the equation $$x+y+z=3.$$ And the answer is $$\binom{3+3-1}{3}.$$


2

Hint: consider cases where $x_4 > 25$ since you only have to deal with $4$ cases in total.Also take into account that $x_1 > 0 \Rightarrow x_1 = 1+y_1, y_1 \geq 0$, same for $x_2, x_3$.


6

Asking whether every arrangement can be reached is the same as asking whether every arrangement can be sorted (into a certain given configuration, such as having the subscripts in ascending order and all coins heads-up). Other posters have pointed out that this is possible. The question of how to this efficiently is known as the "Burnt Pancake Flipping ...


10

Yes, you can get all of them. It suffices to show that you can get any desired coin to the bottom in either orientation, since you can then manipulate the rest of the stack without affecting the bottom coin and so build the desired sequence from the bottom up. But this is easy: any coin can be brought to the top in at most one move, where it can be flipped ...


10

Yes. We know that if we can swap any two adjacent items (without any other changes) and do this repeatedly then we can get all permutations. And if we can flip any single coin (without any other changes) and do this repeatedly then we can get all arrangements of heads and tails. To flip coin $x_n$, first rotate the top $n$ coins, so $x_n$ is now on top. ...


3

The sequence $(a_n)$ generated by $D$ is the number of ways to write $n$ as a sum of positive integers without repeated summands. Sums only differing by the order of the summands are counted only once. $$D(x) = 1 + x + x^2 + 2x^3 + 2x^4 + 3x^5 + 4x^6 + 5x^7 + 6x^8 + 8x^9 + 10x^{10} + \ldots$$ $$3 = 2+1 \\ 4 = 3+1 \\ 5 = 4+1 = 3 + 2 \\ 6 = 5+1 = 4 + 2 = 3 + ...


0

These are the Stirling coefficients of the second kind. If the sum of elements in sets must be equal the problem is a lot harder.


1

Here is another solution via group theory. Consider the group $S_n$, it has $n!$ elements. Now consider the subgroup of $S_n$ consisting of the permutations such that elements in $\{1,2,3\dots k\}$ always go to elements of $\{1,2,3\dots k\}$, it has order $k!(n-k)!$ so by lagrange's theorem $k!(n-k)!$ divides $n!$


2

You can use a combinatorial argument. How many groups of size $k$ can be formed from $k$ students? There are $n$ options for the first student, $n-1$ options for the second $\dots (n-k+1)$ options for the $k$'th student. Therefore there are $n\cdot (n-1)\cdot\dots (n-k+1)=\frac{n!}{(n-k)!}$ possible groups. However we have overcounted! Because in a group of ...


1

If I understand correctly the question is to find for which values of $n,k$ we have that $\binom{n}{k}$ is a multiple of $2,3,5$ In general you can figure out if $\binom{n}{k}$ is a multiple of any prime $p$ using Kummer's theorem, to do this write $n$ and $k$ in base $p$. If each digit in the expression of $n$ is larger than or equal to the respective ...


3

HINT: Let $a_n$ be the number of permutations of $[n]$ having a multiple of $n$ inversions. If $b_{n,k}$ is the number of permutations of $[n]$ with exactly $k$ permutations, we have the generating function $$\sum_{k=0}^{\binom{n}2}b_{n,k}x^k=(1)(1+x)(1+x+x^2)\ldots(1+x+\ldots x^{n-1})\;.$$ From this it’s not hard to calculate the following values of $a_n$ ...


0

An alternate method would be to use symmetry: We have $\dbinom{29}{5}$ solutions in total, and the number of solutions where $x_1+x_2+x_3=x_4+x_5+x_6$ is given by $\dbinom{14}{2}\dbinom{14}{2}$, since then $x_1+x_2+x_3=12=x_4+x_5+x_6$. By symmetry, half of the remaining solutions will have $x_1+x_2+x_3>x_4+x_5+x_6$, so this gives ...


0

Suppose you have $n$ candies, and $c$ kids. You can first select how many candies you want to give the twins, suppose it is $2r$ in total. Then there are $c-2$ kids and $n-2r$ candies left. You can now give these candies away freely. We use the method of stars and bars to count the number of ways: there are $n-2r$ candies(stars) and there are $c-2$ kids left ...


14

Let the set be $\{a_1,a_2\dots a_{2015}\}$ consider the sets $\{a_1\},\{a_1,a_2\},\{a_1,a_2,a_3\}\dots \{a_1,a_2\dots a_{2015}\}$ If one is a multiple of $2015$ we are done, if not two must have the same congruence, suppose $\{a_1,a_2\dots a_j\}$ and $\{a_1,a_2\dots a_h\}$ have the same congruence with $h<j$, then the set $\{a_{j+1},a_{j+2}\dots ...


0

I would not bother with generating functions here. You know that $t_1$ can be any integer in $[13,24]$. For each of those values there are $$\binom{t_1+3-1}{3-1}=\binom{t_1+2}2$$ solutions to $x_1+x_2+x_3=t_1$ in non-negative integers, and similarly $$\binom{24-t_1+2}2=\binom{26-t_1}2$$ solutions to $x_4+x_5+x_6=24-t_1$ in non-negative integers. The ...


0

Perhaps the most elegant solution is to take all $10$ from the $10$-box and deposit the excess $7$ in the $7$-box. Then remove those $7$ and deposit the excess $4$ in the $4$-box. Then remove those $4$ and deposit the excess ball in the $10$-box. Now apply the same idea to the $7$-box: remove all $7$, deposit the excess $4$ in the $4$-box, immediately remove ...


2

A selection of $10$ bulbs, in which both defective bulbs are selected, consists of selecting eight of the twenty-two good bulbs and both of the two defective bulbs, which can be done in $$\binom{22}{8}\binom{2}{2} = \binom{22}{8} \cdot 1 = \binom{22}{8}$$ ways.


2

All even numbers have the same probability of being first. And there are $10$ of them. So the probability is $\dfrac{1}{10}$.


0

I took the trouble of calculating the long expression (1*19!+10*1*18!+10*9*1*17!+10*9*8*1*16!+..........+10*9*8*7*6*5*4*3*2*1*1*9!)/20! and it is = 1/10. Stay happy! Although David's approach is elegant, I just wanted to be absolutely sure about it


1

I assume all light bulbs are different (otherwise the number of ways to select the good ones is just 1). Your solution is correct because the order doesn't matter. You simply 'fix' the 2 defective ones in the sample and select 8 out the remaining items.



Top 50 recent answers are included