For 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)

7
votes
1answer
1k views

Prove Ramsey Number R(3,5)=14

I'm having problem proving the ramsey number of R(3,5) = 14. Below is my proof. Proof. Let $v_0$ be a vertex from a $k_{14}$ vertices. The vertices incident to $v_0$ are $v_1, v_2, \cdots , v_{13}$ ...
41
votes
4answers
3k views

Do circles divide the plane into more regions than lines?

In this post it is mentioned that $n$ straight lines can divide the plane into a maximum number of $(n^{2}+n+2)/2$ different regions. What happens if we use circles instead of lines? That is, what ...
1
vote
1answer
167 views

Total number of ways and minimum number of steps of going up the stair case?

There is a staircase and some person say X can take 1 step or 2 steps . So how many ways can he take in total to climb up the staircase where there are ...
0
votes
1answer
1k views

Distribute distinct objects in identical boxes

Number of ways to distribute $6$ distinct objects to $3$ identical boxes such that each box should have atleast one? $\mathbf {Is\ there\ any\ standard\ formula\ for\ these\ sums}$, as we have for ...
8
votes
2answers
229 views

Shasha's safecracking problem

Suppose you want to open a safe with 10 switches. For each switch there're 3 settings, say, 1,2,3. There're 2 key switches. The safe is unlocked once you set the key pair correctly, but you can't ...
4
votes
1answer
507 views

Dyck Paths, Catalan Numbers, and Trapezoidal Parallelogram Polyominoes

I've been trying to find the number of Dyck paths $P$ of length $2n$ such that $\forall (x,y) \in P, |x-y| \le k$ for some fixed constant $k$. These are the Dyck paths that are bounded by the lines ...
6
votes
2answers
2k views

Probability/Combinatorics Problem. A closet containing n pairs of shoes.

A closet contains n pairs of shoes. If 2r shoes are chosen at random, (where 2r < n), what is the probability that the chosen shoes will contain no matching pair? I have tried thinking about this ...
0
votes
1answer
401 views

On arranging n balls into k buckets (limitation: the number of balls in each)

Since I don’t feel very confident when dealing with generating functions as of yet, I’d like to make sure whether my solution to the following simple problem is correct. Let $P(n, k, a, b)$ denote ...
3
votes
2answers
1k views

Number of triangles inside given n-gon?

How many triangles can be drawn all of whose vertices are vertices of a given n-gon and all of whose sides are diagonals ( not sides ) of the n-gon ? How many k-gons can be drawn in such a way ?
1
vote
3answers
641 views

What is the number of distinct combinations for choosing a pair of numbers between a sorted sequence?

What is the total number of ways in which we can choose pairs of $a_i$ and $a_j$ between a sequence of increasing sorted numbers numbers $a_1,a_2,a_3,\ldots,a_n$ such that $a_1\le a_i\le a_j\le a_n$.
3
votes
1answer
1k views

In how many different ways can we fully parenthesize the matrix product?

We have a finite number of matrices that we wish to compute the product of . Say we wish to compute a product of n matrices and we have the subroutine to compute a ...
3
votes
1answer
138 views

Formal exponential of multivariate power series

I was wondering about this. Consider a formal power series $$\sum_{n=1}^{\infty} a_n x^n$$. We can find its formal exponential, given by $$\exp\left(\sum_{n=1}^{\infty} a_n x^n\right) = ...
3
votes
2answers
336 views

Extension of the Birthday Problem

How do you find the expected number of people (or the expected number of pairs) among the n that share their birthday within r days of each other? For the regular birthday problem, it's ...
2
votes
1answer
856 views

Distance Between Two Sets of Points

Consider two sets of $N$ $n$-dimensiononal points each: $$\mathcal{X}= \lbrace \mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N \rbrace,$$ $$\mathcal{Y}= \lbrace ...
5
votes
1answer
192 views

Is there any good reads for Goodwillie calculus out there?

I have a basic understanding of combinatorial species and category theory and now I am curious about this functor calculus or Goodwillie calculus. Can anyone kindly recommend me a nice place to start. ...
1
vote
1answer
110 views

Subspaces $\mathcal{C_k}\subset(\mathbb{Z}/2\mathbb{Z})^3$ with $\dim(\mathcal{C_k})=2$

