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)

-1
votes
2answers
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$.
4
votes
3answers
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 ...
-5
votes
2answers
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.
2
votes
2answers
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. ...
1
vote
1answer
83 views

Hitting a line in a $d$ dimensional cube

Let $F$ be a finite field of order $n$, and let $d$ be an integer. A line in $F^d$ is a function $\ell: F \to F^d$ given by $\ell(t) = x + t*h$, where $x,h \in F^d$, $h \neq 0$, and $t*h = (tx_1, ...
2
votes
1answer
77 views

Does an Eulerian semi-graceful polyhedral graph exist?

In a graceful graph, the vertices have number values that range from 0 to $n$ and $n$ edges with all values from 1 to $n$ that are differences between the vertex values. Here's a graceful but boring ...
1
vote
1answer
29 views

Find the maximum value of the quotient

Given a real number $x,$ let $\lfloor x \rfloor$ denote the greatest integer less than or equal to $x.$ For a certain integer $k,$ there are exactly $70$ positive integers $n_{1}, n_{2}, \ldots, ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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\}$ ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
3
votes
0answers
42 views

Summing the binomial pmf over $n$, part 2

After the great answers I got to this question, I tried summing a similar-looking series using the same strategies ($k \geq 0, \alpha > 1, p \in (0,1)$): $$ \sum_{n=k}^{\infty} {n \choose k} p^k ...
1
vote
0answers
16 views

Notation or theory on functions which reorder sequences

I wanted to come up with a simple way of reordering the elements in some sequence $a=\left[ a_{0}, a_{1} \cdots a_{n} \right]$ in a specific way. My solution was to have a sequence of integers ...
1
vote
0answers
8 views

Reference for a Dickson Determinant Polynomial

For $2\leq \ell \leq k$, consider the polynomial \begin{equation} P_{k,\ell} = \prod_{1\leq a_1+\ldots+a_k\leq \ell} (a_1x_1+\ldots + a_kx_k)\in \mathbb{F}_2[x_1,\ldots, x_k] \end{equation} ...
3
votes
2answers
57 views

Does there exist integer such that there exist sum of powers congruent mod $p$?

Let $n \in \mathbb{N}$, $p$ prime. For arbitrary $C \in \mathbb{Z}$, does there exist $a_1, a_2, \dots, a_n \in \mathbb{Z}$ such that$$C \equiv \sum_{i=1}^n a_i^n \text{ }(\text{mod }p)?$$
5
votes
0answers
78 views

Showing that only $(n+1)^{n-1}$ of all the possible $n^n$ choices assure a full car park

This exercise is taken from the site of Queen Mary University of London: A car park has $n$ spaces, numbered from $1$ to $n$, arranged in a row. $n$ drivers each independently choose a favourite ...
3
votes
2answers
91 views

How many legal states of chess exists?

I have a fairly simple question. How many legal states of chess exists? "Legal" as in allowed by the rules and "state" as an unique configuration of the pieces. I'm not asking for the number of ...
0
votes
1answer
37 views

Explanation for recurrence relation of a counting problem

This is a problem from a programming contest. A permutaion of numbers from $1$ to $n$ is valid if the first element is $1$ and the absolute difference of all neighboring elements is $\leq2$ Count the ...
19
votes
4answers
204 views

How to Prove : $\frac{2}{(n+2)!}\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^{n+2}=\frac{n(3n+1)}{12}$

While I calculate an integral $$ \int\limits_{[0,1]^n}\cdots\int(x_1+\cdots+x_n)^2\mathrm dx_1\cdots\mathrm dx_n $$ I used two different methods and got two answers. I am sure it's equivalent, but ...
4
votes
2answers
81 views

Find the number of natural number solutions of $a+2b+c=100$

Find the number of natural number solutions of $a+2b+c=100$ I remember something like stars and bars if the equation I change to $a+b_{1}+b_{2}+c=100$ then i get $\dbinom{99}{3}$ ways. If the ...
2
votes
3answers
71 views

Summing the binomial pmf over $n$

I was trying to work out some bounds for a research problem when I came across the innocuous-looking sum: $$ \sum_{n=k}^{\infty} {n \choose k} p^k (1-p)^{n-k}, \quad k \in \mathbb{N}, \; p \in (0,1)$$ ...
0
votes
1answer
28 views

Integer Points in Simplex

