Tagged Questions

This tag is for basic 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 (5)

1
vote
0answers
15 views

Navigation in a graph

The problem Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$. We define the graph metric $d$ for ...
3
votes
1answer
69 views

How can I prove this question using the Binomial Theorem of Newton?

I'm guessing I have to use the Binomial Theorem of Newton, but I'm getting stuck somewhere. Data $p$, $q$ are positive real numbers with $p+q=1$, and $k, n$ are natural numbers with $k\leq n$. ...
1
vote
3answers
61 views

How to prove the amounts of dominos with x+y=n+k = x+y=n-k?

I've been trying to answer this question for hours with no luck at all.. The question is the following: Question Imagine we have domino blocks of the following shape: [ x | y ] with x, y ∈ [0..n]. ...
0
votes
1answer
10 views

Breaking Uniquely decipherable codes.

Is it possible to decode a message that has been encoded using a Uniquely Decipherable Code without knowing the code that is used. If it is possible, what is the time complexity?
2
votes
1answer
53 views

Applying the inclusion exclusion principle to count permutations with forbidden subsequences

I have problem with this: How many permutations of the letters A,B,D,E,I,K,M,N,R,U,Z are there so that none of the words: ARZEN, DRAK, DUM, DURAZ are subsequences of the permutation. This means it ...
0
votes
1answer
16 views

Understanding problem of Combination with repetitions allowed

I was reading topic on "Combinations with repetition" from the book Discrete Mathematics and Its Application by Kenneth Rosen. I understood the first problem and the formula. But I did not understood ...
0
votes
1answer
36 views

how can ı distrubute $1000

A author writes a book and then he publishs it.He realises that there are some mistakes but he do not know how many mistakes are there and he decides to distribute \$1000 someone who find the ...
0
votes
1answer
21 views

What is the length of the longest decreasing sequence in integer matrix?

Given a finite $m \times n$ matrix $M$ with all distinct integers, we travel it following two simple rules: The travel can start from any cell, say, $M[i,j]$. At each cell $M[i,j]$, it computes the ...
1
vote
0answers
24 views

A counting problem related to Parallelogram

There are n distinct points in the plane, given by their integer coordinates. Find the number of parallelograms whose vertices lie on these points. In other words, find the number of 4-element subsets ...
1
vote
2answers
60 views

Counting words with letters from TOWN with conditions

Show that the number of $m$-letter words using letters T O W N (maybe not using some of them) in which the number of Ts and Os are equal, is equal to the number of $2m$-letter words only using Ts ...
0
votes
0answers
50 views

Beautiful combinatorics and logic problem

In some country they use golden and platinum sand. Gold can be exchanged to platinum and vice versa, using an exchange rate defined by postive integers g and p as follows: $x$ grams of gold is ...
2
votes
1answer
49 views

A density question

Let $\theta \in \mathbb{R} \setminus \mathbb{Q}$. Is the set $\{ (2n+1) \theta \bmod 1: n \in \mathbb{N} \}$ dense in $[0,1]$?
1
vote
1answer
22 views

Probability and Combinations Question-Without Replacement.

There are 30 biscuits in a box. 12 are wrapped and the other 18 aren't. If I were to take 4 biscuits without replacement from the box, what is the probability that I take exactly 2 wrapped biscuits? ...
7
votes
0answers
27 views

Need a feedback on my solution (logic) of the combinatorial problem which involves ordinary deck of cards

