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
1answer
51 views

Sum of digits of permutations and combinations of a given set of digits [closed]

What is the sum of all $5$-digit numbers formed from $\{2,3,4,4,6,0\}$ without allowing repetition? What is the sum with repetition allowed?
2
votes
1answer
13 views

Partition lattice-maximal chains

Show that the number of maximal chains in the partition lattice $\prod _n$ is equal to $\dfrac{(n-1)!n!}{2^{n-1}}$. I showed that $\prod _n$ is graded lattice, so all maximal chains has the same ...
0
votes
0answers
25 views

How to calculate sum of LCMs [duplicate]

How to solve this problem? Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n). Is there any way to solve it by math?
1
vote
2answers
49 views

Find all Functions so that $f(1) = 1$ and $f(2) = 2$

Let $F$ denote the set of all functions from $A=\{1, 2, 3, 4\}$ to $B=\{1, 2, 3, ..., 10\}$. Find and simplify the number of functions $f \in F$ so that $f(1) = 1$ and $f(2) = 2.$ My attempt to ...
2
votes
2answers
147 views

2014 iberoamerican olympiad Problem 3

2014 points are placed on a circumference. On each of the segments with end points on two of the $2014$ points is written a non-negative real number. For any convex polygon with vertices on some of ...
-2
votes
1answer
29 views

Probability of Group Standings vs. Randomized Standings

This question concerns MLB baseball standings. There are 6 divisions with 5 teams each for 30 total teams. Currently one division has three of the four best records. What are the odds that this ...
1
vote
1answer
43 views

Find the number of all isosceles triangles, where all three vertices belong to the set $\{A_1,A_2, \cdots,A_{30}\}$

In the coordinate plane let $A_i=(i,1)$ for $l\leq i\leq15$, and let $A_i=(i-15,4)$ for $16\leq i \leq 30$. Find the number of all isosceles triangles, where all three vertices belong to the set ...
0
votes
2answers
89 views

The probability that each delegate sits next to at least one delegate from another country

Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Let the probability that each delegate sits next to at least one delegate ...
0
votes
2answers
45 views

Number of $k$ subsets of $S$ by choosing $i$ elements from $A$ and $j$ elements from $B$ where $S=A \cup B$

Let $A$ be a set with $m$ elements and let $B$ be a set with $n$ elements. Let $S=A \cup B$. Then the number of $k$-subsets of $S$ is clearly $C((m+n),k)$. However, if we want the number of $k$ ...
0
votes
4answers
40 views

Proving binomial coefficient formula based on Pascal's triangle

I am trying to practice proving things, and I came across one I wasn't sure about. We already know that $\binom{n}{k}$ is the sum of the two corresponding "parent" entities in Pascal's triangle, ...
2
votes
2answers
45 views

What is the number of invertible $n\times n$ matrices in $\operatorname{GL}_n(F)$?

