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)

1
vote
0answers
9 views

If $G$ is shellable, then $G \backslash \{x_i\}$ is shellable?

A simplicial complex $\triangle$ is shellable on the vertex set $\{x_1,\ldots,x_n\}$, if the facets of $\triangle$ can be ordered, say $F_ 1 , . . . , F _s$ , such that for all $1 \leq ...
1
vote
1answer
27 views

Reference for a combinatorial theorem

Is there a reference for this theorem https://en.wikipedia.org/wiki/Schur%27s_theorem#Combinatorics? I am unable to locate a reference. Google search does not spot this particular theorem well.
2
votes
3answers
334 views

Hot Dog vendor question

A hot dog stand has 12 different toppings available. How many different kinds of hot dogs can be made, assuming the order of the toppings does not make a difference. I believe the correct answer is ...
1
vote
1answer
24 views

A question on arithmetic progressions

Is it true that for every $n \in \mathbb N$ , $\exists N \in \mathbb N$ such that for any subset $A \subseteq \{1,2,...,N\}$ , either $A$ or $\{1,2,..,N\} \setminus A$ contains an arithmetic ...
3
votes
3answers
33 views

Combinatorics Question - Permutations and Supersets

I had a question that seems pretty straightforward, but I can't seem to wrap my mind around it. Let's say I have a bunch of elements in a set. {A, B, C, D, E}. How many permutations are there of ...
1
vote
1answer
20 views

How many option are there to divide n people into any number of groups of any size?

I found only something like this: $$f(0) = 1$$ $$ f(n) = \sum_{i=0}^{n-1} \binom{n-1}{i} * f(i) $$ Now I wonder if there are other (faster) ways to calculate this.
2
votes
2answers
47 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
55 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
36 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
29 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
27 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
62 views

Help with binomial identity

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
42 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
131 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
43 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
65 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
39 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
28 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
27 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
33 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
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 ...
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
55 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
27 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
16 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
33 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
99 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 ...