So, here is the problem: An ordinary deck of 52 playing cards is randomly divided into 4 piles of 13 cards each. Compute the probability that each pile has exactly 1 ace. My solution: $$\frac { {4 ...
3
votes
1answer
24 views

Given that there are 6 married couples. If we select only 4 people out of 12, what is the probability that none of them are married to each other? [closed]

Please, can you help me to solve this? Given that there are 6 married couples. If we select only 4 people out of 12, what is the probability that none of them are married to each other?
0
votes
4answers
74 views

How many 7-digit ID numbers do not contain three consecutive sixes.

I have a homework question in a discrete mathematics class that asks me to determine how many 7-digit id numbers do not contain three consecutive sixes. It seems clear that I should approach this by ...
0
votes
1answer
30 views

number of surjective functions

Let $A, B$ sets, $|A| = n, |B| = r,~ 1 \le r \le n$. Prove that there are $\displaystyle \sum_{k_1 + \cdots + k_r =~n \atop k_1,\ldots,k_r \in \mathbb N} \frac{n!}{k_1! \cdots k_r!}$ surjective ...
3
votes
2answers
131 views

some combinatorial proofs

These were simple induction proofs, so I decided to try and prove them combinatorially. I think I nailed the first one, not so sure about the second one. $\sum_{i=1}^n(i)(i!)=(n+1)!-1$ Have $n+1$ ...
1
vote
0answers
8 views

Simple lower bound for the connective constant of the plane square lattice for self avoiding walks

We know that the connective constant of plane SAW (Self Avoiding Walks) on the square lattice is between 2 and 3. There are very accurate estimations of this constant. It's very easy to see that it ...
1
vote
0answers
44 views

Probability in Combination of 5 colour in 9 spaces

We have 5 colours: red, green, blue, black and white, and 9 spaces to paint with only one of that colours each. What is the probability of having 5 spaces in white and the other 4 all in different ...
0
votes
1answer
13 views

Finding the number of elements in the set $S=\{(x_1,…,x_k)\in \Bbb{Z}^k| 1\leq x_i \leq n \land x_1<x_2<…<x_k\}$

I got this problem: Find the number of vectors in the set $S=\{(x_1,...,x_k)\in \Bbb{Z}^k| 1\leq x_i \leq n \land x_1<x_2<...<x_k\}$ where $1\leq k,n\in\Bbb{Z}$. I tried to count the number ...
1
vote
0answers
39 views

Parallelogram Counting

There are $n$ distinct points in the plane, given by their integer coordinates. Find the number of parallelograms whose vertices lie on these points. In other words, find the number of $4$-element ...
1
vote
1answer
50 views

Can books be arranged into bags?

I'm trying to find an algorithm (sub exponential) to answer the following question (informal): given a (finite) set of distinct books of different (positive integer) sizes and a (finite) set of bags ...
0
votes
1answer
29 views

A problem related to combinatorics and number theory

$n$ and $m$ are two numbers. We have to make $n$ with $m$ numbers (only taking their sum). For example, if $n=6$, $m=3$, $6$ is formed with $3$ numbers in the following way: $$ 1+1+4=6 \\ 2+2+2=6 \\ ...
1
vote
2answers
25 views

Total number of 8 digit numbers divisible by 3 and composed of 4, 5 and 6?

I know that the total possible 8 digit numbers made using 4, 5 and 6 is $3^8$. But if one more constraint is added like the number must be divisible by 3, how do we find it. The answer is $3^7$, but I ...
0
votes
0answers
32 views

Questions concerning upper densities

Let $D(X) = \limsup_{N \rightarrow \infty} \big( \frac{|A \cap \{1,...,N\}|}{N} \big)$ represent the upper density of set $X$; $FS(X)$ be the set of all finite sums of terms/elements in $X$. Note: $0 ...
0
votes
2answers
75 views

Find the coefficient of $x^{24}$ in $(1 + x + x^2 + x^3 + x^4 + x^5)^8$

I'm not sure how to go about doing this. Do I find the ways to add up to 24 using the exponents with repetition? Is the multinomial theorem useful here? I also have a feeling that generating functions ...
2
votes
3answers
46 views

Show that $\begin{align}{n \choose k}{k \choose m} = {n \choose m}{n-m \choose k-m}.\end{align}$

Show that $\begin{align}{n \choose k}{k \choose m} = {n \choose m}{n-m \choose k-m}.\end{align}$ Not sure how to approach this exactly. I've tried to use the property $\begin{align}{n \choose k} = {n ...
6
votes
1answer
86 views

Dividing tournament into “equal” groups

In a tournament of $n$ teams, each team plays all other teams exactly once, with no draw. For which $n$ is it always possible to divide all teams into several groups so that each group of teams won ...
2
votes
0answers
520 views
+50

Relation I found: $ (\sum_{r=1}^{\infty}\frac{z(r)}{r})\times \int_0^\infty f(x) dx = \lim_{h \rightarrow 0} \sum_{i=0}^{n} f(k_ih)h$

I was fiddling with some maths and came up with an interesting relationship: $$ (\sum_{r=1}^{\infty}\frac{z(r)}{r})\times \int_0^\infty f(x) dx = \lim_{h \rightarrow 0} \sum_{i=1}^{n} f(k_ih)h$$ ...
0
votes
2answers
31 views

A tricky problem on permutation and combination

Let $A_n$ denote the number of all $n$-digit positive integers formed by the digits $0,1$ or both such that no consecutive digits in them are $0$. Let $B_n$ the number of such $n$-digits integers ...
1
vote
2answers
29 views

A combinatorics and algebra problem

I'm given two numbers $n$ and $m$. I have to make $n$ with $m$ numbers (only taking their sum). For example, if $n=6$, $m=3$, $6$ is formed with $3$ numbers in the following way: $1+1+4=6$ ...
1
vote
2answers
29 views

Dividing students into teams-combinatorics

In how many ways can $n$ number of students be divided into two teams such that each team has at least one student. This is what I did: Let $x_1$ be the number of students in the one team and $x_2$ ...
0
votes
2answers
79 views

Number of ways to seat people around a circular table

I got (i) which is $9!$, but there are no answers for the second question. I stated that $$P(\text{none together})=1-P(\text{3 together})-P(\text{2 together})$$ and got the answer $7/12$. Is this ...
1
vote
2answers
46 views

In how many ways can we choose $2$ integer numbers from $1$ to $128$ such that their sum is divisible by 4? [closed]

In how many ways can we choose $2$ integer numbers from $1$ to $128$ such that their sum is divisible by $4$?
1
vote
2answers
51 views

Consider the lists of length six made with the symbols $P, R, O, F, S$ where repetition is allowed.

Consider the lists of length six made with the symbols $P, R, O, F, S$ where repetition is allowed. (For example, the following is such a list: $(P,R,O,O,F,S)$.) How many such lists can be made if the ...
0
votes
0answers
22 views

Constant-weight code for error correction

I need some Constant-weight code for error correction. Understanding how these codes generated is really hard for me. The papers of this topic are focus on lower bound and upper bound. What I need is ...
0
votes
2answers
30 views

Finding the subsets in a set that contains x or y but not z

Let S be a set of size 37, and let x, y, and z be three distinct elements of S. How many subsets of S are there that contain x or y, but do not contain z? $(a) 2^{36} − 2^{34}$ $(b) 2^{36} − 2^{35}$ ...
1
vote
0answers
40 views

Five cards dealt off of a $52$ card deck

Five cards are dealt off of a standard $52$-card deck and lined up in a row. How many such line-ups are there in which all $5$ cards are of the same suit? With $13$ cards per suit and $5$ cards being ...
3
votes
2answers
34 views

How to count the amount of subsets within a set

Let S be a set of size 37, and let x, y, and z be three distinct elements of S. How many subsets of S are there that contain x and y, but do not contain z? (a) $2^{33}$ (b) $2^{34}$ (c) $2^{35}$ ...
0
votes
0answers
25 views

Average number of cycles in a uniformly selected random permutation of {1,…,n} [duplicate]

I (think) I'm on the right heading with this problem, but I feel like I'm taking a jump with my reasoning and relying on intuition. I've proved combinatorially that for a permutation of $\{1,...,n\}$ ...
4
votes
0answers
22 views

How to number the natural numbers lexicographically with minimal overhead (and provide a lower bound for the overhead)?

Working in binary, note that the number 100 is lexicographically smaller than the number 11 even though $100 > 11$. How can we devise a function $f$ such that $f(a)$ is lexicographically smaller ...
1
vote
0answers
20 views

Syndeticity and A.P.-richness of certain sets

Let $A \subset \mathbb{N}: \sum_{a \in A} (\frac{1}{a}) = \infty$; denote $\{ \alpha_1 @ \alpha_2: \alpha_1, \alpha_2 \in A \} = A @ A$, where "$@$" is any appropriate binary operator. (Note: $A$ is ...
0
votes
1answer
73 views

Prime number in set $\{1,…,60\}$

How can we calculate by using the principle of inclusions and exclusions how many prime numbers are in the set $ \{1, ..., 60 \} $?
-1
votes
1answer
61 views

Mathematically prove that a bench which 2 chidlren fit in can't fit 3. [closed]

You have a bench( Only 2 children can sit on it), 3 children and you have to prove logically that 3 children don't fit on the bench.
-2
votes
1answer
28 views

Combination and Permutation

In how many ways can 4 men and 5 women make up a special committee looking into safety in the workplace if 3 persons are selected and at least 1 committee member must be a woman? I tried to do it i ...
0
votes
1answer
39 views

How many $4$ digit numbers can be formed using $0,0,2,2,2,2,3,3$?

I've solved forming 8 digit number using 1,1,2,2,2,3,3,3. We have 8 digits: two 1, three 2 and three 3. First I put three 2s in 8 possible places. Number of putting 2s = 8!/(3!∗5!) . After putting 2s ...
2
votes
2answers
48 views

How many ways can 40 people be split into 10 quartets?

"A certain music school has 49 students, with 10 each studying violin, viola, cello, and string bass. The director of the school wishes to divide the class into 10 string quartets; the four students ...
2
votes
1answer
33 views

How many $7$ digit numbers can be formed using $0,1,1,2,2,2,3$?

I understand that we can't use 0 for the first digit. I've solved forming 8 digit number using 1,1,2,2,2,3,3,3. We have 8 digits: two 1, three 2 and three 3. First I put three 2s in 8 possible places. ...
1
vote
0answers
14 views

Logarithm of an applied permutation

Say I have a cyclic permutation $P$, a known input $x$, and a known output $y$ such that $$y = P^a x$$ for some $a$. Is there a good way to search for $a$ (i.e. better than brute force)? Are some ...