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)

2
votes
1answer
64 views

Use of pigeonhole principle in ramsey-theorem about monochromatic triangles.

Im trying to prove that for any number n the complete graph with $p(n)$ vertices whose edges have been colored with n colors in some way has a monochromatic triangle (a triplet of nodes that are ...
0
votes
1answer
29 views

Graph isomoprhims

Assume that graphs $G$ and $H$ are isomorphic and that $f$ is an isomorphism from $G$ to $H$. The distance between two vertices is the length of the shortest path between them. Show that the distance ...
5
votes
1answer
114 views

Matching with probabilistic edges

Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $0.01$, independently of the remaining edges. Is it true that ...
1
vote
0answers
95 views

How many ways are there to pair up $10$ girls and $11$ boys ($1$ boy & $1$ girl) such that one of the pairs has $2$ boys and $1$ girl?

How many ways are there to pair up $10$ girls and $11$ boys ($1$ boy & $1$ girl) such that one of the pairs has $2$ boys and $1$ girl? Is the answer to this question same as $10$ girls & $10$ ...
1
vote
1answer
179 views

Relative positions in permutation

Say we have the following string: $$\text{s=aaaabbcdefghijkl} \tag{1}$$ a) In how many ways can we permute $s$ ($|s|=16$) such that all $4$ a's are spaced by at least 3 spaces relative to another ...
3
votes
1answer
37 views

number of functions >$g:\{1,2,3\}\rightarrow \{1,2,3\}$ such that $f(x)=g(x)$ least one $x\in\{1,2,3\}$

Let $f:\left\{1,2,3\right\}\rightarrow \left\{1,2,3\right\}$ be a function. Then the number of functions $g:\{1,2,3\}\rightarrow \{1,2,3\}$ such that $f(x)=g(x)$ for at least one ...
3
votes
1answer
74 views

What is the minimum of shirts that must be selected to ensure five shirts of the same color are selected?-Pigeonhole Principle

A closet has 3 red, 7 blue and 10 black shirts. What is the minimum number of shirts you’ve to blindfoldedly pick to ensure a. at least 4 of the same color? b. at least 5 of the same color? Soln: I ...
0
votes
1answer
64 views

How many possible groups of 4 can you create from 9 people?

I'm fairly sure I know how to solve this through combination: $ \frac{9!}{4!5!} = 126 $ But how do I go about solving this using the product or sum rule? When I try using the product rule I get ...
1
vote
1answer
48 views

If a graph is planar, how to prove any of its minors is also planar?

In my head this is trivial, but I got this question as part of an assignment, so I am pretty sure my argumentation has to be more complete. If a graph is planar, then removing any edge will keep it ...
0
votes
1answer
69 views

$M \times N$ binary matrix where $\sum ($any row$)=R$ and $\sum ($any col$)=C$

I have encountered a fairly structured $M\times N$ matrix $A$: $A$ has only $1$s and $0$s The sum along any row of $A$ equals $R$ The sum along any column of $A$ equals $C$. ...
1
vote
0answers
56 views

How to make a canonical coin system so that greedy solution is the only optimal solution for change-making problem

Related to the paper: http://arxiv.org/PS_cache/arxiv/pdf/0809/0809.0400v1.pdf and coin-change problem in general. We say that a coin system of coins canonical if the greedy algorithm to the coin ...
1
vote
1answer
31 views

Interpretation and combinatoric

Situation: Imagine that we are playing a game, like Free cell. There are $52$ cards. There are eight columns, where the first four have seven cards each and the rest columns have six cards each. ...
3
votes
0answers
46 views

Amount of combinations of sets summing to number

(Apologies for the confused arbitrariness here; I don't have experience in formal maths to make abstract my lay-person thoughts, but I've tried my best.) I have $x$ identical but order-important sets ...
1
vote
2answers
56 views

lower bound on $\sum_{i=0}^{k}\binom{n}{i}$ for $k<n$

Given two positive numbers $n,k$ s.t. $k<n$, an upper bound for $\sum\limits_{i=0}^{k}\binom{n}{i}$ is $\frac{2n^k}{k!}$. Are there any known lower bounds as well? (in particular when $k=2^x-1$ and ...
0
votes
0answers
23 views

HyperGeometric distribution and tests

A friend of mine and myself were discussing the following problem and could not reach and agreement: Say I have a system that can be modelled by an hypergeometric distribution. One can think about a ...
1
vote
2answers
56 views

Integer solutions to an equation with a constant before x

The question is: How many integer solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + 3x_5 = 80$$ if $x_i$ is greater than or equal to 0? I understand how to get integer solutions to a ...
10
votes
2answers
314 views

Proving that $\sum_{a=1}^{b} \frac{a \cdot a! \cdot \binom{b}{a}}{b^a} = b$

Prove that for all positive integers $b$ that $$\sum_{a=1}^{b} \frac{a \cdot a! \cdot \binom{b}{a}}{b^a} = b.$$ My idea is induction, but I cannot figure stuff out on the inductive step.
1
vote
2answers
68 views

How many solutions does the equation have if all variables are positive integers?

How many solutions does the equation $X_1 \cdot X_2 \cdot X_3 \cdot X_4 \cdot X_5 = 2^{20}$ have if all $X_i$'s are positive integers? So I approached this problem by setting all the $X_i = Y_i + 1$ ...
3
votes
1answer
98 views

Possible permutations of elements within sets

I'm trying to resolve a permutation problem. Say I have n apples, k bags and each bag has a c storage space. (Let's assume every bag has the same c storage), I need to know how many permutations are ...
1
vote
3answers
210 views

