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
2answers
41 views

Probability that among 3 random digits two different one

I have been trying to solve the following problem: What is the probability that among 3 random digits, there appear exactly 2 different ones? The formula for no repititions is: ...
14
votes
13answers
3k views

Show that from a group of seven people whose (integer) ages add up to 332 one can select three people with the total age at least 142. [on hold]

I need help with this problem, and I was thinking in this way: $$ x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} = 332 $$ and I need to find three of these which sum is at least 142. But I ...
0
votes
0answers
22 views

How to enumerate (not count) combinations and permutations? [duplicate]

I’d like to ask if there is any formula or method to enumerate combinations and permutations such that if I know that there are X unique combinations/permutations, I could take a number between 1 and ...
10
votes
0answers
71 views
+100

Congruent quadrilaterals in a tri-colored $72$-gon

I recently watched a movie (A Brilliant Young Mind) in which this problem appeared: Let the vertices of a regular $72$-gon be colored red, blue, and green in equal parts. Show that there are $4$ ...
0
votes
0answers
40 views

What is the maximum value of $M$ when $T$ is set of $\{2,4,8,16,… 2^n\}$ and $S$ is subset of $T$ by given conditions

Qns $T$ is set of $\{2,4,8,16,... 2^n\}$ and $S$ is a subset of $T$ if the sum of no two elements of $S$ is greater than $2^n-2$. let $m$ be $M$ number of elements in $S$. what is ...
1
vote
1answer
30 views

Chessboard pawns arrangement clarification

I have a 8 X 8 chessboard, and 8 identical pawns. These pawns are arranged at random. What is the probability that the pawns are arranged in such a way that each row and column have only one pawn? My ...
2
votes
2answers
51 views

Two problems on combinatorics

Suppose we have a bag which has chips of four colors numbered $1$ to $13$, i.e. in total $52$ balls. Now what is the difference between these two problems. Problem-$1$- In how many ways can you ...
-3
votes
1answer
67 views

Pigeonhole Principle proving [on hold]

Suppose that there are 30 people in the room. Assume that everyone in the room has at least one acquaintance. Show that there are two persons in the room who have equal numbers of acquaintances. Since ...
0
votes
0answers
34 views

Comparison of entries of a real matrix

Let $A$ be an $m$ by $n$ real matrix and let $p$, $q$ be positive integers with $p\leq n$, $q\leq m$. In $A$, mark $p$ smallest entries of each row with red color and mark $q$ smallest entries of each ...
0
votes
2answers
77 views

How many pairs $(m, n)$ exist?

For certain pairs $ (m,n)$ of positive integers with $ m\ge n$ there are exactly $ 50$ distinct positive integers $ k$ such that $ |\log m - \log k| < \log n$. Find the sum of all possible ...
0
votes
0answers
41 views

partitions and generating functions ( combinatorics ) [closed]

Given partition into distinct parts, let’s say the the ODD parts are: the biggest part, the $3$-rd biggest part, the $5$-th biggest part, etc.; and the EVEN parts are: the $2$-ne biggest part, the ...
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
0answers
26 views

Is there a good way to break down the order of the centraliser in a symmetric group?

I recently rediscovered the rather nice formula for the order of the centraliser of a permutation in the symmetric group and its realtionship with conjugacy classes. I wondered whether we could say ...
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
43 views

In how many ways can a student select six classes from three groups if they must take at least two from the first and second groups?

Question: Students at school can choose from 16 subjects to study for their Certificate. Seven of these subjects are in group I, six are in group II, and the other three are in group III. Students ...
-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
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 ...
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 ...
-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
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
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}$
5
votes
2answers
66 views

Average length of a cycle in a n-permutation

What is the average length of a cycle in a permutation of $\{1,2,3,\dots ,n\}$?
0
votes
1answer
37 views

How many different six digit numbers can be formed by various arrangements of the six digits: 2, 2, 2, 2, 4, 7 [closed]

The fact that there are four 2's is throwing my off. Any pointers? Thank you for your time.
4
votes
1answer
60 views

Each number in $S\subseteq \{1,\ldots,2n\}$ does not divide another one, with $|S|= n$. In how many ways?

Let $f(n)$ be the number of subsets $S\subseteq \{1,2,\ldots,2n\}$ such that $|S|=n$ and $a$ does not divide $b$ whenever $a,b \in S$ are distinct. Can we evaluate $f(n)$, at least asimptotically? ...
-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 ...
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
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
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] ...
-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
2
votes
3answers
108 views

Probability that the eventually a six on a dice will appear.

Dave rolls a fair six-sided die until a six appears for the first time. Independently, Linda rolls a fair six-sided die until a six appears for the first time. Let $ m$ and $ n$ be relatively prime ...
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 ...
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 ...
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 ...
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
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
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 ...
5
votes
4answers
142 views

Combinatorial Proof for Binomial Identity: $\sum_{k = 0}^n \binom{k}{p} = \binom{n+1}{p+1}$ [duplicate]

I am studying combinatorics and I came across the identity $$\sum\limits_{k=0}^n \binom kp =\binom {n+1}{p+1}.$$ I have read the algebraic proof and it does not appeal to me. Is there an elegant ...
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 ...
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$.
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
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.
2
votes
2answers
44 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
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 ...
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
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 ...
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
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 ...