# Tag Info

## Hot answers tagged combinatorics

6

One easy way is to observe in the binomial expansion of $(1+1)^{2n} = \sum\limits_{k=0}^{2n} \binom{2n}{k}$, the term $\binom{2n}{n}$ is the largest one among all the $2n+1$ terms of the form $\binom{2n}{k}$. This gives us a bound $$\frac{2^{2n}}{2n+1} \le \binom{2n}{n} \le 2^{2n} \quad\implies\quad \log 2 - \frac{\log(2n+1)}{2n} \le ... 5 Alternative computation:$$\begin{align*} a_n &= \frac{1}{2n} \log \binom{2n}{n} = \frac{1}{2n} \log \frac{(2n)!}{(n!)^2} \\ &= \frac{1}{2n} \sum_{k=1}^n \log \frac{n+k}{k} = \frac{1}{2n} \sum_{k=1}^n \log \Bigl( 1 + \frac{1}{k/n} \Bigr). \end{align*}$$Therefore, as n \to \infty, we get a Riemann sum:$$\begin{align*} \lim_{n \to \infty} a_n ...

3

You mean like this? http://ruwix.com/online-rubiks-cube-solver-program/solution.php?cube=0343515641165422615412533412316442361454656232126363525&x=1 To find the solution just click "play".

3

One could equally ask for the probability with ordered or unordered pairs, with different results. It suffices to count the number of pairs $a,b$ satisfying $x=ab\vee x=ba$, where $x\in G$ is fixed. Say we wish to count ordered pairs of not necessarily distinct elements. Notice the equivalence $x=ab\vee x=ba\iff b=a^{-1}x\vee b=xa^{-1}$. If we naively ...

3

You could use the binomial theorem twice. Let $[x^{k}]$ denote the coefficient of $x^k$ from the polynomial $P(x)=\sum_{j=0}^{n}a_jx^j$, i.e. $[x^{k}]P(x)=a_{k}$. Now, ...

3

Here is what Wikipedia has to say about the matter: Hamiltonicity of the hypercube is tightly related to the theory of Gray codes. More precisely there is a bijective correspondence between the set of $n$-bit cyclic Gray codes and the set of Hamiltonian cycles in the hypercube $Q_n$. There is a reference to a 1963 paper by W. H. Mills in Proc. AMS.

3

A number is divisible by $8$ if the last three digits are divisible by $8$. Now, we can arrange the first $5$ digits of our answer in $5^5$ ways, because each of the position can take $1$ of $5$ values. Now, our problem reduces to the following. How many three digit numbers formed with $\{1,2,3,4,5\}$ are divisible by $8$? We can enumerate all the ...

3

We know that the string will take the form of $$*S█S█S█S*$$ where $█$ MUST have at least one character and $*$ can be of any length (even 0). I would suggest the following steps: Find the number of ways you can put the $S$s (they can be in positions $(1,3,5,7)$, $(2,5,8,11)$, $(1,4,6,9)$, etc.) Find the number of different strings you can make with ...

2

Usual tricks to get started for any problem Try a simpler problem Try brute-force calculation Look for other problems that this one resembles Have you any ideas on how to do any of these three things? For counting problems in particular, one trick that is: Try counting the complement: how many things are there in all, and how many aren't the kind of ...

2

