Articles of combinatorics

Permutation & Combination

There is a game in which there is a point P and k other points on a plane. To win, we must draw directed lines starting from point P and ending at point P with exactly n number of lines to be drawn. P can also come in between. Example: $n=2$, $k=4$ suppose points are […]

Shortest ternary string containing all ternary strings of length 3?

How can we find/construct the shortest ternary string that contains all ternary strings of length 3? For instance, $120011$ contains $120$, $200$, $001$, and $011$. (The shortest such a string could possibly be is 29 digits long, as we would have one digit for each 3 digit string, and the last trailing 2 digits for […]

Finding a generating function of a series

So say if you have a sequence defined as, for $a\in\mathbb{Z}$, $$ c_n = \binom{a}{0} \binom{a}{n} – \binom{a}{1} \binom{a}{n-1} + \cdots+ (-1)^n \binom{a}{n} \binom{a}{0} = \sum_{i=0}^n (-1)^i \binom{a}{i} \binom{a}{n-i}$$ How would you find the generating function? It’s easy to see that for $n = 2k+1$, $c_n= 0$, and for $n = 2k$ we can make […]

Placing stones on vertices of polygon

We have an $n$-gon with $n\geq 3$. Players $A$ and $B$ place a stone alternately on one of the unused vertices that is not adjacent to a vertex with a stone. The player who cannot move loses. Who has a winning strategy? If $n$ is even, $B$ can win by placing a stone at a […]

Nice problem of combinatorics..

I know a family that has $10$ children and half of them are married. Sometimes they ask me about mathematics, and ask me to show them nice things… I asked them: How many possible ways there are to pick $5$ of your children and that $3$ of them (at our selection) will be married? I […]

Arrange $n$ people so that some people are never together.

This question already has an answer here: Permutation of n objects with restriction of adjacent pairs 1 answer

How many combinations of 20 balls can be drawn from a bag of 10 blue balls and a bag of 10 red balls

Given: A bag of 10 red balls A bag of 10 blue balls. In how many sequences can one draw all the 20 balls. so a sequence could be (r for red ball, b for blue ball): b b b b b b b b b b r r r r r r r r […]

Proof for number of weak compositions

I’m looking for an alternative to the following (possibly standard) proof for the number of weak compositions: The number of $k$-compositions of $n+k$ corresponds to a weak one by subtracting 1 from each “bin”. Thus we have $\binom{n+k-1}{k-1}$. While I kind of like this proof and always felt it made sense lately I’ve been left […]

Kind of basic combinatorical problems and (exponential) generating functions

I have a pretty straightforward combinatorical problem which is an exercise to one paper about generating functions. How many ways are there to get a sum of 14 when 4 distinguishable dice are rolled? So, one die has numbers 1..6 and as dice are distinguishable then we should use exponential generating functions (we count sequences […]

What are the properties of these two functions?

OK, so I was kinda doodling stuff in my free time and I came up with these two functions: $$C_1(n) = \sum^{\infty}_{k = n} {{k \choose n}^{-1}}$$ $$C_2(n) = \sum^{n}_{k = 0} {{n \choose k}^{-1}}$$ I don’t have Mathematica or anything at the moment, so I can’t analyse these functions as such. Would anyone help […]