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)

0
votes
0answers
13 views

Enumerating Subspaces that Do Not Intersect a Given Subset

Consider the $n$-dimensional vector space $\mathbb F_2^n$ of $n$-tuples of elements of $\mathbb F_2$. Suppose I have a subset (not necessarily a subspace) $S\subseteq\mathbb F_2^n$ and a positive ...
1
vote
0answers
25 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$ ...
0
votes
1answer
23 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 : $$ ...
3
votes
2answers
44 views

Simplifying a combinatorial expression

Find \begin{eqnarray} \sum_{i=1}^{k-1}i(2k-2-i)\binom{2k}{2i+1} \end{eqnarray} I know how to find $\sum_{i=1}^{k-1}a_i\binom{2k}{2i+1}$ if $a_i$ is linear in $i$, but got stuck when $a_i$ is ...
3
votes
1answer
72 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)!} ...
0
votes
0answers
29 views

Converting base 10 to base 52 using a bijective function

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 ...
1
vote
2answers
20 views

Probability theory combinatoric problem

A total of $n$ bar magnets are placed end to end in a line with random independent orientations. Adjacent ends with equal polarities repel each other, and adjacent ends with opposite polarities ...
0
votes
0answers
44 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
21 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
26 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 ...
0
votes
1answer
27 views

How to calculate powers of a permutation in cyclic notation? [on hold]

How do I calculate powers of an 8-cycle (1 2 3 4 5 6 7 8) ?
0
votes
0answers
20 views

Mixing up seating charts: Measuring “mixedness” over time

Background: My class has $10$ students and $3$ tables; naturally, the students are distributed with $3, 3,$ and $4$ seated at the individual tables. On the second day of class, students sat in the ...
1
vote
0answers
42 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
1answer
19 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 ...
1
vote
2answers
75 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 ...
0
votes
0answers
16 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 ...
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 ...
1
vote
0answers
32 views

How to manipulate the bound on the summation

$$ B_n^{f^2}(x) = \sum_{k=1}^n\sum_{j=0}^{n-k} 2^{k-j} {j+k \choose j} \frac{d^j}{df^j}[f^k] B_{n,j+k}^f(x) $$ I am looking to have the bounds switched, can someone show me exactly how this is done? ...
-1
votes
1answer
42 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.
3
votes
1answer
27 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? ...
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: ...
1
vote
1answer
32 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
58 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: ...
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 ...
0
votes
0answers
18 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 ...
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 ...
4
votes
3answers
331 views

Students in a class, girls sitting with boys and boys sitting with girls

This is a very interesting word problem that I came across in an old textbook of mine. So I mused over this problem for a while and tried to look at the different ways to approach it but unfortunately ...
0
votes
1answer
53 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 ...
0
votes
2answers
65 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
3answers
50 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 ...
2
votes
0answers
11 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 ...
5
votes
5answers
185 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: ...
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
50 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
0answers
98 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
1answer
57 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 ...
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 ...
10
votes
4answers
1k views

N gunmen in a field

Let n be an odd integer. In some field, n gunmen are placed such that all pairwise distances between them are different. At a signal, every gunman takes out his gun and shoots the closest gunman. ...
5
votes
3answers
685 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 ...
1
vote
0answers
42 views

Given a number $N$ and a prime $P$, how many numbers $\leq N$ are divisable by P but not by any smaller primes?

The following Math Exchange question deals with a similar problem: not divisible by 2,3 or 5 but divisible by 7 However, the answers given become infeasible quite quickly because the amount of ...
5
votes
2answers
68 views

Generating functions of bills

Using generating functions, find the number of ways to make change for a $\$$100 bill using only dollar coins and $\$$1, $\$$5, and $\$$10 bills. My answer: I had ...
4
votes
1answer
54 views

Probability of consecutive floors on an elevator with more people

Another user posted this question about elevator occupants, which made me curious about a harder question. In a $t$-story building (with no basement), $n$ people get on an elevator on the first ...
1
vote
3answers
55 views

Probability of selecting consecutive floors in an elevator

Three people get into an empty elevator at the first floor of a building that has 10 floors. Each presses the button for their desired floor (unless one of the others has already pressed the button). ...
3
votes
2answers
59 views

Probability that all colors are chosen

A box contains $5$ white, $4$ red, and $8$ blue balls. You randomly select $6$ balls, without replacement, what is the probability that all three colours are present. Most similar problems ask for ...
0
votes
0answers
41 views

How can I prove that these numbers are integers?

Let $n, k$ integers, $n \ge 0$ and $0 \le k \le n$; further let $b(n)$ be the number of $1$'s in the binary expansion of $n$. $$ q(n) = 2^{3n - b(n) } $$ $$T(n, k) = ...
0
votes
0answers
10 views

Prove that if $e \in \left ( S\to \overline S \right )$ when $\left ( S, \overline S \right )$ is a min-cut, then $f(e) = c(e)$

Given a min-cut $\left( S, \overline S \right )$, we define $\left ( S\to \overline S\right ) =\{\left (u\to v\right )|u \in S, v\in \overline S\}$ and $\left ( \overline S \to S \right )$ similarly. ...
-3
votes
2answers
20 views

How many four-digit even numbers have all four digits distinct? [on hold]

How many four digit even number have all four digit distinct?
0
votes
0answers
26 views

How do I calculate all possible combinations for a player creator in a game?

I'm currently working on a character creator for a game, but I don't know how to calculate all possible character combinations the player can create. In the creator, the player is required to choose ...
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 ...
2
votes
3answers
23 views

Picking edges from a connected graph so that any vertex is incident with an odd number of those edges

Suppose you are given a connected graph G having an even number of vertices. Show that you can select a set $E$ of edges from this graph so that any vertex in G is incident with exactly an odd ...