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
0answers
15 views

Decomposing the Complete Graph into Forests

Which spanning forests can we partition the complete graph $K_n$ into? I am primarily interested in partitions into one fixed isomorphism class of forest. I'm also assuming whatever divisibility ...
0
votes
1answer
11 views

Counting sequences of increasing numbers that may be equal

What is the number of sequences $(a_1,a_2,\dots ,a_k)$ of length $k$ such that $a_1,a_2,\dots,a_k$ are in the set $\{1,2,\dots,n\}$ and $a_1\le a_2 \le \dots \le a_k$? I have worked on this problem ...
0
votes
2answers
26 views

Converting seconds into days, hours, minutes, and seconds

I'm working on an assignment for a computer science class, but am having a little trouble. Here is the problem: If we use a modem to transfer files, how long will it take to transfer 1,288,490,188,800 ...
0
votes
0answers
12 views

Let $L$ and $L'$ be lattices. Prove that $L \times L'$ is also a lattice.

Can someone please verify my proof or offer suggestions for improvement? Some preliminaries: Let $A$ and $B$ be two posets. $A \times B$ is the poset on the cartesian product of $A$ and $B$ such ...
1
vote
0answers
37 views

Simple König theorem

I have to prove the "simple" König theorem, without using the marriage theorem: Let $S$ be a set of size $mn$. Suppose that $S$ is partitioned into $m$ subsets, all having size $n$, in two ways: ...
1
vote
0answers
18 views

Prove that $P$ is a lattice (details inside)

Can someone please verify my proof or offer suggestions for improvement? There may be answers to the same questions elsewhere, but I need help with my proof in particular. Show that if $P$ is a ...
1
vote
2answers
31 views

Permutations on 5 letters

I was doing a riddle which said "five points are randomly distributed on the circumference of a circle. From any of these points, a continuous line may be drawn that connects the other points on the ...
1
vote
1answer
8 views

Let $P$ be a finite poset. Show that the number of order ideals equals the number of antichains.

Can someone please verify my proof or offer suggestions for improvement? I am aware that there are similar questions posted elsewhere, but I need help with my proof in particular. Some preliminaries: ...
1
vote
3answers
32 views

Probability of caugh at least 1 of one type of fish

In the lake we have got 3 types of fish: k - number of roach 2k - number of crucian 4k - number of perch Mr Smith caught 7 fish. What is a probability that Mr Smith caught at least 1 roach. My ...
1
vote
0answers
20 views

A method of making a graph bipartite

If we take a graph $G$, and sequentially delete the edge which belongs to the most odd cycles until we have a bipartite graph, will at least half the edges remain when the graph is bipartite? ...
2
votes
0answers
19 views

Let $P, Q, R$ be finite posets. Prove that $P^{Q+R} \cong P^Q \times P^R$.

Can someone please verify my proof and offer suggestions for improvement? I feel that my proof might have been a little hand-waving in showing that $\varphi$ is a bijection, and I feel that it is not ...
-1
votes
1answer
55 views

Number of ways to empty three boxes in a given number of steps, while taking at most one ball from each box at every step

Given a set of three boxes, each of which contains number of balls (say $x,y,z$ respectively), we have to empty the all the three boxes in exactly $N$ steps. At each step we have to pick at least ...
1
vote
3answers
27 views

Combinations of winning scholarships

If six students are eligible for two scholarships worth 1k each, how many different combinations of 2 students winning the 2 scholarships are possible? My attempt 6 nCr 2. How am I wrong?
1
vote
1answer
39 views

Binomial Congruence (mod 5) Identity

I've got a (hard?) Putnam-style problem that I've been given to look at . . . I've never worked any problem even vaguely like this, but my director thinks I should be able to do it. I doubt it (100% ...
4
votes
1answer
32 views

Let $S$ denote the set of all functions $f :\{0,1\}^4 \rightarrow \{0,1\}$. What is the number of functions from the set $S$ to the set $\{0,1\}$?

They say the answer is $2^{2^{16}}$ but I think the answer is $3^{3^{16}}$ because they have not specified the functions to be total. Am I correct? PS: I am a newbie so please don't be too harsh if ...
2
votes
1answer
54 views

Counting partition of set that $i$ and $i+1$ are not in one part

I have to count the number of partitions of the set $\{1,\ldots,n\}$ under the constraint that for each $i$, the elements $i$ and $i+1$ are in different parts. The my idea is: We have two situation ...
2
votes
0answers
30 views

