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)

4
votes
3answers
2k views

How can I (algorithmically) count the number of ways n m-sided dice can add up to a given number?

I am trying to identify the general case algorithm for counting the different ways dice can add to a given number. For instance, there are six ways to roll a seven with two 6-dice. I've spent quite ...
3
votes
1answer
521 views

What is the maximum number of combinations with repetitions, that the sum could be the same?

Suppose I have $n$ integers (both negative and positive) and I get all combinations of $k$ elements with repetition $((n, k)) = (n + k-1, k)$ My question is: what is the maximum number of ...
1
vote
2answers
180 views

On the Homology of Posets

Is there a homology theory of posets which computes topological invariants (e.g., number of $k$-faces, etc.) of the associated Hasse diagrams (viewed as simplicial/cellular/singular complexes) as ...
1
vote
2answers
32 views

Formula for counting ways to divide a number of people into separate groups

Assume six people at a party. Is there a formula to calculate the total possible combinations? Ie: Six alone. Four together, two alone. Four together, two together. 3 together, 3 others ...
3
votes
3answers
504 views

How many functions are transitive?

Let the set of all functions defined as: $\left\{a,b,c,d\right\} \rightarrow \{a,b,c,d\}$ How many functions are transitive? I've been told to use the fact that a function is transitive iff "it's ...
-2
votes
0answers
25 views

31 Knights round table problem formula. [on hold]

A legendary King decided who was the fittest to marry his daughter. The way he chooses is to have 31 knights all sit down at the round table and he'll say to the first knight, "You live." He'll say to ...
1
vote
1answer
38 views

Combinatorial identity on partitions

In Stanley's Enumerative Combinatorics, there is the following identity $$\sum_{n \geq k}S(n,k) x^n = \frac{x^k}{(1-x)(1-2x) \dots (1-kx)}$$ where $S(n,k)$ denotes the number of partitions of an ...
1
vote
1answer
31 views

Simple Countability Problem

Count the number of strings of length 8 over A = {a, b, c, d} that begins with either a or c and have at least one b. My attempt: 4^8 total possibilities. a or c will occupy the first part, so ...
2
votes
2answers
480 views

How many 90 ball bingo cards are there?

In the UK there are 90 bingo balls. A bingo card consists of 9 columns and 3 rows. A row contains exactly five numbers and four blanks. A column consists of one, two or three numbers and never three ...
3
votes
2answers
48 views

Binomial Theorem Application Exercise

In my theoretical mathematics class notes, the following problem is left open as an exercise. The professor thinks the solution should be easily seen, but after many hours, I cannot gain the proper ...
0
votes
0answers
8 views

Specific property of complete weighted graphs with 6 vertices with distinct weights

Given a complete graph with 6 vertices such that all edge weights are distinct. Prove that there exist edge which is lightest in one triangle, and heaviest in another. My first approach was to find ...
2
votes
2answers
46 views

Expected number of output letters to get desired word

I am using a letter set of four letters, say {A,B,C,D}, which is used to output a random string of letters. I want to calculate the expected output length until the word ABCD is obtained; that is, the ...
1
vote
4answers
31 views

dealing cards probability

