Tag Info

New answers tagged

0

Given that there are 5 types of person, each of whom sits to the left (or right) of ONE other person, this relationship can be shown as a square (person by neighbour). Also, the seating is going to be a continuous sequence where the 'left' person of the current pair will be the 'right' person of the next pair. Each neighbour relationship can be numbered 1 ...


2

Permutations with repetition of n elements are permuations where the first element is repeated a times, the second b times, the third c times, ...: $$\frac{n!}{a! b! c! \dots}$$ We have in this case $6$ elements where the first element is repeated $3$ times and the second also $3$ times. So there are $$\frac{6!}{3! 3!}$$ possible numbers.


0

I tried to generalize, but equation $(2)$ shows why $x=\frac12$ is needed to make a simple equation. Note that $$ \begin{align} \sum_{k=0}^{n+1}x^k\binom{n+k+1}{k} &=\sum_{k=0}^{n+1}x^k\left[\binom{n+k}{k}+\binom{n+k}{k-1}\right]\\ &=\sum_{k=0}^nx^k\binom{n+k}{k}+x^{n+1}\binom{2n+1}{n+1}\\ ...


2

The easy way to prove this seems by example. The easiest way to make sure that no pair gets seated wrongly, is to make sure that there is no pair at all. You have five classes, just seat one of each like so: ABCDE Then, keep seating such clusters untill you are done: For 2x5 BCD A E E A DCB For 4x5 BCD A E E A D B C ...


1

The question here is in how many different ways you can select the $n$ positions of the ones from the $2^m$ available positions in the vector. That's called combinations.


2

A To expectation of the minimum used label, $K$, we first measure the probability that all the balls being among the top $n-k$ boxes. That is, that the minimum label will be greater than some value $k$. In the total space each of $n$ balls has a choice of $n$ boxes ($n^n$). In the restricted space each of $n$ balls has a choice of $n-k$ boxes $(n-k)^n$. ...


1

I am getting: $\left(x+x^2+x^3+x^4+...+x^{15}\right)\left(x^{15}+x^{20}+x^{25}+...+x^{85}\right)$ for the first kid. $(\left(x^3+x^4+x^5+...+x^{15}\right) \left(x^{15}+x^{20}+x^{25}+...+x^{45}\right))^3$ for the next 3 kids. Then multiply both of them and check the coefficient of $x^{100}$


5

An inductive proof can be made according to the following schema: $$A\to A(ABB)\to A(ACBCC)(ABB)\to A(ADBDCDD)(ACBCC)(ABB)\to A(AEBECEDEE)(ADBDCDD)(ACBCC)(ABB)$$ At each stage you have $n$ people of $n$ types, with all $n^2$ possible consecutive pairs.


4

You can construct a solution by induction. Assume you have a solution for $n$. There are $n$ doubles- put an $n+1$ between each pair and two of them in one of the spaces. Now all of $1$ to $n$ have the required neighbors except themselves so double one of each. So starting from $1221$ we go to $1233213$ and then to $112233213$ The next one is then to ...


3

Thinking of a $10\times10$ chessboard is good - don't forget that you have to imagine the top and bottom sides as being adjacent, as also the left and right sides. For any given pair $p=(x,y)$ in $S$, define the neighbourhood of $p$ to be the set of all pairs which can be reached in at most one nudge from $p$. That is, the neighbourhood is ...


9

It's a graph theory problem. What you're looking for is an Eulerian circuit in a complete directed graph of order $5$, consisting of five vertices $M,B,C,P,E$ and $25$ directed edges, one going from every vertex to every other vertex and also one looping from each vertex to itself. The existence of an Eulerian circuit (i.e. traversing each edge exactly once) ...


18

