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
2answers
81 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
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 ...
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
42 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
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.
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? ...
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
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
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: ...
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
362 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
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 ...
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
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 ...
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
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: ...
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
0answers
100 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
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 ...
1
vote
0answers
46 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
56 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
66 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
60 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
22 views

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

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 ...
2
votes
0answers
19 views

Alternating sum of subfactorials: Is there a closed form for this: $\displaystyle \sum_{i=0}^{m-2}(-1)^i\left[\frac{(m-i)!}{e}\right]$?

The problem was to find the number of ways in which $n$ objects in circular arrangement can be placed so that each one has a new object in front of it (assuming a particular, initial arrangement). ...
2
votes
1answer
24 views

What is the maximum number of subsets can be formed from n data subsets?

What is the maximum number of subsets can be formed from $n$ data subsets of a fixed set by the operation of intersection, union, and complement? I think the answer is $2^{2^n}$. Because $2^n$ ...
0
votes
0answers
11 views

Selecting minimal no. of unit kth dimensional cubes in kth dimensional cube (nxn…xn) so that each remaining is on axis of selected cubes

This comes from a old Russia MO problem, which asks for ($k=3$), among the set of $k$-tuples $(a_1,...,a_k)$, $1\leq a_i\leq n$, what is the minimal number of tuples chosen such that for any remaining ...
1
vote
2answers
61 views

Exponential generating function for the number of binary strings of length $n$

I know that the generating function of the sequence counting the number of binary strings of length $n$ is $e^{2x}$. But my book doesn't explain why this is the case. Could you give me a little more ...
3
votes
1answer
30 views

Integer Partitions and distinguishable permutations

I'm not a mathematician but I'm faced with a problem where I can't find an answer, also because I do not know what I shall ask for: I have to deal with partitions of an integer k, only small values, ...
0
votes
1answer
48 views

Tiling problem : Number of ways a floor can be tiled

Find number of ways a floor n meter length and 11 meter wide can be floored with tiles of 2 cm length and 1 cm wide wide tiles without breaking the tiles (assume n is even) Could you please help in ...
-2
votes
1answer
27 views
-1
votes
0answers
30 views

Number of simple, connected graphs with K edges and N distinctly labelled vertices [closed]

Ok. I'm aware of this question and answer, but it's over my head. I've written a recursive function that I thought would do the job, but it doesn't, apparently. Could someone explain to me why it's ...
4
votes
2answers
84 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 ...
14
votes
3answers
414 views
+200

Finding real money on a strange weighing device

You have 50 coins which each weigh either 20 grams or 10 grams. Each is labelled from 0 to 49 so you can tell the coins apart. You have one weighing device as well. At the first turn you can put as ...
2
votes
0answers
8 views

Special class of Brenke Polynomials

I was wondering if there are any particular papers dealing with a particular class of Brenke Polynomials, defined as $$A(t)B(xt)=\sum_{n\ge 0}P_n(x)t^n$$ where $A=B$ or, where $A(t)=C(B(t),t)$ for a ...
4
votes
1answer
150 views

Why aren't there 21 players in this tournament?

In a tournament each player played exactly one game against each of the other players. In each game the winner was awarded 1 point, the loser got 0 points, and each of the two players earned ...
3
votes
2answers
77 views

Among $k$ consecutive numbers one has sum of digits divisible by $11$

Find the least positive integer $k$ with the property that given any $k$ consecutive positive integers, there is at least one whose sum of digits is divisible by $11$. I can show for $k\leq 57$. ...
3
votes
1answer
62 views

Another Evaluation of the Ramsey number $\mathcal{R}(3,3,3)$

The problem Show that $\mathcal{R}(3,3,3)=17$ The story behind the problem and some notation It was first proven by Greenwood and Gleason in 1955 in their paper Combinatorial relations and ...