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
26 views

How to prove that the subsets of $\mathbb{N}$ that don't contain arithmetic progressions of some length form closed sets of a topology?

I have exactly the same problem as this person, which I will rewrite below:Topology and Arithmetic Progressions. The reason I'm posting this is that I'm stuck at a later stage than the OP of that ...
0
votes
0answers
8 views

Properties of Coefficients of Order Polynomials

I am working on a problem involving determining the order polynomial $\Omega_P(k)$ of a partial order $P$, which counts the number of order-preserving transformations/maps from $P$ to the $k$-chain ...
2
votes
1answer
45 views

How to show $\binom{2n}{n} \ge \prod_{n < p \le 2n} p $?

What is the best way to show \begin{equation} \binom{2n}{n} \ge \prod_{n < p \le 2n} p \end{equation} for prime $p$. I know that $ 2^{2n} = (1+1)^{2n} \ge \binom{2n}{n}$. and \begin{equation} ...
1
vote
0answers
6 views

Submodular function, square of which is also submodular?

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ ...
3
votes
3answers
41 views

Simplifying $\sum_{i=0}^n i^k\binom{n}{2i+1}$

What is the formula for \begin{eqnarray}\sum_{i=0}^n i^k\binom{n}{2i+1}?\end{eqnarray} I tried to use the identity $$ ...
2
votes
3answers
33 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
44 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$ ...
-2
votes
0answers
36 views

the identity permutation

for the permuation $ \pi $ on n elements we define the term : $ \pi^k=i $ if the composition of $ \pi $ on it self k times is the identity permutation . A. let $ a_n $ be the number of permutation of ...
0
votes
0answers
22 views

Locks and Keys using permutation and combination [on hold]

This is a problem using permutations, combinations and factorial. There are four bankers in charge of a bank vault. We can not trust all of the bankers (2 of them are untrustworthy, we don't ...
1
vote
0answers
11 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
vote
2answers
33 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: ...
6
votes
8answers
1k 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.

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 142. But I don't know ...
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 ...
7
votes
0answers
32 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$ ...
-1
votes
0answers
32 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
28 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
46 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 ...
0
votes
0answers
26 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
75 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
26 views

partitions and generating functions ( combinatorics ) [on hold]

given partition, lets say the the ODD parts are : the biggest part, the 3th biggest part, the 5th biggest part etc and the EVEN parts are : the 2th biggest part, the 4th biggest part and so on . show ...
1
vote
0answers
13 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
24 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
33 views

How to solve this using set theory? [on hold]

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
41 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
35 views

Non repeatable combinations [on hold]

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
42 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
58 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 [on hold]

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
17 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
62 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
32 views

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

The fact that there are four 2's is throwing my off. Any pointers? Thank you for your time.
4
votes
1answer
57 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
150 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
64 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
41 views

Odd prime combinatorics problem [on hold]

How should I show that ${2p \choose p}\equiv 2\pmod p$ if p is an odd prime! help please
2
votes
3answers
100 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
37 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
19 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
35 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
133 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
40 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
23 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 ...
4
votes
4answers
97 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$.