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)

-3
votes
1answer
19 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 ...
-1
votes
1answer
27 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 ...
0
votes
0answers
9 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 ...
1
vote
1answer
27 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
5 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
68 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 ...
2
votes
1answer
21 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
16 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
23 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
0answers
16 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
15 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
27 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
23 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 ...
1
vote
1answer
18 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
29 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
14 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
17 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
19 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
31 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
12 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
26 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
18 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 ...
1
vote
2answers
29 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 ...
0
votes
2answers
34 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
67 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 ...
1
vote
5answers
109 views

Sum of $1+2+4+8+…$ [duplicate]

I was solving a recurrence problem which had a sequence such as $y = (1+2+4+8+...)\sqrt n$, and I wanted to find what $x = 1+2+4+8+...$ was. So consider $x = 1+2+4+8+...$ as an infinite series. $$x-1 ...
0
votes
2answers
51 views

Clueless when solving recurrence relations

I really need some help solving recurrence relations in a relatively quick manner, so any insight would be highly appreciated. Here are a few of the ones on my midterm sample that I'm struggling with: ...
3
votes
1answer
86 views

Prove a theorem in combinatorics

I want to show that for $k=1,...,(n-1)$ we have : $\binom{n}{k}\leq \frac{n^n}{k^k(n-k)^{n-k}}$ I have used induction on $k$, but I have not deduced the above relation.
1
vote
2answers
37 views

Put B balls in C containers. How many combinations have box(es) with exactly 2 balls?

Assume that we have B balls (all the same) and C numbered containers (distinguishable). We want to calculate how many of the total combinations contain exactly 1 container with 2 balls, exactly 2 ...
-2
votes
0answers
25 views

Rectangular Seating Combinations [on hold]

Show me how I can seat 22 people in a rectangle with everyone sitting side by side. There are supposed to be 5 ways (different rectangles)? How do I do this?
2
votes
2answers
81 views

Beautiful combinatorial painting problem

Mark paints squares of a white $10 \times 10$ board. He can either paints some vertical row of squares blue or some horizontal row red.(Every row is painted at most once). If blue paint is put on ...
0
votes
4answers
86 views

Algebraic Proofs in Combinatotics

Prove the following identity using an Algebraic Proof. $$\binom{n + m}{2} = nm + \binom{n}{2} + \binom{m}{2}$$ I have no idea where to begin on this problem or let alone finish it.
0
votes
1answer
18 views

how to convert index into C(N,K), K=2

i am trying to enumerate pairs in random order, by generating index $J$ and converting it into pair parts $\binom{N}{2}$ have two items - let's say $x$ and $y$ $N, x, y, J \in \{0,1,2,..\}$ $0 <= ...
0
votes
4answers
56 views

How many boxes can be painted while respecting this restriction?

We have 30 boxes in a line: $x_1,x_2,...,x_{30}$. Some of them we can color in red. The rule is that if $x_k$ is colored red then $x_{k+2}$ can't be colored red and vice versa. What is the maximum ...
0
votes
2answers
23 views

Counting anagrams

