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)

4
votes
2answers
83 views

No Adjacency Combinatorics Problem via Generating Function

I would like to find the generating function solution for the following combinatorics/probability problem. I have a combinatorial solution and the generating function deduced thereof. But I can not ...
6
votes
2answers
59 views

$\sum_{k=1}^n \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$

(Own) Let $n,m$ be positive integers such that $m>n$. Prove that $$\sum_{k=1}^n \sum_{a_1+a_2 + \cdots +a_k=n} \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$$ ...
2
votes
1answer
25 views

Tuples in cartesian product without duplicates

I have $n$ sets $S_1,\ldots,S_n$ and I would like to count the number of tuples $(i_1,\ldots,i_n)\in S_1\times\cdots\times S_n$ such as $i_h\neq i_k$ $\forall h,k\in \{1,\ldots, n\}$. Is there a ...
2
votes
0answers
43 views

Unique ways to distribute k1, k2, .. colored balls into n boxes uniquely

Example: Uniquely distribute 2 Red Balls and 4 Blue Balls into 3 boxes: [B][BB][RRB] [B][BBB][RR] [B][R][RBBB] [B][RB][RBB] [BB][R][RBB] [BBB][R][RB] Answer: ...
1
vote
1answer
49 views

Name of the numbers defined by $T(p,q) = T(p-1,q) + T(p,q-1)$?

I came across these numbers : $$ T(p,q)= \sum_{k=0}^{q-1} {p+k-1 \choose p-1} + \sum_{l=0}^{p-1} {q+l-1 \choose q-1} \quad p,q \in \mathbb{N} $$ While trying to solve this recurrence relation : $$ ...
6
votes
1answer
231 views

Special Products of Transpositions

[Edit. Significantly expanded to add examples and (I hope) clarification. Feel free to skim by reading the gray boxes.] A colleague asked me for insights on a collection of special permutations, ...
4
votes
1answer
94 views

A Combinatorial Sum!

Is there a closed form formula for the following sum \begin{equation} F(x;n,m)=\sum_{k=0}^{\min\{n,m\}} {n \choose k}{m \choose k}k!\ x^{k}=n! \, m!\sum_{k=0}^{\min\{n,m\}}\frac{1}{k!(n-k)!(m-k)!} ...
1
vote
0answers
30 views

Notation for indexing the factorizations of a number?

Background Given any $n \in \mathbb{N}$, the ordered factorization count of $n$ can be computed and is traditionally written $H(n)$. This is, essentially, the number of unique decompositions of $n$ ...
1
vote
2answers
80 views

Proving inequalities using Calculus

In general how do you prove inequalities using calculus, I believe it is using maxima or minima right? For example $$a^2b+b^2c+c^2a \le 3, \qquad a,b,c \ge 0,\quad a+b+c=3.$$ How would you use ...
4
votes
2answers
134 views

Proof sought for a sum involving binomials that simplifies to 1/2

A proof of: $$\begin{align*}(1/2)^{2m+1} \sum_{k=0}^{m} \binom{m}{k} \sum_{j=0}^{k} \binom{m+1}{j} = \frac{1}{2} \end{align*} $$ Conjecture based on the following Maple code: ...
8
votes
4answers
9k views

Proof a graph is bipartite if and only if it contains no odd cycles

How can we prove that a graph is bipartite if and only if all of its cycles have even order? Also, does this theorem have a common name? I found it in a maths Olympiad toolbox.
0
votes
0answers
34 views

Converting base 10 to base 52 using a bijective function [migrated]

I was recently asked in an interview the following question: "How would you design a URL shortener?" My response was to store the URL into a database which provides a unique key of maximum length 10 ...
0
votes
0answers
32 views

Number of permutations on nearest neighbors

Consider a finite connected set $A \subset \mathbb{Z}^d$ and let $S_A$ be the set of permutations on nearest neighbors. Namely, the elements of $S_A$ are bijections $\pi : \, A \rightarrow A$ such ...
5
votes
3answers
87 views

Number of ways through a modified grid

I was in math class listening to my teacher blather on about solids of revolution when my friend passed me a note with a puzzle on it. It looked something like this: How many different ways can you ...
0
votes
2answers
2k views

Outcome possibilities with three teams and three outcomes for each game

