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

43 views

### calculation of all possible combinations.

Suppose we are given $x_1 - x_2 = 31$. Constraints - $0 \leq x_1 \leq 45$ and $0 \leq x_2 \leq 45$. Then we have to tell number of all possible distributions for $x_1$ and $x_2$.
50 views

### Let $g_{n}$ be the no. of derangements with $n$ elements and $f_{n}$ the no. of permutations with one fixed point. Show that $|g_{n}-f_{n}|=1$

This is a problem from Loren Larson's "Problem solving through problems", 2.5.13, page 78. Let $S_{n}=${$1,2,...,n$}. A derangement of $S_{n}$ is a permutation with no fixed points. Let $g_{n}$ be ...
52 views

### Discrete mathematics: Question regarding “Pigeonhole principle”. [closed]

Each point in the plane is coloured either red or blue. Show that there are two points of the same colour which are exactly 1 cm apart.
46 views

### Is $P(n) = \frac{a n }{b}$ or $\frac{(a+1) n}{b + 1}$?

I investigated Some random data and I was a bit confused. Could be Mathematical coincidence but i'm not sure. Consider the integers $1,2,3,...,a$ Randomly Pick $b$ dinstinct element out of them. ...
83 views

48 views

### Rotating groups of people

I have a total of 30 people and I want to create rotating groups of 5 individuals. I have to come up with a system that allows each person to meet each other only once (maximum). As I already ...
16 views

### Lattice points in simplices - reference request

I found this paper http://homepages.math.uic.edu/~yau/35%20publications/An%20upper.pdf which, in formulas (1.2) and (1.3), relates the number of non-negative and positive integer values that are ...
37 views

### Caro-Wei Theorem Proof

I was reading a proof of the Caro-Wei Theorem using the probabilistic method when I came acroos something that I did not understand. I learned characteristic functions such that $1_{s\in A}$ equals 1 ...
34 views

### How many finite sequences with exactly k different elements?

How many different sequences/strings of length $\ell$ contain exactly $k$ (out of $n$) different elements? Or, to put it differently, how many functions from $\{1,\dots,\ell\}$ to $\{1,\ldots,n\}$ ...
27 views

### Seating people around a circular table (elementary counting technique)

Eight people, including Abigail, Bethany, and Charlene, are to be seated at a circular table. Two seatings are considered distinct if, and only if, the ordering of people starting with Abigail and ...
39 views

### Salem Spencer Theorem

The Salem Spencer Theorem seems to be a very interesting combinatorial theorem. This blog motivated me to read more about it. I understand the statement of the theorem, however the proof isn't very ...
42 views

13 views

### Number of ways to sample a specific number of objects from a collection with several types of objects.

I'm trying to figure out the following combinatoric problem: Simple case: Suppose I have $N$ objects of two types with sizes $i_{1},i_{2}$ . I sample $n\leq N$ objects without returning, how many ...
45 views

### Finite partitions of $\mathbb{N}$ and relations betweens sets of natural numbers

Suppose that $R\subseteq \mathcal{P}(\mathbb{N})\times\mathcal{P}(\mathbb{N})$ is a relation such that $(x,y)\in R$ only if $|x|=|y|$. Say that a partition $P$ divides a set $x$ if $x$ is the union ...
46 views

### Combinatorics & Cupcakes

There are $10$ cupcakes left over after a birthday party: $3$ vanilla, $2$ red velvet, and $5$ chocolate. Each of the $8$ guests can take home as many of the cupcakes as they want. How many ways can ...
21 views

### Number of Crossing Cycles of length $3$ in a complete graph if we put $m$ edges on one side?

Alice and Bob don't play games anymore. Now they study properties of all sorts of graphs together. Alice invented the following task: she takes a complete undirected graph with $n$ vertices, ...
39 views

### A strange scheduling for $K_{24}$.

This question came from a question asked earlier today linked here The question implicitly asked how to make a schedule with his/her class of 24 students such that: 1) Everyday will consist of the ...
17 views

### Affine Weyl group as coxeter group

How do you write the affine Weyl group corresponding to type $A_n$ as a Coxeter group ?The generators are $s_0,s_1,s_2,\cdots ,s_n$ where $s_0$ corresponds to the highest root. What are all the ...
29 views

### What is the terminology of the collection of all possible combinations of the element of a set?

Let me explain my question better: Suppose I have a set $(1,2,3)$. Clearly, I have 6 ways to choose some elements from it: $$(1),(2),(3),(1,2),(1,3),(2,3)$$ and I can make a collection to ...
54 views

### Grouping kids in Groups of $4$

How many different groups of $4$ can I create using $24$ students? I want to break my class of $24$ students into groups of $4$. I would like to create different groups each day until each student ...
19 views

29 views

### Lower bound on circuit size of a Boolean function

I'm currently reading a proof of the following claim from the notes http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf which can be found on the bottom of page 6. I'd like to point out i'm interested ...
### Proof: A matrix with $m$ rows and $n$ colums has $nm$ entries.
How to prove rigorously the following statement: A matrix (a collection of numbers $a_{ij}:1\leq i \leq m, 1\leq j \leq n)$ with $m$ rows and $n$ colums has $nm$ entries. By rigorously I mean ...
Given $n$ balls placed in $m$ boxes, prove that if $n < \frac{m(m-1)}{2}$ then at least two boxes have same number of balls in them.