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)

2
votes
2answers
25 views

The number of ordered pairs of positive integers $(a,b)$ such that LCM of a and b is $2^{3}5^{7}11^{13}$

I started by taking two numbers such as $2^{2}5^{7}11^{13}$ and $2^{3}5^{7}11^{13}$. The LCM of those two numbers is $2^{3}5^{7}11^{13}$. Similarly, If I take two numbers like ...
2
votes
1answer
75 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 ...
3
votes
1answer
66 views

Each number in a subset $S\subseteq \{1,\ldots,2n\}$ does not divide another one. Then $\max |S|$?

This problem comes from a seemingly innocuous question from a professor during a lesson for a Math Olympiad course. [A part of this question is really a classic of number theory/combinatorics] ...
2
votes
2answers
153 views

Improvised Question: Combination of selection of pens

This is a improvised version of the question here. Supposing there are four brands of pens, W, X, Y, Z. You want to choose $10$ pens made up of any combination of the brands, but limited to a ...
-3
votes
2answers
43 views

Odd prime combinatorics problem [closed]

How should I show that ${2p \choose p}\equiv 2\pmod p$ if p is an odd prime! help please
0
votes
1answer
37 views

probability that 5 square lie along a diagonal line - doubt [duplicate]

If 5 squares are chosen at random from a chess board, what is the probability that they lie on a diagonal line? this is the same question indeed. Answer is given by Mr.Brian M. Scott. But I got a ...
0
votes
0answers
20 views

How many degree m elements in the exterior algebra on n generators over a finite field, vanish when raised to the r-th power?

Let $R=\Lambda_{\mathbb{F}_p}[e_1,...,e_n]$ be the exterior algebra on $n$ generators over the finite field with $p$ elements (this arises naturally as the mod-p cohomology ring of the $n$-dimensional ...
1
vote
5answers
5k views

How do I determine the number of odd integers in a range?

Say I have a range of integers, [1..100]. How do I determine the number of odd integers in that range? Does it make a difference if the beginning and end numbers are [odd .. odd], [even .. odd], [even ...
-1
votes
2answers
44 views

Finding coefficients of $x^n$ and $x^{n+r}$ in an expansion

I have to find the coefficients of $x^n$ and $x^{n+r}$ $(1 < r < n)$ in the expansion of: $$(1 + x)^{2n} + x(1 + x)^{2n - 1} + x^2(1 + x)^{2n - 2} + ... + x^n(1 + x)^n$$ How do I solve it?
2
votes
1answer
38 views

Paths starting from a given node that touch each node a given number of times

How many paths starting from a given node touch each node a given number of times? We have a complete graph with vertices $1,2,3…j$. We want to know the number of paths of length $N$, starting from ...
1
vote
2answers
1k views

Combinatorics-permutations and combinations

In a soccer tournament of 15 teams, the top three teams are awarded gold, silver, and bronze cups, and the last three teams are dropped to a lower league. We regard two outcomes of the tournament as ...
3
votes
2answers
56 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)?$$
2
votes
1answer
24 views

Hamiltonian cycles in associahedron graphs

Let two distinct fully parenthesized products of $n$ symbols be called adjacent provided one of them may be obtained from the other by a single application of the associative law. Such graphs may be ...
7
votes
0answers
105 views

Counting the size of the largest sets of independent strings

This question derives from a PPCG coding challenge I posed previously. For a given positive integer $n$, consider all binary strings of length $2n-1$. For a given string $S$, let $L$ be an array of ...
1
vote
2answers
514 views

points with integer coordinates inside triangles in $\Bbb{R}^3$

I'm taking off from Number of lattice points inside a triangle and its area Consider a triangle in $\Bbb{R}^3$ whose vertices have integer coordinates. What's the fastest way of counting how many ...
2
votes
1answer
26 views

How many unique numbers can be obtained by adding two numbers from two different sequences?

Let the two integer sequences $\{a_m\}$ and $\{b_m\}$, be defined as: $a_n+D_n=a_{n+1}$ and $b_n=a_n-k$, where $D_n$ may be any natural number (and $D_i$ may or may not be equal to $D_j$), $k$ is an ...
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 ...
2
votes
1answer
48 views

Combinatorics - Counting the number of binary strings with specified length and sum, with substring constraints

Suppose I have a string of bits of length R. The sum of the bits must be equal to S, so there are S ones and R-S zeros. The longest string of ones cannot exceed X in length. Also the number of places ...
-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$.
13
votes
3answers
228 views

What is $\sum_{r=0}^n \frac{(-1)^r}{\binom{n}{r}}$?

Find a closed form expression for $$\sum_{r=0}^n \dfrac{(-1)^r}{\dbinom{n}{r}}$$ where $n$ is an even positive integer. I tried using binomial identities, but since the binomial ...
-5
votes
2answers
49 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.
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, ...
0
votes
0answers
37 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 ...
2
votes
2answers
164 views

A combinatorial identity

In trying to prove the Taylor expansion of the Spread Polynomials as given ( also in Wikipedia ) by S Goh in a new way I miss a final decisive step. How to prove a combinatorial simplification for ...
1
vote
0answers
45 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 ...
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 ...
0
votes
1answer
27 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 ...
0
votes
1answer
15 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 ...
-2
votes
2answers
76 views

In how many ways can 4 red, 3 blue and 2 green balls be arranged? [closed]

In how many unique ways can 4 red, 3 blue and 2 green balls be arranged if they are indistinguishable aside from color?
3
votes
2answers
89 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
290 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
1
vote
2answers
78 views

How many two letter words can be formed from 26 English letters?

There are 26 English letters(a-z). From layman approach, How can one calculate the possible two letter words from these 26 English letters?
3
votes
2answers
97 views

Sum of series ${n\choose 2a}{a\choose 0}+ {n\choose {2a+2}}{{a+1}\choose 1} + {n\choose {2a+4}}{{a+2}\choose 2} + \ldots$

I wanted to check the rationality of the cosine function for some rational multiples of $\pi$. And I found out that, $\cos(n \cdot\arccos x)$ generates a polynomial in $x$ whose co-efficients have the ...
1
vote
4answers
448 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
35 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
35 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
316 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 ...
18
votes
4answers
195 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 ...
-5
votes
1answer
62 views

Proof that ${2n \choose n}= \frac {1\cdot3\cdot5\cdots(2n-1)}{n!}2^n$ [closed]

HELP ME WITH THIS EXERCISES.. Proof for induction that $${2n \choose n}= \frac {1\cdot3\cdot5\cdots(2n-1)}{n!}2^n$$
0
votes
1answer
359 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 ...