$F$ is a finite field of order $q$. What is the size of $\operatorname{GL}_n(F)$ ? I am reading Dummit and Foote "Abstract Algebra". The following formula is given: $(q^n - 1)(q^n - q)\cdots(q^n - ...
7
votes
1answer
62 views

What is maximum a number of to form right-triangles from in n straight lines

I am interested what is maximum a number of to form right-triangles from in $n=100$ straight lines such $n=3$,then maximum number of is $1$,see fig:$\Delta ABC$ is right-triangles. $n=4$ then ...
2
votes
1answer
33 views

The equation $x_1+x_2 + \cdots + x_{251}=708$ and $y_1+y_2 + \cdots + y_{n}=708$ have the same # of solutions $n \neq251$ find n.

The equation $$x_1+x_2 + \cdots + x_{251}=708$$ Has a certain # of solutions in positive integers $$x_1,x_2, \ldots, x_{251}$$ Now the equation $$y_1+y_2 + \cdots + y_{n}=708$$ also ...
8
votes
4answers
160 views

Proof of $\sum_{d|n} {\tau}^3(d)=\left(\sum_{d|n}{\tau}(d)\right)^2$ (not standard proof)

I am trying to prove that $\sum_{d|n} {\tau}^3(d)=\left(\sum_{d|n}{\tau}(d)\right)^2$ without using the fact that $\tau$ is multiplicative and products/sums of multiplicative funcions are also ...
1
vote
1answer
29 views

Enumeration of trichotomous relations

I stuck with Logic, Computation and Set Theory by T. Forster. In Ex. 9 p. 14 it is stated that on the given set the amount of antisymmetrical relations equals to the amount of trichotomous ones. ...
-1
votes
1answer
32 views

number of ways to select a committee of at least 3 students [closed]

Suppose a class have 7 girls and 5 boys. How many ways can a committee of at least three students of among 7 girls and 5 boys can be choosen? and how many ways can a committee of at least 1 boy and ...
5
votes
1answer
139 views

The locker puzzle - predetermined strategy

The question is related to the famous locker puzzle: The director of a prison offers 100 prisoners on death row, which are numbered from 1 to 100, a last chance. In a room there is a cupboard with ...
3
votes
1answer
37 views

$\binom{n}{k}$ modulo prime power for large $n$ and small $k$

I have to compute several value of $\binom{n}{k}$ mod $p^a$ for prime $p$ over a range of $k$, where $n$ is large and fixed, and $k$ is small and dynamic. Is there a way to speed the process up? If I ...
8
votes
5answers
113 views

$32$ Goldbach Variations - Papers presenting a single gem in number theory or combinatorics from different point of view

A short time ago I found the nice paper Thirty-two Goldbach Variations written by J.M. Borwein and D.M. Bradley. It presents $32$ different proofs of the Euler sum identity \begin{align*} ...
0
votes
1answer
68 views

Probability of hitting a number $Ib$ (rare case)

Consider a set $S$ of $N^{3/2}$ numbers. Fix a collection $T$ of $N^{\frac{1}{2}}$ numbers. With every trial, we have the freedom to choose $N^{1-\epsilon}$ of them at a time without overlapping. My ...
1
vote
0answers
11 views

Prove that $\{m \in S_{\sigma} \, | \, \gamma(m) \neq 0\}$ is a face of $\sigma^V \cap M$

I am trying to solve exercise 3.2.6 pag.124 of Cox, Little, Schenck book http://www.math.colostate.edu/~renzo/teaching/Toric14/CoxLittleShenck.pdf because it is required to prove orbit-cone ...
0
votes
0answers
46 views

Generalization to: n children at a round table swap places with their neighbors

$ n > 3 $ children occupy the places $ 0,..., n-1 $ mod $ (n) $ , so that every place is occupied by exactly 1 child. The original problem states: Now the children are allowed to swap places, ...
4
votes
2answers
191 views

Is the limit $ \lim_{n\to \infty}\left(\sum^{n}_{r=0} \binom{n}{r}\big/{n^{r}(r+3)}\right)$ rational or irrational?

How can I prove that the result of the following limit is rational/irrational?$$ \lim_{n\to \infty}\left(\sum^{n}_{r=0} \frac{\binom{n}{r}}{n^{r}(r+3)}\right)$$ Would solving this limit satisfy? How ...
1
vote
4answers
73 views

Probability of visiting $4$ cities

On her vacations Veena visits four cities $(A, B, C\ \text{and}\ D)$ in a random order. What is the probability that she visits (i) $A$ before $B$? (ii) $A$ before $B$ and $B$ ...
1
vote
2answers
37 views

Clarification needed to understand elementary combinatorics problem

10 objects are randomly distributed among 3 boxes. What is the probability to have 6 objects in one of the boxes, 3 in another one and a single object in the remaining third box. My solution is ...
0
votes
1answer
34 views

Find the number of sets satisfying the conditions

Let $ N$ be the number of ordered pairs of nonempty sets $ \mathcal{A}$ and $ \mathcal{B}$ that have the following properties: • $ \mathcal{A} \cup \mathcal{B} = ...
0
votes
1answer
32 views

Find a recurrence to count paths in a directed graph

Suppose we have an unweighted directed graph with vertices numbered as $1...n$ From each vertex $i$ there are edges to $i+1$, $i+2$ and $i+7$. My task is to find a recurrence $f(i,j)$ to compute the ...
0
votes
2answers
37 views

Find the total number of selections of r things from n different things when each thing can be repeated unlimited number of times?

Find the total number of selections of r things from n different things when each thing can be repeated unlimited number of times ? I know that the formula is $$ n+r-1\choose r $$ But how do we get ...
3
votes
3answers
48 views

Number of Non - Decreasing functions?

Let A={1,2,3.....10} & B={1,2,3....20}. We have to find the number of non decreasing functions from A-->B. What I tried :No. Of non decreasing functions = (Total functions) - (Number of ...
2
votes
2answers
23 views

How to solve/approach for counting the large range of numbers in mind for this particular type of eliminating numbers?

Here is the following question. I was wondering on how to solve such questions. 100 people standing in a circle in an order 1 to 100. No 1 has a sword. He kills next person i.e. No 2 and gives sword ...
0
votes
0answers
22 views

Probability of hitting a number - $\mathsf{II}$

Suppose you have $\frac{cn}{(\log c+\log n)^a}$ distinct pairs of numbers where fixed $c,a$ satisfies $1<c,a<\infty$. You are to choose two sets of $\frac{4\sqrt{n}}{(\log n)^b}$ distinct pairs ...
1
vote
1answer
34 views

Permutations where no partial sum is divisible by 3 (contest question)

A permutation of the integers $1901,1902\dots 2000$ is a sequence in which each of those integers appears exactly once. Given such a permutation, we form the sequence of partial sums $$s_1 = ...
-1
votes
2answers
43 views

Expected number of jacks drawn given that you draw cards till you draw all 4 kings?

I don't understand how to solve this. Basically define J as our random variable such that J: {0,1,2,3,4}. To solve this, we need to know the probability of getting e.g., 0 jacks given that we draw ...
3
votes
2answers
43 views

Correctly calculating permutations and combinations without duplicate patterns

Given 16 balls each numbered 1 through 16, and 5 glass tubes numbered 1 through 5; how many ways are there to slot all 16 balls into the glass tubes, selected one at a time, with the only condition ...
3
votes
1answer
56 views

Maximize the Cyclic sum

Let $x_1,x_2,\dots ,x_6$ be nonnegative real numbers such that $x_1+x_2+x_3+x_4+x_5+x_6=1$, and $x_1x_3x_5+x_2x_4x_6 \geq \frac{1}{540}$. Let $p$ and $q$ be positive relatively prime integers such ...
1
vote
1answer
23 views

What is the name of the transform which finds the number of ways to make partitions of the given sizes?

I'm looking for the name of a transform which takes a sequence giving the number of 'prime' elements of a given size to the number of ways to make a number out of a sum of 'prime' elements, up to ...
0
votes
1answer
23 views

Counting number of times a given segment will occur in all subarrays

I have an array A having $n$ elements and for a given segment $[i,j]$ where $1\le i\le j\le n$, I want to count the number of times that segment will occur in all possible subarrays. For example, ...
0
votes
1answer
45 views

Stat: Probability to have one element of a combination identical to one element of another combination

For a business application, I currently have to provide the probability we are going to have an issue in one application. The combination is composed of N unique ...
0
votes
1answer
38 views

Is that a permutation or a combination problem?

I have to create a process where people would be asked to do 3 faces out of 7 possible. The idea is that fraudster will not be able to record a video of all possible combinations. If I have 7 ...
1
vote
1answer
37 views

On counting and generating all $k$-permutations of a multiset

Let $A$ be a finite set, and $\mu:A \to \mathbb{N}_{>0}$. Let $M$ be the multiset having $A$ as its "underlying set of elements" and $\mu$ as its "multiplicity function". (Hence $M$ is finite.) ...
2
votes
1answer
45 views

Combinatorial and probability question

I have a basic combinatorics and probability question (not homework) that I cannot seem to figure out because I have clearly misunderstood something. I apologise if this has been asked before as I did ...
1
vote
1answer
41 views

What is a mapping? Why are there $k^n$ mappings from $[n]$ to $[k]$?

Apologies for a rather basic question. My previous understanding was that mapping is a function from a set to another set. Now a combinatorics textbook states that the total number of mappings from ...
1
vote
0answers
51 views

What is the probability to pass through $1\le m\le n$ vertices of an $n$-sided polygon after $t$ seconds?

Suppose a flea is on a vertex of an $n$-sided polygon. It stays still for exactly one second, and then jumps instantly to an adiacent vertex. Let us assume it has no memory of its previous jumps and ...
10
votes
1answer
175 views

Prove $\sum\limits^m_{k=0} \frac{2n-k\choose k}{2n-k\choose n}\frac{2n-4k+1}{2n-2k+1}2^{n-2k}=\frac{n\choose m}{2n-2m\choose n-m}2^{n-2m}$ for-

Let $n$ be a positve integer. Prove that$$\sum\limits^m_{k=0} \frac{2n-k\choose k}{2n-k\choose n}\frac{2n-4k+1}{2n-2k+1}2^{n-2k}=\frac{n\choose m}{2n-2m\choose n-m}2^{n-2m}$$ for each non-negative ...
0
votes
2answers
34 views

Ways to order all possible videos, between $90$ minutes and $3$ hours long

Let's say you could generate all possible videos, assuming that each pixel can display $16,777,216$ possible colors, a monitor size of $1920\times1080$ pixels, a frame rate of $24$ frames/second, and ...
1
vote
2answers
66 views

Determine the smallest positive integer $M$

On some planet, there are $2^{N}$ countries $(N \geq 4)$. Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1\times 1$ each field being either yellow or ...
2
votes
2answers
66 views

Finding the number of permutations of $\{1,\cdots,6\}$ which do not contain 3 consecutive integers.

I tried to find the number of permutations of $\{1,\cdots,6\}$ which do not contain the strings 123, 234, 345, or 456 using the following method, and I would like to find out why this method ...
0
votes
1answer
20 views

Number of groups of five balls such that the sum of all the balls is even

An urn contains 10 white balls, numbered 1-10, and ten black balls, numbered 1-10. A sample of five balls is chosen. How many samples have the property that the sum of all of the balls is ...
0
votes
0answers
30 views

Natural Number Decomposition [duplicate]

Given an arbitrary natural number $n$ , in how many ways can we write it as the sum of consecutive natural numbers? Is there any closed form answer in terms of $n$? Example: if $n=270$ then it can be ...
4
votes
0answers
22 views

Echalon decomposition in binary shuffle (Hopf) algebras

Consider a binary shuffle algebra $\mathcal{W}$ of two letters $a, b$. As usual the concatination of two words $u = u_1 \dots u_m$, $v = v_1 \dots v_n$ is defined as: $$u \bullet v := u_1 \dots u_m ...