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
0answers
87 views

Permutation equivalence classes with kendall-tau distance

Consider a set $A=\{a_1,...,a_m\}\subset \{1,...,n\}$ for which $a_i<a_{i+1}$ for all $i = 1,\ldots,m-1$. Take any two distinct permutations $\sigma, \tau$ of $\{1,...,n\}$ such that $ ...
0
votes
1answer
43 views

Probability problem 1

I just wanted to double check to see if I'm doing this problem correctly. 3 kids (Alice, Bob, and Carol) have to divide 15 different toys among themselves in a way that each kid gets 5 toys. How many ...
5
votes
3answers
142 views

Prove ten objects can be divided into two groups that balances each other when placed on the two pans of balance. [closed]

There are 10 objects with total weight 20, each of the weight being a positive integer. Given that none of the weights exceed 10, prove ten objects can be divided into two groups that balances each ...
10
votes
1answer
478 views

A polynomial sequence

I have a sequence of polynomials $Q_k(x, y)$, $k\geq 1$ defined recursively as follows: $Q_1=x$. There is a sequence of polynomials $p_j(y)$ of degree $j$ such that $Q_{2m}$ is of the form ...
1
vote
1answer
51 views

Block of integers: Divisibility

Let a < b be natural numbers. Prove that every block of b consecutive natural numbers contains two distinct elements whose product is divisible by ab. (I've proved this) Suppose now a < b < ...
0
votes
0answers
34 views

How many distinct non-negative integer solutions to $x+y+z=S$ are there, without variable naming?

How many distinct non-negative integer solutions to $x+y+z=S$ are there, without variable naming? Any two solutions $(x_0,y_0,z_0)$ and $(x_1,y_1,z_1)$ are considered equivalent if $x_0,y_0,z_0$ can ...
1
vote
2answers
34 views

How to show that this interesting difference of products is $O \left( \frac{1}{n^2} \right) $

Let $k \leq n$. Consider the following difference of products: $$ \prod_{i=1}^{k-1} \left( 1 - \frac{i}{n+1} \right) - \prod_{i=1}^{k-1} \left( 1 - \frac{i}{n} \right)$$ For $n=1,2,3$, this is ...
-2
votes
0answers
17 views

combination problem in coding [on hold]

consider we have K input symbol of length 1 bit and also from this K input symbols we can produce symbols which are XOR of 2 input symbols, chosen uniformly from these K input symbols which gives us ...
3
votes
3answers
100 views

High computation in probability

Six men and some number of women stand in a line in random order. Let $p$ be the probability that a group of at least four men stand together in the line, given that every man stands next to at ...
1
vote
1answer
42 views

How to calculate combinations by drawing out the spaces?

I'm learning about probability on khanacademy. They teach a certain method (they draw out the spaces) to calculate combinations. Two Examples: 1. Take the question "What is the probability to get ...
1
vote
1answer
51 views

Optimize for happiness and equality

I'm trying to solve an optimization problem: There are $N$ students who can choose to enroll into $C$ courses, each of them has a set of 3 preferences $P = \{c_1, c_2, c_3\}$ about the courses they ...
0
votes
0answers
42 views

Can you verify the combinatoric recurrence?

There are $2^{10} = 1024$ possible 10-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than 3 adjacent letters that are identical. ...
16
votes
1answer
342 views

On the inequality $\frac{1+p(1)+p(2) + \dots + p(n-1)}{p(n)} \leq \sqrt {2n}.$

For all positive integers $n$, $p(n)$ is the number of partitions of $n$ as the sum of positive integers (the partition numbers); e.g. $p(4)=5$ since $4=1+1+1+1=1+1+2=1+3=2+2=4.$ Prove ...
2
votes
2answers
79 views

Find a recursion (combinatorial)

Consider sequences that consist entirely of $ A$'s and $ B$'s and that have the property that every run of consecutive $ A$'s has even length, and every run of consecutive $ B$'s has odd length. ...
0
votes
1answer
20 views

Closed solution to double recursion

I have a problem, where a subproblem is counting how many ways there are to interleave two words from disjoint alphabets while keeping the relative order of the letters within each word. For example, ...
2
votes
2answers
247 views

In how many ways can eight people, denoted $A,B,C,D,E,F,G,H$ be seated about a square table that seats two people on each side?

In how many ways can eight people, denoted $A,B,C,D,E,F,G,H$ be seated about a square table that seats two people on each side? My approach: Since each side of the table seats two people, there are ...
1
vote
1answer
19 views

Amount of match combinations of creating a 5 v 5 team from a pool

This question is inspired by the popular games: Dota 2, Heroes of the Storm and League of Legends; where players have to create two teams of 5 from a pool of "Heroes" in each match. How many ...
0
votes
1answer
28 views

Simplify the formula for the number of distributions leaving none of the $n$ cells empty

I'd like to help with the following problem: $$ \binom{x}{r-1} + \binom{x}{r} = \binom{x+1}{r} \tag{8.6}\label{8.6} $$ 7. Let $A(r, n)$ be the number of distributions leaving none of the n cells ...
0
votes
0answers
16 views

Which partitions $P$ of $n$ give the row and column sums of some $|P| \times |P|$ $(0,1)$-matrix? [duplicate]

Question: Which partitions $P$ of $n$ give the row and column sums of some $|P| \times |P|$ $(0,1)$-matrix? Someone comes along and gives us the partition $P=\{2,2,3,3,4\}$ of $14$. How can we ...
2
votes
4answers
97 views

When will Andrea arrive before Bert?

The question was as follows- on any given day, Andrea is equally likely to clock in at work any time from 8:50am to 9:06am. Similarly, Bert is equally likely to to clock in at work at any time ...
0
votes
1answer
29 views

Shortest Path Length as mathematical function/expression

I have a graph (unweighted and undirected) of n vertices. My objective is to express the following constraints as inequalities. The degree of any node should be at least 3. The shortest path length ...
-1
votes
5answers
56 views

Picking (and replacing) among five balls in an urn

An urn contains 5 balls numbered from 1 to 5. A ball is chosen at random and its number is noted the ball is then returned to the urn. this is done a total of 5 times. What is the probability that ...
1
vote
3answers
54 views

Right answer, wrong explanation, probability of grids?

Two unit squares are selected at random without replacement from an $n\times n$ grid of unit squares. Find the least positive integer $n$ such that the probability that the two selected squares are ...
0
votes
0answers
34 views

A residue question in integers

Given $N\in\Bbb N$, is it possible to find $9$ positive integers $A_j,N_i$ with $j\in\{1,2,3\}$, $i\in\{1,2,3,4,5,6\}$ such that following holds? $(1)$ $N\log N < A_j < cN\log N$ at every $j$ ...
0
votes
1answer
29 views

combination of 5 digit numbers

looking at 5-digit number when digits can be $1,2,...,9$ and with repetition, $|\Omega|=9^5$ the event of $5$ distinct digits is $9\times 8\times 7\times 6\times 5$? and the event 2 digits the same ...
0
votes
1answer
33 views

Prove that $\sum_{t \vert n} d^3(t) = (\sum_{t \vert n}d(t))^2$ for all $n \in \mathbb{N}$ [duplicate]

here $d(n)$ counts the number of positive divisors of $n$. I've tried 2 things: Using Bell series. But then again it just showed me that the bell series of the square of a function is not the ...
2
votes
2answers
58 views

Generate all De Bruijn sequences

There are several methods to generate a De Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length ...
4
votes
1answer
70 views

Proving a Binomial Identity

Problem $\boldsymbol{25}$ [$\boldsymbol{5}$ Points]: Show that $$ \sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}=2^n $$ Hint: Denote the left hand side by $f(n)$ and prove that $f(n+1)=2f(n)$. Original Image ...
10
votes
1answer
86 views

Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem: Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$ Where the Problem Comes From: If we ...
1
vote
3answers
116 views

