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
19 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
32 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
27 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
19 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
15 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$. Are the ...
0
votes
2answers
56 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 ...
1
vote
3answers
35 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 ...
3
votes
0answers
35 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 ...
1
vote
0answers
355 views

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=0}^{n} f(k_ih)h$$ ...
0
votes
2answers
29 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
28 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
27 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
60 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
41 views

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

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
47 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
19 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
38 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
33 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
23 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
21 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
13 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
67 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
57 views

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

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
27 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
37 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 ...
1
vote
2answers
45 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
32 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
13 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 ...
2
votes
2answers
94 views

Counting permutations that respect a partial order

Suppose you have three kinds of coins, say: pennies, nickels, and dimes. Each penny has a unique date, likewise for nickels and dimes. (A penny and a nickel may have the same date, etc.) How many ways ...
4
votes
1answer
34 views

Number of different magmas up to isomorphism

Let $(M,\circ)$ be a magma over a finite set of order $n$. I tried to count all the possible magmas up to isomorphism, but I just can't get it right. My naive approach was to count all the possible ...
1
vote
0answers
28 views

Generating Function for 2-Associated Stirling Numbers of the Second Kind

I am looking for a paper which explicitly defines a power series for 2-associated Stirling Numbers of the Second Kind. The paper defines the generating function as follows: Let $S_2(n,k)=b(n,k)$ be ...
0
votes
2answers
26 views

Symmetries of a Polynomial

I was wondering how many symmetries the polynomial $(x_1-x_2)(x_2-x_3)(x_1-x_3)$ has, and what they are. I got four: (i) $(x_1-x_2)(x_2-x_3)(x_1-x_3)$ (ii) $(x_2-x_1)(x_1-x_3)(x_2-x_3)$ (iii) ...
1
vote
1answer
29 views

Worst-case time to copy one movie

The capacity of hard drive $H_k$ is $10^k$ movies and $|H_k|$ represents the number of movies currently stored on $H_k$. Whenever $H_k$ fills up (i.e. $|H_k|=10^k$) you copy everything onto ...
1
vote
1answer
20 views

Showing that $\sum_{i=0}^m \binom{k_i}{2} \leq \binom{n-m}{2}$ when $k_0 + \ldots + k_m = n$

I came across the following inequality (well, it's in a paper, I am assuming it is correct for now...). Let $n$ be a positive integer and suppose $k_0 + \ldots + k_m = n$, $k_i > 0$. Then ...
1
vote
0answers
30 views

What does “combining the solutions in O(n) time” mean?

Algorithm $X$ proceeds by recursively solving $5$ subproblems of one-half the size, then combining the solutions in $O(n\log n)$ time. Algorithm $Y$ makes $9$ recursively calls on ...
0
votes
2answers
26 views

$n$ families with $k$ members and $r$ rooms

Suppose that we have $nk$ persons such that there are $n$ families with $k$ members. We have $r$ rooms and we want to send persons to rooms such that each room has exactly one person. I want to count ...
2
votes
1answer
39 views

Strategy to find out set with nice subset structure

Let $A=\{0,1\}^n=\{(a_1,a_2,\ldots,a_n)\mid a_i\in\{0,1\}\}$. Let $B\subseteq A$ be such that if $(b_1,b_2,\ldots,b_n)\in B$,$ (c_1,c_2,\ldots,c_n)\in A$, and $c_i\leq b_i$ for all $i$, then ...
1
vote
2answers
34 views

Past GRE Question

Below is a problem from a past math subject GRE exam (GR9367). Is there a quick way to solve this? Let $A$ and $B$ be subsets of a set $M$ and let $S_0=\{A,B\}$. For $i\geq 0$, define $S_{i+1}$ ...
0
votes
0answers
16 views

Paperfolding Constant

In the Wikipedia article about the regular paperfolding sequence, it says (more or less quoted): Taking $G(t_n;x) = G(t_n;x^2) + \sum_{n=0}^{\infty}x^{4n+1} = > G(t_n;x^2) + \frac{x}{1-x^4}$ ...
4
votes
0answers
24 views

Selecting cells so that every $2\times 2$ square is odd, then even

Jacob selects some cells from a $12\times9$ table, so that every $2\times 2$ subsquare contains an odd number of selected cells. He then selects some more cells, so that every $2\times 2$ subsquare ...
0
votes
1answer
22 views

Find $\sum_{i=0}^{\log n} \frac{1}{2^i}$

I'm not really sure how to solve summations, so any help would be great. In particular, I had thought that $n^2\sum_{i=0}^{\log n} \frac{1}{2^i}=O(n^2\log n)$ but it's actually $O(n^2)$, and I'm ...
0
votes
1answer
33 views

How to quickly determine running time of such recurrence relations?

$$T(n)=5T(\frac{n}{2})+n\log n$$ $$T(n)=9T(\frac{n}{3})+n^2$$ $$T(n)=2T(\frac{2n}{3})+n^{1.5}$$ What are the running times of each $T(n)$? Each one looks like the form of the Master Theorem, but only ...
1
vote
0answers
17 views

How to show that a set of random strings has unit probability

I am encountering a problem where I want to show that the generation of a random string terminates in finite time with probability one, where the termination is condition is reaching an element of a ...
0
votes
2answers
27 views

Solve the recurrence $T(n)=3T(n/3)+\log n$, $T(1)=1$

So $T(n)=3T(n/3)+\log n$ and $T(1)=1$. I tried to solve this by expanding it out to see a pattern, but I don't really see the pattern: $T(n/3) = 3T(n/9)+\log (n/3)$ $T(n) = 3[3T(n/9)+\log ...
0
votes
1answer
27 views

Combination with two letters together

I've to type of letters A and B and fill the 5 five blank spaces. And calculate in how many ways i can perform a conbinations in which AA are always together. My first attenpt was to calculate ...
3
votes
2answers
58 views
+50

Different approaches to N balls and m boxes problem

Suppose that you have N indistinguishable balls that are to be distributed in m boxes (the boxes are numbered from 1 to m). What is the probability of the i-th box being empty (where the i-th box is ...
0
votes
2answers
42 views

There are 10 sticks of length 1,..,10. How many triangles can be formed

There are 10 distinct sticks of length 1,..,10. How many triangles can be formed? I do not know whether there are some counting tricks for this one.
2
votes
1answer
69 views

Compute $\sum_{k=0}^{n}\frac{1}{\binom{n}{k}}$

I want to calculate $\sum_{k=0}^{n}\frac{1}{\binom{n}{k}}$. No idea in my mind. Any help? Context I want to calculate the expected value of bits per symbols in adaptive arithmetic coding when the ...
0
votes
0answers
22 views

Check if intervals overlap

I have a set of activities $A$, where each activity $i \in A$ has a starting date $s_i$ and an end date $e_i$ (or equivalently a starting date and a duration $d_i$). Therefore, each activity can be ...