# 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.

72 views

267 views

### a 2-regular graph is cyclic or not?

We know the common result : - If every vertex of a graph G has degree at least2, then G contains a cycle. Can I conclude that 2-regular graphs are cycles where degree is exactly two of every vertex? I ...
67 views

### Number of ways two matrices can be multiplied?

Given the dimensions of two matrices what are the different ways they can be multiplied? Example $A[2][2]$ and $B[2][2]$ then answer is $2$. Let the dimensions of first matrix be $n \times m$ and ...
341 views

### Counting graph isomorphisms and entropy

Question: If all graphs on $n$ vertices are given equal probability, what does the induced probability distribution on the graph isomorphism classes look like? Are there any patterns that emerge as ...
80 views

43 views

38 views

### Prove that $P$ is a lattice (details inside)

Can someone please verify my proof or offer suggestions for improvement? There may be answers to the same questions elsewhere, but I need help with my proof in particular. Show that if $P$ is a ...
46 views

### Permutations on 5 letters

I was doing a riddle which said "five points are randomly distributed on the circumference of a circle. From any of these points, a continuous line may be drawn that connects the other points on the ...
51 views

### Let $P$ be a finite poset. Show that the number of order ideals equals the number of antichains.

Can someone please verify my proof or offer suggestions for improvement? I am aware that there are similar questions posted elsewhere, but I need help with my proof in particular. Some preliminaries: ...
72 views

### Probability of caugh at least 1 of one type of fish

In the lake we have got 3 types of fish: k - number of roach 2k - number of crucian 4k - number of perch Mr Smith caught 7 fish. What is a probability that Mr Smith caught at least 1 roach. My ...
252 views

### A method of making a graph bipartite

If we take a graph $G$, and sequentially delete the edge which belongs to the most odd cycles until we have a bipartite graph, will at least half the edges remain when the graph is bipartite? ...
38 views

### Let $P, Q, R$ be finite posets. Prove that $P^{Q+R} \cong P^Q \times P^R$.

Can someone please verify my proof and offer suggestions for improvement? I feel that my proof might have been a little hand-waving in showing that $\varphi$ is a bijection, and I feel that it is not ...
81 views

### Number of ways to empty three boxes in a given number of steps, while taking at most one ball from each box at every step

Given a set of three boxes, each of which contains number of balls (say $x,y,z$ respectively), we have to empty the all the three boxes in exactly $N$ steps. At each step we have to pick at least $1$...
49 views

### Combinations of winning scholarships

If six students are eligible for two scholarships worth 1k each, how many different combinations of 2 students winning the 2 scholarships are possible? My attempt 6 nCr 2. How am I wrong?
87 views

### Binomial Congruence (mod 5) Identity

I've got a (hard?) Putnam-style problem that I've been given to look at . . . I've never worked any problem even vaguely like this, but my director thinks I should be able to do it. I doubt it (100% ...
87 views

### Let $S$ denote the set of all functions $f :\{0,1\}^4 \rightarrow \{0,1\}$. What is the number of functions from the set $S$ to the set $\{0,1\}$?

They say the answer is $2^{2^{16}}$ but I think the answer is $3^{3^{16}}$ because they have not specified the functions to be total. Am I correct? PS: I am a newbie so please don't be too harsh if ...
118 views

### Counting partition of set that $i$ and $i+1$ are not in one part

I have to count the number of partitions of the set $\{1,\ldots,n\}$ under the constraint that for each $i$, the elements $i$ and $i+1$ are in different parts. The my idea is: We have two situation ...