We prove this generalization: If there are $n$ people each of $n$ different specialties, then the $n^2$ people can be seated around a round table such that, if $A$ and $B$ are two different people with the same specialty, then the people sitting to the immediate left of A and to the immediate left of $B$ are of different specialties. (Our problem is the case ...


3

Your thought of a chessboard is a good one. Each element you put in$S$ rules out $12$ others. It seems knight moves cause a lot of overlap of the excluded squares. My first thought would be $00,12,24,36,48,50,62,74,86,98,05,17,29,31,43,55,67,79,81,93$ for $20$


0

If the dogs are to be viewed as identical, as the "=" in the post hints at, line up the dogs like this: $$D\quad D\quad D\quad D\quad D\quad D\quad D\quad D\quad D\quad D\quad D\quad D\quad D\quad D\quad D$$ There are $14$ interdog gaps. Choose $3$ of these to put a separator into. The dogs from the left end to the first separator will go to Kid 1, the dogs ...


1

Assume that the 4 boys have at least one dog. Now we have $11$ dogs left. The way to arrange them is $$11 C 4 = \frac{11!}{(11-4)!4!} = \frac{11*10*9*8}{4*3*2} = 330\ \text{ways}$$ Comment if you have any questions.


1

Recall the species of permutations marked by cycle count which is $$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{\ge 1}(\mathcal{Z}))$$ so that it has the generating function $$\exp\left(u \log\frac{1}{1-z}\right)$$ and in particular $$\sum_{n\ge q} \left[n\atop q\right] \frac{w^n}{n!} = \frac{1}{q!} \left(\log\frac{1}{1-w}\right)^q.$$ Continuing, recall the ...


0

Suppose we seek to evaluate $$\sum_{j=a}^N {N\choose j}{j\choose a} d^{-j}.$$ Start from $${j\choose a} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{a+1}} (1+z)^j \; dz.$$ Note that with $j$ and $a$ integers when $j\lt a$ then $j-a \lt 0$ and $j-(a+1) \lt -1$ so we may extend the sum to start at $j=0$ because the extra contribution is zero. This ...


0

Let $g_{e}(x)=\displaystyle\left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\right)^3\left(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots\right)^2=(e^x)^3\left(\frac{e^x+e^{-x}}{2}\right)^2$ $\;\;\;\;\;\;\;\;\;\;\;\;=\displaystyle e^{3x}\left(\frac{e^{2x}+2+e^{-2x}}{4}\right)=\frac{1}{4}(e^{5x}+2e^{3x}+e^x)$. The coefficient of $x^{100}$ is given by ...


0

There are no magic knight tours on $6 \times 6$ or $10 \times 10$ boards. On this web page from George Jelliss : http://www.mayhematics.com/t/mg.htm, we see "Theorem 4. A magic knight's tour is impossible on a board with singly-even sides." (Here, "singly even" means a number of the form $2k$, where $k$ is odd.) Now, Jelliss's definition of a magic ...


0

