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)

0
votes
2answers
18 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
9 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
16 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
17 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
11 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
28 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
1answer
12 views

Distribute ANDs over ORs in this sentence

$$[\neg C(x,y)]\vee [\neg A(x) \vee B(x)\wedge C(x,y)]$$ Can someone explain how we turn this sentence into conjunctive normal form by distributing the AND over the ORs? It's confusing me because the ...
0
votes
0answers
10 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
14 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
18 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
27 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
9 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
17 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
22 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
64 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
18 views

Asymptotic approximate for Binomial sum

How would you approximate the following sum in terms of n: $$\sum_{k=1}^{n} \binom{n}{k} (k-1)(a - n + k)^{-a + n - k - 1/2}(-1 - a - k + 2)^{1 + a + k - 5/2} e^{-n + 2-\frac{(n - k)}{12*a*(a - n + ...
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
107 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.
0
votes
1answer
32 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 ...
0
votes
0answers
28 views

Rearranging a integer sequence to minimize function on subsequences

Given a nonempty finite sequence of integers $Q$ with $g$ elements, it will sum to an integer $S(Q)$. For each sub-sequence within $Q$ of length $n$, there is a value $A(n)= \frac{n}{g}S(Q)$ that ...
-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
85 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
22 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
24 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
38 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
54 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
34 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 ...
2
votes
1answer
28 views

Enumerating Ideals in Posets

I am trying to work through Exercise 44 (a) in Ch.3 of R. Stanley's Enumerative Combinatorics. The problem is as follows: Let $w=a_1a_2\cdots a_n\in \mathfrak{S}_n$. Let $P_w=\{(i,a_i)\colon ...
1
vote
2answers
49 views

Solve the recurrence relation $a_n=4a_{n-1}-3a_{n-2}+2^n, a_1=1, a_2=11.$

First I solved $a_n=4a_{n-1} -3a_{n-2}$: $$x^2-4x+3=0\Rightarrow (x-3)(x-1)=0\Rightarrow a_n=k_1(1)^n +k_2(3^n)=k_1+k_2(3^n)$$ The problem is, I have no idea how to handle that part which has made ...
0
votes
1answer
35 views

Recursion and divisibility by $2^n$

A team plays a series of games, each of which results in either a win (W), a draw (D), or a loss (L). Let $S_n$ denote the number of possible sequences for a team which never loses two successive ...
0
votes
0answers
10 views

Probabilistic subset intersection

Let $\left \{ \left ( A_{i},B_{i} \right ),1\leq i\leq h \right \}$ be a family of pairs of subsets of the set of integers such that $\left | A_{i} \right |=k$ for all $ i$ and $\left | B_{i} \right ...
1
vote
1answer
27 views

Kraft-McMillan inequality

Let $F$ be a finite collection of binary string of finite lengths and assume that no two distinct concatenations of two finite sequences of codewords result in the same binary sequence. Let $N_i$ ...