Tag Info

New answers tagged

0

This is not a print error. Indeed, $11+1+5=17\ne 16.$ In these elementary combinatorics book problems, we describe this approach of counting $9$ movies together as $9!$ different single movie series of $9$ movies, as they are arranged among themselves in $9!$ ways. Don't forget to start by treating the $9$ as $1$ solitary being, and then by arranging them ...


0

Do you mean how many distinct substrings or do you allow duplicates? If you wish to count distinct substrings, the answer depends on the particular string. I will address the latter question, the number of substrings allowing duplicates. A substring is defined by a start index and an end index. Let the start index be the index of the first character in the ...


0

It is not a print error. Consider the 9 romantic movies as a single pack of movies. And consider the other movies as unitary pack of movies. So, the 9 romantic movies can be arranged in $9!$ ways. And the 11 action movies, 5 thrillers AND the 1 pack of 9 romantic movies can be arranged in $17!$ ways. Therefore the result is $9!17!$


0

Here is a sample program I wrote with $C=35$, $N=2$ and the weights $S_1=3$ and $S_2=4$. You can try pasting it and compiling it here. You can change the capacity C, the number of coordinates N and the weights. Just be sure to leave the program consistent, otherwise it would not produce a correct result. In short, I am using a recursive function $rec$ to ...


1

Note that the total of the cards is odd. For each subset $E_i$ with an even sum, the complement $O_i$ is a subset with an odd sum. It is clear that this is a bijection between the subsets with even sums and the subsets with odd sums. Hence half the subsets have an even sum. Of course that would include the empty set.


4

Using the fact that sum of two odd cards is even or a single even card is even.If you want even cards you must take these in these quanta. The number of ways in which you can take even cards(total 7) is [none or more]: $$2^7=128\text{ ways }$$ The number of ways in which you can take pairs of odd cards(total 8 cards, 4 pairs at a time) is same as taking ...


0

I am sorry, but you will have to write down all possible combinations. It's not too bad though. For the first one, $a$ and $b$ are both less than $c$, which is less than $d$. So $c$ is at least 3, and at most 4. If $c=3$, there are two ways to do $a$ and $b$; for each of those there are two choices for 4. So that makes $2\times 2$ ways if $c=3$. If ...


7

Generating function approach. Let $$f(x)=\prod_{i=1}^{15} \left(1+x^i\right)=\sum_{j=0}^{15\cdot 16/2} a_jx^j$$ where $a_j$ is the number of ways of getting a total of $j$ from taking cards. Then you are looking for $\frac{f(1)+f(-1)}{2}$. But $f(-1)=0$, so you are looking for $\frac{f(1)}{2}=2^{14}$. That includes taking zero cards to get zero, so you ...


2

Hint: Arrange Men first and Then fill gaps between them with women This method will work because No matter what there will be at least one man between them. Don't forget to include spaces before first and after last man


3

Hint: 7 cards have even numbers and 8 cards have odd numbers. You can take any of the even cards, and you must take an even number of the odd cards. Calculate these two amounts separately, then multiply.


11

Hint: For any subset of the first $14$ cards ($1, 2,..., 14$), there is exactly one way to complete it by using or not using card $15$, so as to make the sum even.


0

You are correct so far. Now use the definition of the binomial coefficient to show that the last equation is true. CORRECTION Sorry, I was wrong. The sum of binomial coefficients you are using is not correct. Try this instead. If $n=0$ or $n=1$, then there are no 2-element subsets. Also, in both cases $\frac{n(n-1)}{2}=0$. Now assume that the statement is ...


1

if you are seating $n$ people round a fixed table in a restaurant then there are $n!$ ways of doing it. however in terms of eye-contact and conversation only, all the relevant data are contained in the list of who was sitting on who's right. starting with any given person there are only $n -1$ possibile "right neighbours", then $n-2$ and so on until the ...


1

But each permutation is taken as being the same as the other $n-1$ permutations which arise when you rotate it, so you have to divide by $n$ - only relative positions matter. Alternatively, given any permutation, you can count it clockwise from person $1$ to fit in the other $n-1$ people.


2

The ones digit can only be either 2 or 6, so that's 2 choices. For the remaining 2 digits, you have 4 numbers to choose from and they can be permuted. Hence it should be: 4P2 (4 permute 2) * 2 = 12 * 2 = 24 You can also write them all out systematically: 236,256,276,326,352,356,362,372,376,526,532,536,562,572,576,632,652,672,726,732,736,752,756,762


