Hot answers tagged

2

I don't see an easy way. For your example, there are ${100 \choose 5} = 75287520$ possibilities for $B$. Of those, ${96 \choose 5}=61124064$ have no neighboring pairs. To count the number with neighboring pairs, you have $2$ choices pair at the end, then ${95 \choose 3}=138415$ ways to choose three non-neighbors out of what is rest, plus $97$ ways to ...


2

What you’re looking for is the number of partitions of $[n]$ into $k$ sets; this is a Stirling number of second kind, denoted by ${n\brace k}$ (or $S(n,k)$). These numbers satisfy a nice recurrence relation: $${{n+1}\brace k}=k{n\brace k}+{n\brace{k-1}}\;,$$ with initial conditions ${0\brace 0}=1$, and ${n\brace 0}={0\brace n}=0$ for $n>0$. There is an ...


1

The requirement that $f\circ f=f$ is equivalent to the requirement that if $x\in f[A]$, then $f(x)=x$. That is, $f\upharpoonright\operatorname{ran}f$ must be the identity on $\operatorname{ran}f$, and any function whose restriction to its range is the identity will have the desired property. Since it’s just as easy, I’m going to generalize your question. ...


1

The only bijective map that satisfies the condition is the identity. So the other maps are not surjective. Suppose the image of $f$ is $\{a,b\}$. Then $a=f(x)$ for some $x$ and so $f(a)=f(f(x))=f(x)=a$; similarly $f(b)=b$. Therefore we're left with $f(c)=a$ or $f(c)=b$. This gives two maps. Therefore we have $2\cdot 3$ maps having their image with ...


1

The answer is yes. Let $v(u)$ be the binary value of a binary word $u$. By definition, $$L = \{u \in \{0,1\}^* \mid 0^{v(u)} \in R\},$$ where $R$ is some regular language. First of all, since $R$ is regular, $S = R \cap 0^*$ is also regular and $$ L = \{u \in \{0,1\}^* \mid 0^{v(u)} \in S\}. $$ A regular language on the alphabet $\{0\}$ is semilinear, that ...


1

The formulation "$n(r,3,1)$ exists and is at most $2r+1$" is misleading, as it talks about $n(r,3,1)$ as if this denoted a minimal number, whereas $n=n(r,m,k)$ was introduced as any number with the given property, not necessarily minimal. It should say "we can choose $n(r,3,1)=2r+1$" instead. The lecturer didn't choose $n$ as $r+1$. Without fixing $n$, we ...


1

With the question by the OP asking for a reference I will try to do just that, providing links to the OEIS. Surprisingly enough even the OEIS does not offer the usual variety of references here, suggesting that this problem is open. We compute generating functions $T_{\le h}(z)$ for the height being at most $h$ and the desired count is then given ...


1

There's in fact a simple linear-size construction: Choose as $m$ the smallest power of two that is greater or equal to $n$. Then pick any $n$ rows of the $m\times m$ Hadamard matrix. Here's an example image of a Hadamard matrix:


1

We have 4 or 5 surgeons among the 6 in the panel. Count these separately. The order does not matter, so we can pick the 4 surgeons in ${5 \choose 4}$ ways followed by ${6 \choose 2}$ ways to pick 2 physicians. Add this to ${5 \choose 5}{6 \choose 1}$ ways to pick all 5 surgeons and 1 physician. The correct answer is not among your answers, BTW, unless you ...


1

The problem is known as derangements, usually presented as passengers with tickets randomly assigned seats on a plane or guests receiving the wrong hats. Solution to it is an inclusion-exclusion principle/theorem. Obviously the total number of seatings is $100!$. How many do we need to exclude to get all 'wrong' ones? Assume at least 1 person has a correct ...



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