So there are six teams (let's say: 1,2,3,4,5,6), and they pair up to face each other, (so three games in total). In each game, one team either wins or their is a tie. Let's set up the teams and their ...
1
vote
1answer
40 views

Cartesian product with all elements

I have two sets A and B with $A = \{1,2,3\} \\ B = \{ A, B, C, D, E \}$ Now I need to get something similar to the Cartesian product. If my understanding is correct, the Cartesian product would ...
0
votes
0answers
63 views

Number of graphs with 5 vertices

Let $v_i$ where $i=1,2,3,4,5$ be vertices of a graph. Each vertex makes only one directed edge to any other vertex. For instance $v_1 \to v_2 \to v_3 \to v_4 \to v_5 \to v_1$ and $v_1 \to v_3 \to v_4 ...
1
vote
1answer
42 views

Permutations for a set of rules

The question is from - http://www.iarcs.org.in/inoi/2015/zio2015/zio2015-question-paper.pdf - Q.2 I tried solving it but I have no clue how to go about doing it. The question says that a railway ...
5
votes
1answer
47 views

Number of representatives from states to from a comittee?

Among the three representatives to a conference from each of the fifty states, either none, one, or two of the representatives will be chosen for a large special committee. How many ways can this ...
5
votes
1answer
64 views

Function equation, find the function evaluated at the certain point.

Let $f(x)$ be a polynomial with real coefficients such that $f(0) = 1,$ $f(2)+f(3)=125,$ and for all $x$, $f(x)f(2x^{2})=f(2x^{3}+x).$ Find $f(5).$ The constant term, $a_0 = f(0) = 1$. Let: ...
0
votes
1answer
29 views
0
votes
4answers
43 views

All possible combinations

I have two sets (1,2,3) and (A,B,C,D,E). I want to calculate all possible combinations. This would be my approach: combinations with a single 1: ...
5
votes
1answer
94 views

The vertices of the $n$-cube are painted in two colors

The vertices of the $n$-dimensional cube are painted in two colors. The number of vertices of each color is the same ($2^{n-1}$). Prove that at least $2^{n-1}$ edges connect vertices of different ...
11
votes
3answers
315 views

Proof of the identity $\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}$

Prove the identity: $$\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}.$$
3
votes
2answers
123 views

Proving the combinatorial identity: $\sum_{k=0}^m (-1)^k 2^{2k-1}\left[{m+k-1\choose 2k}+{m+k\choose 2k}\right]=(-1)^m$

Let $m$ be a positive integer. I have trouble proving that $$\sum_{k=0}^m (-1)^k 2^{2k-1}\left[{m+k-1\choose 2k}+{m+k\choose 2k}\right]=(-1)^m$$ Anyone?
1
vote
0answers
43 views

How to give a rigorous proof of a fact about convex polygon?