Solving the recurrence relation $T(n) = 2T(n^\frac{1}{2}) + c$

I've been trying to do this for hours. I just don't know how. I'm familiar with recurrence relations in the form of $T(\frac{n}{2})$, but what do you need to do to solve $T(n^\frac{1}{2})$? I've ...
2
votes
0answers
24 views

Mathematics of Magic Squares

I have seen many popular accounts of simple magic squares but I would like to find a proper mathematical background to understanding magic squares. What background knowledge do I need. I am a retired ...
2
votes
0answers
249 views

permutation and combination advanced

I have n sets having values less than 100. I need to find how many arrangements could be made if I pick one element from each set such that in the given arrangement there are no duplicates? NOTE: A ...
3
votes
2answers
93 views

a vector inequality and combinatorics related question

This question is a similar restatement of this question which has been recently closed. Let $$A=\{\ (x,y,z)\in\mathbb{N}^3\ |\ 0\leq x,y,z\leq7\}$$ and $$B\subset A \text{ with } ...
1
vote
3answers
67 views

Probability that two numbers differ by one bit

Assuming that t is the bit length of the numbers and that we can pick 2 random numbers (the same number cannot be chosen twice), which is the probability that the two numbers will differ by exactly ...
3
votes
0answers
20 views

On a metric over m-subsets of [n]

