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
0answers
12 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
15 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
71 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
60 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
29 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
49 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
36 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
39 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
68 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 ...
5
votes
0answers
94 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
20 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
37 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
59 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
172 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
66 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
29 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
70 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
42 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
45 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
26 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 ...
0
votes
0answers
26 views

What's the name of $\sum_{k = 0}^{n} (-1)^k {n \choose k} (n-k)^w$?

I worked out the following expression as the number of all possible "words" consisting of exactly $w$ letters from an alphabet $L$ of size $\left|L\right| = n \leq w$, and containing each of these $n$ ...
0
votes
1answer
27 views

Count ways to sit men women in row of size K

Suppose we are given N men and M women.They are to sit in a row of size K such that no two women sit next to each other.What are the number of ways. Like if suppose their are 3 men and 2 women and ...
1
vote
1answer
23 views

What is the probability that the maximum number of shots fired successively from a type A gun is $2$?

A gun salute always takes place at the funeral of a military leader who has died in a certain country. (The $21$ gun salute where $21$ rounds are fired - is the most common for the most senior ...
2
votes
3answers
85 views

Number of attempts needed to open lock

There are $3$ knobs for a lock $A,B,C$. Each can take $8$ positions, and for each knob there is one correct position. When $2$ of the knobs are at their correct positions, the knob opens (irrespective ...
0
votes
2answers
30 views

Probability that the first $2$ balls are white, given that the sample contains exactly $6$ white balls

An urn contains $30$ white and $15$ black balls. If $10$ balls are drawn without replacement, find the probability that the first $2$ balls are white, given that the sample contains exactly $6$ ...
2
votes
2answers
78 views

Combinatorial proof of $a^n - b^n = (a - b)(a^{n – 1} + a^{n – 2}b + \dots + ab^{n – 2} + b^{n – 1})$

Is it possible to come up with a combinatorial argument which proves the following identity? $$a^n - b^n = (a - b)(a^{n – 1} + a^{n – 2}b + \dots + ab^{n – 2} + b^{n – 1})$$ My idea was this: ...
1
vote
3answers
64 views

Number of groups containing at least 1 and at most k elements

In Counting of the elements in a set, I've been answered that the number of ways of grouping $n$ elements in $n_{G}$ groups such that each group contains at least 1 element is $$ {n-1 \choose ...
0
votes
1answer
30 views

Binomial Coefficients (2,1) [on hold]

What are binomial coefficients? Can someone explain. For example: (2,1). or what (2n,n) means
0
votes
1answer
33 views

Proof of De Bruijn-Erdos theorem

I am reading Cameron's Combinatorics and came across following part of the proof of De Bruijn-Erdos theorem which I am unable to follow. $F$ is the family of set such that any two sets in $F$ ...
-1
votes
1answer
32 views

4096 vs 12! Binary Combinatorics in 12 bits

Given a $3\times4$ matrix keypad, each key encoded onto a unique index on a 12 bit string (0000-0000-0000), the maximum combinations are $2^{12}=4096$. However, $12$ available keys have a maximum ...
7
votes
1answer
81 views

Integer solutions of the factorial equation $(x!+1)(y!+1)=(x+y)!$

The problem is: are there solutions for the next equation? $$(x!+1)(y!+1)=(x+y)!$$ with $x,y\in\mathbb{N}$. My solution: $\left(x!+1\right)\cdot \left(y!+1\right) = \left(x+y\right)!$ ...
1
vote
3answers
57 views

Relaxed magic squares

I found the definition that a relaxed magic square of type $n\times n$ has row and column sums constant, and all numbers from $1$ to $n^2$ appears exactly once. How can one enumerate those, like how ...
1
vote
1answer
34 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...
0
votes
1answer
42 views

Number of ways to divide students into groups of 4 with additional conditions

Ok, I have this question: I have the answers available but I'm struggling to get my around a few parts of the answer. So far I believe: Q1a) $(4n)!$ dictates the number possible ways of ...
0
votes
2answers
47 views

6 Professors and 8 floors - expected value

I have this problem I need help with. There are 6 professors on an elevator that has 8 floors/stops. Each professors exits the elevator randomly(1/8 chance). What is the expected value E(X) of stops ...
0
votes
1answer
59 views

Count numbers with prime digit

Given a number N I need to find the count of the numbers that have atleast one prime digit (2,3,5 or 7) in it. Now N can be upto 10^18.What is the best approach to solve this problem. Example : Let ...
-3
votes
0answers
45 views

Odd Number Query [on hold]

Using the odd numbers less than 10, what smallest 4-digit odd number can be formed?
2
votes
2answers
31 views

Distinct balls into distinct boxes with a minimal number of balls in each box

Find the number of ways to distribute $8$ distinct balls into $3$ distinct boxes if each box must hold at least $2$ balls. The stars and bars approach would not work because the balls are ...
2
votes
2answers
52 views

Question of Permutation and combination

I have found a question from somewhere in the internet as follows: English language has 26 alphabets, out of 4 distinct vowels and 7 distinct consonants, how many letter patterns can be made ...