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
10 views

How to simplify this 2F1 function?

I have a hypergeometric function $_2F_1(x, y; 1; 2)$ where $x$ and $y$ are negative integers. Is there another way to state this, perhaps as a combinatoric?
2
votes
2answers
41 views

Count all possible combinations

I want to check how many combinations of $2$ numbers I can generate from $20$ different numbers when the same number can be picked twice. I calculated it like this and answer is $20 \cdot 20 =400$. Is ...
1
vote
0answers
40 views

Find the number of “p-safe numbers”

For a positive integer $p$, define the positive integer $n$ to be $p$-safe if $n$ differs in absolute value by more than $2$ from all multiples of $p$. For example, the set of $10$-safe numbers is ...
1
vote
0answers
14 views

Permutation of numbers from multiple sets [May contain duplicate numbers among other sets], resulting in Non-Duplicate Set

We have 3 Data Sets. From each set we will be selecting few numbers. 3 from Set 1, 2 from Set 2, 3 from Set 3. Totally, we will get 8 Numbers from 3 Sets. The resulting sets shouldn't contain any ...
1
vote
0answers
28 views

Number of triangles possible in android lock patterns?

I recently starting using the patternlock on my android phone and i play around with it a lot, just drawing lines until im locked out for 30 secs. I thought i'd make it into a pointless game of ...
0
votes
3answers
36 views

Why is it true that $(a_1, a_2, \dots, a_r) = (a_1, a_r)(a_1, a_{r-1})\dots(a_1, a_3)(a_1, a_2)$?

In the theory of permutation, a $r$-cycle $(a_1,a_2,...,a_r)$ is defined in the following way: Start from $a_i$, a permutation function $f$ sends $a_i$ to $a_{i+1}$. When $i=r, a_i \text{ will be ...
0
votes
0answers
26 views

Let $T$ be the set of all positive integer divisors of $2004^{100}$. Size of largest subset $S$ of $T$ such that no element in $S$ divides another?

I am getting an answer slightly over $100^2$. Is this right (working below), or is there a better way of selecting elements of S? The following question appeared on the 2004 Canada National Olympiad: ...
3
votes
0answers
43 views

Help with binomial identity [on hold]

In my work, I was led to the following identity. I would be grateful if someone could provide an easy proof. $$ \sum_{j = 0}^d (-1)^{d-j} \cdot \binom{d}{k} \cdot \binom{n-j-1}{n-d-1} \cdot ...
0
votes
1answer
41 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 ...
6
votes
5answers
119 views

Show that $(1+p/n)^n$ is a Cauchy sequence for arbitrary $p$

It is a generalization of this question. I am looking for a similar derivation as in here. Can we prove that $(1+p/n)^n$ is a Cauchy sequence for any $p \in [a, b]$ by showing that $$ \Bigg| \left( ...
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
1answer
40 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 < ...
1
vote
2answers
33 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 ...
1
vote
2answers
60 views

How to derive the Taylor expansion form of a polynomial expression?

I want to change this polynomial into the form $\sum_{k=0}^m a_k x^k$ $$q_m(x)=\sum_{k=0}^m(-1)^k\binom{2m+1}{2k+1}x^k(1-x)^{m-k}$$ I see no way to do this as I fear one might need intricate binomial ...
-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 ...
0
votes
0answers
38 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. ...
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, ...
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
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 ...
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
1answer
26 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
vote
1answer
26 views

Functions that are “balanced” on the support of a permutation

Let $F = GF(2^n)$. Let $P(x), Q(x) \in F[x]$ be such that $P(x)$ is a permutation, while $Q(x)$ is not a permutation. For $\lambda \in F^*$ define the function $g_\lambda(x) = Tr(\lambda Q(x))$. Let ...
0
votes
1answer
28 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
0answers
30 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
32 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 ...
10
votes
1answer
85 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
52 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 ...
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
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. ...
-1
votes
5answers
52 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 ...
3
votes
0answers
19 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
vote
3answers
66 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 ...
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 ...
1
vote
2answers
26 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 ...
-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 ...
0
votes
0answers
15 views

Why $|N(P_{i, j})| \cong [0, 1]^n$ as stated in page 21 of HTT?

maybe this is an idiot question, however I could not solve this after thinking for a while. I added the tag about higher categories simply because of the nature of the question, however this is just a ...
-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$ ...
-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 ...
1
vote
1answer
41 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 ...
0
votes
1answer
25 views

Probability the range is disjoint

Let $A=\{1,2,3,4\}$, and $f$ and $g$ be randomly chosen (not necessarily distinct) functions from $A$ to $A$. The probability that the range of $f$ and the range of $g$ are disjoint is ...
2
votes
1answer
27 views

Given $n>0$, let $S$ be a set whose elements are positive integers $\leq 2n$ such that:

S is a set with the property that for all a,b∈S with $a<b$, a doesn't divide b. What is the maximum number of integers that $S$ can contain ? I thought it was the number of prime numbers smaller ...
1
vote
0answers
24 views

Count the number of strings containing $ac$ or $ca$ for a fixed length over ternary alphabet $A = \{a,b,c\}$ using rational series

This question is a continuation the one asked here, and which already received good answers. Here I am asking for a solution using rational series of formal languages as suggested by the user J. E. ...
2
votes
1answer
50 views

NP combination puzzle (Klotski)

I've written a C++ program to solve sliding puzzles games such as UnblockMe and Car Parking. I'm quite happy about it, since it solves various schemes in less than a second. Recently I fed the game ...
-2
votes
0answers
32 views

combinatorial nullstellensatz [on hold]

I was wondering if there is any trick for selecting the polynomial in Combinatorial Nullstellensatz method by Alon. This could be a powerful tool provided we choose right polynomial.
3
votes
3answers
97 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 ...
4
votes
1answer
41 views

Arrangement counting problem

This is my son's exercise: How many ways that 6 rabbits can be put in 10 cages. I count in 2 different ways: The first rabbit can be in any of 10 cages. Same for the second and so on. So in total, ...
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$ ...
0
votes
0answers
18 views

Calculating Variance of payment in patterns of balls.

We have five different bags labeled from 1 to 5 and several colored balls. There are 9 different possible colors. We know how many balls of each color there are in each bag. We have a grid of 5x3 ...
3
votes
2answers
90 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 } ...
0
votes
1answer
21 views

Isomorphic relation between Catalan representations

There is an unanswered question at MathOverflow: Intersecting Family of Triangulations This article at Wikipedia explains the concept of non-intersecting partitions of a polygon: Catalan number So ...