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)

3
votes
3answers
38 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
37 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
54 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
38 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
9 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 ...
4
votes
5answers
158 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
28 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
38 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
91 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
2answers
40 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
38 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 ...
8
votes
3answers
989 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
673 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
39 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
52 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
48 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
41 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
40 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
9 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 ...
6
votes
1answer
112 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
18 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
23 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
10 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
52 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
27 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
46 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 ...
-1
votes
1answer
22 views
-1
votes
0answers
24 views

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

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 ...
3
votes
2answers
52 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 ...
5
votes
0answers
96 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
6 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
76 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
56 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 ...
0
votes
2answers
25 views

Student card handing Inclusion–exclusion principle

I got the following question and would very much appreciate any help with understanding it solution. "5 Student cards are handed to 5 students so that each student gets 1 student card, what is the ...
1
vote
1answer
12 views

How many Schedules possible with given set of Transactions? Given that total ordering of operations in a transactions is there.

Given that : There are $m$ transactions = $\{T_1, T_2, \dots, T_m\}$ and for each transaction $T_i$ there are $n_i$ operations in it. It is required that the relative ordering of operations within ...
1
vote
3answers
99 views

Binomial Sum: Values

I need this as lemma. Regard the sums: $$S_k:=\sum_{n=0}^N\binom{N}{n}(-1)^{N-n}n^k\quad(k\in\mathbb{N}_0)$$ Then it holds: $$S_k\stackrel{k<N}{=}0\quad S_k\stackrel{k=N}{=}N!$$ How can I check ...
-1
votes
1answer
29 views

Functions from $\{w,x,y,z\}$ to $\{a,b,c\}$

I'm having some problems understanding how functions and Big-O notation works... I've checked a couple of other threads here but still unsure Let's say I have $A = \{w, x, y, z\}$ and $B = \{a, b, ...
0
votes
1answer
37 views

How do I prove the formula for multichoose?

In combinatorics, there is a formula "$n$ multichoose $k$", which is the way of making a multiset having $k$ elements choosing out of $n$ options. "$n$ multichoose $k$" is the same as "$(n+k-1)$ ...
-2
votes
0answers
54 views

How many increasing functions $f:\{1,\ldots,n\} \to \{1,2,\ldots,n\}$ are there such that $f(i) \ge i , \forall i=1(1)n$ , where $n \in \mathbb N$?

Let $n\in \mathbb N , n \ge 3$ . How many increasing functions $f:\{1,,\ldots,n\} \to \{1,2,\ldots,n\}$ (i.e. $f(i) \ge f(j) , \forall i=1(1)n$ ) are there such that $f(i) \ge i , \forall i=1(1)n$ ?
2
votes
1answer
24 views

combinatorics problem: find all possible ordered permutations in a tuple

I have a tuple that looks like this: $(1,2,3,4)$ I want to generate all possible nested tuples that can be made from the original tuple which maintain the original order of the array. For the ...
3
votes
2answers
80 views

Probability with changing number of marbles

Given a bag containing 20 marbles of 5 different colors in this configuration: 8x Blue 6x Red 3x Green 2x White 1x Black How would you determine the probability of picking a marble of a specific ...
1
vote
2answers
30 views

Simple counting question- numbers in sequences.

I'm taking a counting/probability course. Got this one question that I originally thought was simple, but my solution turned out to be wrong. "How many $6$-digit sequences have a digit that appears ...
0
votes
0answers
14 views

Enumeration of skew Ferrers diagrams revisited.

In M. P. Delest, J. M. Fedou, "Enumeration of skew Ferrers diagrams", Discrete Mathematics. vol.112, no.1-3, pp.65-79, (1993) http://dx.doi.org/10.1016/0012-365X(93)90224-H a generating function is ...
2
votes
2answers
52 views

Probability Modem is Defective

A store has 80 modems in its inventory, 30 coming from Source A and the remainder from Source B. Of the modems from Source A, 20% are defective. Of the modems from Source B, 8% are defective. ...
0
votes
1answer
23 views

number of binary strings with equal number of 0's and 1's

I am trying to count the number $S$ of binary strings with equal number of 0's and 1's. Since this boils down to picking $n$ out of $2n$ places where 0's can fall into, my ansatz is $$ S = ...