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
44 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 ...
3
votes
1answer
31 views

Number of possible rectangles from at most N identical squares

I was looking to find the number of distinct rectangles possible from at most $N$ identical squares. (Two rectangles are distinct if one cannot be rotated to obtain another) e.g for $N = 6$ , $8$ ...
0
votes
1answer
23 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
47 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 $ = ...
6
votes
7answers
162 views

How many $10$ digit number exists that sum of their digits is equal to $15$?

How many $10$ digit number exists that sum of their digits is equal to $15$? Additional info: First digit from left is not $0$.we could use any digits from $0$ to $9$. I saw in some ...
2
votes
2answers
61 views

Number of ways to put one or more of $5$ books in $5$ bags

In how many ways can we put one or more of 5 books in to 5 bags? Additional info: books are labeled. Bags too. One or more bags can remain empty. Things I have done so far: There are $5$ ...
2
votes
3answers
63 views

Combo Identity: How to prove this using Induction [closed]

$$ \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
3answers
32 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
21 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 ...
6
votes
1answer
78 views

Size of a family of sets $F$ such that if $|A\cap X|=|B\cap X|$ for all $X\in F$, then $A=B$

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
2answers
47 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 ...
1
vote
1answer
54 views

An upper bound and simplification for expression

I would like to find the upper bound (or simplification) of this expression: $$\sum_{j=1}^{n+1}\sum_{i=0}^{j-1} a^{j+i} {j+i \choose i}{n+1\choose j}{n \choose i}/{2n+1 \choose j+i}$$ where ...
1
vote
1answer
77 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 ...
1
vote
3answers
296 views

Have any one studied this binomial like coefficients before?

Consider the following identities. $\dfrac{n}{n-r}\dbinom{n-r}{r}=\dfrac{n}{r}\dbinom{n-r-1}{r-1}$ ...
-3
votes
0answers
54 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
2answers
63 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.
11
votes
5answers
264 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, ...
1
vote
2answers
74 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 ...
5
votes
1answer
102 views

Probability of drawing a run of a specific color from an urn with two colors of balls

I was sent a puzzle involving an urn with 128 white balls and 288 black. If the balls are drawn without replacement until the urn is exhausted, what is the probability that a sequence of 10 or more ...
2
votes
1answer
52 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
0answers
27 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} ...
37
votes
13answers
9k views

Why is it that if I count years from 2011 to 2014 as intervals I get 3 years, but if I count each year separately I get 4 years?

I'm not a very smart man. I'm trying to count how many years I've been working at my new job. I started in May 2011. If I count the years separately, I get that I've worked 4 years - 2011 (year 1), ...
3
votes
1answer
33 views

Number of distinct grids formed

Let $n$ be a positive integer and let $\mathcal{G}_n$ be an $n\times n $ grid with the number $1$ written in each of its squares. In each step we multiply all entries of a row or column is multiplied ...
0
votes
1answer
29 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 ...
1
vote
1answer
33 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 ...
1
vote
1answer
20 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 ...
0
votes
1answer
43 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
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 ...
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
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 ...
4
votes
1answer
42 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
3answers
58 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
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
vote
0answers
19 views

minimum number of unit distances required for a unit equilateral triangle

Problem. Suppose we have $n$ points on the plane. Among $\binom{n}{2}$ pairwise distances, there are $e$ number of unit distances. Find minimum $e$ ($e$ as a function of $n$) so that there is a ...
2
votes
1answer
39 views

A small variation of the Magic square problem

Let us consider a $n \times n$ grid squares. We put numbers from $0$ to $n^{2}$ ( note that you can omit any one number from $0$ to $n^{2}$ ) such that sum of elements in each row ,each column and ...
1
vote
1answer
37 views

paths from from point A to point B with length 8

Question How many paths from point A to point B with length 8 exists that that have even number of negative signs? path example my main problem is that i can't find a good way for counting ...
0
votes
1answer
40 views

prove $a^2_o-a^2_1+a^2_2-…+(-1)^{n-1}a^2_{n-1}=\frac {1}{2}(a_n+(-1)^{n+1}a^2_n)$

Question if $a_k$ is multinomial coefficient of $x^k$ in polynomial $(1+x+x^2)^n$,where $0\le k\le 2n$,prove: using this equality $(1+x+x^2)(1-x+x^2)=1+x^2+x^4$,show that ...
1
vote
0answers
40 views

Finding whether a sum of numbers in a set generate another number

I have a set of numbers {a1....an} and another number k. I need to find whether sum of any combination of numbers in the set ...
0
votes
1answer
65 views

Combination Problem with Sofa [closed]

Suppose we have 5 sofa on room A. in this room, 4 students seated on these sofa. These Strudents go to another room for eating dinner, and after that come back to room A. how many way the students can ...
1
vote
0answers
31 views

Probability that a subset of a degree-regular graph shares at least a certain number of mutual connections

Consider a set of $n$ vertices of common degree $p$. What is the probability that some subset of $x$ vertices from $n$ share $q$ mutual connections within that group of size $x$? i.e. If we have ...
2
votes
2answers
33 views

Flip cards to get maximum sum

Given N cards where if ith card has number x on its front side then it will have -x on back side and a single operation that can be done only once that is to flip any number of cards in consecutive ...
1
vote
1answer
46 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
1answer
63 views

Will I will be able to sit and watch the movie?

Recently I went to the theater. When I came to buy my $3$ tickets (two friends and I), the machine tells me that there is $18$ seats out of $300$ ($15$ rows of $20$ seats). What is the probability ...
1
vote
1answer
41 views

Find extra work done by Bob

Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0. Move ...
2
votes
1answer
24 views

What are the probability that the first two rows of the class are full?

I was boring in my class. So I ask myself the question: What are the probability that the first two rows of the class are full? Knowing that we're $25$ students in my class and the class have ...
6
votes
0answers
121 views

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 ...
5
votes
3answers
82 views

Ordered partitions of an integer (with a twist)

I would like to know how to prove (preferably algebraically) that $P_1(2,n)=F_{2n+1}$, where $P_1(2,n)$ is what I define to be the number of ordered partitions of an integer, where the number $1$ has ...
1
vote
0answers
44 views

The probability that exactly / at-least $k$ numbers are in the correct position [duplicate]

Given a sequence of $[1,\dots,n]$ in random order: Let $P_k$ be the probability that exactly $k$ numbers are in the correct position Let $Q_k$ be the probability that at least $k$ numbers are in the ...