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

14 views

### Find the number of ways to reach from one end of grid to another

There's a 6 by 6 grid and you're asked to start on the top left corner. Now your aim is to get to the bottom right corner. You are only allowed to move either right or down. You must never move ...
41 views

### Subset of Coins with maximal value

Let $n \in \mathbb{N}$ with $n\ge 3$ be given. Assume that you have $k-1$ coins of value $1/k$ for all $k \in \lbrace 2,\ldots,n \rbrace$. Now you have to choose a subset of these given ...
73 views

### What is the number of Sylow p subgroups in S_p?

I am reading the Wikipedia article entitiled Sylow theorems. This short segment of the article reads: Part of Wilson's theorem states that (p-1)! is congruent to -1 (mod p) for every prime p. One ...
27 views

24 views

### Order of $\mathrm{SL}(n,\mathbb{F}_p)$ (Constructive proof)

Most proofs of $$\vert ~\mathrm{GL}(n,\mathbb{F}_p) ~\vert = \prod_{k=0}^{n-1} (p^n-p^k)$$ I have seen so far, are done by counting the possibilities to build up invertible matrices i.e. counting ...
40 views

### Painting the unit line black and white

A unit segment [0, 1] is colored randomly using two colors, white and black, according to the following procedure. The segment starts white. On each step, we choose two random points a and b on the ...
35 views

### what are the number of ways to select a 4 digit number with a 3 digit number always included? [on hold]

Number of ways to select 4 digit number( X X X X ) should have three digit number ( say 1 2 3 ) It should be in same order.
9k views

23 views

### How do I interpret following equations on fibonacii numbers?

I went through an online tutorial (http://codeforces.com/blog/entry/14385) on finding n-th fibonacci number which explains a method as, You are standing at position n in Ox axis. In a step, ...
3k views

### Fibonacci sequence divisible by 7?

Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$. I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.
2k views

### Triangle dissection, no shared edges

It's possible to divide a triangle into smaller triangles such that no edge lengths are shared. Alternately, no two internal triangles share two vertices. The top three are the known simplest ...
2k views

### hat matching problem (Ross, p.41)

I'm studying Ross's probability book, and kind of got stuck on the matching problem. Suppose that each of $N$ men at a party throws his hat into the center of the room. The hats are first mixed up, ...
17k views

### possible combinations of 3-digit

How many possible combinations can a 3-digit safe code have? Because there are 10 digits and we have to choice 3 digits from this, then we may get $10^P3$ but A author used the formula $n^r$, why is ...
385 views

### Probability of a slot having exactly $K$ elements

From this question asked in an interview: Consider a hash table with $M$ slots. Suppose hash value is uniformly distributed between $1$ to $M$. Suppose we put $N$ keys into this $M$-slotted ...
60 views

### What is the probability of two-pair poker hand?

To start with, this question has never been asked as how I am going to ask: What is the probability that a five card poker hand will have two pairs (with no additional cards)? Example of two-...
41 views

### Material to learn some basic combinatorics?

I realize that I'm pretty weak when It comes to basic combinatorics, even with simple things like n choose k I don't feel confident. Furthermore, I've viewed some combinatorics books and the reasoning ...
45 views

### Calculating the number of “birthday days” in the birthday problem

Given 's' students in a room and 'd' days in the calendar year, what is the probability 'P' that there will be 'k' "birthday days"? i.e., 'k = 1' means that everybody's birthday falls on the same day,...
84 views

What is an equivalent combinatorial presentation for the problem? Can I use the stars and bars approach to find the number of integral solutions of $a+b+c=n$ where $a,b,c\geq 0$? If in addition $a+b&... 1answer 403 views ### Number of 'unique' one bit binary functions with N-bit inputs Consider the set of binary functions that takes an N-bit input -> 1 bit output. There are 2^(2^N) elements in this set. Now potentially reduce this set by restricting to only considering functions ... 3answers 135 views ### Maximum area of triangle inside a convex polygon Prove that within any convex polygon of area$A$, there exists a triangle with area at least$cA$, where$c=\tfrac{3}{8}$. Are there any better constants$c$? I'm not sure how to approach this ... 1answer 23 views ### Find an explicit map with certain combinatorial properties The following combinatorial problem popped up in a totally uncombinatorial context: Let$\mathcal{P}$denote the power set of a set and let$k \in \mathbb{N}$. Is there a map$c: \mathcal{P}(\{1,2,\...
Find the number of integral solutions of the equation: $a+b+c=m$ with $0\gt a\gt b\gt c$ And the generalized version: $a_1 + a_2 + \cdots + a_k = m$ with $0\gt a_1\gt a_2\gt \cdots \gt a_k$