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
24 views

counting sets with condition

I have $O$ objects (private case: 7). I need to count how many set combinations satisfy the conditions: there are at least two objects in a set each object is in at least one set no set is a subset ...
6
votes
1answer
79 views

Prime Factorization Question involving Product of Consecutive Terms

I came across this question while doing some research at an REU this summer. It was supposed to be just a small part of a larger proof, but we've been stumped on it for a while. I don't have much of a ...
2
votes
1answer
59 views

What are the most common sets to which one should try to set a bijection?

Let's say I'm faced with the problem of counting the number of elements in a set A. This set is extremely difficult to count, but maybe I could set a bijection with another known and well studied set (...
6
votes
1answer
100 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 ...
6
votes
6answers
114 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)(...
1
vote
2answers
42 views

Efficiently mapping a finite powerset into the first n natural numbers?

Say I have a finite set $S$, where $|S| = n$. How would I efficiently map $\mathcal{P}(S)$ to $0, 1, \ldots 2^n$? For example, let $S = \{0, 1, 2\}$ and $\mathcal{P}(S) = \{\emptyset, \{0\}, \{1\}, \{...
8
votes
5answers
354 views

Proving $\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$

Prove that $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$ I ...
1
vote
2answers
43 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\}$?
2
votes
0answers
25 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$ ...
1
vote
2answers
54 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 ...
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
25 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 ...
2
votes
2answers
452 views

Let $A$ be the set of all $4$ digit numbers $a_1a_2a_3a_4$ such that $a_1 < a_2 < a_3 < a_4$, then what is $n(A)$ equal to?

How can you solve this problem relatively quickly using combinatorics? I found it really interesting. Let $A$ be the set of all $4$ digit numbers $a_1a_2a_3a_4$ such that $a_1 < a_2 < a_3 < ...
3
votes
1answer
39 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 ...
2
votes
5answers
746 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
3answers
32 views

Find the number of ways to arrange 8 students with restriction [on hold]

8 students are arranged in a row. How many ways to arrange them if 3 particular students must be separated?
1
vote
1answer
21 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
31 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
102 views

Any underlying reason why these equations look similar? [on hold]

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)}{...
6
votes
1answer
46 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
24 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 ...
2
votes
1answer
45 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
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
29 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 ...
3
votes
3answers
277 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 ...
0
votes
1answer
20 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 ...
0
votes
2answers
389 views

There are 10 sticks of length 1,..,10. How many triangles can be formed

There are 10 distinct sticks of length 1,..,10. How many triangles can be formed? I do not know whether there are some counting tricks for this one.
1
vote
1answer
44 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$$
2
votes
3answers
32 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 ...
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 ...
-1
votes
1answer
53 views

A binomial sum identity

Let \begin{align*} f(n, r, \pi, k) &= \sum_{z=0}^{n}\sum_{s=0}^{r}\binom{z}{s}\binom{n}{z}\binom{n-z}{r-s}(-1)^{r+s}\left(\frac{\pi}{1-\pi}\right)^{r/2-s}\pi^{z}(1-\pi)^{n-z}z^k \end{align*} I am ...
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 ...
3
votes
1answer
74 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
34 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
32 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 ...
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.
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
70 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 ...
1
vote
1answer
30 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
19 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
50 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
83 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
24 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
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 ...
0
votes
2answers
24 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
68 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 ...
2
votes
3answers
73 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 ...