If a standard deck of cards is deal to 4 players, 13 cards each, how many possibilities are there assuming that it matters which player gets but card order does not matter. Why is the answer not (52 ...
1
vote
3answers
1k views

Notation for the set created from the combination or permutation of a set

For a set $S$ with $n$ elements, the notation for a combination $\binom{n}{k}$, or $C(n, k)$, indicates the number of combinations of $k$ elements from $S$, but how does one indicate the actual set ...
0
votes
2answers
21 views

combinatorics question sampling without replacement

Suppose a bag has $x$ blue marbles and $y$ red marbles, and the marbles are picked one at a time without replacement. Would the probability that all blue marbles are picked before red marbles be ...
-2
votes
0answers
22 views

Relaxation of optimization problem [duplicate]

Can I solve the following optimization problem, $$f= \max \{h(Y) - h(Y|U)\}$$ by solving an easier upperbound on $f$ for example $g > f$ where $g= \max\{h(Y)-h(Z)\}$. My aim is to prove that ...
1
vote
2answers
33 views

How many different DNA sequences of length 4 consist of exactly two different letters?

Note: $P(A)=p_A, P(C)=p_C, P(G)=p_G, P(T)=p_T$ My attempt: I tried to make a list of every single possible sequence. How can I solve this question more efficiently?
0
votes
1answer
27 views

Rolling a three sided die six times?

Consider the problem of a rolling a three-sided die six times (independently). The probability of seeing 1 is 0.5, 2 is 0.25, and 3 is 0.25. With this model, I have been given the claim that: We ...
0
votes
0answers
24 views

Number of outcomes of n lines in 3d space

Given $n$ lines in a 3d space what is the number of outcomes for these lines. For example: For $n = 1$ the result is $1$. For $n = 2$ the result is $4$. ( both intersect in one point, parallel, ...
0
votes
2answers
26 views

Probability counting question combinatorics

You must choose 9 courses from a list of 20 classes. At least one course has to be a math class, and 5 out of the 20 classes are math classes. How many possible combinations of 9 classes can the ...
2
votes
2answers
98 views

Hat Matching Problem Expectation

I have an interesting problem in the context of the hat matching problem: There are n people with hats at a party. Each person randomly grabs a hat. A match occurs if a person gets his own hat. I'd ...
0
votes
2answers
37 views

How many of the n! permutations π from set N to N satisfy min(π(A)) = min(π(B))

Given a set of elements $N = \{1, 2,\ldots, n\}$ and two arbitrary subsets $A\subseteq N$ and $B\subseteq N$, how many of the $n!$ permutations π from $N$ to $N$ satisfy min(π$(A)$) = min(π$(B)$), ...
-1
votes
0answers
50 views

semantic word problem $1$ to $20$ containing the letter $A$ [on hold]

How many numbers between $1$ and $20$ have an $A$ in them/it? Hint: You should make a minimal amount of assumptions and use an open mind when answering this question. Well it appears the admins ...
-2
votes
1answer
39 views

Summation of Combination [on hold]

PROVE $$\sum _{ t=0 }^{ r }{ { (-1) }^{ t } } {r \choose t}{ n-t \choose s}\quad =\quad { n-r \choose n-s }$$
0
votes
4answers
79 views

Random walk on a finite square grid: probability of given position after 15 or 3600 moves

An ant is walking on the squares of a 5x5 grid - it starts in the center square. Each second, it will choose (with equal probability) to do one of the following: Move north one square Move south ...
1
vote
0answers
24 views

Bijection between $n$-partitions and “flattened” canonical $n+1$-partitions

The set of $n$-partitions (partitions of the set $\{1, 2, \ldots, n\}$) and the set of "flattened" canonical $(n+1)$-partitions (those permutations obtained by removing the bars from an $(n+1)$ ...
0
votes
1answer
17 views

Methods of enumeration(counting techniques)

"Ten children are to be grouped into two clubs, says the lions and the tigers, five in each club. Each club is then to elect a president and secretary. In how many ways can this be done?" The answer ...
3
votes
0answers
26 views

Combinatorics, equality, $n$-permutations with $k$ cycles

Let $b_r(n,k)$ denote the number of $n$-permuations with $k$ cycles in which all numbers: $1,...,r$ are in one cycle. Prove that for $n \ge r$, $\sum _{k=1} ^n b_r(n,k) x^k = (r-1)! ...
1
vote
2answers
183 views

Conditional Probability [on hold]

In a $13$ card hand, given that a person has one ace, what is the probability that person has more than one ace? In a $13$ card hand, given that a person has the ace of spades, what is the ...
0
votes
2answers
39 views

Combinatorics. Could somebody explain how binomial theorem is applied here?

I do not understand this solution and this formula and why we are using (1+1)^n... I need some help to get an idea of what is going on here Thanks
1
vote
2answers
249 views

Probability of picking specific balls

Suppose I have $20$ red balls in one box and $20$ blue balls in another box. There $12$ red balls and $7$ blue balls have stars on them. I randomly take out one red ball and one blue ball at each ...
5
votes
1answer
46 views

Proving that $\displaystyle\sum_{i = 0}^{m}{\binom{k+i}{i} \binom{n-i}{m-i}} = \binom{n+k+1}{m}$

How to give a combinatorial argument, i.e. counting in two ways, for this problem? I tried by picking the least or largest element in the set, but it is just hard to get rid of the product of two ...
1
vote
1answer
28 views

Possible Pool Table Layouts

There is a pool game called Nine-ball. It involves 9 numbered balls 1-9 and a cue ball, so 10 balls overall. A player starts the game with a "break" shot by hitting the cue ball into the "rack of 9 ...
10
votes
0answers
150 views

$1^2+2^2+\cdots+24^2=70^2$ and squarily squaring the torus

The unique nontrivial solution to $1^2+2^2+\cdots+n^2=m^2$ is $(n,m)=(24,70)$. (This fact has connections to modular forms, special functions, lattices and string theory.) Martin Gardner, in the ...
1
vote
2answers
45 views

Outcome of a Tournament (Combinatorics)

I'd like a tip or a hint in this elementary problem: Three Tennis Players A, B and C will compete in a tournament with 10 rounds (one play per round). Two players face each every round and the winner ...
1
vote
0answers
14 views

Polynomial time algorithm for determining if there exists an ordering of subsets

Given n subsets of cardinality k of a set $S=\{1,2,...,m\}$. Is there a polynomial time algorithm to determine if there exists an ordering of subsets $s_1,...,s_n$ such that ...
0
votes
0answers
22 views

City grid problem: how to interpret such that we use Vandermonde's convolution

A person wants to return to their house that is two blocks north and three blocks east. The problem resolves to taking five moves such that two are northward; there are thus $C(5,2) = 10$ total paths. ...
1
vote
1answer
40 views

How many terms are in $\sum \alpha_1^{a_1}\alpha_2^{a_2}\cdots \alpha_r^{a_r}\alpha_{r+1}\alpha_{r+2}\cdots \alpha_s$

Suppose that $\alpha_1, \cdots, \alpha_n$ be $n$ roots of the polynomial equation $p(x)=0$ of degree $n$. I was studying on symmetric polynomial and have come accross of several problems on like $\sum ...
1
vote
2answers
30 views

Partitions tending to a constant

$P_{k}(n)$ = the number of partitions of n into k parts. Now, if we fix some $t\ge 0$ , then $\lim_{n\to\infty}P_{n-t}(n)\to$ c, c being some constant. Please help me with this! I believe ...
2
votes
3answers
642 views

What are the symmetries of a tic tac toe game board?

What are the symmetries of the tic tac toe board game? Ie, what are the ways you can rotate, reflect, and/or flip the tic tac toe board, such that the next best move to a board(after it was rotated, ...
0
votes
1answer
15 views

Find the possible number of assignments?

S students, I interviewers, each student has to undergo R interviews, each interviewer can interview at max X students. No student interviews with an interviewer more than once, and no interviewer ...
1
vote
1answer
30 views

Soccer tournament with an unspecified schedule

16 soccer teams are taking part in a tournament where teams play with each other once. Every team scores $n$ goals in their $n$-th play. What is the minimal total number of draws in the tournament? ...
1
vote
2answers
43 views

Stuck on Generating Functions

1) Determine how many ways Brian, Katie, and Charlie can split a 50 dollar dinner bill such that Brian and Katie each pay an odd number of dollars and Charlie pays at least 5 dollars . 2) Determine ...
0
votes
2answers
245 views

Permutation and combination problem - word arrangement

This is a question of permutation and combination. Q. How many words can be formed from the word "LUCKNOW" when i) No restriction is there ii) L is the first letter of the word iii) All the ...
0
votes
0answers
19 views