If the contestants are all distinct, you can take account of that by changing your coefficients: Of the $5$ entrants from each state, there are $\binom{5}{0}$ ways to choose 0 of them, $\binom{5}{1}$ ways to choose $1$, $\binom{5}{2}$ ways to choose $2$, and so on. So, the generating function for contestants from a single state is $$... 2 An explicit but not very useful formula would be$$ \sum_{ c=1}^C {\sum_{ 0 \le n_i \le N_i \atop {\sum {n_i}=c}}} \frac{c!}{\prod n_i!} $$were C is the maximum word length and N_i coutns the available repetitions of each letter. Java code (not very elegant or efficient): https://ideone.com/4lLX2u 2 For a you have a stars and bars problem where you have to have exactly 10-1=9 dividers. For b you multiply by the factorial of each component. For c the Wikipedia article shows how to modify the number. 2 An equivalent way of describing the game is that, starting from 1, the two players simply take turns multiplying the current product by any number between 2 and 9. It sounds as if the winner is defined to be the player who first produces a product that is greater than or equal to n. Naming the player who is supposed to win and asking whether they ... 2 There must be at least 14 participants signed up for one of the three classes (by the pigeonhole principle), and this is the best possible n if one means simply that some (single) combination of a class must attract at least n participants. However if instead we mean to count participants whose entire signup selections agree, then the number n will ... 2 This is simpler if you rewrite your left hand side as$$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2= \sum_{i=0}^{2n}(-1)^i\binom{2n}i^2= \sum_{i=0}^{2n}(-1)^i\binom{2n}i\binom{2n}{2n-i} $$first. So you are looking for the coefficient of X^{2n} in the product (1-X)^{2n}(1+X)^{2n}=(1-X^2)^{2n}, which is the same as the ... 2 HINT :$$\begin{align}f'(x) &= 3x^2 + 2ax + b \\ &= 3(x + \frac{a}{3})^2 + b - \frac{a^2}{3}\\ &\ge b - \frac{a^2}{3}\end{align}$$Now, f'(x) > 0 \implies f(x) is an increasing function (an unrelated but good question to think about : does f(x) increasing \implies f'(x) > 0?). What can you now say about the probability for which ... 2 I. First calculate the number of words that can be formed from "CHISEL", with no restrictions. Subtract from your answer to I the number of words that contain (the "chunk" "LE" or the chunk "CHEL"). Assuming repetition of letters is not allowed, then we we have 6 possible letters to choose from for the first letter of the word, 5 possible choices ... 2 Of all the numbers that are formed with 1,2,3,4,5 - the last three digits need to be divisible by 8. There are 5^3 ways you could arrange the five numbers for the last three digits. Of these last three digits that are divisible by 8 are 312, 152, 512, 432, 352, 112, 232, 224, 144, 424, 344, 552, 544. A total of 13 of them which I got by brute force ... 2 As suggested in several comments, the simplest form of Stirling approximation for n! is$$\sqrt{2 \pi } e^{-n} n^{n+\frac{1}{2}}$$(http://en.wikipedia.org/wiki/Stirling%27s_approximation) Take the logarithms and develop first$$\log\left(2n!\right) - 2\log\left(n!\right)$$which results to be (2 n+1) \log (2). The remaining is obvious. If I may, ... 2 Just a sketch of a proof; sorry, this is all I can do with the time I have right now. If m\in\mathbb N is arbitrary, then an m-reciprocal polynomial means a polynomial p \in \mathbb Z\left[q\right] whose coefficient before q^i equals its coefficient before q^{m-i} for every i\in\mathbb Z (this implies that the degree of p is \leq m). Let ... 1 I'll provide a combinatorical counting argument. Without the non-consecutiveness condition, the answer would be {n \choose 2} = \frac{n\cdot(n-1)}{2}. Intuitively, you choose 1 number first (n choices) and another one from the remaining set (n-1 choices) and abstract away the move sequence. Back to the original problem, for each m \in \{2, ..., ... 1 First of all, some unsolicited advice: your derivation for (b) need not be so messy. It greatly simplifies things to observe that$$ f(n,m,k) = f(n-1,m,k) + f(n-1,m-1,k) - f(n-k-1,m-k,k) \tag{1} $$holds not just when 0 \le k \le m \le n, k < n. In fact, it holds for any n \ge 0, m \ge 0, k \ge 1, except in the two cases m = n = k, and m = n = ... 1 Hint: There are two vowels A and E. So 4-letter words with them side by side have one of the 6 follows forms: AE-- -AE- --AE EA-- -EA- --EA Given any of these forms, how many ways can we add in the consonants? This gives the total number N of 4-letter words with A and E side by side. And the probability will be N/^6 P_4=N/360. 1 Hint: Assume your number has n+1 (distinct, i.e. no repetitions allowed) digits d_0, ... d_{n} (where d_0 denotes the unit digit that corresponds to 10^0, d_1 the tenth's digit that corresponds to 10^1 and so on), so that the number N can be written as$$\sum_{i=0}^{n}10^id_i$$Denote with P the set of all the allowed permutations \sigma. ... 1 Nicely done! As an alternative approach, you could note that the main issue is where J,M,P are sitting. So, we could proceed casewise as follows: (1) If we seat J on an end--2 ways to do this--then that leaves 6 open seats in which we can put M,P--\binom{6}{2}\cdot2!=\frac{6!}{4!} ways to do this--at which point, once those three are seated, ... 1 Consider how you can place the numbers \{1,2,...,2n\} into the columns, starting with 1 and proceeding from there. We create a string of X's and Y's, which, when read from the beginning indicate where to place the next number. X means place the number in the left column, Y says place the number in the right column. Now, note that all of the ... 1 You need to be a little more careful in applying the Counting Theorem. You're correct that all 2^6=64 colorings are fixed by the identity element, but it's only for the two rotations by \pm\pi/3 that only 2 colorings are fixed. For the two rotations by \pm2\pi/3 there are 2^2=4 colorings that are fixed, and for the (one) rotation by \pi, there ... 1 If people vote reflecting their preferences (i.e. voting for their first preference candidate) then somebody who gets over 50% of votes would be the Condorcet candidate. There are other issues: in particular simple plurality systems may discourage some voters from voting for their first preference candidate, and if this happens, then somebody who gets ... 1 Find the total number of words that can be formed using the letters C-H-I-S-E-L, and subtract the number of words containing LE or CHEL, noting that no word can contain both. In order to find the number of words containing, for example, CHEL, we may consider CHEL as its own character, so that$$ n_{CHEL} = 3 \times 2 \times 1  since there are $3$ ...

1

$\binom{4}{1}\binom{4}{2}\binom{44}{2}+\binom{4}{1}\binom{4}{3}\binom{44}{1}+\binom{4}{1}\binom{4}{4}\binom{44}{0}+\binom{4}{2}\binom{4}{2}\binom{44}{1}+\binom{4}{2}\binom{4}{3}\binom{44}{0}+\binom{4}{3}\binom{4}{2}\binom{44}{0}$ First factor deals with kings, second with aces, third with remaining cards. It might not be the shortest route, but gives you a ...

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