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 (4)

1
vote
2answers
41 views

Upper bound on $ \binom{a}{m+1}\sum ^m_{j=0} \binom{a-m-1}{j}/\binom{b}{j+m+1}$

Given $a,b,m$ such that $0<2m<a<b$. I would like to find out upper bound of $$S = \binom{a}{m+1}\sum ^m_{j=0} \frac{\binom{a-m-1}{j}}{\binom{b}{j+m+1}}$$ Anyone can help me please? Thank you ...
0
votes
0answers
14 views

How many Homomorphisms are there from one bounded lattice to another?

for a project that I work on, I need to know how many homomorphisms there are from one finite lattice with 0 and 1 to another. I remember that I already worked it out if one of them is the trivial ...
0
votes
7answers
149 views

Calculating $\displaystyle\sum_{i=1}^{n} \binom{i}{2}$

Show $\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$. I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to $i!/2!(i-2)!$ and ...
2
votes
0answers
29 views

Counting symmetric binary matrices with constant line-sum

I'm trying to count, as the title suggests, symmetric matrices with entries $0$ or $1$ and constant line-sum $k$. ($0 \leq k \leq n$). If you start listing the number of these on a table you'll get a ...
1
vote
1answer
74 views

Choosing 5 of 40 people sitting at a circular table so that between any two are at least three other people

$40$ people sit around a circular table. In how many ways can we choose $5$ people so that between any two of them there are at least $3$ other people? Things I have done so far: This question is ...
0
votes
1answer
21 views

Probability $\sum_{j=n+1}^{2n+1} {M \choose m+1}{M-m-1 \choose j-m-1}/{N \choose j} $

I have a prob. problem: A school has $N$ students in which $M$ students are leader (of each class in school), and $N>M$. There are $2n+1$ balls in the black box including $n+1$ blue balls and $n$ ...
0
votes
2answers
43 views

Combinatorial argument $a(n-a)$ $n \choose a $ = $n(n-1)$ $n-2 \choose a-1$

I can not make sense of this; I am looking for a combinatorial argument that would prove the equivalence of this statement. I can prove it with algebraic manipulation. $a(n-a)$ $n \choose a $ = ...
7
votes
5answers
661 views

How many arrangements of $\{a,2b,3c,4d, 5e\}$ have no identical consecutive letters?

How many arrangements of $\{a,2b,3c,4d, 5e\}$ have no identical consecutive letters? I find it very tough... Could anyone have some good ways?
0
votes
1answer
45 views

Counting the ways for two professors to schedule individual exams for $12$ students

Two professors are scheduling separate individual exams for $12$ students in the same hour. Examination of one student in each subject takes $5$ minutes. In how many ways can this scheduling be ...
-2
votes
1answer
104 views

A Twin Primes Sequence [on hold]

How to prove the relation below and is it enough significant to prove the infinitude of the twin primes? For every twin primes $x,y$ there exists $\alpha,\beta$ positive integers such that ...
-1
votes
0answers
78 views

Find the highest story from which an egg can be dropped without breaking it (lowest average, not worst-case scenario) [on hold]

EDIT: Not looking for worst-case scenario solution, but rather the lowest average. This question has been answered many times for worst-case scenario being 14, I know this already :) PROBLEM: You ...
11
votes
5answers
236 views

Unit circle is divided into $n$ equal pieces, what is the least value of the perimeters of the $n$ parts?

A unit disk is divided into $n$ equal pieces, that is, each piece has area $\dfrac\pi n$. equal "pieces" means equal area Let $l_1, l_2,\dotsc,l_n$ be the perimeters of the $n$ parts, ...
0
votes
2answers
45 views

Counting combinations with a restriction of the form “either … or …, but not both”

The following is the problem that I am dealing with. There are 9 people in a class and 4 of them is randomly chosen to form a committee. Jack and Nick are 2 of the 9 people in the class. How ...
2
votes
3answers
60 views

Combo Identity: How to prove this using Induction [on hold]

$$ \sum_{n = 0}^{\infty} \binom{n + k}{k}x^n = \dfrac{1}{(1 - x)^{k + 1}} $$ Could someone suggest how I should get started to prove this using induction?
1
vote
1answer
44 views

Proof that ordinary multinomial coefficients rise monotonically to a maximum and then decrease monotonically

While most computations of ordinary multinomial coefficients for the following case require recursive summations, I found here a closed-form solution: $$(1+x+x^2+\cdots+x^q)^L = \sum_{a \geq 0} ...
1
vote
2answers
69 views

Number of possible patterns?

