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
12 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
16 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
20 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
0answers
23 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
2answers
17 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
26 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
21 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
45 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
31 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.
2
votes
3answers
72 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 ...
3
votes
1answer
37 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
85 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
16 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 ...
2
votes
2answers
67 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
19 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 ...
0
votes
2answers
33 views

A question on probability of choosing coins

Six identical-looking coins are in a box, of which five are unbiased, while the sixth comes up heads with probability $3 \over 4$ and tails with probability $1 \over 4$. Three coins are chosen from ...
2
votes
2answers
81 views

Algebraic proof that $\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$

I'm looking for an algebraic proof of this identity for $n, k \in \mathbb{N}$: $$\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$$ So far, I've turned the left hand side of the equality into ...
1
vote
2answers
29 views

Find the total number of matchings in a complete graph with even vertices

I am trying to solve questions from a Walk through combinatorics.., I came across this proof which I was unable prove: Determine the number of perfect matchings for a graph with 2n vertices. I don't ...
3
votes
1answer
25 views

Median of waiting time for $k$-th ace from bridge cards

I can't figure out how to get median of a waiting time from the exercise 36 from W. Feller's book An Introduction to Probability Theory and Its Applications Vol.1 (bold in the quote): ...
3
votes
1answer
41 views

Choose 8 distinct integers from $\{1, 2,\dots,16,17\}$. Show that the eight contain at least three pairs with a common difference for _any_ choice.

This problem is from the 1999 Canada National Olympiad. I am stuck trying to prove the first part using the pigeonhole principle. Is there a refinement that will allow it to be used more sharply, or ...
3
votes
2answers
39 views

number of triangles determined by a rectangular grid

Suppose we are given an $m\times n$ rectangular grid of lattice points, such as $S=\{(k,l): 0\le k\le n-1,\; 0\le l\le m-1, \;k,l\in\mathbb{Z}\}$, and we want to determine the number of ...
0
votes
1answer
29 views

Lottery probability with payout system

Assume we have a lottery which has following payouts 1,2,5,6,9,10,16. The organizer expects 4% profit from the lottery. I wrote ...
2
votes
1answer
33 views

Number of distinct permutations given a character set.

How many distinct three-letter sequences with at least one $T$ can be formed by using three of the six letters of $TARGET$? One such sequence is $T-R-T$. [MathCounts 2005 National Countdown] The ...
2
votes
2answers
87 views

Sum of remainders of $2^n$

Hints Only Let $R$ be the set of all possible remainders when a number of the form $2^n$, $n$ a nonnegative integer, is divided by $1000$. Let $S$ be the sum of all elements in $R$. Find the ...
0
votes
0answers
21 views

What is the PMF of the Hamming weight of a multinomial random variable?

Assume that $X$ is a random variable following a multinomial distribution of parameters $n$ (number of trials) and $p=(p_1,\dots,p_k)$ (event probabilities). Hence, ...
1
vote
1answer
66 views

Interesting property of Pascal's Triangle

I was looking at the Pascal's Triangle and saw that for all central numbers in even length row $a \gt 17$, the number $\dbinom{a}{b-2}$ is greater than $\dbinom{a-1}{b}$. This is where $b$ is equal to ...
0
votes
1answer
30 views

Interesting Combinatorics question relating the coefficients of variables in Pascal's Triangle

I tried this problem for a while by canceling the factorials on either side but for whatever reason, wasn't able to solve it. Could someone please help me? Is there a proof that ...
0
votes
0answers
26 views

All-pairs top-k min-cost flow paths

I am using a directed multigraph to model network flow. For example: Associated with each edge is: a cost of sending flow down that edge (red) a maximum capacity which the amount of flow sent ...
4
votes
1answer
42 views

Identities involving binomial coefficients, floors, and ceilings

I found the following four apparent identities: $$ \begin{align} \sum_{k=0}^n 2^{-\lfloor\frac{n+k}{2}\rfloor} {\lfloor\frac{n+k}{2}\rfloor\choose k} &= \frac{4}{3}-\frac{1}{3}(-2)^{-n},\\ ...
0
votes
1answer
47 views

consider a graph of a gameboard

Consider a graph of a game board. Rounds in the game result in a token moved from a game board location to a game board location, possibly returning to the same one. Let the game board location at the ...
4
votes
2answers
40 views

Number of divisors of the form $(4n+1)$

Find the number of divisors of $$2^2\cdot3^3\cdot5^3\cdot7^5$$ which are of the form $(4n+1)$ I know how to find the total number of divisors. But, to find the number of divisors of the form ...
2
votes
1answer
42 views

How many height arrangements are there for people?

Let's suppose $n$ people of different height stand in line, and the observer (who is smaller than the people in line) looks at them from the side. The observer sees a person unless there is a taller ...
0
votes
0answers
24 views

A question on choosing numbers to form geometric sequence

So the question states: In how many ways can you choose three numbers from $1,2,...,100$ to form a geometric sequence $k,{km \over n}, {km^2 \over n^2}$ such that $n \gt 1$,$m \gt n$,$n^2|k$ and ...
1
vote
0answers
46 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 ...
1
vote
1answer
28 views

