This tag is for basic 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
1answer
13 views

Number of binary vectors of length $2^m$ with exactly $n$ $1$s

Consider the set $S_n$ defined as follows: $$S_n =\{b : b\text{ is a binary vector of length $2^m$ where exactly $n$ $1$s are present} \}.$$ Here $n$ is ranging from $1$ to $2^m$. Clearly $m$ is a ...
0
votes
0answers
18 views

Stirling Numbers of the Second Kind: A Problem from Lovasz

Problem: Prove that $n\brace n-k$ is a polynomial in $n$. My efforts at a formal derivation got me no where. Lovasz gives a solution in the form of a combinatorial argument: Note that a partition ...
0
votes
0answers
11 views

Block design: derived designs

I am now study some theorems of block design. I have a question about the derived designs. Let $B$ be the oringinal design $t-(v,k, \lambda)$. Suppose we omit one of the points, say $P$, then we have ...
0
votes
1answer
50 views

About putting $n$ distinct balls into $n$ distinct boxes.

Let the balls be labelled $1,2,3,..n$ and the boxes be labelled $1,2,3,..,n$. Now I want to find, What is the expected value of the minimum value of the label among the boxes which are non-empty ...
1
vote
1answer
36 views

How can I distribute 15 pennies (1 cent) and 17 nickels (5 cents)?

How can I distribute 15 pennies (1 cent) and 17 nickels (5 cents), between four children, with the following restriction: A child receives at leat 1 penny and 3 nickels The children 2,3 and 4, ...
8
votes
4answers
315 views

Prove that the 25 people can be seated in this way

5 mathematicians, 5 biologists, 5 chemists, 5 physicists, and 5 economists sit around a large round table. Prove that the 25 people can be seated such that, if A and B are two different people with ...
5
votes
2answers
31 views

What is the maximum possible number of elements of $S$?

This is an interesting problem I found. Let there be a 2-digit sequence that can start with 0, like 04 or 93. Let a "nudge" be defined as exactly one of the following operations: 1) Increasing one ...
4
votes
0answers
26 views

For the exponential operator $e^{f(x)\frac d{dx}}= \sum_{i=0}^\infty F_i(x) \frac{d^i}{dx^i}$, is there a formula for the $F_i$ in terms of $f$?

Consider the operator $$ e^{ f(x) \frac{d}{dx} } = \sum_{i = 0}^\infty \frac{1}{i!} \left(f \frac{d}{dx} \right)^i $$ If one commutes the derivatives with the powers of $ f $, then there are functions ...
2
votes
1answer
57 views

Proving combinatorial identity with the product of Stirling numbers of the first and second kinds

$$ \sum_{k} \left[\begin{array}{c} n\\k \end{array}\right] \left\{\begin{array}{c} k\\m \end{array}\right\} = {n \choose m} \frac{\left( n-1\right)!}{\left(m-1 \right)!}, \quad \text{for } n,m > 0 ...
0
votes
0answers
41 views

Are there magic knight tours on a $6\times6$ or $10\times10$ board?

In mathworld, magic tour, it is mentioned that for odd $n$, only semimagic knight tours are possible on a $n\times\ n$ - board. For $n = 8$, it has been verified that there are no magic knight ...
2
votes
1answer
40 views

How many ways are there to divide $100$ different balls into $5$ different boxes so the last $2$ boxes contains even number of balls?

How many ways are there to divide $100$ different balls into $5$ different boxes so the last $2$ boxes contains even number of balls? I tried to think about tylor function but got stuck. Thanks.
2
votes
2answers
43 views

A cog wheel math puzzle

A machine has 4 cog wheels in connection. The largest wheel has 242 teeth and the others have 66,48 and 26 respectively. How many rotations must the largest wheel make before each of the wheel is back ...
0
votes
0answers
27 views

Kempe chain color swaps in a partially colored map

Question: In this partially Tait's colored map, using only Kempe chain color swaps (as many as wanted), how many differently colored maps can I have? This map has these Kempe chains: (R,G) - 1 - ...
1
vote
2answers
35 views

Probability problem: n different balls in n different boxes

Problem Suppose $n$ different balls are distributed in $n$ different boxes. Calculate the probability that each box is not empty when distributed the balls. I'll define the sample space as ...
0
votes
4answers
71 views

How many subsets of $\{1, 2, …, n\}$ contain $1$ and how many don't? [on hold]

Consider the set $A = \{1, 2, …, n\}$ (a) How many subsets of A contain $1$? I got $ 2^n - 2^{n-1}$ (b) How many subsets of A do not contain $1$? I got $2^{n-1}$ (c) Use the pigeonhole principle ...
4
votes
2answers
92 views

Number of solutions of $x_1 + x_2 + x_3 + x_4 = 14$ such that $x_i \le 6$

