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)

1
vote
2answers
49 views

Number of 1's among all partitions of an integer

I am trying find a recurrence relation for the number of 1's among all partitions of an integer. The OEIS database has an entry mentioning this particular sequence but does not give a recurrence ...
3
votes
3answers
872 views

How many ways are there for 10 women and six men to stand in a line

How many ways are there for 10 women and six men to stand in a line so that no two men stand next to each other? [Hint: First position the women and then consider possible positions for the men.]
0
votes
0answers
23 views

Two dimention recursive recursive equation

I am unable to solve the following recursive equation which I must solve in my research problem. Please give me advice or solution to the problem. For $K=\min(N/2,C)$ and N,C T_c, T_s,p,T are ...
3
votes
1answer
49 views

Probability of a typing monkey backspacing all letters. [duplicate]

Suppose a monkey is typing on a keyboard into a word document. The word document has x letters already in the document. The keyboard has n number keys on it (i.e. keys that cause another digit to ...
1
vote
0answers
32 views

Family of sets. Directed acyclic graph representation.

We are given a family of sets $F=\{F_1,\ldots,F_n\}$ with each $F_i$ being a subset of a ground set $N=\{1,\ldots,n\}$. In addition, we assume for each $F_i$ that it's not the subset of another $F_j$ ...
1
vote
1answer
128 views

Catalan numbers - number of ways to stack coins

How many ways are there to stack coins on top of the other (2D stack) without any coin falling down ? Here's an example for $n=3$: Now this is most likely just like the monotonic path of Catalan ...
2
votes
1answer
88 views

number of derangements

In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses. A derangement of n numbers is a ...
1
vote
2answers
89 views

Calculate the determinant of the matrix.

Calculate the determinant. \begin{bmatrix} C_{n}^{p+n} & C_{n}^{p+n+1} & \dots & C_{n}^{p+2n} \\ C_{n}^{p+n+1} & C_{n}^{p+n+2} & \dots & C_{n}^{p+2n+1} \\ \vdots & ...
2
votes
1answer
67 views

Using matrix theory to solve this problem

I'm sorry that I couldn't find a better title for this. I was wondering if my solution is valid for the following problem, or if I've made some mistake. Problem: Let $N=\{a_1, \dots, a_n\}$ be a ...
7
votes
2answers
126 views

Continuity of a map with constrains

Let $A_i$ be a disjoint union of finite number of closed sub intervals of $[0,1]$, $1\leq i\leq n$. Each of $A_i$ has non-empty intersection with $A_j$. However, the intersection of each triple of ...
1
vote
1answer
39 views

Number of selection containing at least one of each kind.

From 3 cocoa nuts, 4 apples, and 2 oranges, how many selections of fruit can be made, taking at least one of each kind ? Ans:315 My thought: For any of our selection that contains at least one of ...
0
votes
1answer
59 views

Non-isomorphic labeled forests [closed]

Prove that the number of non-isomorphic labeled forests on the vertex set [n] is at least p(n) (the number of partitions of the integer n).
2
votes
0answers
71 views

How do you specify a link to a blind combinatorialist?

Regular projections of links look like graphs in the plane. So I'm wondering if it would be possible to specify a link up to isotopy with purely combinatorial data about this graph. If so, what kind ...
0
votes
2answers
47 views

Number of ways to remove some cards from a deck

I'm currently studying discrete mathematics and I've just bought "Mathematics: A Discrete Introduction" by Edward A. Scheinerman. The book is awesome but unfortunately it doesn't contain the answers ...
1
vote
2answers
103 views

Deriving a formula for the number of ways to partition a set

I'm working on a question below: Let $H(n,k)$ denote the number of ways to partition a set with $n$ elements into $k$ subsets of the same size. Derive a formula for $H(n,k)$. Thanks in advance ...
0
votes
3answers
4k views

A coin is flipped 8 times: number of various outcomes

A coin is flipped eight times where each flip comes up either heads or tails. How many possible outcomes a) are there in total? b) contain exactly three heads? c) contain at least three heads? d) ...
4
votes
1answer
181 views

Number of ways to seat nine people around circular table with restrictions

Problem: Nine delegates, three each from three different countries, should be seated at a round table that seats nine people. How many different ways are there to seat them in such a way that no two ...
0
votes
2answers
298 views

Finding number of cases , arranging people around circular table

Suppose we have a circular table and it contains 10 seats how many way we can arrange 15 people in this table ? Please Correct me: $ \dbinom {15}{10} \cdot \dfrac {15!}{5!} $
1
vote
0answers
79 views

Possible combinations for a cube