Minimise total cost and count ways

A country has a + b cities located in a row, which are uniformely placed. There are two large telecommunication operators in this country. The first operator will install BTSs in a cities and the ...
3
votes
0answers
40 views

Combinatorial interpretation of an equality

In a recent project, I came up with the following equality which turned out to be extremely useful for counting conjugacy classes in certain division algebras (I won't go into the details here, it's ...
0
votes
1answer
69 views

Interview Question on Set Theory [on hold]

Following things are true about the flats (100 in total) in the Royal Society: There are 93 flats which have Wi-Fi connection. There are 62 flats which have landline telephone. There are 85 flats ...
1
vote
3answers
42 views

If I have 12 books and 12 book spaces, how many ways can I arrange these books? Not all spaces have to be filled. All the books are the same.

If I have 12 books and 12 book spaces, how many ways can I arrange these books? Not all spaces have to be filled. All the books are the same. In other words, putting a book in space 1 and a book in ...
0
votes
1answer
24 views

recursive automata, or recursion mod 2.

Consider the list of length $m$ $(1,0,\dots 0)$ we call this list $l_1$, we now define a sequence of lists recursively, where $l_1$ is the previous list, and if $l_n$ is the list $(a_1,a_2\dots a_n)$ ...
-3
votes
0answers
19 views

There are mn+1 different integers randomly arranged [duplicate]

,then,there either exist m integers arranged in the order that one behind is bigger than one infront,or....I have tried look the order in the view of set theory.
0
votes
0answers
16 views

What does a presentation on block design and Latin squares consist of?

I read the wikipedia pages of both and I just cannot understand these two concepts. I have a presentation on both of these topics next week and I need some headway on both of these topics.
3
votes
1answer
36 views

Tiling squares with L-Trominoes

Is there a simple proof that any square besides a 3x3 square with area divisible by 3 is tileable with L-trominos?
2
votes
1answer
35 views

More computationally optimal way to solve probability of N or more empty buckets given B buckets and A balls

Problem What is the probability of observing N or more empty buckets given B buckets and A balls, if you throw the balls into any of the buckets with equal probability. Python Simulation ...
-1
votes
2answers
25 views

One output for input of $n$-tuples using AND, OR, NOT

Let $B$ be set of $\{0,1\}$ and $B_n$ be the set of all strings of length $n$. How many functions can be constructed from $B_n$ to $B$ using logical operators like AND, OR, NOT. Help $\rightarrow$ ...
0
votes
2answers
29 views

Method to solve probability of chips

A bag contains six chips, numbered 1 through 6. If two chips are chosen at random without replacement and the values on those two chips are multiplied, what is the probability that this product will ...
-1
votes
1answer
66 views

Chess Game with N knights [on hold]

Given an infinite chess board containing N knights. The bottom left corner of the board is labelled as (0,0). Two geeks decide to play the following game on the board : In one turn, a player may move ...
3
votes
3answers
77 views

How many ways can $10$ digits be written down so that no even digit is in its original position

If I have the numbers $0,1,2,3,4,5,6,7,8,9$ written down in that order, how many ways can the $10$ digits be written down so that no even digit is in its original position? It would seem that I can ...
-2
votes
1answer
59 views

Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}\;$

I am unsatisfied with the answers here. (Half of which used algebraic methods despite being advised not to!) Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$ ...
6
votes
1answer
59 views

The number of combinations $(a,b) \in \mathbb{Z}_n \times \mathbb{Z}_n$ such that $a \cdot b = 0$

This question is about a ring for some chosen $n \in \mathbb{N}$ I wanted to find the number $M_n$ of combinations $(a,b) \in \mathbb{Z}_n \times \mathbb{Z}_n$ can be found such that $a \cdot b = 0$ ...
1
vote
1answer
39 views

Finding Kth string by applying given operations

Given is a matrix of dimension 4*4 in which we are given the result when value along row is computed with value along column. ...
1
vote
1answer
103 views

How to convert a problem to a stars and bars problem?

Continued question from here. With certain questions I have $x_i$ being constrained by various different inequalities, I want to know how to remove these from the problem, to bring me back to a ...
2
votes
3answers
57 views

probability rolling a dice 5 times