1

What can happen if a family is blessed with $3$ children? Possibilities: BBB BBG BGB BGG GBB GBG GGB GGG Each of these events have the same probability. Note that $7$ of these possibilities remain if it is demanded that at least one of the children is a boy. The last (GGG) falls off. In how many of these $7$ possibilities are there exactly $2$ boys? ...


2

There are $2^3=8$ combinations, with no restrictions. There are $7$ combinations with at least a boy, because there is only $1$ combination with no boys (namely, three girls). The number of combinations with exactly two boys is $\binom 32=3$. (These are $BBG$, $BGB$ and $GBB$). Then the probability is $3/7$.


1

This is a conditional probability. You are given there is at least 1 boy and asked to find the probability that there are two boys. Let even $A=$ three children with 2 boys, $B=$three children with at least 1 boy, then $$P(A|B)=\frac{P(A\cap B)}{P(B)}$$ where, $$P(A\cap B)=\binom{3}{2}\left(\frac{1}{2}\right)^3$$ $$P(B)=1-\left(\frac{1}{2}\right)^3$$ ...


1

If you just look for the matrices with $1,1,0,0$ in the top row, then each of those matrices has five others, that you get by shuffling the columns. Since the first column starts with a 1, there are three positions for the other 1 in that column. So if you only look for matrices with $1,1,0,0$ in the top row and $1,1,0,0$ in the first column, each of those ...


0

Here's a sketch of an argument that $2^{n-1}$ is optimal. Let $p_k$ denote the probability that a randomly chosen set of order $k$ lies in $\mathcal{F}$. The local LYM inequality implies $p_{k-1}+p_k\leq 1$ for all $1\leq k\leq n$. Now we can forget the original problem and try to maximise $M(p)=\sum p_k\binom{n}{k}$ over all values $0\leq ...


1