When drawing one of two possible diagonals on each side of a cube, how many unique patterns are possible with regard to all sides of the cube and all possible diagonal orientations. I am stuck on ...
1
vote
0answers
62 views

How many buckets options are there for putting N balls in the buckets?

N balls and how many buckets you want. You want to put the N balls into buckets. How many buckets options are there? For example, (N=)4 balls can be put in the following ways: {1,1,1,1} - 1 ball ...
3
votes
2answers
141 views

Possible sides of and octahedron

What number of unique patterns can be made if all sides of an equilateral octahedron is blue or green? How do you solve such a problem? I have only tried to solve this by a hands-on approach, i.e. ...
3
votes
1answer
114 views

Number theory: 2 numbers within a set with same difference

You have the numbers 1,2,3...,99,100. From that set you have to choose 55 different numbers. Show that: There are 2 numbers with a difference 9,10,12,13 Show that there aren't ...
16
votes
3answers
952 views

Alternating sum of squares of binomial coefficients

I know that the sum of squares of binomial coefficients is just ${2n}\choose{n}$ but what is the closed expression for the sum ${n}\choose{0}$$^2$ - ${n}\choose{1}$$^2$ + ${n}\choose{2}$$^2$ + ... + ...
4
votes
1answer
117 views

What is the minimum number of locks on the cabinet that would satisfy these conditions?

Eleven scientists want to have a cabinet built where they will keep some top secret work. They want multiple locks installed, with keys distributed in such a way that if any six scientists are present ...
1
vote
1answer
21 views

Combinatorics of possible vectors with length 3 without duplicates

Suppose I have a vector with a length of 3. I have 6 choices. They are: 1a, 2a, 2b, 3a, 3b, 4a. Choices with the same beginning number cannot be on the same vector. For example, a vector with [ 1a, ...
0
votes
1answer
31 views

Number of Injury claims per month

The number of injury claims per month is given by $N$ where $\\$ $ P(N=n) =\dfrac{1}{(n+1)(n+2)} $ where $0 \leq n$ Determine the probability of at least one claim during a particular month given ...
1
vote
2answers
60 views

Probability that at least 1 person receives its letter for a distribution of n letter to n people (paired 1 to 1)

I'm trying to solve an elementary probability problem, but I don't get the right answer and can't find the flaw in my reasoning. The problem and my (wrong) solution goes as follows. Somebody ...
0
votes
2answers
74 views

Possibilities for changing one $1024$ banknote to banknotes from $\{2^i: i = 0,\ldots,9 \} $

How many possibilities do there exist to change one banknote $1024$ to denominations from the set set $\left\{2^i: i = 0,...,9 \right\} $. I think that there really are a lot, but I don't have any ...
3
votes
2answers
70 views

Counting the number of $n$-digit quaternary sequences that have #0s=#1s and #2s=#3s

Consider an n-digit quaternary sequence. I want to count how many such sequences have BOTH the same number of 0s as 1s and same number of 2s as 3s (e.g.if n=6, one such sequence is 001123). Thanks in ...
1
vote
0answers
84 views

Sum of all possible products when each product is truncated if too large

I have a set of sets of real numbers greater than $1$. Each set can have a different quantity of numbers. Set $A_1 = \{a_{11}, a_{12},\ldots,a_{1m_1}\}$ Set $A_2 = \{a_{21}, a_{22}, \ldots, ...
2
votes
1answer
95 views

Generating function for the number of choices $I,J\!\subseteq[n]$ such that $\max\,[n]\!\setminus\!(I\!\cup\!J) < \max I\!\cap\!J$

Suppose that each pair $I,J\!\subseteq[n]=\{1,\ldots,n\}$ for which $$\max\,([n]\!\setminus\!(I\!\cup\!J)) < \max (I\!\cap\!J) \tag{1}$$ contributes $t^{|I|+|J|}$ to a generating function, and ...
0
votes
0answers
50 views

Combinatorics: how to solve non homogeneous two dimentional recursive equation

I am unable to solve the following recursive equation which I must solve in my research problem. Please give me advice or solution to the problem. For $K=\min(N/2,C)$ and $N$,$C$ $T_c$, $T_s$,$p$,$T$ ...
3
votes
3answers
150 views

Counting ways to arrange envelopes by inclusion (from Stanley's Enumerative Combinatorics)

This is a question from supplement( Bijective proof problems ) to the Stanley's Enumerative Combinatorics. The question statement goes like this. "In how many ways can $n$ square envelopes of ...
3
votes
2answers
527 views

Computing a probability of finding defects by random sampling

This is a problem from my semester end exams (which have got over). I suspect that the problem below is vague or open for misinterpretation. I would really like to know the actual answer to the ...
0
votes
0answers
15 views

If $A_j=\sum_{x,y,z}B_{x}B_{y}B_{z}$, where $x+y=z+j$, is there a closed form expression for $\frac{\partial A_j}{\partial{B_k}}$?

I am working on a problem involving equations whose interaction is governed by a conservation of momentum condition. Essentially I have two vectors $\mathbf{A}=\left\{A_j\right\}$ and ...
0
votes
1answer
59 views

Hunting Birds probability

A hunter locates 20 geese, 25 ducks 40 eagles, 10 ostriches, and 5 flamingos. He randomly selects 6 birds to target. What is the probability at least one of each species is targeted? My reasoning $20 ...
5
votes
1answer
280 views

Generating Function for Binary String Question

The following is an assignment question I have been trying to work out for quite some time. Let $C(x,y)=\sum_{n,k \geq 0} c_{n,k} x^{n} y^{k}$, where $c_{n,k}$ is the number of binary strings of ...
0
votes
1answer
18 views

Selecting Cards

A special deck of 51 cards constists of 25 pairs and 1 wild card. The deck is distrubuted evenly between 3 players (17 cards each). What is the probability that your hand has only two pairs that is ...
1
vote
1answer
72 views

k critical graph cannot have k + 1 vertices

$k$-chromatic graph is called $k$-critical if removal of any vertex from graph makes it $k - 1$ vertex colorable. Now i have to prove that if $G$ is a $k$ critical graph then it cannot have $k+1$ ...
3
votes
2answers
199 views

Characterizing sums of permutation matrices

Given an $n$ by $n$ matrix $A$ whose rows and columns sum to $m \in \mathbb N$ and entries are nonnegative integers, does there exist a permutation matrix $P$ such that $A - P$ has only nonnegative ...
1
vote
2answers
58 views

Why can't you solve this probability problem in this way?

Daphne is visited periodically by her three best friends: Alice, Beatrix, and Claire. Alice visits every third day, Beatrix visits every fourth day, and Claire visits every fifth day. All three ...
1
vote
1answer
58 views

A bagel shop has plain muffins, cherry muffins, chocolate muffins, almond muffins, apple muffins, and broccoli muffins.

How many ways are there to choose: 1.) two dozen muffins with at least two of each kind? 2.) two dozen muffins with at least five chocolate muffins and at least three almond muffins? 3.) two dozen ...
0
votes
0answers
32 views

