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
0answers
15 views

Number of ways of contraction of N (N is even) three-index tensors?

Suppose I have N (N is even) three-index anti-symmetric tensors, I need to calculate the number of ways of total contractions. There are several constraints: The indexs of the same tensors cannot be ...
1
vote
1answer
1k views

what is maximum number of points of intersection between the diagonals of a convex octgon?

What is the maximum number of points of intersection between the diagonals of a convex octagon (8-vertex planar polygon)? Note that a polygon is said to be convex if the line segment joining any two ...
0
votes
1answer
38 views

How to solve this using set theory? [closed]

Of the 38 people in my office, 10 like to drink chocolate, 15 are cricket fans, and 20 neither like chocolate nor like cricket. How many people like both cricket and chocolate?
1
vote
3answers
62 views

Combinatorial Proof of a Simple Identity

Consider the following identity: $\binom n r = \frac n r \binom {n-1} {r-1}$ where $n \ge r \ge 1$. It's easy to supply an algebraic proof, but I'm looking for a combinatorial proof. I tried the ...
5
votes
4answers
180 views

Make $n$ cents with $1$-cent, $2$-cent, and $3$-cent coins

I encountered the following problem in Herber Wilf's book Generatingfunctionology: Prove that, in country that has $1$-cent, $2$-cent, and $3$-cent coins only, the number of ways of changing ...
-5
votes
0answers
39 views

Non repeatable combinations [closed]

There are 10 girls and 15 boys in class. They're preparing zumba dance for the final show. The teacher decided that boys are doing better and only boys will play 3 zumba dances. Every each of them ...
0
votes
0answers
44 views

Product of +1 and -1 with all combinations

I am looking for an algorithm or a smart way to do this in excel. I have this table. ...
-1
votes
1answer
85 views

partitions of the number n

I'm having difficult with the following question : show that the number of partitions of n into parts of size 3,5,7,9,... equals to the number of partitions of n into different parts which are not ...
-4
votes
0answers
21 views

groups of colors in a colorful cube - combinatorics [closed]

find natural number n, such that in every paint of a cube $$ 2^{[n]} $$ with the seven colors of the rainbow : a) there is 3 different groups $$ A, B , A \cap B $$ with the same color b) there is 3 ...
1
vote
2answers
30 views

Further Improvised Question: Combination of selection of pens

Following from my first improvised question here and the two excellent answers given, here's another twist to the question. What happens if the total number of pens to be selected is $15$ instead of ...
0
votes
0answers
18 views

Upper limit on Ramsey number $R(a,b)$

How could we prove that if $R(a-1,b)$ and $R(a,b-1)$ are both even then $R(a,b)$ is strictly less than $R(a-1,b)+R(a,b-1)$ or $\begin{equation} R(a,b) < R(a-1,b)+R(a,b-1) \end{equation}$
1
vote
2answers
25 views

Combinations question related to cards game

In how many ways can a player get 4-4-3-2 (4 cards from 1 suite, 4 cards from one suite, 3 cards from one suite and 2 cards from the last suite)? I calculated this way, but my answer is supposed to ...
0
votes
1answer
37 views
5
votes
2answers
387 views

Alternative combinatorial proof for a combinatorial identity

I have a question with regards to combinatorics. I am supposed to show the following combinatorial identity: $\sum_{r=0}^n\binom{n}{r}\binom{m+r}{n}=\sum_{r=0}^n\binom{n}{r}\binom{m}{r}2^r$. The ...
8
votes
4answers
275 views

Prove that $\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$ [duplicate]

Prove that $$\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$$ What should I do for this equation? Should I focus on proving ...
4
votes
2answers
127 views

A summation involving multinomial coefficient

We need to find out $$\sum {\binom{N}{a_1,a_2,a_3...a_B} a_1^{\alpha}a_2^{\alpha}...a_C^{\alpha} }$$ $$a_1+a_2...a_B=N, \alpha>0 ,0\lt C \le B$$ All are nonnegative integers. We need to sum ...
2
votes
4answers
138 views

Summing n times binomial(n,k)

I'm trying to do $\sum_{n=a}^b \left( \begin{array}{rl} n \\ a \end{array} \right) n $ . Is there a formula, that anybody knows?
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, ...
1
vote
0answers
44 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 ...
2
votes
1answer
38 views

probability that 5 square lie along a diagonal line (modified)

This is a modified version of the question here and asked based on the clarifications obtained here. If 5 squares are chosen at random from a chess board, what is the probability that they lie on a ...
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 ...
1
vote
3answers
61 views

How can I find the generating function of this sequence?

I am preparing for a test and I came across this example: Find the closed form generating function of: $$\dbinom{50}{1}, 2\dbinom{50}{2}, 3\dbinom{50}{3},..., 50\dbinom{50}{50},0,0,0,0$$ I know ...
1
vote
2answers
363 views

Number of Ways to Draw a Pair in a Poker Deck

I am confused over calculating the number of ways in which I can select a pair out of a deck of 52 cards. This is how I go about solving the problem: Following the definition of a pair in card ...
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
23 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
39 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
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)?$$
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
516 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
38 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
46 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 ...