I'll name $S_n$ your sum. Let's change the index: $k \leftarrow k-1$ $$ S_n = -2\sum_{k=0}^{n-1} {(-1)^{k} {{n-1} \choose {k}} (2*(n-1)-k) 2^{k}} $$ $$ S_n = -2[2(n-1)*(-1)^{n-1}\sum_{k=0}^{n-1} {(-1)^{n-1-k} {{n-1} \choose {k}} 2^{k}} +\sum_{k=0}^{n-1} {(-1)^{k} {{n-1} \choose {k}} k*2^{k}}] $$ $1 = (2-1)^{n-1} = \sum_{k=0}^{n-1} {(-1)^{n-1-k} {{n-1} ...


2

Hint: $$ \begin{align*} &\sum_{k=1}^{n} (-2)^{k-1} \binom{n-1}{k-1} (n-k) = (n-1) \sum_{k=1}^{n-1} (-2)^k \binom{n-2}{k-1} = (-1)^{n-2} (n-1), \\ &\sum_{k=1}^{n} (-2)^{k-1} \binom{n-1}{k-1} = (-1)^{n-1}. \end{align*} $$ Therefore $$ \sum_{k=1}^n (-2)^{k-1} \binom{n-1}{k-1} (n-k+n-1) = (-1)^{n-2} (n-1) + (-1)^{n-1} (n-1) = 0. $$


1

Any flip sequence where all heads come before all tails will preserve the initial ordering. For example, if $n = 4$, then each of the following will work: $$ (H, H, H, H) \\ (H, H, H, T) \\ (H, H, T, T) \\ (H, T, T, T) \\ (T, T, T, T) $$ It's easy to see that in general, this can happen in $n + 1$ ways.


0

As you rightly observe, every $3\times 3$ block covers a cell of the form $(3m, 3n)$. You can extend this observation to show that each block contains cells equivalent to $(0,0),(0,1),(0,2),(1,0), (1,1), (1,2), (2,0), (2,1), (2,2)$ modulo $3$. You can make sure that two cells in each block are painted by choosing two of these classes and painting them. ...


1

Haven't extensively tested this, but based on your own logic of leaving $(3k,3k)$ blank, we could paint every cell that is $3k+1,3k+1$ i.e. cells 1,4,7... and so on and $(3k,3k)$ cells. That would mean only 2 of every 9 cells are painted (I tested a limited set and it was working). Going by the above logic the number would be ...


1

An old paper of Frucht (referenced on the wikipedia page on graph automorphisms) contains the following results (Theorems 3.1 and 3.2): If $n>2$, then there is a cubic graph $G$ on $6n$ vertices with $\text{Aut}(G)\simeq \mathbb{Z}_n$. If $n>3$, then there is a graph $G$ on $3n$ vertices with $\text{Aut}(G)\simeq \mathbb{Z}_n$. Note also ...


3

I found Frucht's theorem on Wikipedia. http://en.wikipedia.org/wiki/Frucht%27s_theorem According to this theorem, any finite group occurs as the automorphism group of a finite, undirected graph.


0

Expand $$ (1+x)^n = (1+x)(1+x)\times (1+x) $$ As there are $n$ factors that are either $1$ or $x$, this has the expanded form $$ \sum_{k=0}^n a_k x^k $$ $a_k$ is the number of times you get $k$ $x$s. As there are $n$ factors and that every product $$ b_1 b_2 \dots b_n $$ with $b_i\in\{1,x\}$ are present in the sum, the number of such products is $\binom ...


1

Convince yourself of the proof of the binomial theorem instead. That way it will not matter what "direction" you go, as you will understand fully why the binomial theorem works. First, note that the binomial theorem holds true for $n=0$. That is, $$ \left(1+x\right)^{0}=1=\sum_{k=0}^{0}\binom{n}{k}x^{k}=\binom{0}{0}x^{0}=1. $$ Proceed by induction. ...


0

Returned to the problem and things became clear. Thank you to almagest for the inspiration to consider his recursive function. To keep everything in one spot, I'll start from the beginning defintions: Let $S \colon \mathbb{N}^{2} \to \mathbb{N}$ and define as follows: $$ \begin{align} S(0,0) & \equiv 0 \\ S(0,k) & \equiv 0 \\ S(a,0) & \equiv 1 ...


1

You wish to draw a five-card hand comprised of at least two red cards, at least one of which is a diamond, and at least one spade. The ways to obtain this are to: Draw from 2 to 4 red cards that are not all hearts, and the remainder of the cards drawn are to be black but not all clubs. $$\begin{align} &\text{Thus we count:} \\ &\quad ...


0

You correct with choosing a diamond is $\binom{13}{1}$ and spade $\binom{13}{1}$; however, when you are choosing any other red card, you need to remember you already have one diamond so $\binom{25}{1}$. At this point, the player has 3 cards so there are 49 cards left to pick two cards from.


0

I propose this algorithm for the partition: Select an unassigned vertex and put it in $A$. Put all the unassigned neighbors of vertices in $A$ in $B$. Put all the unassigned neighbors of vertices in $B$ in $A$. Repeat steps 2 and 3 until no more progress is made. If graph is partitioned, you're done. If not (in case of multiple components), return to 1. ...


0

Markus Scheuer's answer is spot-on. Just another -hopefully simpler- example. Suppose we have two balls, $A,B$ (let's assume them distinguishable to begin with) to be placed into two boxes $1,2$. We call "success" the event that both boxes are non empty. We have four possible configurations: $$\begin{array}{cc} 1 & 2\\ \hline \{ A,B\} & ...


0

The bijection in (2) can be established by noting that the $(k + 1)$-th block also contains the initially omitted $(n + 1)$-th element. So when you want to determine which $k$ out of $k + 1$ sets were those that spawned from $S_{i,k}$ you just pick those that do not contain the $(n + 1)$-th element. I'm also struggling with (1) right now. Update: Stirling ...


3

Here is another algebraic proof, somewhat involved where the calculations are concerned but simple conceptually. We seek to compute $$\sum_{k=0}^n {n-k\choose k} (-1)^k m^k (m+1)^{n-2k}$$ or $$(m+1)^n \sum_{k=0}^n {n-k\choose k} (-1)^k m^k (m+1)^{-2k}.$$ Introduce the integral representation $${n-k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} ...


3

Here's a combinatorial proof based on rewriting the right hand side as $1+m+m^2+\cdots+m^n$ and using inclusion-exclusion for the left hand side. Suppose you have jars labeled $1,2,3,\ldots,n$, each containing balls labeled $0,1,2,\ldots,m$. Starting with jar $1$, you pick one ball from each jar, but stopping as soon as you've picked a ball labeled $0$. ...


3

First notice that $\frac {m^{n+1}-1}{m-1}=1+m+\ldots +m^n$, which every summand is just the numbers of functions from $[i]$ to $[m]$. But that is equivalent to some functions $f$ from $[n]$ to $[m+1]$ where from some $i$, for $i<j\leq n$, $f(j)=m+1$, thats the right hand side. For the left hand side, we can use inclusion exclusion by the fact that those ...


4

The question is poorly worded. The number of ways of choosing a set of three balls from the bag is $\binom{n}3$; if the balls are truly identical, however, the number of distinguishable outcomes is, as you say, just $1$. If the former answer is intended, the inclusion of the words identical red is misleading at best. If the latter answer is intended, this ...


2

You’ve found the nicest and easiest solution. Just for fun, here’s another (much less efficient!) approach showing how to convert this problem into a more familiar one. Let the sequence be $\langle a_1,a_2,a_3,a_4,a_5,a_6\rangle$. Let $x_1=a_1$, let $x_k=a_k-a_{k-1}$ for $k=2,\ldots,6$, and let $x_7=49-a_6$. Then you want the number of integer solutions to ...


0

As I have essentially asked the same question somewhere else, I wanted to share the answer I was given there by Gage: See here for more information [on row-complete Latin squares] http://personal.maths.surrey.ac.uk/st/H.Bruin/MMath/LatinSquares.html The reference outlines a fairly straight forward algorithm and I wrote a a quick MATLAB script to build ...


3

I think I got it, I would say it's $\binom{49}{6}$, because once you chose your 6 numbers, there is only 1 way to order them.


0

That is equivalent to prove $x^\overline{n}=x(x+1)\ldots (x+n-1)=\sum |s(n,k)|x^k$, taking x=-y, and remembering $|s(n,k)|=(-1)^{n+k}s(n,k)$. So, recall $|s(n,k)|=|\{\pi \in S_n:\pi = (a_{1,1}\ldots a_{1,b_1})_1\ldots (a_{k,1}\ldots a_{k,b_k})_k\}|$, the permutations of $S_n$ with exactly $k$ disjoint cycles. Also, recall that $x^k$ is the numbers of ...


3

My attempt: The probability that a single column has at least one blocked site is 1-P(the column has no blocked site) = $1−p^n$ The probability of n columns each having at least one blocked site is then $(1−p^n)^n$. So your answer is $1−(1−p^n)^n$ [All the cell / column probabilities multiply because we assume their occupancies are independent of each ...


2

It can't end in $99$ since that is $3$ mod $4$. Therefore it can't start with $99$, so the next-highest prefix is $98$. Searching numbers of the form $989?989$ quickly yields $9896989$.


3

$9896989$ is prime and is $\equiv 1\pmod 4$, hence is the sum of two squares.


1

Are you interested in the number of compositions, or the list of compositions itself? The number of compositions can be obtained using generating functions. I assume, as in your example, that a two-person bedroom cannot be occupied by a single person. The number of compositions for $n$ people is the coefficient of $y^n$ in the expansion of $$ ...


0

Suppose we have a derangement of length $N - 1$. From this derangement, $N-1$ derangements of length $N$ can be constructed$^{[1]}$: Replace an entry of the derangement with $N$ Append the replaced value to the end of the list Example: $$\{2, 4, 1, 3\} \text{ becomes } \begin{cases} \{\color{blue}5, 4, 1, 3, 2\} \\ \{2, \color{blue}5, 1, 3, 4\} \\ ...


1

You can solve this using generating function such as this Bedroom 1 can be 0,1,2,3,4 Bedroom 2 can be 0,1,2,3,4 Bedroom 3 can be 0,2,4 Translating this into generating function and the number of combinations would be the coefficient of $x^4$ Thus the above problem could be translated into $(1+x+x^2+x^3+x^4)^2(1+x^2+x^4)$ and finding the coefficient of ...


1

This is not a combinatorial proof but I still find it rather nice. Let us replace $m$ by $x$ to get a more general polynomial identity. We can notice that \begin{equation*} (-1)^{k} \binom{n-k}{k} x^{k}(x+1)^{n-2k} \end{equation*} is the coefficient of $y^{k}$ in $(1+x-xy)^{n-k}$. Consequently the left hand of the identity is the coefficient of $y^{n}$ in ...



Top 50 recent answers are included