Recurrence in Two Variables

Anyone know how to solve the following recurrence relation in two variables: $$ f(x,y) = b f(x-1,y) + c f(y,x-1) \\ f(x,0) = b^{(x-1)} \\ f(0,y) = 0 $$ (Note: repost of a post I asked yesterday with ...
0
votes
1answer
50 views

Permutations - combinations

Task is: ,,How many arrangements of the word TRIGONAL can be made if only two vowels and three consonants are used?" The solution is quite clear: 3600 = 3C2 * 5C3 * 5!. But, why I do not get the same ...
1
vote
2answers
93 views

Combinatorial proof with binomial coefficients

I need to prove this with combinatorial arguments. I don't know how to start. $$ \sum_{j = r}^{n + r - k}{j - 1 \choose r - 1}{n - j \choose k - r} = {n \choose k}\,, \qquad\qquad 1\ \leq\ r\ \leq\ ...
1
vote
0answers
24 views

Shortest ways in a grid above the angle bisector

Suppose, you have a grid with the side lengths n and m and the angle bisector from the upper left corner to the bottom side. To walk along the lines from A to B, there are $\binom{n + m}{n}$ shortest ...
1
vote
0answers
54 views

Expectation of trial numbers on Multinomial distribution.

Player extracts card from the deck (which has infinite number of size) to obtain one of $k$ colors of cards. The possibility that the player pick a card with $i$th color is given by $p_i>0$. Of ...
2
votes
1answer
158 views

Counting certain partitions of integers

[Recall that] Young's lattice is a partially ordered set in which all partitions of integers are ordered thus: The elements just one step below any partition are those that you can get by subtracting ...
0
votes
1answer
457 views

Binary string with even and odd number of 1s [duplicate]

How could it be shown that the number of binary string of length k with an even number of 1s is the same as those with an odd number of 1s. Eg. for $k = 3$ : Binary string length 3 with even amount ...
1
vote
3answers
67 views

How many ways can a couple be selected out of a party.

Hi I wounder if I'm thinking correctly about this question: There are 15 married couples at a party. In how many ways can a man and a women at the party be selected so the two are (a) married with ...