Counting Enumeration Problem

Assume a set $N={1,...n}$. Let An be the set of ordered pairs $(a,b)$ so that b is a subset of N and a is a subset of b. Show that $|An|=k^n$ for a suitable k. So far, I am thinking that if we take ...
0
votes
1answer
49 views

Find number of solutions to the equation?

Find the number of distinct ways to make a sum N using numbers given numbers $a_1,a_2,a_3...a_k$ where $1\le k\le n$ .Here $a_1,a_2,...a_k$ can be used more than once. Example: If N=19 and the ...
2
votes
1answer
239 views

Number of ways of placing $n$ distinguishable balls in $k$ indistiguishable bins where the maximum size of a bin is $m$

I know that the number of ways of placing $n$ distinguishable balls in $k$ indistinguishable bins is given by the Stirling number of the second kind. But I don't know how to modify it to include the ...
1
vote
1answer
22 views

Number of Integer solutions for this optimization problem

What is the number of integer solutions to the problem $$\sum_{i=1}^{i=k}x_i = n$$ subject to $\forall_i\ \ x_i \ge 0 $ note This should hold for both cases $k < n$ and $k \ge n$
0
votes
1answer
109 views

A point in a circle is selected at random. Calculate probability that point is closer to centre than circumference

State any assumption(s) you make Well, I decided to draw a circle with a center at the origin of a Cartesian plane. It had radius r so it's coordinates on the axes were (0, r), etc. I then drew ...
-2
votes
2answers
42 views

Combinatorics (Yahtzee)

Well I am trying to solve some math problems and I am stuck, I really need some help. Here are the problems, please feel free to help me out. How many of the outcomes on a single "Yahtzee Throw" ...