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)

4
votes
0answers
16 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
19 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?

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
55 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
21 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 ...
1
vote
0answers
34 views

some combinatorial proofs [on hold]

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
5 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
31 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
11 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
25 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
41 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
24 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
18 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
60 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
36 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 ...
4
votes
0answers
41 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
397 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
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
28 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
71 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
44 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
20 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
39 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
14 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
68 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
59 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
46 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
21 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
40 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
17 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
25 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
23 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 ...