Argue that $\binom{n}{n_1,n_2,…,n_r} = \binom{n-1}{n_1-1,n_2,…,n_r} + \binom{n-1}{n_1,n_2-1,…,n_r}+…+\binom{n-1}{n_1,n_2,…,n_r-1} $

Argue that $\binom{n}{n_1,n_2,...,n_r} = \binom{n-1}{n_1-1,n_2,...,n_r} + \binom{n-1}{n_1,n_2-1,...,n_r}+...+\binom{n-1}{n_1,n_2,...,n_r-1} $ Each term on the right hand side is the number of ways ...
2
votes
1answer
60 views

Probability of getting the same vector result

This is part of a mathematical puzzle I was given to me by a friend a while ago and I can't work out how to solve it. Does anyone have any ideas? For a given vector $v \in \{-1,1\}^n$ we consider the ...
0
votes
0answers
59 views

I have a 8 DIP Switches on a device. How many combinations and permutations are there? [on hold]

I do not know how to figure this out. It is a head scratcher for me. $\begin{array}{cc} \text{DIP Switch} & \text{Possible Settings} \\ 1 & 4 \\ 2 & 4 \\ 3 & 9 \\ 4 & 4 \\ 5 ...
0
votes
1answer
19 views

Number of transformations of rank $m$

Let $\mathcal{T}_n$ be the set of all transformations on $\mathbb{N}_n = \{1, 2, \ldots, n\}$. For all $\phi \in \mathcal{T}_n$ let $\text{rank}(\phi) := |\phi(\mathbb{N}_n)|$. What is the cardinality ...
2
votes
2answers
37 views

How to find the number of all the possible ordered trees with n edges and k leaves?

We know that a tree with n edges have n+1 nodes.So if $|B_{n+1}|$ is the number of all possible ordered trees with n+1 nodes then its true that $C_{n+1} = |B_{n+1}|$ where $C$ is the Catalan ...
1
vote
3answers
51 views

Ordered Sum of Odd Numbers

EDIT: The vectors can be any length. That is $k$ is not fixed. For a given natural number $n$, let $S_1(n)$ be the number of vectors $(a_1, a_2, \ldots, a_k)$ such that $$a_1 + a_2 + \cdots + a_k = ...
4
votes
0answers
44 views

Terminology in graph theory

Let $G$ be a finite graph with the following property: For any vertex $a$ and edge $\{b, c\}$ of $G$, there is an edge connecting them: there is one of $\{a,b\}$ or $\{a, c\}$ in $G$. Is there ...
1
vote
1answer
17 views

Number of decompositions in sum of $s$ elements

Let $E=\{ 3^k+3^l; 0\leq k\leq l\}$. For all $n\in \mathbb{Z}$ and $s \geq 1$ denote $r_s(E,n)$ the cardinality of $$ \{(n_1, \ldots ,n_s) \in E^s, n_1+\ldots +n_s=n \}.$$ I'm looking for an upper ...
2
votes
1answer
73 views

How many different sums of parts of a vector

The following mathematical puzzle was given to me by a friend a while ago and I can't work out how to solve it. Does anyone have any ideas? For a given vector $v \in \{-1,1\}^n$ we consider the ...
0
votes
1answer
27 views

Length of substring if we just consider a subdivision in $\log n$ substrings

Let $u$ be a string of length $n$ and consider a subdivision in $\log n$ substrings $u = u_1 u_2 \cdots u_{\log n}$. Is it true that there exists a constant $C$ such that for each $1 \le i \le \log n$ ...
1
vote
1answer
31 views

How to come up with this recurrence relation for putting p rooks in a m×n chessboard?

I have a m×n chessboard and I have to put p rooks in the board so that no two of them are in attacking position. (Two rooks attack each other if they are in the same row or same column) How many ways ...
4
votes
2answers
94 views

When does this sum of combinatorial coefficients equal zero?

$p>2$ is a prime number, $n\in \mathbb{N}$. Is the following statement true or false? Thanks. $$\sum_{i=0}^{\lfloor n/p\rfloor}(-1)^i {n\choose ip}=0$$ iff $n=(2k-1)p$ for some $k\in \mathbb{N}$.
0
votes
0answers
47 views

Finding permutation matrix

Let $P_{\pi}$ denote a permutation matrix associated to the permutation $\pi:\{1,...,n\}\rightarrow \{1,...,n\}$ and $\sigma$ denote the cyclic permutation $(1 2 ...n)$. If T is the $n\times n$ lower ...
1
vote
2answers
25 views

Interpretation of double factorial solution to a problem of pairing two types of objects

I'd like a clarification about or some insight into one possible form of solution to the following problem: Suppose that each of n sticks is broken, into one long and one short part. The 2n ...
0
votes
0answers
60 views

What is wrong with my proof by exhaustion?

$n$ colored balls are placed in an urn, with $c$ colors such that there are an equal number of balls of each color. What is the expected number of distinct colors in $k$ randomly picked balls, ...
0
votes
1answer
29 views

Total number of triangles that can be made by $4n$ points, $n$ at each side of square

We are given a square with $n$ points on each side of the square. None of these points co-incide with the corners of this square. We have to compute the total number of triangles that can be formed ...