Articles of combinatorics

Use mathematical induction to prove the product rule for m tasks from the product rule for two tasks.

I’m not exactly sure how to do this using mathematical induction. Thanks for the help. I’m trying to prove that the product rule is valid for some number of tasks $m$, such that $m$ is greater than two using induction and the product rule for two tasks as a given. The product rule for a […]

Flip coin Problem Combinatorics

Let’s say we are flipping a coin $n$ times. What is the probability that we always have more heads than tails. Meaning that if we are counting the number of times we have had heads and the number of time we have had tails, what is the probability that throughout the $n$ throws we continuously […]

Can we get the line graph of the $3D$ cube as a Cayley graph?

Given a graph $G=(V,E)$, the line graph of $G$ is a graph $\Gamma$ whose vertices are $E$ (the edges of $G$) and in $\Gamma$, two vertices $e_1,e_2$ are connected if, as edges in $G$, they share an endpoint. Now let $G$ be the $3D$ cube graph. It has $8$ vertices, $12$ edges and it is […]

Counting overlapping figures

How many four-sided figures appear in the diagram below? I tired counting all the rectangles I could see, but that didn’t work. How do I approach this?

How to check if any subset of a given set of numbers can sum up to a given number

Given a number, say $x$, and a set of numbers made up of only $k$ different numbers, where each of the $k$ numbers is repeated $n_1,n_2,\dots n_k$ times. How do I tell if it is possible to find a subset such that it sums to $x$. E.g.: $$x=6 , k=3$$ $$S=\{1,2,3,3,2,1\}$$ $$n_1=2, n_2=2, n_3=2$$ $$1+2+3=6$$ […]

Selecting from $\{1,2,3,4,5,6,7,8,9\}$ to guarantee at least one pair adds to $10$

How many numbers must be selected from the set $\{1,2,3,4,5,6,7,8,9\}$ to guarantee that at least one pair of these numbers add up to $10$? Justify your answer. Here’s my answer. Consider the two sets $\{1,2,3,4\}$ and $\{6,7,8,9\}$. In the worst case, one may pick the number $5$ and then all the numbers from one set […]

Combinatoric puzzle: minimum servings at dinner

During a dinner with $k=20$ persons sitting at $n=4$ tables with $m=5$ seats, everyone wants to share a table with everyone. The assembly decides to switch seats after each serving towards this goal. What is the minimal number of servings needed to ensure that everyone shared a table with all the other persons at some […]

Given $n$ distinct elements, how many Young Tableaux can you make?

Given $n$ distinct elements, how many Young Tableaux can one make?

Finding a bijective function from integer to words

I need to find a function to enumerate the ordered list of sequential words based on a charset. Let me give you an example. If the charset is “abc”, the function to be found “f” should compute the following: f(0) = a f(1) = b f(2) = c f(3) = aa f(4) = ab f(5) […]

Number of 5 letter words over a 3 letter alphabet using each letter at least once

This is similar to my previous question, Number of 5 letter words over a 4 letter group using each letter at least once. The only difference is that there are 3 letters to choose from instead of 4. However, I’ve run into a problem. Using inclusion exclusion I get: $3^5 – 3 \cdot 2^5 + […]