I claim that there exists universal constants $0<\delta_1(m), \delta_2(m)<1$ such that for any convex polygon $P$ in $\mathbb{R}^n$ with $m$ faces, \begin{equation} \frac{\mathcal{H}^{n-1}(\{x ...
1
vote
3answers
53 views

What is the number of mappings?

It is given that there are two sets of real numbers $A = \{a_1, a_2, ..., a_{100}\}$ and $B= \{b_1, b_2, ..., b_{50}\}.$ If there is a mapping $f$ from $A$ to $B$ such that every element in $B$ has an ...
9
votes
2answers
251 views
+50

How do I prove this combinatorial identity using inclusion and exclusion principle?

$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity ...
5
votes
5answers
187 views

Binomial coefficients in Geometric summation

Guys please help me find the sum given below. $$\sum_{k=j}^i\binom{i}{k}\binom{k}{j}\cdot 2^{k-j}$$ (NOTE):The two coefficients are multiplied by 2 power (k-j) I am using the formula: ...
1
vote
1answer
20 views

Optimize order of a list based on time to complete, probability of success

I'm a programmer participating in a coding challenge, but I'm not up on my advanced math. I'm currently working on a solution to a problem, and have a semi-functional program, but I'm still missing a ...
0
votes
0answers
19 views

Determine $ex(n,P_k)$ for each pair of n and k

I have to find the maximum number of edges in $P_k$ free graph where $P_k$ is path of length $k$. I know the result that a graph on $n$ vertices with no path of length $k$ has edges$\ \le ...
0
votes
1answer
33 views

Chains of people names

Consider the set $X$ of possible names for people. Let $(x, y) \in P$ (in the partial order) if and only if $x$ ends in a consonant and $y$ ends in a vowel. What is the length of the longest ...
0
votes
0answers
19 views

Minimal posets and chains [on hold]

Given a poset (X, P ) we can say that an element x ∈ X is minimal if it doesn’t cover any other element y ∈ X. Think about the relation between finding a maximal chain and the minimal elements. Isn't ...
3
votes
2answers
76 views

Partitioning $\{1,2,\cdots ,n\}$ into $2$ sets guarantees $3$ numbers $a,b,c$ in the same set with $ab=c$ for some $n$

(ISL-20-$1988$) Find the least natural number $ n$ such that, if the set $ \{1,2, \ldots, n\}$ is arbitrarily divided into two non-intersecting subsets, then one of the subsets contains 3 distinct ...
3
votes
1answer
30 views

How many ways can I connect labeled trees into a tree.

Suppose I have the labeled trees $T_{1}, \ldots, T_{n}$ with $b_{1}, \ldots, b_{n}$ vertices respectively. I would like to know how many ways I can compose a tree from these trees by using all trees? ...
2
votes
1answer
112 views

Catalan's number with a twist

We all know that $$C_n = \frac{1}{n+1} {2n \choose n} $$ But what if I want to calculate the same property of catalan, but with number of zeros is $s$ and number of ones is $t$ when $s\neq t$? As ...
-1
votes
1answer
44 views

Probability of winning consecutively [on hold]

India and USA play $7$ football matches. No match ends in a draw. Both the countries are of same strength. Find the probability that India wins at least $3$ consecutive matches.
0
votes
1answer
59 views

Number of combinations where the sum of values must be the same

My question is as follows: let there be $n$ different numbers $a_i$ in a set $A$, where each $a_i$ is a number between 0 and 1. How many different sets of values can I have that fulfill the condition ...
7
votes
2answers
145 views

Expand $\binom{xy}{n}$ in terms of $\binom{x}{k}$'s and $\binom{y}{k}$'s

Motivated by this question, I want to find a complete set of relations for the ring of integer-valued polynomials, where the generators are the polynomials $\binom{x}{n}$ for $n\in \mathbb{N}$. The ...
3
votes
4answers
64 views

How to solve this combinatorics problem?

As a tourist in NY, I want to go from the Grand Central Station (42nd street and 4th Avenue) to Times Square (47th street and 7th Avenue). I needed my morning coffee, and wanted to go to a Starbucks ...
1
vote
1answer
25 views

What is this 2-D array of numbers called?

Define $c(n,r)$ ($n\in\Bbb N;r\in\Bbb Z$) by setting $c(0,-1)=-1$, $c(0,0)=1$, and $c(0,r)=0$ otherwise, with all further $c(n, r)$ given recursively by $$c(n+1,r)=rc(n,r-1)-(r+1)c(n,r)$$(rather in ...
1
vote
0answers
32 views

Combination estimation

I am looking at a proof where part of it derives an estimation for the number of combinations and I cant understand how the following step is derived: $\varepsilon^{-\varepsilon L}\underset{j \leq ...
0
votes
2answers
67 views

Summation of special series

Does anybody know how to evaluate $$\sum_{i=2}^n(i^2)\cdot{i\choose2}$$ How about the general case of $(i^k)*{i\choose2}$? A nice formula would be great!
1
vote
0answers
99 views

Maths puzzle 1: smart play with sets

Let $$X=\{ a, b, c, d, e, f, {ab}, {ac}, {ad}, {ae}, {af}, {bc}, {bd}, {be}, {bf}, {cd}, {ce}, {cf}, {de}, {df}, {ef}, {abc}, {abd}, {abe}, {abf}, {acd}, {ace}, {acf}, {ade}, {adf}, {aef}, {bcd}, ...
2
votes
0answers
12 views

There are $m$ distinct sets of $k$ positive integers such that no two form a fat pair, show that $m<n^{k-1}$.

[ELMO 2015] Let $m, n, k > 1$ be positive integers. For a set $S$ of positive integers, define $S(i,j)$ for $i<j$ to be the number of elements in $S$ strictly between $i$ and $j$. We say two ...
0
votes
2answers
36 views

Find the sum of the roots of the exponential equation

The equation $$2^{333x - 2} + 2^{111x + 2} = 2^{222x + 1} + 1$$ has three real roots. Find their sum. I'll simplify it first as: $$\frac{1}{4}2^{333x} + (4)2^{111x} = (2)2^{222x } + 1$$ Let ...
0
votes
3answers
58 views

Counting numbers of possible solutions

For the equation $\displaystyle x_1+x_2+x_3+x_4+x_5=n$ there are $\displaystyle \binom{4+n}{4}$ solutions. But what about the equation $\displaystyle x_1x_2x_3x_4x_5=n$ ? Assuming $\displaystyle ...
1
vote
2answers
43 views

Integer solutions of a less than inequality

I need to determine how many integer solutions are to this inequality:$$ y_1 +y_2 +y_3 < 100 $$ with $$y_1 > 0,y_2 ∈ [0,10],y_3 ∈ (0,19]$$ I'm having trouble where to start. I know ...
2
votes
1answer
61 views

How to find out the probability of an event about which we have two informations

I would like to know how to find out the probability of an event about which we have two informations. Say we have $A$ and we know it is lower than $K$ but greater than $X$. How do you find the result ...
5
votes
3answers
695 views

Number of 11-digit length number with all 10 digits and no consecutive same digits

Here is the question: In how many ways we can construct a 11-digit long string that contains all 10 digits without 2 consecutive same digits. Initially, I came up with $10!9$. I thought that there ...