Enumerate all two-dimensional subspaces of the space $(\mathbb Z/2\mathbb{Z})^3$. Obviously we have $|(\mathbb Z/2\mathbb{Z})^3|=2^3=8$ with $$(\mathbb ...
-1
votes
5answers
584 views

Cryptography in Maple and Mathematica

Is Maple or Mathematica preffered over the other for Cryptography/Number Theory? What are the advantages for each in terms of this area of mathematics? Also could someone compare and contrast ...
1
vote
2answers
99 views

Confusion about combinations

In a combination problem I can think of three relevant numbers: i, the number of slots v, the number of valid values you can put in each slot k, the number of occurrences of one particular valid ...
0
votes
1answer
228 views

Number of possible rod cuts of a long rod .

Basically I am trying to understand the concept of dynamic programming via Rod Cutting example. How the number of ways in which a rod of length $n$ units can be cut is ${2}^{n-1}$ and not ...
1
vote
2answers
163 views

How to calculate number of favourable cases for the following problem

How to find the total cases where a four digit number has two like digits,three like digits, two pairs of like digits, four like digits etc...
3
votes
0answers
192 views

Find the number of specific permutations

Find the number of all permutations of the set $\left\{ 1,2,...,2n \right\}$ such that does not have compact subsequence: $\langle i, \ i+1\rangle$ or $\langle i+1, \ i\rangle$ for all $1\le i\le ...
2
votes
1answer
121 views

Throwing the dice, sum of the points

We are throwing the die (original cube for the board games). How many are ways to get the sum of the points equal to $n$ ? I've heard this problem today in the morning and still can't deal with ...
28
votes
1answer
1k views

Expiring coupon collector's problem

The well-studied coupon collector's problem asks, given $N$ different coupons from which coupons are being drawn with equal probability and with replacement: How many coupons do you expect to need ...
3
votes
2answers
150 views

showing that there is a shape which has three connected black squares

We have square lattice with dimensions $n × n$, such that $n \ge 2$. Some of the squares on this lattice are coloured black. How can we show that there are at least 3 connected black squares if there ...
5
votes
2answers
771 views

$n$-th digit in the sequence of natural numbers

What's the $n$-th digit in the sequence $S$ of numbers formed by the natural numbers, i.e., $n$-th digit in the sequence 1 2 3 4 5 6 7 8 9 10 11 12... ? For example 11th digit in the sequence is 0.
3
votes
1answer
159 views

Measuring unknown weight with n weight and a balance?

If we are given a set of $n$ weights and a balance we can weigh $2^n-1$ different sized objects by putting them one side of the balance and comparing them with $2^n-1$ set of weights. However we can ...
3
votes
2answers
182 views

Construction of some function on the group of permutations

Let $x=(x_1,\ldots, x_{2m})$ be vector in $R^{2m}$ and let $r=(r_1,\ldots,r_{2m})$be sequence, such that $P(r_i=1)=P(r_i=-1)=1/2.$ Consider the following set $$\begin{align*} X=\{r \in\{-1, ...
1
vote
0answers
138 views

is it possible to extend combination C(n, k) definition to 2 real numbers C(r,s)?

Combination is defined as $C(n,k) = n! / k!(n-k)!$, where n & k are non-negative integers. Now, the definition can be extend to C(r,k), where r is real number and k is an integer: ...
2
votes
2answers
127 views

what is the usage of combination $C(r,k)$ where $r$ extends to real number?

Combination is defined as $C(n,k) = \dfrac{n!}{k!(n-k)!}$, where $n$ and $k$ are non-negative integers. Now, the definition can be extended to $C(r,k)$, where $r$ is real number and $k$ is an ...
1
vote
3answers
776 views

What are the number of ways in selecting 5 elements from 25 unique elements? The order of the selected elements are not important

What are the number of ways in selecting 5 elements from 25 unique elements? The order of the selected elements are not important? I have 25 numbers, 1,2,3,4,5......23,24,25. What are the number of ...
3
votes
1answer
691 views

In how many ways can 2 balls be arranged in 5 boxes so that one box does not contain more than one ball?

What is the number of ways 2 balls can be arranged in 5 boxes? The boxes may not contain more than 1 ball. The balls are of different colors. I forgot to mention the order of the boxes are important. ...
9
votes
2answers
430 views

Techniques for summing ratio of binomial coefficients

There are several identities that involve the sum of the product of binomial coefficients. However what I am searching for is an identity that involves the ratio of binomial coefficients. ...
3
votes
1answer
266 views

Grid-constrained probability question

A little rusty on my combinatorics/probability, and looking for some pointers on figuring out some probabilities in a game setup. Given a 2-dimensional grid that is divided into 2x2 tiles, with each ...
1
vote
1answer
591 views

How many surjections are there from a set of 3 elements onto a set of 2 elements?

I know we can use inclusion-exclusion principle or stirling numbers to solve this for a set of n elements onto a set of m elements. But I wanted to know how can we get the result using simple ...
4
votes
5answers
519 views

Spivak's Calculus - Exercise 4.a of 2nd chapter

4 . (a) Prove that $$\sum_{k=0}^l \binom{n}{k} \binom{m}{l-k} = \binom{n+m}{l}.$$ Hint: Apply the binomial theorem to $(1+x)^n(1+x)^m$. I'm having a hard time trying to solve the problem ...
2
votes
5answers
525 views

How do we determine if the set of rational numbers and the set of all english sentences are countable or not?

How do we determine if the set of rational numbers and the set of all english sentences are countable or not? I had proved it for the set of Integers in graduation. Our instructor at that time told us ...
1
vote
1answer
321 views

Total number of solutions of a completely blank sudoku

In how many ways can we fill a $9\times 9$ matrix with digits from 1 to 9 so that all rows, all columns and all the nine $3\times3$ submatrices [obtained after partitioning the bigger matrix into nine ...
1
vote
0answers
144 views

Round Robin Scheduled for pre-determined meetings

I want to schedule a meeting between (P) number of parties, having (T) number of timeslots such that multiple meetings are arranged in one timeslot and of course, no party has more than one meeting in ...
0
votes
2answers
228 views

generating function of multinomial coefficient

How to express this series in closed form? $$\sum_{i=1}^{\infty}\frac{(3i)!}{(i!)^3}x^{i}$$ Motive of the generating function is to evaluate the number of the paths from the $(0,0,0)$ to $(n,n,n)$ ...
2
votes
2answers
310 views

Arranging people in a row

I've been stuck on this problem: How many ways can you place n identical items in k spots(with k>2n-1) so that none of the items are next to another item (not all of the items need to be placed). I ...
4
votes
3answers
224 views

Majority in Parliament Problem

In the parliament of a certain country there are 201 seats, and 3 political parties. How many ways can these seats be divided among the parties such that no single party has a majority? Is there any ...
3
votes
1answer
137 views

An inequality involving Stirling numbers of the second kind

The task is to prove the following inequality: $\begin{Bmatrix} mn\\ n \end{Bmatrix} \geqslant \frac{(mn)!}{(m!)^nn!}$ , where $m, n \in \mathbb{N_+}$ and to determine when the equality ...
0
votes
1answer
49 views

Binomial/Tensor Identity

Let $k$ be a a field and consider the space $k[x] \otimes_k k[x]$. I would like to verify the equation $$ \sum_{k=0}^{m+n} {m+n \choose k} x^k \otimes x^{(n+m)-k}= \sum_{i=0}^n \sum_{j=0}^m{n \choose ...
3
votes
2answers
189 views

Maximum intersecting subsets

There are n elements. What is the maximum number of subsets chosen at any one time so that every pair of subsets from collection intersect?
8
votes
1answer
224 views

The first column of the $n$th power for a triangular matrix

I have found a interesting thing but I cannot prove it. Given $k_i$ are positive for any $i\geq1$, and we have $M+1$ by $M+1$ matrix $A$, which is $$ A=\left[\begin{array}{ccccc} 0\\ k_{1} & 0\\ ...
1
vote
2answers
2k views

Given digits $2,2,3,3,4,4,4,4$ how many distinct $4$ digit numbers greater than $3000$ can be formed?

Given digits $2,2,3,3,4,4,4,4$ how many distinct $4$ digit numbers greater than $3000$ can be formed? one of the digits which can be formed is $4444$ $4$ digit numbers greater than $3000$, which ...
4
votes
1answer
258 views

Inequality involving sums of fractions of products of binomial coefficients

Let $n\in\mathbb{N}$. For $0\le l\le n$ consider \begin{equation} b_l:=4^{-l} \sum_{j=0}^l \frac{\binom{2 l}{2 j} \binom{n}{j}^2}{\binom{2 n}{2 j}}\text{.} \end{equation} Do you know a technique how ...
1
vote
1answer
110 views

The number of subset sum

If we have that $S=\{1,2,3,4,5,6,7,8,9,10\}$,how to know the number of subset sum T from :S in which for every $x\in T$ and for every $2x\in S $ then: $2x \in T$
8
votes
2answers
323 views

Combinatorics proof (any set of 16 numbers from 1 to 100 contains repeated sums)

Suppose that $A$ is a set of 16 distinct natural numbers and that $1\leq p\leq100$ for every $p$ in $A $. Prove that $A$ contains 4 different numbers $a$, $b$, $c$, and $d$, such that $a+b=c+d$.
0
votes
2answers
76 views

Combinations of nonincreasing sequences within bounds?

Given integers: $n,a_1, a_2, ..., a_n, b_1, b_2, ..., b_n$ How many nonincreasing integer sequences $(x_1, x_2, \dots, x_n)$ of length $n$ are there subject to the bounds: $a_1 \le x_1 \le b_1$ ...