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.

learn more… | top users | synonyms (4)

0
votes
2answers
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 ...
1
vote
2answers
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 ...
3
votes
1answer
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 ...
1
vote
3answers
27 views

Problem related to series of binomial coefficients

Problem related to series of binomial coefficients in which each term is a product of two binomial coefficients. In this question: Prove that $$\binom{n}0^2+\binom{n}1^2+\ldots+\binom{n}n^2=\...
0
votes
0answers
26 views

Functional equation of $f(n)=\sum_{k=0}^{n-1}g\left(x+\frac{k\pi}{n}\right)$

Suppose the function $f(n)$ is given by: $$f(n)=\sum_{k=0}^{n-1}g\left(x+\frac{k\pi}{n}\right)$$ Where $x\in\mathbb{R}$. I am looking for a formula that enables me to express $f(n)$ as : $$f(n)=\sum ...
1
vote
0answers
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 ...
1
vote
2answers
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 ...
-2
votes
0answers
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.
14
votes
10answers
9k views

Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$

I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$. I suppose I could use the counting rules in probability, perhaps combination= ${{n}...
0
votes
1answer
68 views

Number of sequences that maintain a property

In how many ways can i create a sequence of $m$ elements from the set $1,2,...,n$ such that the longest strictly increasing subsequence of it is exactly $n$? For example if $n=3$ and $m=4$ then the ...
4
votes
0answers
63 views

example of toric varieties with nontrivial first cohomology group

If I remember correctly, when a toric variety is smooth or simplical (the moment polytope is simplicial rational), then there is no odd dimensional cohomology group and the dimension of the even ...
1
vote
1answer
25 views

On a possibility/impossibility of a certain twisted situation in a tournament

Recently I encountered the following puzzle: Consider a game for two players which can only result in a win of one of the players (no ties). Now $n$ players decided to play this game each with ...
0
votes
0answers
16 views

Count the number of functional digraphs with special restrictions

Given a set of $n$ nodes, how can I count the number of possible functional di-graphs whose biggest connected component contains k node? With a restriction that no node can have an edge point to ...
0
votes
1answer
48 views

Closed formula for ${r \choose 1}+{r \choose 2}\cdots{r \choose w}$ where $w < r$ [on hold]

Let $r,w \in \mathbb{N}$. Are there some formula for the next sum? $${r \choose 1}+{r \choose 2}\cdots{r \choose w}$$ where $w<r$?
3
votes
3answers
60 views

Combinatorial identity's algebraic proof without induction. [duplicate]

How would you prove this combinatorial idenetity algebraically without induction? $$\sum_{k=0}^n { x+k \choose k} = { x+n+1\choose n }$$ Thanks.
0
votes
2answers
21 views

Formation of Teams in Permutation and Combination

A class has $n$ students , we have to form a team of the students including at least two and also excluding at least two students. The number of ways of forming the team is My Approach : To include ...
1
vote
1answer
29 views

Counting problem: How many triangles?

Sixteen points are on the sides of a $4\times 4$ grid so that the center portion of $2\times 2$ are removed. How many triangles are there in total that have vertices chosen from those remaining points ...
0
votes
2answers
22 views

Colors on sets $S=\{1,2 \cdots ,1000\}$.

To each element of sets $S=\{1,2 \cdots ,1000\}$ a color is assigned. Suppose that for any two elements $a$ and $b$, of $S$,if $15$ divides $a+b$, then they both are assigned with same color. What is ...
-1
votes
2answers
63 views

How many 3 digit numbers that the sum of their digits equals 12?

How many positive 3-digit numbers exist such that the sum if their digits equals 12? A) 54 B) 61 C) 64 D) 65 E) 66 I believe the answer is E. Online problems state that is a stars and bars ...
0
votes
2answers
38 views

How to prove that ${l \choose a_1,…,a_n}\le n^{l-1} $ , when $a_1+…+a_n=l$.

