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
vote
4answers
450 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
1
vote
1answer
36 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 ...
13
votes
6answers
494 views

Combinatorial interpretation of an alternating binomial sum

Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove ...
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\}$ ...
3
votes
2answers
67 views

Finite projective planes

How big a set of points in general position (i.e., no three collinear) can be found in a finite projective plane of order $n$? I hope the answers won't be too technical, as I know almost nothing ...
0
votes
1answer
26 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 ...
1
vote
2answers
36 views

Combinatorics problem on the size of A+B

Let $A$, $B$ be finite subsets of $\mathbb{Z}$ with $|A|=n$, $|B|=m$. Denote $A+B=\{a+b:a \in A, b \in B\}$. It's fairly easy to show that $|A+B| \geq n+m-1$. My question is: If $|A+B|=n+m-1$, ...
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 ...
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} ...
22
votes
2answers
318 views

How many planar arrangements of $n$ circles?

Is there a known formula or recursion for the number of distinct arrangements of $n$ distinct circles in a plane, where two arrangements are regarded as distinct unless one can be obtained from the ...
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 ...
19
votes
4answers
202 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 ...
7
votes
5answers
1k views

discrete math book suitable for younger person?

When I took discrete math as an adult I realized that this was a subject I would have enjoyed and done well at much earlier in life, even in my early teens. Does anyone know if there are good books, ...
7
votes
1answer
62 views

What is maximum a number of to form right-triangles from in n straight lines

I am interested what is maximum a number of to form right-triangles from in $n=100$ straight lines such $n=3$,then maximum number of is $1$,see fig:$\Delta ABC$ is right-triangles. $n=4$ then ...
0
votes
1answer
360 views

Probability of picking exactly one correct from a pool of 6 incorrect and 4 correct

So as the question says. You have 6 incorrect objects and 4 correct ones. What are the odds that, when picking 3 of them at random, you end up with exactly one of them being correct. This seems to be ...
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 ...
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 ...
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$ ...
3
votes
4answers
53 views

Counting integral solutions

Suppose $a + b + c = 15$ Using stars and bars method, number of non-negative integral solutions for the above equation can be found out as $15+3-1\choose15$ $ =$ $17\choose15$ How to extend this ...
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)$$ ...
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 ...
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 ...
3
votes
1answer
85 views

Is it possible to solve sudoku without backtracking?

I occasionally solve sudoku puzzles on smartphone in spare time. My approach is based on the belief that at each stage in solving a sudoku puzzle there is at least one cell where there in only one ...
7
votes
1answer
127 views

Partial sums of falling factorials

I want to know if there exists some way, approximate or exact, to do a partial sum of falling factorials of the kind: $$\sum_{k=i}^{n}(a+k)_{h}$$ where all are constants. And I'm interested too in ...
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 ...
1
vote
2answers
7k views

How many different passwords of length 6 can be formed…

Each user on a computer system has a password, which is six characters long, where each character is an uppercase letter or digit. Each password must contain at least one digit. How many possible ...
0
votes
1answer
69 views

Probability of hitting a number $Ib$ (rare case)

Consider a set $S$ of $N^{3/2}$ numbers. Fix a collection $T$ of $N^{\frac{1}{2}}$ numbers. With every trial, we have the freedom to choose $N^{1-\epsilon}$ of them at a time without overlapping. My ...
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 ...
8
votes
2answers
222 views

Counting number of distinct systems

This is an enumeration problem in conjunction with some lottery problems. Given an integer $N \ge 5$. Let a ticket be a set of 5 distinct integers between $1$ and $N$. Given an integer $T$ between ...
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 ...
7
votes
3answers
2k views

How many turns can a chess game take at maximum?

The shortest number of moves that a game of chess can have is 2, as far as I know: White moves pawn from f2 to f3, black moves ...
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
1answer
22 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 ...
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
1answer
40 views

On counting and generating all $k$-permutations of a multiset

Let $A$ be a finite set, and $\mu:A \to \mathbb{N}_{>0}$. Let $M$ be the multiset having $A$ as its "underlying set of elements" and $\mu$ as its "multiplicity function". (Hence $M$ is finite.) ...
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 ...
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
2answers
557 views

How do 3 points define a plane?

I was solving a combinatorics problem which asked me to find the number of planes that can be constructed from a set of 25 points such that no 4 points in the set of 25 points are co-planar and then I ...
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 ...
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, ...
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 ...
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 ...
7
votes
4answers
436 views

Trying to show $1-\frac12 -\frac {1} {4}+\frac {1} {3}-\frac {1} {6}-\frac {1} {8}+\frac {1} {5}-\cdots =\frac {1} {2}\log 2$

Now I think the lhs can be rewritten as $$\sum _{n=1}^\infty \left( \dfrac {1} {2n-1}-\dfrac {1} {2\cdot 3^{n-1}}-\dfrac {1} {2^{n+1}}\right) =\dfrac {1} {2}\log 2$$ I guess one way to do this may be ...
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 ...
4
votes
2answers
1k views

Probability of Posting a Quad and Trip on 4chan

Important Pre-Requisite Knowledge On the image board 4chan, every time you post your post gets a 9 digit post ID. An example of this post ID would be $586794945$. A Quad is a post ID which ends with ...
-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 ...
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 \\ ...
3
votes
2answers
62 views

Number of unique binary strings containing at least m sequential 1s

Let $Z\left(n,m\right)$ be the number of unique binary strings of length $m$ containing at least one instance of $n$ consecutive 1's. I am trying to come up with an expression for $Z$, preferably ...