Tagged Questions

For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

2k views

Making Friends around a Circular Table

I have $n$ people seated around a circular table, initially in random order. At each step, I choose two people and switch their seats. What is the minimum number of steps required such that every ...
676 views

Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
594 views

Prove this determinant identity combinatorially

This is for those of you who understand the Lindstrom-Gessel-Viennot lemma. I am looking for a proof of the following identity using paths and such: Let $A$ be an $n\times n$ matrix, and for ...
206 views

Two interview questions

I recently came across two interview questions for admission in B.Math at an university. I gave the two questions a try and want to know if my solutions are correct or not. Q1: Given that ...
703 views

How to find a total order with constrained comparisons

There are 25 horses with different speeds. My goal is to rank all of them, by using only runs with 5 horses, and taking partial rankings. How many runs do I need, at minumum, to complete my task? As ...
334 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
How many $n$-element subsets $A$ of $\{1,2,3,\cdots,2n\}$ with specified sum are there？
Question: Let $n$ be an postive integer number.and let $A=\{x_{1},x_{2},\cdots,x_{n}\}$, How many $n$-element subsets $A$ of $\{1,2,\dots,2n\}$ are there,such ...