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)

3
votes
1answer
56 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
0answers
42 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 ...
7
votes
2answers
201 views

About one generating function

Initially, I have the following problem: find $$\sum_{k=0}^{n+1}(−1)^{n−k}4^k{n+k+1 \choose 2k}.$$ I thought, if I found the function $g_n(x) = \sum_{k=0}^{n}{n+k \choose 2k}x^k$, the answer would be ...
1
vote
1answer
23 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 each is unique, but one node from A can be connected ...
1
vote
2answers
331 views

What is the probability of of drawing at least 1 queen, 2 kings and 3 aces in a 9 card draw of a standard 52 card deck?

The title problem is just one specific example of a more generalized problem that I'm trying to solve. I'm trying to write an efficient algorithm for calculating the probability of at least k ...
0
votes
4answers
158 views

How many combinations of four letters each can be made from the word PEPPER?

As the title says. I know that if there is no certain number of letters to choose you would have to just do 6!/3!2!. But what would you do if you have to only choose 4 letters?
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
3answers
24 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 ...
5
votes
0answers
92 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 ...
1
vote
0answers
39 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 ...
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 ...
1
vote
3answers
466 views

Finding characteristic equation of problem and solve recurrence relation

I have a homework assignment to find the characteristic equation of the set which a(n) = the number of sequences of length n which can be build from ${1,2,3...8}$ but you can't have two even numbers ...
2
votes
2answers
34 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 ...
-1
votes
1answer
33 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?
6
votes
3answers
4k views

How many distinct n-letter “words” can be formed from a set of k letters where some of the letters are repeated?

How many distinct n-letter "words" can be formed from a set of k letters where some of the letters are repeated? Examples: __ How many 6-letter words can be formed from the letters: ABBCCC? This ...
4
votes
2answers
171 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
2answers
90 views

What algorithm do i need to solve my problem?

unfortunately I even don't know what kind of problem I deal with. But I'll try to explain as good as I can and maybe you can tell what kind of problem this is and how to solve it. I want to find ...
0
votes
2answers
18 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
2answers
49 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 ...
4
votes
2answers
67 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 ...
15
votes
2answers
946 views

any pattern here ? (revised 2)

for any positive number $k$, I have a $(k+1)*(k+1)$ matrix. I wonder if these matrices follow any "obvious" pattern. My goal is to guess the elements for matrix with $k=5$ and above (most probably in ...
1
vote
1answer
36 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\}\\ ...
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 ...
1
vote
0answers
64 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
19 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
36 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
58 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
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 ...
2
votes
1answer
29 views

Finite projective planes

How big a set of points in general position (i.e., no three collinear) can be found in a finite projective plane of order $n$? I hope the answers won't be too technical, as I know almost nothing ...
4
votes
1answer
233 views

Finding intersecting subsets for given binomial coefficient

My apologies if this question is more appropriate for mathisfun.com, but I can only get so far reading about combinatrics and set theory before the interlocking logic becomes totally blurred. If this ...
1
vote
1answer
30 views

proof of Konig's Theorem for bipartite graphs from Menger's Theorem

Could someone provide me with a good reference for a proof of Konig's Theorem for bipartite graphs from Menger's Theorem? Konig's Theorem is as follows: For a bipartite graph $G$, the maximum size ...
0
votes
0answers
28 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 ...
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 ...
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 ...
8
votes
1answer
245 views

Bipartite graph: how many closed walk with given properties

Let be $G=(U,V,E)$ a bipartite graph where $U$ has $K$ possible vertices and $V$ has $N$ possible vertices. We focus on closed walks of length $2L$. Such walks can be described by the sequence of ...
-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?
1
vote
1answer
254 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
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
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!}$$
2
votes
4answers
131 views

Log concavity of binomial coefficients: $ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $

How do we prove that Binomial coefficients are log-concave? A sequence $a_0, \dots, a_n$ is log-concave if $a_k^2 \geq a_{k-1}a_{k+1}$. $$ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $$ If $ n ...
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 ...
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 ...
5
votes
6answers
2k views

Proving $\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $

[Corrected question] I'm struggling at proving the following combinatorical identity: $$\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $$ I would like to see a combinatorical (logical) solution, ...
3
votes
3answers
101 views

Evaluation of a sum of $(-1)^{k} {n \choose k} {2n-2k \choose n+1}$

I have some question about the paper of which name is Spanning trees: Let me count the ways. The question concerns about $\sum_{k=0}^{\lfloor\frac{n-1}{2} \rfloor} (-1)^{k} {n \choose k} {2n-2k ...
-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 ...
3
votes
1answer
283 views

What is the number of ways to divide a rectangle into $n$ smaller rectangles line by line?

The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is ...
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 ...
0
votes
4answers
30 views

In how many ways can we arrange $n$ A's and $n-1$ B's into $2n-1$ slots?

There are $2n-1$ slots/boxes in all and two objects say A and B; total number of A's are $n$ and total number of B's are $n-1$. (All A's are identical and all B's are identical.) In how many ways ...
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 ...