Let $x_1, x_2, x_3, x_4$ be nonnegative integers. (a) Find the number of solutions to the following equation: $$ x_1 + x_2 + x_3 + x_4 = 14 $$ I got $17 \choose 3$ for this. ...
1
vote
1answer
59 views

If $P(n, k)$ is the number of partitions of $n$ elements into $k$ sets, then $P(n, k) = kP(n-1, k) + P(n-1, k-1)$ [on hold]

A partition of the set $\{1, 2, \dots , n\}$ into $k$ parts is a way of writing the set as a disjoint union of k subsets. For example $\{1, 2, 3, 4, 5\} = \{1, 4\} \cup \{2, 3\} \cup \{5\}$ is a ...
0
votes
0answers
36 views

Find solutions to given equation

Find all integer solutions $x$ for $0 < x < 10^9$ of the equation: $$x=b\cdot s(x)^a+c,$$ where $a$, $b$, $c$ are some predetermined constant values and function $s(x)$ determines the sum of ...
2
votes
1answer
41 views

Sufficient condition for $n$

There are $n$ people (distinct men and women) sitting around the table. After the break they will sit around the table again. What is the sufficient condition for $n$ such that there always exists $2$ ...
0
votes
1answer
31 views

Counting antichains in the limit $n \rightarrow \infty$.

By the Dedekind number function, let us mean the function $M : \mathbb{N} \rightarrow \mathbb{N}$ given by asserting that $M(n)$ is the number of antichains present in $\mathcal{P}(X)$, where $X$ is ...
0
votes
1answer
19 views

How to show a triple represents all possible selections?

Let $Y=\{y_1, y_2, y_3,y_4,y_5\}$ Then, the choices of selecting 3 objects (repetitions allowed) from $Y$ can be represented by the triple $(y_{i_1},y_{i_2},y_{i_3})$ where $i_1 \le i_2 \le i_3$. Is ...
3
votes
1answer
77 views

What is the mathamatical term for this programming concept?

In python's itertools, there is a function called permutations. It returns the number of ways to arrange x number of variables into a given space. For example, ...
2
votes
1answer
68 views

Sum of Catalan numbers

What is $C_1 +C_2 + C_3 +... + C_n$, where each $C_i$ is Catalan number? I want to know if we can bound this sum by some function of $n$. I am looking for an upper bound. For sure it is less than ...
1
vote
1answer
30 views

Combinatory, expected number of connected nodes. Sum on positive multinominal coefficients

I'm struggling with the following problem: Problem Consider two sets A and B containing m and n nodes. These sets are connected by l edges. Each edge connects one node from A to one node from B. ...
2
votes
3answers
30 views

Explain solution to calculating number of ways of selecting 3 objects from 5 objects (repetitions permitted)

The solution is: Let $Y=\{y_1, y_2, y_3,y_4,y_5\}$ Then, each selection corresponds to a triple $(y_{i_1},y_{i_2},y_{i_3})$ where $i_1 \le i_2 \le i_3$. A bijection from this set of triples to ...
0
votes
1answer
23 views

Why does this combination correspond to an injection from $\mathbb{N_2} \rightarrow Y$?

Suppose 3 people each select a main dish from a menu of five items. How many distinct choices are possible if 2 people select the same dish? The solution: Let $X$ be the set of 3 people and $Y$ be ...
0
votes
1answer
54 views

distribution of books among students

There are $p$ students and $q$ books where $q>p$ and all books are different, but each student will get a minimum of $1$ book and a maximum of $(p – 1)$ books. Find the total number of ways of ...
2
votes
2answers
37 views

Subset Probability to Element Probability

Is there any way to match (or map) from Subset Propabilities to Element Probabilities? Suppose that John may select x-sized subsets from a population of N items. In every subset he has exactly x ...
2
votes
4answers
40 views

Subsets $S$ such that $7 \notin S $ or $2 \notin S $

How many subsets $S \subseteq\{1,2...10\}$ are there such that $7 \notin S $ or $2 \notin S $? I can't find the right way to write a formal response. I think that we should consider at least ...
2
votes
0answers
41 views

Realisations of associahedra

I seem to have lost the reference to a realisation I am interested in. Hopefully someone can steer me to a paper that fully explains the realisation. For the case $K_2$(the 5-gon) the following ...
-1
votes
1answer
34 views

How many unique Binary Search Trees can be created with N keys? [on hold]

I have been given a set of keys $\{1,2,3,...,N\}$. How many unique binary search trees can I make with N keys?
0
votes
2answers
19 views

Set of ten distinct two-digit natural numbers

I am confused why there are $2^{10}$ (1024 subsets of distinct 10 digit natural numbers) Can someone please explain? Reference : pigeonhole principle problem : Prove that from a set of ten distinct ...
1
vote
1answer
41 views

Anagrams and related problems

I have a word like CONSTITUTIONALIST that is very fun for Anagram problems. So, in order to count the anagrams I have to: \begin{align*} s=\left\{C(2),O(2),N(2),S(2),T(3),I(3),A(1)\right\}\\ ...
4
votes
2answers
70 views