(teeth on cog #1)×(turns of cog #1)÷(teeth on smaller cog)=(turns of smaller cog) For each small cog: 242×168÷66 =616=2×2×2×7×11 242×168÷48 =847=7×11×11 242×168÷28 =1,452=2×2×3×11×11. No common factors exist for the three results. Your answer is the solution.


0

Your calculation is correct, but there is a typo in the problem: Replace $28$ by $26$, and you are done.


2

For part (c), suppose that we have $m$ different subsets of $A$, where $m > \frac{2^n}{2} = 2^{n-1}$. Now by part (b), we know that there are $2^{n-1}$ subsets of $A$ that don't contain a $1$; let's name them as: $$ S_1, S_2, \ldots, S_{2^{n-1}} $$ Using these $2^{n-1}$ subsets, notice that we can obtain the other $2^{n-1}$ subsets from part (a) by ...


0

Like WLOG said, consider the set A, and exclude element 1 so you have B={2,3,...,n}. Now, the cardinality of set A is n. And it follows that the cardinality of B is n-1. Then, if we make all of the possible subsets of B, there are 2^(n-1) of these. Which, does count both the number of subsets which contain 1, and the number of subsets which do not contain 1. ...


2

Each of $n$ balls can land in each of $n$ boxes, so there are $D=n^n$ distributions possible. For each box to be non-empty you need a distribution in which each ball sits in its own box, which is equivalent to assigning each of $n$ ball numbers to one of $n$ box numbers - and each such assignment is just a permutation of $n$ natural numbers. There are $P_n = ...


2

Place a first ball. It will end up in an empty box. Then place a second ball. The probability that it is placed in an empty box is $\frac{n-1}{n}$. Now place a third ball. The probability that it is placed in an empty box is $\frac{n-2}{n}$. Going on like this you come to a probability that each ball is placed in an empty box (and consequently each box is ...


0

For every subset $A$ which contains $1$, there is a subset , namely $ A \setminus \lbrace 1 \rbrace $ which doesn't contain $1$ . This is a bijection. The subsets of $ \lbrace 1, \ldots , n \rbrace $ are $2^n$ and thus the answer to both $a)$ and $b)$ is $$ \frac{2^n}{2} = 2^{n-1} $$


0

there are $n$ numbers out of which 1 is already selected. So we are left with $n-1$ numbers. If $B\subset A$ where $B=\{1, x: x\in A\}$ then noting that the number of such $B$ is same as number of subsets of a set of $n-1$ elements, we get $2^{n-1}$ as answer for (a). For (b), the answer is total number of subsets of $A$ - total number of subsets that ...


2

For part "a" it is correct. For part "b": Using Multinomial: The ways are equivalent to: $$\text{ Coefficient of $x^{14}$ in}(x^0+x^1+x^2+...x^6)^4\\ =\text{ Coefficient of $x^{14}$ in}(1-x^7)^4(1-x)^{-1}\\ =\text{ Coefficient of $x^{14}$ in}\left(1-\binom41x^7+\binom42x^{14}-...\right)(1-x)^{-4}\\ ...


3

The answer you got for the first question is right. For the second, call a distribution bad if one or more of the $x_i$ is $\ge 7$. Our strategy is to count the number of bads, and subtract from the answer of a). One can have $2$ of the $x_i$ equal to $7$. This can be done in $\binom{4}{2}$ ways. Now we count the number of bads in which only one of the ...


3

Every partition counted in $p(n,k)$ is one of the following two forms. One of the subsets in the partition is $\{n\}$. There are $p(n-1,k-1)$ of these, since all you need to count is the number of ways to partition the remaining elements $1,\ldots, n-1$ into $k-1$ subsets. $\{n\}$ is not one of the subsets. Then, you need to count the number of ways of ...


0

This is too long for a comment, but it may help to understand the problem. Also, it may shed a light into some assumptions that may or may not be useful. I'm taking these assumptions: A) It is a round table, so the $n$-tuple is cyclic. B) The number of men/women is not known. C) The "pair" of men/women is made of different people. In a cyclic ...


2

I am one of the friends mentioned in the question! Here are my ideas yet. I will edit this post as I get deeper in the resolution, or if I find any other ideas. I will only be able to work on this on the side during free time. One approach, which would reduce the first part of the problem to a finite computational task, would be to find the number of ...


1

OEIS sequence A000372 and references there. In particular, it says that the asymptotics of $M(n)$ are stated in A. D. Korshunov, The number of monotone Boolean functions, Problemy Kibernet. No. 38, (1981), 5-108, 272. MR0640855 (83h:06013) (which I have not looked at). EDIT: the link http://www.mathpages.com/home/kmath094.htm quotes Korshunov's result for ...


1

If you select three objects one after another (repetitions allowed), you'll end up with $(y_{j_1},y_{j_2},y_{j_3})$ where $j_k \in \{1,\dots,5\}$ for $k=1,2,3$. Now, obviously each permutation of this $3$-tuple represents the same selection of objects, i.e. it doesn't depend on the order in which you selected them. So you can as the "canonical" ...


0

Reading the Wikipedia article about compositions, I found this article which gives another version of the result (Example 2.7 p.3), i.e.: $$ \#(n,n_G,1,k) = F(k,n+k-1) $$ where F(a,b) is the shifted a-generalized Fibonacci number.


1

We have $2^n$ players, so basically there are $\frac{2^n}{2} = 2^{n-1}$ games in the first round. The combination of possible players going to the next round is given by $2^{2^{n-1}}$ because in each game we have two possible winners. In the second round, we will have $2^{n-1}$ players and $2^{n-2}$ games. Following the same reasoning, the combination of ...


0

Just a quick heuristic, too long fo a comment: Using Pari/GP I get this for the quotient of consecutive Catalannumbers: r=300; 4-cat(r)/cat(r-1) %133 = 6/301 r=400; 4-cat(r)/cat(r-1) %134 = 6/401 r=500; 4-cat(r)/cat(r-1) %135 = 2/167 \\=6/501 r=600; 4-cat(r)/cat(r-1) %136 = 6/601 So the partial sums up to index $r$ should be bounded by the ...


1

If $f(n)$ is the sum of k-permutations of n, then \[ f(n)=\sum_{i=1}^{n} \frac{n!}{(n-i)!},\ \mbox{for}\ n\ge1 \]


0

Suppose we seek to evaluate $$\sum_{k=0}^{n+1} {n+1+k\choose 2k} (-1)^{n-k} 4^k = (-1)^n \sum_{k=0}^{n+1} {n+1+k\choose n+1-k} (-4)^k.$$ Start from $${n+1+k\choose n+1-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+2-k}} (1+z)^{n+1+k} \; dz.$$ This yields the following expression for the sum $$\frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} ...


