Combinatorics: Examples, Equations, and Practice Problems

The knight's tour is a sequence of 64 squares on a chess board, where each square is visted once, and each subsequent square can be reached from the previous by a knight's move. Tours can be cyclic, if the last square is a knight's move away from the first, and acyclic otherwise.
There are several symmetries among knight's tours. Both acyclic and cyclic tours have eight reflectional symmetries, and cyclic tours additionally have symmetries arising from starting at any square in the cycle, and from running the sequence backwards.
Is it known how many knight's tours there are, up to all the symmetries?

There are numbered cards 1 to 13 each of colour red, green, yellow and white. And four players have been distributed 4 each of these cards randomly. What is the probability that each player gets at least one card from each colour?

Let us be given a $n\times <!--\; \times \; -->n$ matrix containing only zeros and ones.Now, the goal is to remove some 'ones' from the matrix (i.e. replace them with zeros) so that in each row and each column there is at most one 'one'. Of course, it is preferable that we leave as much 'ones' as it is possible (maximum is obviously $n$).
Now, let us define the following algorithm: if there is a 'one' which is all alone in a column or a row, leave it there, and replace all 'ones' in its column and row with zeros. We repeat the process as long as there are single 'ones' in rows or columns. If there are no single 'ones' left, we take the first row or column (first is counted from up (for rows) and from left (for columns)) containing two 'ones' (if there are no pairs, we go for the first triplet and so on). In that pair (or triplet, or ...) we leave the first 'one' intact (first is counted from the left for elements of row, from the top for elements of a column) and change all other 'ones' in the row and column of that first 'one' into zeros. Now, we check are there now any single 'ones' as defined above - if yes, we repeat that part of the algorithm, if no, we look for the first pair, triplet, etc. The algorithm ends when all 'ones' are singles both in their column and row.
Does this algorithm always give the maximum covering, i.e. does it always terminate with maximal number of 'ones' in the final matrix? In other words, can there be a matrix with a possible exclusion of some ones such that it ends up with n ones using some other exclusion scheme, while ending up with less than n 'ones' using the algorithm described above?

What are the uses of pascal's triangle in real life?

Suppose we have 20 balls numbered 1,2,...,20. Each day we pick a single ball randomly.
1) What's the probability of picking all 20 balls in 22 days ?
2) What's the probability of picking only 1and2 in 4 days (Atleast 1 times each) ?

Is it possible to quantify the number of dimensions in combinatorial spaces. The space I am particularly interested is all partitions of a set, bounded by the Bell number, where objects in this space are particular partitions.

n men and m women are standing in a line (randomly).
Find the expectancy of the number of men that stand beside a women (at least one side - left or right)
Harder question: Now solve it, but they stand in a circle and not a line.
I wanted to use an indicator:
$X=$ number of men standing beside at least one women.
$$\begin{gathered} X_i=1\text{if standing besides a women} \\ 0\text{else} \end{gathered}$$
And so: $E[X]=E[\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{X}_i]=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}E[X_i]$
the problem is that I am having a time computing what is the probability a random men will stand next to a women (left or right or both)

Given n students participating in a contest of m questions. At each stage, a student may choose to do the question in English or German or skip it. For every two questions, there exists a student who chooses to do both the questions and do them in different languages. What is the largest value that m can take.
Hint: The answer to this question is $m\le <!--\; \le \; -->2^n$, you might expect where the binary system is used

