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

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 ...
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 ...
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 (...
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 ...
114 views

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 ...
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 ...
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 ...
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$.
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 ...
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 ...
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 ...
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.
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$$
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 ...
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 ...
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 ...
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 ...
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 ...
34 views

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