Let $$A_w(d,q):=\left\{{\bf k} \in \mathbb{N}_0^d: \sum_{j=1}^d w_j k_j \leq q\right\}$$ denote the number of non-negative integer points in the $\ell_1$-ellipse with semi-axes of length ...
3
votes
0answers
66 views

Trajectories on a circular billiards table

This question is related to The case of Captain America's shield: a variation of Alhazen's Billard problem, but more focused. Let the unit disc in the plane be our billiards table, and let $C$ ...
1
vote
1answer
20 views

Avoiding range of a bivariate integer function or diophantine function

I'm trying to find a function or sequence (of integers) which avoids all the range values of the following integer function where $x,y \in \{0,1,2,...\}$ and $f(x,y)=5+23*x+7*y+30*x*y$. Does anyone ...
2
votes
1answer
69 views

Probabilities in circular arrangements

For computing probability for a circular arrangement, it should not matter whether we take people in a group as distinct and chairs as numbered, or not, and we should be able to choose as per our ...
1
vote
2answers
53 views

Manual generation of all permutations of N non-repeating elements

I am looking to find if there is a way to manually (meaning, not using a machine that has high memory capacity) generate all the permutations of a set of N non-repeating (unique) elements by the way ...
0
votes
1answer
26 views

Optimal partitioning of a planar graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...
2
votes
3answers
110 views

Are these lines going to meet in exactly 2002 points?

There is a plane P.100 lines are on P.Is it possible to arrange them in a way such that they intersect in exactly 2002 points given that no three of them are concurrent? Any help is highly ...
0
votes
1answer
24 views

Making all row sums and column sums non-negative by a sequence of moves

Real numbers are written on an $m\times n$ board. At each step, you are allowed to change the sign of every number of a row or of a column. Prove that by a sequence of such steps, you can always ...
1
vote
0answers
18 views

Understanding ILP formulations of combinatorial optimisation problems

I am having trouble understanding and producing integer linear programming formulations for combinatorial optimisation problems. I can understand basic ones like the knapsack problem: $min \quad ...
6
votes
3answers
93 views

Proving $\binom{n}{m}+2\binom{n-1}{m}+…+(n-m+1)\binom{m}{m} = \binom{n+2}{m+2}$

For $m,n\in\mathbb{N},\;n\geq m$, prove the following: $$ \tag{i}\binom{n}{m}+\binom{n-1}{m}+\binom{n-2}{m}+......+\binom{m}{m} = \binom{n+1}{m+1} $$ $$ ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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, ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
3
votes
3answers
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 ...
0
votes
0answers
19 views

Proving a combinatorics identity (permutations and combinations) [duplicate]

Prove the following identity by interpreting their meaning combinatorially. $$\left( \begin{array}{c} n \\ r \\ \end{array} \right)=\left( \begin{array}{c} n-1 \\ r-1 \\ ...
-1
votes
0answers
39 views

Number of possibilities of a dataset

I have objects defined by $20$ dimensions rated from $1$ to $10$ with no decimal. How many distinct objects can I have ? Ok it's $10^{20}$. But how many distinct objects Can I have considering that ...
1
vote
2answers
57 views

Combination of $n$ objects taken $p$ at a time where $n$ contains $r$, $s$, and $t$ identical objects.

I am talking about something like this: $ N = \{2, 3, 3, 3, 5, 5, 7\}$ $ n = 7$ $ s=3 $ $t=2$ In my case specifically, those numbers in $N$ are the prime factors of a number $Z$ repeated the number ...
0
votes
1answer
51 views

Question regarding Application of Combinations and Permutations (HW Problem)

I have a midterm I am studying for and I don't have the solutions to this homework problem. Can anyone please explain how to do it? I would really appreciate it. Here is the problem: I googled the ...
3
votes
2answers
53 views

Sum over two binomials identity

So while trying to count the number of configurations in a statistical mechanics research problem I come across this lovely sum: $$\sum_{i=0}^k \binom{i+r}{r} \binom{k-i+r}{r}$$ I scoured the ...
1
vote
3answers
126 views

Why do we subtract [Combinatorics]

I asked Here This question and I am still confused. I got that, for at least one group together there are: $$3 \cdot 9 \cdot \binom{6}{3, 3}$$ But why do we subtract: $3 \cdot 9 \cdot 4$. Lets ...
0
votes
1answer
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 ...
-2
votes
1answer
51 views

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 ...
3
votes
4answers
104 views

Application of Pigeon-Hole Principle to balls in bins.

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.