0

If I understand the problem right: given that the number of edges $\ell$ is fixed, there are a total of $m \times n$ pairings possible, so the total number of alternatives is ${mn \choose \ell}$. How many of these involve exactly $k$ elements (out of $m$) from $A$? This is $$g_k={m \choose k} \left[ {k\,n \choose \ell}-{(k-1)\,n \choose \ell}+{(k-2)\,n ...


1

My answer comes rather late, so I don't expect up votes. The response by user155957 was based on assuming that when you said 'combinations', you really meant 'permutations'. Based on this assumption, that user's response is correct by my reckoning. Let us assume that when you said 'combinations', you really meant combinations. In that case, the answer is ...


0

This is a direct application of the stars-and-bars technique.


1

Provided order does not matter, $(y_1,y_2,y_2)$ (for example) represents the same selection as $(y_2,y_1,y_2)$, so requiring $i_1 \leq i_2 \leq i_3$ ensures every selection is only represented once. For the second part, you can use the "stars and bars" method: use 5 + 1 bars to indicate the 5 different $y_i$'s: y_1 y_2 y_3 y_4 y_5 | | | | | ...


1

It's necessary to impose $i_1 \leq i_2 \leq i_3$ because the mapping is a bijection. Every element in the "from" set must map to exactly one element in the "to" set, and vice versa. If you didn't order the elements in non-decreasing order, the mapping would not be unique. The $\mathbb{N}_7$ comes from your original five choices, plus two that may be ...


0

The restriction on the ordering of the indices prevents multiple counting of the same set of three distinct elements, e.g. {y1,y4,y5} = {y4,y1,y5} as sets (these are not 3-tupples)


1

We need to select two distinct dishes, so an injection $f:\mathbb{N}_2 \rightarrow Y$ picks out these two dishes, $f(0)$ and $f(1)$. The injection forces us to pick two $\textit{distinct}$ dishes, and the fact that the two maps $f(0)=x,f(1)=y$ and $f(0)=y,f(1)=x$ give two different injections corresponds to the multiplication by 2 in your solution. ...


0

This is reminiscent of Rota's version of Möbius inversion formula... Here, one is given the probability $P(I)$ of every subset $I$ of size $n$ of some set of size $N$, with $N\geqslant1$ and $0\leqslant n\leqslant N$, and one looks for the probability $p_i$ of each individual element $i$ of the set. If $n=0$ or $n=N$, we are given nothing hence the ...


1

For $i=1,\dots,N$ define $\mathcal{S}_{i}=\left\{ A\mid A\text{ contains item }i\right\} $. Then $Pr\left[\text{item }i\right]=\sum_{A\in\mathcal{S}_{i}}Pr\left[A\right]$. This if John elects one subset. Here $Pr[A]$ stands for the probability that John elects subset $A$.


1

Hint: How many subsets has set $\{1,\dots,10\}$ in total? How many of these subsets $S$ satisfy $2\in S$ and $7\in S$? So how many do not?


6

Another possible method: How many subsets of $\{1,2,3,4,5,6,7,8,9,10\}$ are there in total? Call this number $n$. How many subsets contain both 2 and 7? This is the same as the number of subsets of $\{1,3,4,5,6,8,9,10\}$. Call this number $m$. Then your solution is $n - m$.



Top 50 recent answers are included