Given an integer $n$, denote the set of integers $\{1,2,\dots,n\}$ as $[n]$. For two $m$-subsets $A$ and $B$ of $[n]$, list their elements in the increasing order as $a_1 < a_2 < \dots < a_m$ ...
-1
votes
2answers
2k views

How many three digits even numbers can we form such that if one of digit is $5$ the following digit must be $ 7$?

How many three digits even numbers can we form such that if one of digit is $5$ the following digit must be $ 7$? I need some ideas on how to proceed on this problem.
17
votes
0answers
247 views

Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
2
votes
1answer
45 views

Given $N$, is there a formula for $card( \{(m,n)\, s.t.\, m\cdot n \leq N \} )$?

The formula is also equivalent to : $$ \sum_{m=1}^N \left \lfloor \frac{N}{m} \right \rfloor $$ An interpretation would be to count the discrete rectangles with total area inferior to N. But aside ...
-2
votes
0answers
43 views

Summation of prime multiples less than n [on hold]

How can I sum the following $$ \sum (2^x\cdot3^y\cdot5^z\cdot7^w\cdot\prod_1^m(p_i^{a_i})) $$ with $$2^x\cdot3^y\cdot5^z\cdot7^w\cdot\prod_1^m(p_i^{a_i}) \le n$$ where $p_i \ge 11$ are list of fixed ...
1
vote
2answers
28 views

How many arrangements of the integers 1,2, .., n such that from (ALAN TUCKER Applied Combinatorics)

I was solving a question from alan tucker's applied combinatorial book and got stuck at this question: How many arrangements of the integers 1,2, .., n are there such that each integer differ by ...
0
votes
1answer
53 views

How many ways can this quadrilateral be formed if no two of its vertices are next to each other?

A quadrilateral is formed by joining four vertices of a convex decagon. In how many ways can such a quadrilateral be formed if no two of its vertices are next to each other (that is, no two vertices ...
2
votes
1answer
133 views

proof of a combinatorial identity

How to prove the following using inclusion exclusion $$ \sum _{k=m} ^{n} (-1)^{k-m} {n \choose k} = {n-1 \choose m-1}$$
2
votes
1answer
53 views

Easiest way to find the 'area of a Venn diagram,' given certain information.

We have a bunch of intersecting regions: $$X_1,\dots, X_n,$$ all with non-negative volume, and we know $V(X_i)$ and $V\left((\cup_{a\in A}X_a)\cap (\cup_{b\in B}X_b)\right)$ for any disjoint ...
1
vote
1answer
51 views

Inviting 4 friends out of 8 for a week such that each friend visits at least once

Dave is inviting 4 friends out of 8 for a week how many possibilities there are such that each friend visit at least once. Let's number the friends for brevity, 1 to 8. This is like asking how ...
1
vote
1answer
209 views

Conflicting answers when using Complements Principle and the Inclusion-Exclusion Principle

The question I'm looking at is: Andy, Bill, Carl and Dave are 4 students on a team of 10. 5 must be chosen for a tournament, how many teams can be picked if Andy or Bill or Carl or Dave must be on ...
2
votes
2answers
235 views

Number of 8 character passwords including numbers and letters without repetition

A password must be created with 8 characters. It can use number or letters, but they cannot be repeated (and letters are not case sensitive so we have only 36 characters). How many passwords are ...
19
votes
17answers
15k views

Applications of the Fibonacci sequence

The Fibonacci sequence is very well known, and is often explained with a story about how many rabbits there are after $n$ generations if they each produce a new pair every generation. Is there any ...
-2
votes
0answers
20 views

mapping of integer to unit circle through function $f(k)=k\theta \pmod{2\pi}$ [on hold]

Let $N$ be a positive integer and $\theta$ an angle in $(0,2\pi)$. Consider the map $f\colon\{0,1,\ldots,N\}\to\text{unit circle}$, defined by $f(k)=k\theta \pmod{2\pi}$. Show that the image of $f$ ...
6
votes
2answers
90 views

Describe and count the set of sequences containing $20$ or $02$

Let $X = \{ 0,1,2 \}$ be a ternary alphabet and denote by $X^*$ the set of finite sequences (i.e. strings) with three symbols. For $w \in X^*$ with $n$ the length of $w$ and $w = w_1 w_2 \cdots w_n$ ...
-2
votes
1answer
22 views

Probability of a user references in a network [on hold]

I am trying to figure out no of possible referrals of a user in a network. Where the size of a network is not fixed but we can set an assumption of 1000 persons. Edit: A user knows few users in a ...