In the proof of (Corollary 8 chap. 3 ) in the book "Sobolev Spaces on Domains" by Burenkov the following inequality is used : given $a_1,...,a_n \in \mathbb{N}$ such that $a_1+...+a_n=l$, then $${l \...
0
votes
1answer
42 views

In how many ways can $5$ Indians, $4$ Chinese, and $3$ Americans be assigned to $12$ stations so that no two Americans serve at consecutive stations?

On a railway route from Delhi to Jaipur there are $12$ stations . A booking clerk is to be deputed for each of these stations out of $12$ candidates of whom $5$ are Indians , $4$ are Chinese and the ...
6
votes
6answers
106 views

Proving that ${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k} $

How can I prove that $${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k} $$ I tried the following: We use the falling factorial power: $$y^{\underline k}=\underbrace{y(y-1)(...
2
votes
3answers
70 views

Looking for a proof of a combinatorial relation

While working on a problem, I needed to calculate the following sum $$ n!\sum_{n_i\ge1}^{\sum_i n_i=n} \prod_i \frac{x_i^{n_i}}{n_i!} \tag{*} $$ where $i$ runs from 1 to $m$. After some playing ...
-1
votes
4answers
46 views

How many mixed double pairs can be made from 7 married couples provided that no husband and wife plays in a same set?

So for first man there can be 7 possible partners including his wife, for the next man there will be 6 possible partners and so on, therefore for $7$ men and $7$ women, there will be $7!$ possible ...
1
vote
3answers
2k views

Intuitively explaining the difference between a combination and permutation

I'm having a hard time trying to determine when to use combination and when to use permutation with a problem. Can someone offer a clear and concise explanation or general rules to follow so I don't ...
0
votes
1answer
36 views

How to reduce $f(k, n)$ to $\operatorname{fibonacci}(n)$?

Let's define $f(k, n)$ $f(0, n) = f(0, n - 1) + f(1, n - 1)$ $f(1, n) = f(0, n - 1)$ $f(k, 1) = 1$, for every $k$. $k$, $n$ $\subset \mathbb N$, for $0 \le k \le 1, n \ge 1$. I noted that $f(k, ...
0
votes
1answer
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, ...
10
votes
4answers
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.
10
votes
1answer
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 ...
3
votes
1answer
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, ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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-...
3
votes
2answers
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 ...
2
votes
1answer
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,...
6
votes
1answer
84 views

Number of integer triplets $(a,b,c)$ such that $a<b<c$ and $a+b+c=n$

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&...
4
votes
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 ...
7
votes
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 ...
4
votes
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,\...
-1
votes
1answer
29 views

Number of solutions of the two equations

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$
1
vote
1answer
17 views

Find a map on a power set 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,\...
1
vote
2answers
45 views

How many attending puppy school are brown and have long hair but are not small?

Of the 24 dogs attending puppy school -6 are small -12 are brown -15 have long hair -1 is small and brown and has long hair -2 are small and brown but their hair is not long -2 are small and have long ...
10
votes
8answers
538 views

Proving $\sum_{k=1}^n k k!=(n+1)!-1$

Prove: $\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$ (preferably combinatorially) It's pretty easy to think of a story for the RHS: arrange $n+1$ people in a row and remove the the option of everyone ...
0
votes
0answers
18 views

Homotopy type of some lattices with top and bottom removed

There was an interesting question on MO which OP removed by some reason. Here is a (more or less) equivalent form. Take a finite cartesian product of finite linear orders, and remove top and bottom. ...
4
votes
3answers
106 views

Books for maths olympiad

I want to prepare for the maths olympiad and I was wondering if you can recommend me some books about combinatorics, number theory and geometry at a beginner and intermediate level. I would appreciate ...
0
votes
1answer
30 views

counting number of steps using permutation-combination

We need to climb 10 stairs. At each support, we can walk one stair or you can jump two stairs. In what number alternative ways we'll climb ten stairs? How to solve this problem easily using less ...
1
vote
0answers
97 views

Counting zeros in a factorial(terminal + zeros in between digits)

The usual questions involving counting zeros in a factorial asks us to count only the terminal zeros. This question asks to count the zeros that are in between digits, for example, 8! (40320, has a ...
6
votes
2answers
114 views

Closed form for sequence A145271

I would like to know if there is a simple formula or method of expanding the expression given by $\left[g(x) \frac{d}{dx}\right]^n g(x)$ where $n$ is a positive integer, without having to resort to ...
1
vote
1answer
396 views

Maximum number of terms of a polynomial of degree n and p indeterminates

I am trying to figure out the maximum number of terms a polynomial have. This polynomial f has p indeterminates, the degree is maximum n and its quotients belong to an arbitrary field K. It would ...
2
votes
2answers
52 views

How many length-$k$ strictly decreasing sequences where sum is $N$?

How many strictly decreasing sequences of length $k$ in positive integers can I find where the sum of elements is $N$? The problem can be described this way too, I have a number $N$ . Now I want ...