Prove that if the # of vertices = # of edges, then # of vertices of degree 3 = # of vertices of degree 1

Assume $G$ is a graph where the vertices have degree $1$ or $3$. Let $n$ be the number of vertices. We know $n = |E(G)| = \frac12 \sum \deg(v) $ let $a$ be the number of vertices with degree $1$. ...
2
votes
0answers
34 views

Help check two results of particle-bucket problems

Given $n$ particles and $N$ bucket. Buckets are allowed to be empty. Suppose the buckets are labeled, then the numbers of possible outcomes are $N^n$ when particles are labeled ...
0
votes
1answer
24 views

Number Of Distinct Paths In A Rectangular Grid

Just wanted to share a nice problem.I have given my method below.More answers are welcome. Consider a rectangular integral grid of size $m*n$.A person has to travel from one end say $(0,0)$ to the ...
3
votes
0answers
58 views

An upper bound for the number of answers of this equation

Let $n$ be a natural number and $p$ a prime number less than or equal to $n$. $$\begin{align} n^2 + 2n &\equiv a \pmod p\\ n^2 + 1 &\equiv b \pmod p \end{align}$$ If $a \lt b$, $p$ is ...
0
votes
0answers
21 views

Binomial coefficient for number of k-dimensional objects in the n-simplex

I'm trying to prove that for the $n$-simplex, the number of $k$-dimensional objects are determined by $n+1 \choose k$, $0 \leq k \leq n$. My initial thought was to do this by induction. Beginning with ...
2
votes
1answer
154 views

In how many ways can 7 boys and 3 girls be arranged in a row so that the end positions are taken by the boys?

In how many ways can 7 different boys and 3 different girls be arranged in a row so that the end positions are taken by the boys and no 2 girls are sat next to each other. I think I have an idea on ...
4
votes
1answer
47 views

In how many ways can 9 cars be parked so that there are never two red cars next to each other?

Nine cars are parked in a row. Four of the cars are painted red and five are painted blue. In how many ways can the cars be parked so that there are never two red cars next to each other? I think I ...
0
votes
0answers
35 views

Birthday paradox for years with $D$ days, with $D$ large

I just learned about the birthday paradox and was quite fascinated that you only need 23 people to have a 50% probability that two people share the same birthday. this is 365. The chance p = 1 - ...
0
votes
2answers
106 views

Polya's Urn : proportion Probability

There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected ...
0
votes
1answer
26 views

8 $\alpha$ and 8 $\beta$

We have 8 $\alpha$ and 8 $\beta$. How many sequences do we have if between 2 $\alpha$ we have at least one $\beta$. I know that it will be sum, but probably I have to use floor and celling, but don't ...
3
votes
2answers
71 views

Guy with $7$ friends

Some guy has $7$ friends$(A,B,...,G)$. He's making dinner for $3$ of them every day for one week. For how many ways can he invite $3$ of them with condition that no couple won't be more then once on ...
2
votes
2answers
62 views

An Identity Involving Narayana Numbers