Using the following rule: Each column and each row must contain at least one point, how many patterns can a 4x4 grid (thus with 16 possible point positions) generate? (this rule would thus make the ...
1
vote
3answers
31 views

Choosing $2$ groups of $5$ members and $1$ group of $2$ members from $15$ person

In how many ways can we choose $2$ groups of $5$ members and $1$ group of $2$ members from $15$ person? Additional info: groups are not labeled. Things I have done so far: I know number of ...
1
vote
1answer
24 views

Combinatorics Question about balls in boxes

There are 5 balls numbered 1 to 5, and there are 3 boxes numbered 1 to 3. The question asks in how many distinct ways can the balls be put into the boxes if 2 boxes have 2 balls each and the other box ...
0
votes
1answer
19 views

I'm looking for two euclidean polytopes such that their cartesian product is no longer a euclidean polytope.

I'm looking for two euclidean convex polytopes such that their cartesian product is no longer a euclidean convex polytope. Does such a thing exist? Note here by convex polytope I mean the set $ K ...
1
vote
2answers
34 views

what is the > probability that only one letter will be put into the envelope with > its correct address?

Tanya prepared 4 different letters to 4 different addresses. For each letter, she prepared one envelope with its correct address. If the 4 letters are to be put into the four envelopes at ...
3
votes
3answers
123 views

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac n2 \rceil$ or $ \lfloor \frac n2\rfloor $?

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac{n}{2} \rceil $ or $ \lfloor \frac{n}{2} \rfloor$ ? This link provides a proof of sorts but it is not satisfying. From what I ...
5
votes
0answers
42 views

distinguishing family of sets

Call a family $F$ of subsets of $S=\{1,2,\ldots,n\}$ distinguishing if for every two distinct subsets $A,B$ of $S$ there exists $X\in F$ so that $|A \cap X|\ne |B \cap X|$. Show that there exists such ...
1
vote
1answer
211 views

Probability of a slot having exactly K elements

From this question asked in an interview: Consider a hash table with $M$ slots. Suppose hash value is uniformly distributed between $1$ to $M$. Suppose we put $N$ keys into this $M$-slotted ...
7
votes
2answers
186 views

Showing an indentity with a cyclic sum

Let $n\geqslant2$, and $k\in \mathbb{N}$ Let $z_1,z_2,..,z_n$ be distinct complex numbers Prove that $$ \sum_{i=1}^{n}\frac {{z}_{i}^{n-1+k}} { \prod \limits_{\substack{j = 1\\j ...
-3
votes
0answers
53 views

Existence of a particular monochromatic sequence from a two colouring of $\mathbb{N}$

The positive integers are colored by two colors. Prove that there exists an infinite sequence of positive integers $k_1 < k_2 < \cdots < k_n < \cdots$ with the property that the terms of ...
0
votes
1answer
56 views

Have any one studied this binomial like coefficients before?

Note that the simillarities of following identities. $\dbinom{n}{r}=\dbinom{n}{n-r}$ $\dfrac{n}{n-r}\dbinom{n-r}{r}=\dfrac{n}{r}\dbinom{n-r-1}{r-1}$ $\dbinom{n}{r-1}+\dbinom{n}{r}=\dbinom{n+1}{r}$ ...
15
votes
0answers
295 views

Making Friends around a Circular Table

I have $n$ people seated around a circular table, initially in random order. At each step, I choose two people and switch their seats. What is the minimum number of steps required such that every ...
1
vote
1answer
40 views

Rational Series VS Algebraic Series

I am reading a paper on combinatorics. It mentions some generating functions are rational series and others are algebraic series. I do not understand the difference, can someone help? EDIT $1$: The ...
8
votes
1answer
119 views
+50

Graph partition that span a third of edges

Given a graph G is easy to see that we have a partition $V=V_1 \cup V_2$ so that $$e(G[V_1])+e(G[V_2])\leq e(G)/2$$. How can we improve this result showing that we can choose $V_i$ such that ...
4
votes
2answers
121 views

How many elements of order $k$ are in $S_n$?

I need to find how many elements of order $k$ are in $S_n$ (where $k \leq n$). So if $k$ is prime, it's easy: $k$ can't be the $\mathrm{lcm}$ of any integers besides itself and one's (which we're ...
0
votes
2answers
60 views

Simplify the expression of binom

Any one knows how to simplify this expression or finding upper bound of this expression: $$\sum_{j=1}^{n+1}\sum_{i=0}^{j-1} a^{j+i} {j+i \choose i}$$ where $0<a<1$ is constant. Thanks a lot.
4
votes
1answer
39 views

What is this sequence of all permutations with gaps permissible

Let there be a sequence $a_1, a_2, a_3,...,a_n$ that represent some actions that you know are required to solve a problem. However, you do not know what order these actions need to be taken to solve ...
0
votes
1answer
27 views

To calculate number of combination of sequences having 1 and 2 alternating sequences of R and S.

I have a sequence of 6 letters containing 2 P, 2 R , 1 Q and 1 S. I have PPQ, now I have to add two R and one S in that, these can be placed anywhere. There will be total 60 possible ways to do that ...
2
votes
1answer
50 views

What do you call a set whose subsets all have unique sums?

An example would be $\{1, 3, 7\}$, which has subsets with sums $1, 3, 7, 4, 10, 8, 11$. What is this called?
0
votes
1answer
39 views

Distribution, Combination,Arrangments

How many ways can 25 distinguishable balls be placed in two distinguible boxes? *Order/placing doesn't matter *Only unique combinations accepted (e.g a blue ball weather placed in a box first or last ...
0
votes
0answers
25 views

Simplifying a combinatorial sum

Show that \begin{align} y\sum\limits_{i=1}^dx^iz^i\sum\limits_{j=1}^iq^{i-j}G_d(x,y,q\mid j) = y\sum\limits_{i=1}^d(x^iz^i+\cdots+x^dz^dq^{d-i})G_d(x,y,q\mid i) \end{align} where \begin{align} ...
0
votes
0answers
30 views

Is it true that $k^{\lceil f(k) \rceil}(1+o(1)) = k ^{f(k)}(1+o(1))$? [on hold]

Is it true that $k^{\lceil f(k) \rceil}(1+o(1)) = k ^{f(k)}(1+o(1))$? I think the answer is no?
3
votes
1answer
67 views

Upper bound of $S=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$

EDIT: How can I find a good upper bound to this quantity ? $$S_{n,m}=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$$ where $P=\min\{m,n\}$ et $Q=\max\{m,n\}$.
5
votes
0answers
82 views
+100

Parity of sum of Kronecker deltas in a graph

For some fixed $n\in\mathbb N$ let $G$ be a graph on the vertex set $\{1,\dots,n\}$ with a total number of $k$ edges $e_1,\dots, e_k$. For any vertex colouring $c(i)$ of the graph, $\delta_e$ is ...
0
votes
3answers
55 views

How many four digit numbers begin with $10$?

How many combinations are there for a four digit combination that starts with ten. I have a safe that requires four numbers and I know that the first two numbers are one and zero. I do not remember ...
1
vote
1answer
12 views

Lexicographical rank of a string with duplicate characters

Given a string,you can find the lexicographic rank of a string using this algorithm: Let the given string be “STRING”. In the input string, ‘S’ is the first character. There are total 6 characters ...
1
vote
1answer
30 views

Extracting the coefficient of $x^n$ from a fraction

I need help extracting the coefficient of $x^n$ from a $\frac{1-x}{1-2x}$. So far I have that \begin{align} \frac{1-x}{1-2x} &= \frac{1}{1-2x} - x\frac{1}{1-2x}\\ &= \sum\limits_{k=0}(2x)^k ...
1
vote
1answer
30 views

Upper bound of $\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}$

I would like to find max (or sup.) of the sum: $$S=\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}.$$ I found $S\le \frac{1}{\sqrt{\pi n}}.2(n+1).4^n$ but It seems it's ...
0
votes
0answers
17 views

To determine number of times male and females members of 2 family are arranged alternately in a row [on hold]

To arrange male and female (M,F) of 2 families denoted by P,Q and R,S respectively in such a way that there is exactly one flip (flip means PQ or QP together) in one family and considering the case of ...
0
votes
1answer
39 views

Number of triangles formed by all chords between $n$ points on a circle

We have $n$ point on circumference of a circle. We draw all chords between this points. No three chords are concurrent. How many triangles exist that their apexes could be on circumference of ...
1
vote
1answer
41 views

Is there a set of 69 length-6-sets out of 46 numbers [1..46] so that those length-6-sets “cover” all possible 1035 length-2-sets of 46 numbers?

1.) For this question, we have 46 numbers (balls, cards, whatever): {1,2,3,4 .... 45,46} ======================= 2.) Each length-6-set of 46 numbers ( e.g. {1,2,3,4,5,6} or {1,13,16,17,32,46 } ...
-1
votes
0answers
53 views

Maximise and operation [duplicate]

Given an array of $n$ non-negative integers $A_1, A_2, \dots, A_N$, find a pair of integers $A_u$, $A_v$, where $1 \leq u < v \leq N$, such that the bitwise-and ($A_u$ and $A_v$) is as large as ...
1
vote
1answer
253 views

Permutation & Combination - how many numbers smaller than $2.10^8$ and are divisible by $3$ can be written by means of the digits $0$,$1$ and $2$

How many numbers smaller than $2.10^8$ and divisible by $3$ can be written by means of the digits $0$,$1$ and $2$? Left Zero padding not allowed. I am getting this as - 3 digits - 2*3 = 6 4 digits - ...
0
votes
1answer
18 views

Distribution combinations

How many ways can 25 identical pencils be distributed between two people?.Each all pencils must be shared out. A) Each person must have at least 5 pencils? B) Each person must have at least 7 ...
2
votes
1answer
55 views

Number of permutation with non-consecutive blocks

How many strings are there consisting of exactly M A's, N B's, and K C's so that the string BC does not appear? For example, when M=3, N=1, K=1, $$ABACA$$ counts as a valid string whereas ...