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)

4
votes
3answers
66 views

Chart of Rounds for a Game

I need to solve the following problem for actual use. 10 people will be playing a game. They play the game 4 people at a time. Each time they play they garner points within the game. Each person ...
2
votes
4answers
66 views

Random number function (counting)

I have task I can't get my head around, even with a suggested answer. You have a function the generates a random integer between $0 - 65535$. Your task is to generate random integers $125-525$ ...
3
votes
0answers
170 views

Maximum difference between tails in absolute value

I toss a fair coin $n$ times. Some notation: $S_i=$ difference between #heads and #number of tails after the first $i$ tosses, $1\leq i\leq n$. $M_n=\max(S_1,S_2,\dots,S_n)$, ...
-1
votes
1answer
58 views

Recurrence relation for ternary sequence

Find the recurrence relation for number of ternary strings that do not contain two consecutive 0's or 1's. Strings that contains only 0s, 1s and 2s are called ternary strings. Answer is $a_n =2 ...
1
vote
2answers
73 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: ...
15
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. [closed]

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
25 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 ...
14
votes
1answer
206 views

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
65 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
50 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
64 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
73 views

Pigeonhole Principle proving [closed]

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
66 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
91 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 ...
1
vote
0answers
29 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
111 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
83 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 ...
0
votes
0answers
50 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
78 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
36 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 ...
1
vote
2answers
32 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
41 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
152 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\}$?
-1
votes
1answer
476 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
66 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
95 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
90 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
182 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
76 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
47 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
120 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
74 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
0answers
29 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
42 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
147 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
50 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
33 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
267 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
63 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
126 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 ...
0
votes
2answers
50 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$.
5
votes
3answers
70 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
88 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
63 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
85 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
129 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
38 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
92 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
19 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
175 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 ...