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)

5
votes
1answer
142 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
39 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
115 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
70 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
199 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
74 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
34 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
39 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
24 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
35 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
44 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
24 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
41 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
52 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
180 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
1answer
29 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 ...
0
votes
0answers
41 views

Number of arrangements of A,B,C,D,E,F with conditions.

How many arrangements are there of A,B,C,D,E,F if B follows immediately after A or D immediately after C or F immediately after E ? Here is my solution: let $A1$ be the set where B is immediately ...
3
votes
4answers
53 views

Counting integral solutions

Suppose $a + b + c = 15$ Using stars and bars method, number of non-negative integral solutions for the above equation can be found out as $15+3-1\choose15$ $ =$ $17\choose15$ How to extend this ...
-2
votes
0answers
29 views

A set of cards from which I can make a number [duplicate]

I am trying to solve this Problem I have tried every combination but could not find any patter in it. What is the pattern ...
0
votes
1answer
50 views

Counting non-overlapping substrings of size 2 and 3 in a string

Given a string S of length n that contains exactly $\lceil \frac{n}{4} \rceil $ b's and $\lfloor \frac{3n}{4} \rfloor$ a's: Part 1: How many NON-overlapping occurrences of aa must occur in S? For ...
4
votes
2answers
59 views

AP in Chessboard

The natural numbers $1,2,...,n^2$ are arranged in a $nXn$ chessboard. In how many ways can we arrange the numbers such that the numbers on every row and every column are in arithmetic progression? I ...
0
votes
0answers
42 views

Minimum movements to arrange fruits in boxes

I have $3$ boxes - $B_1, B_2, B_3$. Each box initially contains a mixture of $3$ different kind of fruits say - Apple, Orange, Mango. Our goal is to arrange the fruits in the boxes in such a manner ...
5
votes
5answers
1k views

How many numbers between 4,000 and 7,000 can be chosen using the digits [0, 8]?

I have a homework problem in combinatorics, and I am struggling to solve it because I didn't understand our lesson well. Can you please help me to solve this problem? How many numbers between ...
0
votes
2answers
64 views

Rational number that contains the sequence “$0123456789$”

Let $n$ be a rational number that contains the sequence "$0123456789$" in its decimal representation. Prove or disprove that there are $p,q \in \mathbb{N}$ such that $n = \frac{p}{q}$ and $q$ is a ...
3
votes
1answer
47 views

Finding the n-th arrangement of items with repetitions [duplicate]

I'm new to Stackexchange and maybe I do not have the correct mathematical terms for the question I'm about to ask. I'm given a multiset of given size $N$ which consists of zeros and ones. Example: ...
0
votes
0answers
27 views

To find the best success list among players?

In a Sport league, There are teams or players and their match results are known with each other. How can we do a fair list for players that shows their success in? I would like to give an example to ...
3
votes
0answers
15 views

Existence of fair parallel queues

I just spent a few days at a major theme park. The queue for one particular ride (involving pirates) bifurcated upon entry; the two sides wound independently through a maze and emerged next to each ...
7
votes
0answers
105 views

Counting the size of the largest sets of independent strings

This question derives from a PPCG coding challenge I posed previously. For a given positive integer $n$, consider all binary strings of length $2n-1$. For a given string $S$, let $L$ be an array of ...
1
vote
1answer
27 views

How is Schroeder's generalized parentheses sequence (A001003) actually used to generated parentheses expressions?

The sequence A001003 counts the "number of ways to insert parentheses in a string of n+1 symbols". What I'm trying to figure out is how to generate the expressions with parentheses (in code). For ...
0
votes
1answer
49 views

variation to tower of hanoi problem

Here is the question: There are $m$ different sizes of disks and exactly $n_k$ disks of size $k$. Determine $A(n_l,. . . , n_m)$, the minimum number of moves needed to transfer a tower when ...
7
votes
2answers
221 views

Sum of 1.5-powers of natural numbers

I recently have met the following approximate equation: $$\sum_{k=1}^n k^{1.5}\approx\frac{n^{2.5}+(n+1)^{2.5}}{5}.$$ It's a rather accurate approximation (for $n=40$ the absolute error is $\approx ...
1
vote
2answers
22 views

Word problem on collecting specified liters with two pails

I am thinking through an interesting puzzle. John is near a lake and has two pails, one holding 4 liters, the other holding 7 liters. The pails have no markings. All John knows is if a pail is empty ...