I can't solve this problem: What is the probability that, when rolling a dice 5 times, the number of times when you get a 1 or 2 is greater than the number of times when you get a 6. any help?
0
votes
1answer
44 views

How to evaluate $\sum_{k=0}^{n} \alpha^k \binom{n}{k}$?

I am trying to show that the function that satisfies $f^\prime(x)=f(x)$ with $f(0)=1$ behaves in an exponential way (in other words, I want to justify writing it as $e^x$). I need to show that: $$ ...
-5
votes
0answers
17 views

<html5> draw circle by arc and triangle [on hold]

I want if click the retacgle, draw a triangle around the circle. source code like this... but, triangle was not good each of positions.. How can i draw a triangle around the circle like attached ...
1
vote
0answers
50 views

Expected frequency of most frequent die roll

Suppose we have an fair $m$-sided die, and we roll it $n$ times. What is the expected frequency $E(n, m)$ of the most frequently rolled face? If we fix $n$ we can calculate $E(n,m)$ like so. Let ...
2
votes
2answers
37 views

Collision of 8 Digit, Base-36 Numbers

I have an algorithm that generates a random 8 digit, base 36 number with uniform distribution. Thus, this algorithm can generate $36^8$ unique numbers. I run my algorithm 10,000 times, and write ...
2
votes
1answer
52 views

Combinatorics of a game

Suppose there are $n$ people sitting in a circle, with $n$ odd. The game is played in rounds until one player is left. Each round the remaining players point either to the person on their right or ...
0
votes
2answers
16 views

How many different ways of displaying prints

Magda has 6 different prints that she wants to hang on her bedroom wall, but she has room to hang only 2 of them. In how many different ways can she display the prints on her wall? I tried $6 \times ...
1
vote
0answers
54 views

Interesting combinatoral identity

With the help of Mathematica I have discovered a following identity. Let $T>1$ be an integer, $x$ be a real number and let q be a positive even integer and $l=0,1,\cdots,q/2$. The following ...
0
votes
4answers
35 views

Probability: Linear Seating Arrangement

Okay, I'm new at probability and statistics, so please try to answer this as thoroughly as possible and explain why you did everything, from using a specific number to why using factorials and ...
0
votes
2answers
26 views

Given the sizes of various intersections, find the size of the union.

in a certain examination, 72 candidates offered maths, 64 offered English, 62 offered French, 18 offered maths and English, 24 offered maths and French, 20 offered English and French and 8 offered ...
0
votes
3answers
93 views

How to use stars and bars(combinatorics)

How to use the stars and bars method? Say I want to find number of combinations I can get with $x_1+x_2+x_3+x_4=22$ Where $x_i\in\mathbb{N}$ Is this the correct time to apply the method?
1
vote
0answers
22 views

Transforming spanning sub-graphs

I have the following question: Suppose we have a finite graph $G=(V,E)$. Now take two arbitrary spanning sub-graphs, i.e. $G_1 = (V,E_1)$ and $G_2=(V,E_2)$ with $E_1,E_2 \subseteq E$. Suppose we ...
1
vote
0answers
38 views

A combinatorial enumeration problem on graph

Let $G$ be a complete graph of order $n$, we now delete $i$ edges from it, then how many complete subgraphs are there with order $m$ in the rest graph? (You can assume $m\ll n$ and $i\ll m$ if ...
1
vote
1answer
21 views

Graph with small average degree has two vertices of small degree

Suppose $G$ is a graph and its average degree $\epsilon(G) = \frac{2|E(G)|}{|V(G)|}$ is in the interval $0 < \epsilon(G) < 2.$ Then clearly $G$ has one vertex of degree at most $1.$ Reading ...
3
votes
2answers
41 views

Vocal group no two singer stand next to each other?

A vocal group consisting of alf,bill,cal,deb,eve, and fay are deciding how to arrange themselves from left to right on a stage How many way to do this if Alf and Fay are the least skilled singer and ...
1
vote
0answers
25 views

Vocal group couples ordering

A vocal group consisting of alf,bill,cal,deb,eve, and fay (3 boys and 3 girls) are deciding how to arrange themselves from left to right on a stage. How many ways to this if There are 3 couples (Alf ...
1
vote
1answer
12 views

Combination selecting a vocal group

A vocal group consisting of alf,bill,cal,deb,eve, and fay (3 boys and 3 girls) are deciding how to arrange themselves from left to right on a stage. How many way to do this if A. The boys should be ...