How many pieces of cheese we can obtain from a single thick piece by making five straight slices? (we can't move the cheese when slicing) If we want to maximize the number of pieces which is denoted by $P(n)$, is there any recurrence relation for $P(n)$, where $n$ is the number of slices?

In a chess tournament, each pair of players plays exactly one game. No game is drawn. Suppose the $i^{th}$ player wins $a_i$ games and loses $b_i$ games. Show that
$\sum <!--\; \sum \; -->a_i^2=\sum <!--\; \sum \; -->b_i^2$
$\sum <!--\; \sum \; -->a_i^2=\sum <!--\; \sum \; -->b_i^2$

When does an orthomorphism of the cyclic group exist?
Prove that orthomorphisms of ${\mathbb{Z}}_n$ exist if and only if $n$ is odd.
An orthomorphism of the cyclic group ${\mathbb{Z}}_n$ is a permutation $\mathrm{\sigma <!--\; \sigma \; -->}:{\mathbb{Z}}_n\to <!--\; \to \; -->{\mathbb{Z}}_n$ such that $i\mapsto <!--\; \mapsto \; -->\mathrm{\sigma <!--\; \sigma \; -->}(i)-<!--\; -\; -->i$ is also a permutation.
Actually, one direction is easy: $\mathrm{\sigma <!--\; \sigma \; -->}(i)=2i$ is an orthomorphism of ${\mathbb{Z}}_n$ when $n$ is odd. So what's left is to prove the non-existence of orthomorphisms of ${\mathbb{Z}}_n$ when $n$ is even.

I need $n$ cakes for a party. I go to the cake shop and there are $k$ different kinds of cake. For variety, I'd like to get at least one of each cake. How many ways can I do this?

From a standard $52$-card deck, how many ways are there to pick a hand of $k$ cards that includes one card from all four suits?
I know that for any specific $k$, it's possible to break it up into cases based on the partitions of $k$ into $4$ parts. For example, if I want to choose a hand of six cards, I can break it up into two cases based on whether there are $(1)$ three cards from one suit and one card from each of the other three or $(2)$ two cards from each of two suits and one card from each of the other two.
Is there a simpler, more general solution that doesn't require splitting the problem into many different cases?

Choosing subsets of a set such that the subsets satisfy a global constraint
We have a set of items $I=\{i_1,i_2,...,i_n\}$. Each of these items has what we call a $p$ value, which is some real number. We want to choose a subset of $I$, call it $I^{\prime }$, of size $m$ (for some m with $1\le <!--\; \le \; -->m\le <!--\; \le \; -->n$) such that the average of the $p$ values of the items in $I^{\prime }$ falls within some specified range, $[p_l,p_u]$.
We hope to do this in $O(n)$ time, but any polynomial time algorithm is good enough. We certainly do not want to just try every possible subset of I of size $m$ and then check whether it satisfies the average $p$-value constraint.
Finally, we will be doing this repeatedly and we want the subsets chosen to be a uniformly random distribution over all the possible such subsets.
Is there a way of doing this?

Prove that it is impossible to construct two different seven digit numbers, one of which is divisible by the other, out of the digits 1,2,3,4,5,6,7 (All seven digits must be in each number)

Using generating functions one can see that the $n^{th}$ Bell number, i.e., the number of all possible partitions of a set of $n$ elements, is equal to $E(X^n)$ where $X$ is a Poisson random variable with mean $1$. Is there a way to explain this connection intuitively?

1.How many number of three digit even numbers than can be formed out of the digits 0 to 9 ?
The question seems confusing since there is no mention of whether repetition is allowed or not ?! since if repetition is allowed then the answer would be 450 (5*9*10) where as if not then the answer would be 328 (9p2+ 4*(8*8) = 328).
Am I correct about the question or am missing some point ?
2.How many calendars that can be prepared for the month of February ?
3.A golf player wants to put the ball in the hole in 5 shots. He says that he will put the ball in the hole at most by 3 shots and will qualify for the next round. how many number of possibilities of shots he had played ?

These are two problems I have to solve and I just need you to check if my solution is correct.
First: I have 10 red balls and 3 blue balls. What is the probability of picking 1 red ball and 3 blue balls?
My solution: 10/13 * 3/12 * 2/11 * 1/10 = 1/286
Or should it be 10/13 * 3/12 * 3/11 *3/10 = 9/572?
Second: They have 16 different postcards in the shop. How many possibilities do we have if we want to choose 6 different ones?
My solution: 16 * 15 * 14 * 13 * 12 * 11 = 5765760

Using the numbers 0,1,2,...,9 as digits, how many 4-digit numbers exist in which all digit are different with two digits as even numbers and two as odd numbers?

Suppose we have a sequence of non-negative integers that is periodic with period $N$:
$A_1,A_2,...,A_N,A_1...$
Each $A_k$ takes on a value no greater than some constant $B$:
$0\le <!--\; \le \; -->A_k\le <!--\; \le \; -->B$
We then take this sequence and do a simple convolution, for some constant $L>0$ and $1\le <!--\; \le \; -->n\le <!--\; \le \; -->N$:
$S_L(n)=A_n+A_{n+1}+...+A_{n+L-<!--\; -\; -->1}.$
From $S_L(n)$ we then form a probability distribution $P(n)$ which gives the frequency of each of its values. Let $e_j(k)=1$ if $j=k$ and $0$ otherwise. Then:
$P(n)=(e_n(S_L(1))+e_n(S_L(2))+...+e_n(S_L(N)))/N.$
What I would like to find out is the extent to which this process can be reversed. I have two data points:
1) I know (pretty much) everything about the probability distribution $P(n)$: the distribution itself, its mean, range, variance, skewness, kurtosis, etc.
2) I can tell you the frequency of values of $A_k$ in one period, so that if the sequence is 1,0,2,3,1,0, I can tell you there are two 0's, two 1's, one 2, and one 3.