How many 8 letter words in scrabble can be formed from the tiles used in the word PARRAMATTA? Here's what I've done so far: There are 8 'spots' to choose from, with 10!/2! possibilities (as no ...
2
votes
1answer
23 views

Maximum load is $O(\log\log n/\log\log\log n)$

There are $n$ bins labeled $0,1,\ldots,n-1$, and $\log_2n$ players. Each player chooses a starting location $k$ uniformly at random, and places one ball in each of the bins $$k\bmod n,k+1\bmod ...
4
votes
1answer
51 views

Vandermond identity corollary $\sum_{v=0}^{n}\frac{(2n)!}{(v!)^2(n-v)!^2}={2n \choose n}^2$

I am trying to prove this identity: $$\sum_{v=0}^{n}\frac{(2n)!}{(v!)^2(n-v)!^2}={2n \choose n}^2$$ I think this identity (corollary of Vandermond identity): $${n\choose 0}^2+{n\choose 1}^2+{n\choose ...
0
votes
1answer
25 views

Prove that for a sequence of people sets $S_1,…,S_d$, $\Delta_i \not = 0$ for all people

We have $k$ people $p_1,...,p_k$, and $d$ people sets $S_1,...,S_d$, where the sizes of $S_1,...,S_d$ can vary between $1$ and $k$ (so each $S_1,...,S_d$ is a set of some people from ...
2
votes
1answer
9 views

Poisson approximation to bound probability of balls in different bins

Suppose $n$ balls are thrown randomly and independently into $n$ bins. What is an upper bound that all balls land in different bins using Poisson approximation? The exact probability is $n!/n^n$, ...
0
votes
0answers
28 views

If $\binom{n-1}{r} = (k^2-3)\cdot \binom{n}{r+1}$. Then values of $k\in

If $\displaystyle \binom{n-1}{r} = (k^2-3)\cdot \binom{n}{r+1}$ and $k\in {\mathbb{R}}$. Then values of $k\in $ $\bf{My\; Try::}$ We can write it as $\displaystyle \frac{(n-1)!}{r!\cdot (n-1-r)!} = ...
1
vote
1answer
12 views

Last two bins have same number of balls

If we throw $n$ balls independently and randomly into $n$ bins, what is the probability that the last two bins have an equal number of balls? We can write that as the sum of the probability that each ...
0
votes
0answers
25 views

Combinatoric Easy Problem : How many number from these numbers?

I just want to compare your answer with my answer. As we know, this subject, combinatoric has different answer and different point of view for each person. So, I just wanna know is your answer is same ...
1
vote
1answer
39 views

Showing the equality of two rook polynomials.

I'm reading Barbeau's Polynomials. I've done the following: Taking an arbitrary chessboard $C$ with some of the squares forbidden (with $n$ being the number of squares and $F$ the number of ...
1
vote
1answer
55 views

What is meant by $ab$ on words $a$ and $b$ in $\{ab\ |\ a,b \in Σ^*\}$?

Given language $L$ := $\{ab\ |\ a,b \in Σ^*\}$, $Σ := \{blue, green\}$. Is the notation "$ab$" above taken to be word concatenation, such that $\{bluegreen\} \subset L$? What occurs when $L$ := ...
1
vote
1answer
24 views

The number of ways to paint 3 cubes using 3 cans of paint, so that two cubes are blue

I have a question about the usage of the probability formula (I believe that is what it is called). So, I have 3 cubes and 3 differently colored cans of paint (Let's say, Red, Yellow and Blue). I am ...
0
votes
3answers
32 views

Proof by Induction: Series of binomial coefficients with same k-length subsets

I have no idea how to prove this binomial equation identity. For reference this is included in Discrete Mathematics for Computer Scientists by Clifford Stein, Robert Drysdale and Kenneth Boggart, ...
0
votes
0answers
35 views

Problems about Linear Extensions

The following are exercises 57 and 58 from R. Stanley's Enumerative Combinatorics. I can't see to figure out how to explain an answer to 57, and I don't know where to begin with 58. $e(P)$ denotes the ...
4
votes
0answers
43 views

How to visualise Bollobas' 1965 theorem?

Theorem $[n]=\{1,\ldots,n\}$. Let $\lbrace (R_i, S_i), i \in I \rbrace, R_i, S_i \subset [n]$ be such that $R_i \cap S_i = \emptyset, R_i \cap S_j \ne \emptyset (i \ne j)$. Then $$\sum_{i \in I} ...
3
votes
2answers
43 views

How many binary sequences of length n are there that contain exactly m occurrences of the pattern 01?

I thought there were n-1 places between the first and last digit. In these places I hypothesized there are switches that change (from 0->1 or 1->0) For ...