Let $N(n,m)$ denote the Narayana number defined by $$N(n,m)=\frac{1}{n}{n\choose m}{n\choose m-1}.$$ Let $$A(n,k,\ell)=\sum_{\substack{i_0+i_1+\cdots+i_k=n\\ ...
1
vote
1answer
36 views

$k$ times's draw from $n$ numbers with replacement, each number at least appear once

Sample $k$ times with order from $n$ distinct numbers with replacement where $k\ge n$. Here "with order" means the sample is treated like a sequence rather than a set, so results like "1,3,3" and ...
1
vote
1answer
30 views

If a graph is k-connected, does it mean it has at least one group of k separators?

This question is about clarifying some terms. I am trying to make sure that I understand them correctly. If a graph is k-connected, then the removal of < k vertices keeps the graph connected. ...
1
vote
1answer
27 views

Graphs and cycles

If we have a connected graph $G(V,E)$. Now I want to prove that if $\{a,b \} \in E$ is in a cycle $\iff G \backslash \{a,b\}$ is connected. Proving the second direction is easier If $G \backslash ...
1
vote
2answers
143 views

Probability - 12 pairs of shoes

There are 12 pairs of shoes in a closet. Five shoes are picked at random. (a)What is the probability there is no "pseudo-pair"(i.e., one left and one right shoe)? (b) What is the probability that ...
1
vote
2answers
65 views

Probability to identify faulty machines.

There are four machines and it is known that exactly two of them are faulty. They are tested, one by one, in a random order till both the faulty machines are identified. Find the ...
0
votes
1answer
37 views

Transforming and identity for $n \choose k$ with the “committee and chair” trick

I am not sure if this equality has a more formal name, but it is informally called the "committee and chair" trick from Ross. It is: $$k {m \choose k} = m {m-1 \choose k-1}$$ I saw it applied in the ...
1
vote
1answer
100 views

Connected components of a graph

If we have a graph $G$ and $e$ is an edge in this graph. Now I want to show that $G − e$ has at most one more connected component than G.Now if we remove one vertex from G, by how much can ...
0
votes
0answers
27 views

possiblities of drawing twice from $n$ different urns

This seems simple, and I can certainly write a program that calculates this, but I'm having a hard time coming up with a closed formula. Assume I have $n$ different urns labeled $0$ to $n$. Suppose ...
1
vote
1answer
50 views

How many such ways to group 2n students?

I don't understand something very simple at the beginning of the course in combinatorics. There are $2n$ students in class. They divide to couples to do homework. How many such options of dividing ...
0
votes
1answer
46 views

Seeking a combinatorial proof $\sum _{k=0}^{2n} (-1)^k \binom{4n-2k}{2n-k}\binom{2k}{k}=\binom{2n}{n}\times 2^{2n}$ [duplicate]

I would appreciate if somebody could help me with the following problem Q: Seeking a combinatorial proof $(\binom{n}{k}=\frac{n!}{k! (n-k)!} )$ $$\sum _{k=0}^{2n} (-1)^k ...
0
votes
0answers
23 views

Star and bar problem for finite decimals

The star and bar method of computing all the possible combination of non-negative integers whose sum is set fixed is well known (i-e Total possibilities $=C\big(n+k-1,k-1\big)$ where $n$ is sum and ...
4
votes
1answer
117 views

Another way of counting probability

A set $S = \{1, 2, \cdots, k\}$ is given. Two persons independently choose some numbers from this set. I want to count the probability that the cardinality of intersection of the chosen sets by both ...
2
votes
1answer
44 views

How many words of length $7$ can we assemble if each letter should appear at least twice.

From the letters "a,b,c" we assemble words with $7$ letters, how many words can we assemble if each letter should appear at least twice. My attempt: There are $7$ places: $\color{blue}{*******}$ ...
0
votes
1answer
20 views

Counting partitions of a finite set in $\lambda_j$ $j$-element sets

Suppose we have an $n$-element set $A$ and $\lambda_1,\dots,\lambda_n \in \mathbb{N}_0$ with $\sum_{i=1}^n \lambda_i\cdot i = n$. How many partitions $P$ of $A$ are there, s.t. $\# \binom{A}{j} = ...
1
vote
2answers
35 views

the probability that there's an actual tornado if the alarm goes off (discrete math)

TornadoGuard: If there is a tornado in the users's area, an app has 99% probability of warning the user with a loud alert sound. On the other hand, it has 1% probability of playing the loud alert ...
0
votes
2answers
32 views

Find the number of matrices $A$ with distinct elements such that $AA^{-1}=I$where $I$ is unit matrix of order $2$.

Let $A=[a_{ij}]$ be a square matrix of order $2$ where $a_{ij}\in\left\{0,1,2,3,4,6\right\}$.Find the number of matrices $A$ with distinct elements such that $AA^{-1}=I$,where $I$ is unit matrix of ...
0
votes
0answers
27 views

Please help with probability counting? [duplicate]

A palindrome is a string whose reveral is identical to the string. For example,110010011 is a palindrome. So are BOB and KAYAK. How many of length n are palindrome? Explain your solution clearly. I ...
1
vote
0answers
38 views

Asymptotic binomial ratios

I am in need of asymptotic version of $$\frac{ \displaystyle \binom{n^{1-s}}{n^s}}{\displaystyle \binom{n}{n^{s}}}$$ where $n\in\Bbb N$ and $s\in\big(0,\frac12\big)$ and $$\displaystyle \frac{ ...
0
votes
1answer
25 views

What is the the total number of “magic” circles for a given N?

I came across this this question helping my son with similar math. tasks. Consider the circle with $2^n$ items on its periphery. Each item holds 0 or 1. For each item consider sequence of n items to ...