# Tag Info

## New answers tagged combinatorics

0

For a given crust there are seven pizzas possible (one with six toppings one with five toppings etc all the way to 0 toppings). To compute how many possible pizzas you could make with one crust would be consider how many combinations could be made from the 6 toppings if its a six topping pizza, how many can be made from the 6 toppings for a five topping ...

1

Suppose you have n toppings and $m$ crusts then you can either say yes or no to a topping. So you have two choices for each topping and $m$ choices of crusts. $$C = m \times \underbrace{2}_{Yes \ or \ No} \times \underbrace{2}_{Yes \ or \ No} \cdots \underbrace{2}_{Yes \ or \ No}\times \underbrace{2}_{Yes \ or \ No} \times \underbrace{2}_{Yes \ or \ No} ... 0 The number of ways you can order toppings is the number of subsets of a set with 6 elements. For each topping, you have two choices, include it or not include it. Therefore, there are 2^6 ways of ordering the toppings and three ways or ordering the crust, yielding 3 \cdot 2^6 = 192 different types of pizza. 1 You can re-write your recurrence like a_{n}-5a_{n-1}+7a_{n-2}-4a_{n-3}=0 this gives rise (through a transformation that you'd see in any intro combinatorics text) to the polynomial that have x^3-5x^2+7x-4=0. There are three solutions (maybe some are complex) to that equation, say r_1, r_2, r_3. Then, the closed form expression for you sequence will ... 0 If I have understood the rules of your game, the configuration of the board, depends on the particular movements that make the player. I'll number the squares like this:$$\begin{align} &12 \\ &34 \end{align}$$The following paths yield different color configurations of the board: 1, 12, 13, 121, 124, 131, 134, 1213, 1242, 1312, 1343. That makes ... 3 HINT: Think of it this way. You start with n white balls numbered 1 through n. You pick k of them (for some k\ge m) and paint them red. Then you pick m of the red balls and paint a gold star on each of them. In the end you have m red balls with gold stars, k-m red balls without stars, and n-k white balls. In effect you’ve simply divided the ... 1 Assume that the seats are numbered sequentially from 1 to 8, with Seats 1 and 8 also being adjacent. Without loss of generality, assign the first male to Seat #1 Then Seats 2 and 8 are forbidden for further male assignment. Also, assigning a male to Seats 4 or 6 would leave either two females seated adjacent in the gap (2 & 3 or 7 & 8), or a male ... 0 You're correct that there are 15! different permutations overall, but a lot of them are equivalent for your problems. You can count all the possible solutions (including all permutations) and divide that by 15!, but there's an easier way to think about it. What is the probability that a randomly picked child is a boy. Given a particular boy and ... 3 HINT: For the first question, simply observe that each of the 15 people is equally likely to be in the fourth position. For the second, observe that the boy is equally likely to occupy any of the 15 positions. 1 Note: In order to make a proof by induction better comprehensible we will do it in small steps. Let \varphi^{+}:\mathbb{N}^2\rightarrow\mathbb{N} with \varphi^{+}(i,j)=i+j \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ \ \ (1) Let \varphi_n^{+}:\mathbb{N}^{n}\rightarrow\mathbb{N}^{n-1} with ... 1 Unordered pair of disjoint subsets is exactly what it says it is. You are counting pairs of disjoint subsets (say (\{1,2\},\{3\})) but you want them unordered so the pair I just wrote is the same as (\{3\},\{1,2\}). As for the second part of you question consider what the choice for each element in you set is in terms of where it appears in the pair of ... 2 The answers and their explanations are as follows: 1) E,N,D,E,A have been used so the alphabets left are N,O,E,L now they can be placed before or after the instance of ENDEA, So the cases are ____ENDEA, ENDEA, __ENDEA,_ENDEA___,ENDEA___ each case has 4! permutations so the answer is (after taking ENDEA as one alphabet X) WE need arrangements of X,N,O,E,L ... 1 Hint: (for 1) You can treat the word ENDEA as one letter which for example you can symbolize as X. Now you need to find the permutations of the word with letters XNOEL. 0 note that:$$\begin{align}\text{D}(w)&=\lbrace i\in [n-1]: &w_i>w_{i+1} \rbrace \tag 1\\ \text{D}(w^r)&=\lbrace i\in [n-1]: &w_{n-(i-1)}>w_{n-i} \rbrace \tag 2\end{align}$$and we can write the second relation as:$$ \text{D}(w^r) =\lbrace j \in [n-1]: w_{j}>w_{j+1} \rbrace \tag 3$$now it's clear that$$\text{D}(w^r)\cup ...

3

Calculating the number of permutation is more complex than a classical combinatorial question, since not every permutation of the 6 colors is accessible from the original state. Rubiks cube is actually a group with 3 moves (for each dimension) on either the top or bottom layer. Counting the number of valid states, is actually the size of the group. More ...

1

It's easiest to explain this with an example: take the set of colours {red, green, yellow, blue, orange} The number of permutations is how many different ways they can all be re-arranged; since there are five elements, the answer is 5! With combinations one is asking a different question; which is how many ways we can choose, say two, colours from the set. ...

2

Your example is just saying: how many different unique outfits can I make if I wear one shirt, one pair of pants and one pair of shoes. So you say that there are 3 things you need to do: choose 1 shirt, choose 1 pair of pants and choose 1 pair of shoes. Multiplicative principle: If I have $5$ different shirts, $3$ different pairs of pants and $2$ ...

2

A permutation is a way of rearranging items, a combination is a way of combining different items together. What you want is to combine one item from each set (where the different sets are the set of shirts, set of pants etc') I have added links to Wikipedia for permutations and combinations, it may be worth while reading them

2

You mean permutation of $n$ elements. The formula to obtain this number is $$n!$$ Example $n=4$, then you have the elements $1$, $2$, $3$ and $4$. The permutations are: $$1)~1,2,3,4\\2)~1,2,4,3\\3)~1,3,2,4\\4)~1,3,4,2\\5)~1,4,2,3\\6)~1,4,3,2\\7)~2,1,3,4\\8)~ ... 1 Just so this one doesn't stay unanswered, as Kamster says the chance of one winning number is \frac{\binom{6}{1}\cdot\binom{44}{5}}{\binom{50}{6}} because when you choose the non-winning numbers there are only 44 of them to choose. Once you adjust your other answers with this in mind you will be correct. -1 You have five choices for the first element, four choices for the second, and three choices for the third.$$5 \times 4 \times 3$$Consider a simpler example: How many ways can you arrange three letters of {A,B,C,D}? \begin{matrix} ABC & BAC & CAB & DAB\\ ABD & BAD & CAD & DAC\\ ACB & BCA & CBA & DBA\\ ACD & BCD ... 0 How many ways can you choose three letters from \lbrace A, B , C, D, E\rbrace?; \binom{5}{3}. And how many ways can we arrange the three, where order matters?; well, I have three options for the first, two for the second and 1 for the last. By this multiplication principle, that gives us 3!. Multiplying \binom{5}{3}*3! is your answer. 0$$\begin{align} \sum_{i=0}^k(-1)^i {k\choose i} {m-i\choose k} &=\sum_{i=0}^k(-1)^i {k\choose i} {m-i\choose m-k-i}\\ &=\sum_{i=0}^k (-1)^i{k\choose i }{-k-1\choose m-k-i}(-1)^{m-k-i}&&(1)\\ &=(-1)^{m-k}\sum_{i=0}^k {k\choose i }{-k-1\choose m-k-i}\\ &=(-1)^{m-k}{-1\choose m-k}&&(2)\\ &=(-1)^{m-k}{m-k\choose ...

