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
0answers
6 views

Number of classes $\pmod p$ represented by $b_1s^{n-1} + \dots + b_n$ where $ord_p(s) = n$

Let $n \in \mathbb Z$ with $n \ge 3$ and let $p$ be a prime number such that $n|p-1$. Let $a_1,a_2,\dots,a_{2n-1} \in \mathbb Z/p\mathbb Z$. Suppose that the same class is represented by at most $n-1$ ...
0
votes
4answers
72 views

Prove that ${2^n-1\choose k}$ is always odd.

How can I prove that ${2^n-1\choose k}$ always returns odd numbers? It is possible to prove this by congruence? by the way : $0 <= k <= (2^n-1)$
1
vote
1answer
16 views

Distribute 20 million $ among 4 companies with some constraints

20 million is to be invested in 4 companies A, B, C, D. The minimum amount for investments are 1, 2, 3, 4 million respectively. How many different investment strategies are available if An ...
3
votes
1answer
24 views

In how many ways we can arrange 12 people in a row if 5 men are constrained to sit next to each other together?

In how many ways we can arrange $12$ people in a row if $5$ are men and they must sit next to each other? My approach I consider $5$ men as one entity and so now there are $8$ people to be seated ...
1
vote
3answers
23 views

Find the number of ways to arrange 8 students with restriction

8 students are arranged in a row. How many ways to arrange them if 3 particular students must be separated?
1
vote
1answer
29 views

Distributing identical balls into identical boxes [on hold]

How many ways to distribute 11 identical balls into 3 identical boxes with each box having 2 balls at least
0
votes
0answers
88 views

Any underlying reason why these equations look similar?

Questions Is there any way to go from either of these equations to the other? Or is there any more fundamental reason for their similarities? $$ \frac{1}{\zeta(s)} = \sum_{r=1}^\infty \frac{\mu(r)}{...
2
votes
5answers
700 views

How many possible “words” can be made from the first seven letters of the alphabet, allowing for repetition and enforcing alphabetical order?

Using letters from the alphabet $A = \{a, b, c, d, e, f, g\}$, how many words of length $5$ are possible when repetition is allowed but the letters must occur in alphabetical order? Not sure how to ...
1
vote
2answers
33 views

How many labeled trees exist with vertices $\{1,2,3,4,5\}$ that contain the edge $\{1,2\}$? [on hold]

How many labeled trees exist with vertices $\{1,2,3,4,5\}$ that contain the edge $\{1,2\}$?
6
votes
1answer
40 views

How to pick all the colors?

Prove of disprove: Suppose there are n boxes, each containing m balls of the same color,with n colors in total. No matter how we reallocate these balls (still each box contains m balls), we can pick ...
0
votes
0answers
13 views

Plane partitions of a poset with one specified value

Given a poset $P$ and an element $x \in P$. How many plane partitions of height $m$ (order preserving maps from $f:P \to [1,m]$), exist when $f(x)=j, 1 \leq j \leq m$? I'm interested in this as a way ...
0
votes
0answers
21 views

Generalize subset sum [on hold]

I want to prove this theorem: For a given integer $i$, there exists an $O(n^i)$ algorithm that decides the special case of the Subset Sum problem, where $|S|$ is bounded above by $i$.
1
vote
1answer
25 views

Counting the numbers of linear combination

Let $ A $ be a set that contains numbers of the form $ 2^{i} $ where $ i \in \{0, 1, 2, 3, 4, 5, 6\}. $ How many distinct linear combinations $ \displaystyle \sum_{0 \le j \le 6} c_{j}2^{j} $ can we ...
2
votes
1answer
44 views

Proof of ways to put distinct Balls into distinct Boxes

So I have learned that the formula for putting m balls into n boxes such that no box is empty is the following: $$T(m,n)=\sum_{k=0}^n (-1)^k{n \choose k}(n-k)^m$$ I am really confused as how to prove ...
0
votes
1answer
19 views

How do I find the terms of an expansion using combinatorial reasoning?

From my textbook: The expansion of $(x + y)^3$ can be found using combinatorial reasoning instead of multiplying the three terms out. When $(x + y)^3 = (x + y)(x + y)(x + y)$ is expanded, all ...
3
votes
3answers
264 views

Explanation: In how many ways can 6 things be divided between 2 people?

I have a question in a book which says in how many ways can 6 different things be divided between 2 boys and (my understanding of) the explanation goes something along the lines of: Items: 1 1 1 1 1 ...
1
vote
1answer
20 views

Spanning trees of the complete graph minus two edges

Here is the following problem: What two edges should one remove from the complete graph $K_n$ so that the number of the spanning trees of the new graph is as small as possible? One can solve this ...
0
votes
1answer
24 views

Counting the number of Eulerian trails in a connected, directed graph

I can't find anything about this online, and I'm beginning to suspect it's a hard problem. I know that counting the number of circuits is #P-complete, but I don't need the number of circuits; I need ...
1
vote
1answer
41 views

Distances of points around unit circle

$P_1,\cdots , P_{10}$ are ten points on the unit circle What is the largest possible value of the quantity $$\sum_{1\le i<j\le 10} |P_i-P_j|^2$$
0
votes
2answers
32 views

Is there a way to iterate through a set?

I have a set $X=\{x_1,x_2,...x_n\}$ and I want to define a function: $$f(X)=\prod_{j=1}^n{\sum_{i=j}^nx_i \choose x_j}$$ However, in this function I'm treating this set as a sequence, as sets don't ...
2
votes
3answers
28 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
3answers
33 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
29 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
2answers
50 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 ...
3
votes
2answers
49 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
38 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.
0
votes
0answers
18 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 ...
1
vote
1answer
28 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
1answer
69 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 ...
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
vote
1answer
33 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 ...
-1
votes
2answers
65 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 ...
3
votes
3answers
70 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.
1
vote
2answers
59 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 ...
0
votes
1answer
24 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, ...
0
votes
2answers
23 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 ...
6
votes
6answers
111 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)(...
0
votes
1answer
37 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, ...
3
votes
2answers
42 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 ...
1
vote
1answer
62 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-...
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,...
4
votes
1answer
25 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,\...
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
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,\...
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 ...
7
votes
2answers
101 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&...
0
votes
0answers
19 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
108 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
33 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 ...