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)

1
vote
1answer
12 views

Explanation for ordering cominations.

While studying, I got stuck on this problem: "Seven identical chairs in a row are to be seated by four students. How many arrangements are there such that the only two of the three empty chairs are ...
1
vote
1answer
18 views

Generating Finite Groups By Random Premultiplication With Generators

Let $G$ be a finite group with identity $e$ and $S$ be a set which generates $G$. Is it always possible to define a procedure of the form: Start with $x=e$. With probability $p_1$, replace $x$ with ...
0
votes
3answers
42 views

Proof for number of completely odd and even subsets.

While studying, I read this: "A subset of integers 1,2,...,n has the property that the sum of its members is odd. The number of such subsets is 2^(n-1)." I also read this: "A subset of integers ...
1
vote
1answer
31 views

What is the sum of all $k$ values?

In an urn there are a certain number (at least two) of black marbles and a certain number of white marbles. Steven blindfolds himself and chooses two marbles from the urn at random. Suppose the ...
0
votes
0answers
12 views

Available lists of all latin squares up to order 5?

There are available online lists of the number of all latin squares up to order 11, e.g.: https://oeis.org/A002860. For a permutation-based test of a latin square design, one option is to fit the ...
1
vote
4answers
43 views

Proof for number of ways to select k non-consecutive elements from n consecutive terms.

While studying, I found a formula that found the number of ways to select k non-consecutive elements from n consecutive terms, not necessarily the first n consecutive terms, but any n consecutive ...
4
votes
0answers
23 views

Proving that the intersection of two closed sets is closed in a matroid

I am stuck on a little homework problem I have. Here, $M$ is a matroid with rank function $R$. I am given this definition: In a matroid $M$, a set $A$ is closed if $R(A \cup e) > R(A)$ for all $e ...
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
39 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: ...
6
votes
2answers
51 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,$$ ...
1
vote
0answers
29 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
1answer
45 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
51 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 ...
4
votes
1answer
87 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
33 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
22 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
55 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
38 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
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 ...
0
votes
1answer
29 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
22 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
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
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
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 ...
0
votes
0answers
17 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
1answer
38 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
29 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
40 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
63 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
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 ...
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
335 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
57 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
66 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
51 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
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 ...
5
votes
5answers
186 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
55 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
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
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 ...
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
693 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
44 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 ...