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)

3
votes
1answer
54 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
3answers
247 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
47 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
230 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
53 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
17 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
80 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
65 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
35 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
59 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
43 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
200 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
180 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 ...
7
votes
1answer
110 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
565 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=1}^{n} f(k_ih)h$$ ...
0
votes
2answers
66 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
33 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$ ...
2
votes
2answers
83 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
117 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
94 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
31 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
135 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
78 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
107 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}$ ...
4
votes
0answers
28 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
30 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
130 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 \} $?
-2
votes
2answers
53 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
54 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
107 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
56 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
41 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 ...
3
votes
2answers
192 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
52 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 ...
5
votes
2answers
213 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
46 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
33 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
23 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
32 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
28 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 ...
3
votes
1answer
49 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
52 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
50 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}$ ...
5
votes
1answer
53 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
29 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
38 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
1answer
46 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
61 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
34 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 ...
7
votes
6answers
1k views

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 ...