what is the meaning behind this combinatorial identity

In the following comment: Solution of $\large\binom{x}{n}+\binom{y}{n}=\binom{z}{n}$ with $n\geq 3$ $$ \binom{2n-1}{n} + \binom{2n-1}{n} = \binom{2n}{n} $$ I'm wondering about the meaning of this ...
7
votes
1answer
121 views

The Day Camp Stacking Game

My friend works at a day camp as a counselor and he told me about an interesting game he plays with his group of kids. You have a perfectly shuffled, regular $52$-card deck and a group of $2 \leq n ...
0
votes
0answers
22 views

Sperner family intersection with chains.

Consider a maximal sperner family $F$ of subsets of $X = \{ 1,2,3 \ldots n \}$. I need to prove that this family intersects with each chain of subsets exactly once. Each chain is defined as : ...
-3
votes
1answer
39 views

From a bag with 20 fruits of 4 kinds, how many must one pick to get a dozen fruits of the same kind? [on hold]

A bag contains 20 apples, 20 bananas, 20 oranges and 20 pears. In the worst case, how many fruits must one pick in order to be sure that they have a dozen fruits of the same kind? How many in order ...
0
votes
1answer
65 views

Help me (probability) [on hold]

Frederick and Paulo were conducting an experiment to see how many heads they could toss in 100 tosses of a coin. After 10 tosses they had 4 heads and 6 tails. Their friend Juliana came into the room ...
4
votes
2answers
178 views

Chess rook problem

Determine the number of ways for a rook to get from left bottom corner to top right corner of table $3\times 7$, if the rook can only move top and right. (Two ways are different if rook stops at least ...
1
vote
0answers
79 views

How many possibilities would you have in an android lock pattern, always using all 9 moves?

We are doing some research and wanted to know how many possibilities you would have if you would use all 9 dots/options in an (android) swipe lock pattern. What would the formula be to get to this ...
0
votes
0answers
30 views

K- Regular families. Proof of existence.

A family F of subsets is regular if every point lies in a constant number r of the elements of F. Theorem : Let $b,k,n,r$ be positive integer satisfying $bk = nr, k<n, b\leq $ $n\choose{k} $. Then ...
3
votes
0answers
72 views

What's so special about binomial coefficients that someone decided to organize them in a triangle?

I know that binomial coefficients are related to figurate numbers (which were studied by Greeks a loooong time ago, because of its connections to geometry). I also understand how the Pascal's triangle ...
4
votes
1answer
51 views

Order of group $GL_{2}\left( \mathbb{F}_{p}\right) $

I'm having a hard time counting. I need to count the number of elements for the multiplicative group of invertible $2\times 2$ matrices $GL_{2}\left( \mathbb{F}_{p}\right) $ with elements from the ...
0
votes
2answers
29 views

How many ways to withdraw $k$ balls from an urn with $n$ red and $m$ blue ones?

An urn contains $n$ red balls and $m$ blue balls. Of how many ways can we withdrawn a total of k balls, so that $k\le m+n$? My friend told me that there are $\binom {m+n}{k}$ ways to do that but ...
1
vote
2answers
43 views

How to show the identity relating to Matrix

Suppose that $$ A=\begin{bmatrix}a_{11}&a_{21}\\a_{21}&a_{22}\end{bmatrix}, \ \ B=\begin{bmatrix}d&-1\\1&0\end{bmatrix}. $$ and $$A=B^N$$ Show that $$a_{11}=\sum_{i=0}^{[N/2]}(-1)^i ...
-1
votes
1answer
46 views

Simplify factorials into a combinatorial formula

Is there any way to simplify this into a combinatorial formula? $$\frac{t!(n-t)!}{n!}$$
-1
votes
0answers
27 views

proof of equation by interpretation [on hold]

Let $a_n$ is number of ordered partition set ${1,...,n}$. The order is between parts. Prove : $$\sum_k \left[\begin{array}{c} n \\ k \end{array} \right]a_k = n!2^{n-1}\qquad n\ge 1$$ ([] - Stirling ...
1
vote
1answer
34 views

What is the probability that each of the vehicles will be made to carry at least one local tourist?

Three vehicles (one blue, one green and one grey) with a carrying capacity of 8 passengers each are to be used to ferry 18 international tourists and 5 local tourists (who are a family) from OR Tambo ...
2
votes
0answers
47 views

What is combinatorial probability a special case of?

Once I complained to one of my undergrad math professors that I was hopelessly lost when it came to combinatorics and combinatorial probability problems. He remarked, half-jokingly, that combinatorics ...
1
vote
2answers
43 views

Combinations of $5$ cards out of $52$ that don't include $4$ aces

How would I calculate the number of different ways (order doesn't matter) I can take out $5$ cards from a deck of $52$ cards, without ending up with $4$ aces? A way would be to say that the number ...