0

If I take a graph with vertex set $\mathbb{R}$, and connect 0 to every $x \in \mathbb{R} \setminus \{ 0 \}$, then I have uncountably many finite paths from 0. If on the other hand you require the vertex set to be countable, then the number of finite paths from any given point is countable. (As it is a countable union of countable sets). As Tryss says, if ...

1

Note: Here is a slightly different variation of the same story. These techniques are also known as formal residual calculus for power series. They are based upon Cauchys residue theorem and were introduced by G.P. Egorychev (Integral Representation and the Computation of Combinatorial Sums) to compute binomial identies. We use the residue notation and write ...

2

First notice that $(k + 1)^{n}$ is the number of $n$-digit integers written in base $k+1$, allowing for leading zeroes. (For example, there are $1000=(9+1)^3$ three-digit numbers in base $10$: $000, 001,\dots,$ and $999$. Now count those same integers in a different way. First count those that don’t use the digit zero at all. There are $k^n$ of them ...

1

You know that $$e^z=\sum_{n\ge 0}\frac1{n!}z^n$$ and that $$D(z)=\sum_{n\ge 0}\frac{d(n)}{n!}z^n\;.$$ Now take the Cauchy product: $$D(z)e^z=\left(\sum_{n\ge 0}\frac{d(n)}{n!}z^n\right)\left(\sum_{n\ge 0}\frac1{n!}z^n\right)=\sum_{n\ge 0}c_nz^n\;,$$ where ...

1

Let us list the elements from $1$ to $n$ divisible by $k$. We have the set $A_k$ to be $$A_k = \left\{k,2k,3k,\ldots,\left\lfloor{\dfrac{n}k}\right\rfloor k \right\}$$ and the total set to be $A = \{1,2,\ldots,n\}$. Hence, the probability of a number being divisible by $k$ is $$p = \dfrac{\vert A_k \vert}{\vert A \vert} = \dfrac1n \left\lfloor ... 1 Let n=ak there are are exactly a numbers between 1 and n divisible by k which are :$$k,2k,3k,\cdots,ak $$and there are n numbers in total so:$$p(A_k)=\frac{a}{n}=\frac{1}{k} $$0 \cup is the union. It means that you take the total number of people in both sets regardless of where they fall in between. \cap is the intersection. It means that you take only the people that are in both sets. i.e. they play both sports n(A) is the number of people in a set A Let S = sample space Let H = event that children play hockey Let ... 0 Sometimes a little research can help. The formula you posted was discovered by Jon Perry in 2003. The generating function for this problem is:$$g(x) = \frac{1}{(1-x) \left(1-x^2\right) \left(1-x^3\right) \left(1-x^4\right)} $$There does not seem to be something simple for your question but Michael Somos comes up with ... 1$$\begin{align} \sum_{k=0}^r(-1)^k\binom rk\binom{n+r-k-1}{r-k-1} &=\sum_{k=0}^r(-1)^k\binom rk\binom{-n-1}{r-k-1}(-1)^{r-k-1}&&(1)\\ &=(-1)^{r-1}\sum_{k=0}^r\binom rk\binom{-n-1}{r-1-k}\\ &=(_1)^{r-1}\binom{r-n-1}{r-1}&&(2)\\ &=(-1)^{r-1}\binom{n-1}{r-1}(-1)^{r-1}&&(3)\\ &=\binom{n-1}{r-1}\qquad\blacksquare ...

0

OK, $B_0$ is the ways you get no match, using Inclusion-Exclusion Principle where $a_i$ is the probability that $i$ is in correct place: $$P\left(\sum a_i\right)=S-1-S_2+S_3...$$ And now ${\rm P}(\text{none in correct place})+{\rm P}(\text{atleats one in correct place})=1$, so proceed. Thus obtained formula is so common it is called derangements, $!n$ or ...

3

This turns out to be a detailed explanation of Jack's answer. \begin{align} \left(\frac{1-x^{13}}{1-x}\right)^5 &=(1-x^{13})^5(1-x)^{-5}\\ &=\sum_{j=0}^5(-1)^j\binom{5}{j}x^{13j}\sum_{k=0}^\infty(-1)^k\binom{-5}{k}x^k\tag{1}\\ &=\sum_{j=0}^5(-1)^j\binom{5}{j}x^{13j}\sum_{k=0}^\infty\binom{k+4}{k}x^k\tag{2}\\ ... 6[x^{30}]\left(\frac{1-x^{13}}{1-x}\right)^5 = [x^{30}]\sum_{k=0}^{5}\binom{5}{k}(-1)^k x^{13k}\sum_{n\geq 0}\binom{n+4}{4}x^n \tag{1}$$hence the LHS of (1) equals:$$\binom{5}{0}\binom{34}{4}-\binom{5}{1}\binom{21}{4}+\binom{5}{2}\binom{8}{4}=\color{red}{17151.}\tag{2}$$2 The coefficient attached to x^{30} will be the number of ways you can add up to 30 by using the numbers 0-12 up to five times. (Here order matters) For instance 1+1+2+10+6=30 is one way. 10+10+10+0+0=30 is another and so is 0+10+10+10+0 = 30. The reason for this is more apparent for smaller polynomials. For instance let's calculate the ... 0 Once you have:$$ g(x)=\sum_{n\geq 0}h_n x^n = \frac{\color{red}{x}}{(1-2x)(1-x)} = \frac{1}{1-2x}-\frac{1}{1-x}\tag{1}$$it is straightfoward to check that \color{red}{h_n=2^n-1}. Just check your computations since the value in zero of \frac{1+x}{(1-2x)(1-x)} is one, while you have h_0=0. 0 It is fine. Now you need to split this expression g(x)=\frac{1+x}{(1-2x)(1-x)} as a combination of simple elements, i.e. terms of the form \frac{1}{a x + b} (in your case). From there, finishing should be easy. You may also check your answer by directly computing the terms h_n as A \lambda^n + B \mu^n for the characteristic roots \lambda and \mu. ... 1 Your answers are right. Here is a different presentation but same idea. P(3 cards with at least 2 of the same suit) = ({4 \choose 2} * 2!*13*{13 \choose 2} + {4\choose1}*{13 \choose 3})/{52 \choose 3} 1 Making use of what you call 'COMBIN' function:$$1-\binom{4}{3}\binom{13}{1}\binom{13}{1}\binom{13}{1}\binom{13}{0}\binom{52}{3}^{-1}$$if you draw 3 cards.$$1-\binom{4}{4}\binom{13}{1}\binom{13}{1}\binom{13}{1}\binom{13}{1}\binom{52}{4}^{-1}$$if you draw 4 cards. 1 If you look at :$$(X+1)^n=(X+1)...(X+1) $$Then it is a product of the sum of two terms :$$(a_1+b_1)(a_2+b_2)...(a_n+b_n) $$any term in the distribution will look like :$$c_1\times c_2\times ...\times c_n $$where c_i is either a_i or b_i. In other terms :$$(a_1+b_1)(a_2+b_2)...(a_n+b_n)=\sum_{(c_1,...,c_n)\in \{a_1,b_1\}\times...\times ...

1

We will count certain connected subgraphs of a "master graph" like a chess board, namely a rectangular grid of size $m\times n$ vertices (rows by columns) with $m\cdot(n-1)$ horizontal and $(m-1)\cdot n$ vertical edges. All of our graphs will be simple, i.e. the edges are undirected and may be identified by an unordered pair of distinct vertices. Thus ...

0

HINT: The sequence might start $S=\{0,1,4,5,16,17,20,21,64,...\}$ Write them in base 4.

1

You can try prove this by mathematical induction. If n=1 then $(a+b)=\sum_{i=0}^{1} {{1}\choose{i}} a^{1-i}b^{i}$. Now we guess that is true for $n=k$ this is: $$(a+b)^k=\sum_{i=0}^{k} {{k}\choose{i}} a^{1-i}b^{i}$$ and now we should prove that is true for $n=k+1$. Then we can start by: $$(a+b)^{k+1}=(a+b)(a+b)^k= (a+b)\sum_{i=0}^{k} {{k}\choose{i}} ... 1 In (k+1)^n = \underbrace{(k+1) * \cdots * (k+1)}_n you will get a sum of single terms like k^l. The idea is to calculate how many times each k^l appears in the sum. The ways of taking l factors "k" out of a total of n factors is \binom{n}{i}. For example, using distributive law (k+1)^3 = (k+1) * (k+1) * (k+1) = k*k*k + k*k*1 + k*1*k + k*1*1 ... 0 By definition, the generating function is$$H(z)=\sum_{n=0}^\infty h_nz^n=\sum_{n=0}^\infty (-2)^n n^2 z^n=\sum_{n=0}^\infty n^2(-2z)^n. $$From$$\frac1{1+2z} = \sum_{n=0}^\infty (-2z)^n,\frac{\mathsf d}{\mathsf dz}\left[\frac1{1+2z}\right] = \frac{-2}{(1+2z)^2} = \sum_{n=0}^\infty -2(n+1)(-2z)^n,$$and$$\frac{\mathsf d^2}{\mathsf ...

3

It seems the following. The average $A$ is uniquely determined by two other numbers, which have to have equal parity in order to $A$ be integer. So the number of ways is equal to the number of ways to choose two distinct even numbers from 1 to 80 (which is equal ${40 \choose 2}$) plus to the number of ways to choose two distinct odd numbers from 1 to 80 ...

2

Counterexample for your question: Let $L$ be the lattice of all subsets of $\{1,2,3,4,5,6\}$ and let $n=2,\ t=\{1,3,5\},\ x_1=\{2,3,6\},\ x_2=\{4,5,6\}.$ Counterexample to the identity you're trying to prove: Consider the $7$-element lattice $L=\{0,1,a,b,c,d,t\}$ where $$a\wedge b=0,\ a\vee b=t,\ c\wedge t=a,\ d\wedge t=b,\ c\vee d=c\vee t=d\vee t=1.$$ Then ...

1

Let $(x,y) \in \mathbb{Z}^2$ be any solution for the inequalities $$x^2 - 2013^2 \le y \le 2013^2 - x^2\tag{*1}$$ It is clear $|y| \le 2013^2 - x^2 \le 2013^2$ $x^2 - 2013^2 \le 2013^2 - x^2 \iff 0 \le 2013^2 - x^2 \iff |x| \le 2013$ From these, we can conclude $N$, the number of solutions for $(*1)$, is finite. Notice If $(x,y)$ is a solution, so ...

1

For any $A$ the inequality $-A \le y \le A$ has an odd number of solutions, since $0$ is one solution and other solutions come in pairs $(-t,t)$ where $t \neq 0.$ So if $x$ in your problem is any fixed integer, there are an odd number of solutions. On the other hand if $x$ is allowed to be just any integer there are infinitely many solutions, which is not ...

Top 50 recent answers are included